Path Search Algorithm for Combining Bresenham with JPS's Static Raster Map
ZHANG Yao
MA Lili
Abstract：Path planning has always been the focus of research on artificial intelligence and games.The most widely used heu-ristic algorithm is the A*algorithm.Its disadvantage is that there are too many dynamic expansion nodes,which will take up a lot of computer memory and affect the pathfinding rate.The improved JPS jump point algorithm is proposed to reduce memory consump-tion.This algorithm has problems such as a large number of jump points and calculation redundancy.This algorithm has problems such as a large number of jumping points and calculation redundancy.This paper combines the Bresenham algorithm with the JPS jumping point algorithm.Before using the JPS jumping point algorithm,firstly the Bresenham algorithm is used to find the straight path between the starting point and the end point,and the previous node of the obstacle node in the straight path is recorded.Second-ly,the JPS jumping point algorithm is used to find the path of the two points,and finally the paths are spliced to reduce the number of jumping points and the number of nodes for offline search.The simulation results show that the algorithm can effectively reduce the number of jump points and reduce the number of nodes for offline search.
Keywords：Bresenham algorithmJPS algorithmA*algorithmpath planning
Publication Date：2023-12-20
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：6( 2846-2851 )