Implementasi Algoritma Jump Point Search Pada NPC Musuh Untuk Mengejar Pemain Dalam Game Labirin

Salah satu algoritma pathfinding yang dapat dipakai dalam mencari dan mengenali jalur dari satu titik ke titik lain adalah algoritma Jump Point Search (JPS). Algoritma JPS merupakan pengembangan dari algoritma A* yang dikembangkan oleh Daniel Harabor dan Alban Grastien pada tahun 2011.Penelitian ini bertujuan untuk mengukur performansi algoritma Jump Point Search dalam mencari jalur dengan halangan yang bersifat dinamis. Penelitian pada algoritma Jump Point Search akan diterapkan pada sebuah game labirin. Karakteristik game yang akan dibangun didasarkan pada sebuah game yaitu game bomberman, dimana game tersebut memiliki beberapa fitur yang dapat digunakan pada penelitian ini. Salah satu fitur tersebut adalah penggunaan sebuah halangan untuk menghalangi musuh dalam mengejar pemain. Hasil penelitian menunjukkan bahwa, pada uji coba algoritma dengan program simulasi didapatkan algoritma ini dapat mengenali jalur yang berubah secara dinamis, hal ini ditunjukkan dari tingkat persentase keberhasilan menemukan jalur di atas 90%. Dengan demikian algoritma ini layak digunakan pada kasus game labirin.

One of the pathfinding algorithms that can be used in the search for and identify the path from one point to another is the algorithm Jump Point Search (JPS). JPS algorithm is an enhancement of the A* algorithm developed by Daniel Harabor and Alban Grastien in 2011. This study aims to measure the performance of the algorithm Jump Point Search in the search for the path with obstacles that are dynamic. Research on the algorithm Jump Point Search will be applied in a maze game. Characteristics of games that will be built based on a game called Bomberman, in which the game has several features that can be used in this study. One such feature is the use of an obstacle to hinder the enemy in pursuit of the player. Data was collected through research from books, research, journals, websites and articles related to problems that occurred or related to the object of research. The results showed that in the trial program algorithm with simulation, this algorithm can identify dynamically changing lanes, it is shown on a percentage rate of success finding the lanes at over 90%. Thus this algorithm fits for use in case of a maze game.