An Improved Jump Point Search Pathfinding Algorithm for Hexagonal Grid Maps

Pathfinding in hexagonal grid maps is a common problem in some specific areas, especially in video games (like the highly acclaimed Civilization series). The main challenge of these problems lies in how to handle the paths that seemingly different, but in fact equivalent. Jump Point Search (JPS) is regarded as the best algorithm in the current research based on square grid maps. It effectively solved this problem. The efficiency of JPS far exceeds other similar algorithms, including the widely used A-Star algorithm. This paper presents an adaptation of the JPS algorithm for hexagonal grid maps and presents a comparative analysis of its efficiency against the widely-used A-Star algorithm. The result proved that the adjusted JPS algorithm has significantly improved the efficiency of solving pathfinding problem compared to the A-Star algorithm when dealing with medium to long paths and complex paths.