Implementasi Algoritma Jump Point Search dalam Mencari Rute Dungeon Berbasis Grid 2D

Abstract

Finding efficient paths in a two-dimensional grid environment presents its own chal-lenges, especially when the space is filled with obstacles that restrict movement. This study discusses the implementation of the Jump Point Search (JPS) algorithm for pathfinding in a 2D grid-based dungeon. The A* (A-Star) algorithm is used as a com-parison to evaluate JPS in terms of efficiency and processing time. The research is limited to uniform-cost grids, with elements consisting of walls, walkable paths, a start point, and an end point. The application was developed using the Python pro-gramming language in the form of a desktop GUI. Testing was carried out by compar-ing the performance of JPS and A* (A-Star) in finding paths across various dungeons with different movement spaces, obstacle densities, and structures. The results show that JPS is consistently faster and more efficient than A* (A-Star), especially on larger grids and in complex environments. In several scenarios, JPS achieved more than a 97% reduction in processing time and up to a 99% decrease in the number of visited nodes. However, A* (A-Star) still produced more optimal path costs in certain condi-tions. JPS also demonstrated stable performance in multi-end node and dynamic envi-ronment testing, as long as the grid structure did not change drastically.