结合Bresenham与JPS的静态栅格地图的路径搜索算法  

Path Search Algorithm for Combining Bresenham with JPS's Static Raster Map

作　　者：张遥 马丽丽[1] ZHANG Yao;MA Lili(School of Computer Science,Xi'an Polytechnic University,Xi'an 710000)

机构地区：[1]西安工程大学计算机科学学院,西安710000

出　　处：《计算机与数字工程》2023年第12期2846-2851,共6页Computer & Digital Engineering

基　　金：陕西省教育厅科研计划项目(编号:21JP049)资助。

摘　　要：路径规划问题一直是人工智能及游戏的研究重点,现在使用较为广泛的启发式算法是A^(*)算法,其缺点在于动态扩展节点过多,会占用大量计算机内存,影响寻路速率。通过改良提出JPS跳点算法,减少内存的消耗,该算法存在跳点数量多,计算冗余等问题。论文将Bresenham算法和JPS跳点算法结合,在使用JPS跳点算法之前,首先用Bresenham算法求出起点和终点之间的直线路径,并记录该直线路径中碰到障碍物节点的前一节点,其次用JPS跳点算法求出两个点的路径,最后将路径加以拼接,以达到减少跳点的数量和离线搜索的节点数量。仿真结果表明该算法可以有效减少跳点数量的生成,减少离线搜索的节点数量。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.

关 键 词：BRESENHAM算法 JPS算法 A^(*)算法 路径规划 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]