结合Bresenham与JPS的静态栅格地图的路径搜索算法
张遥
马丽丽
西安工程大学计算机科学学院 西安 710000
摘要：路径规划问题一直是人工智能及游戏的研究重点,现在使用较为广泛的启发式算法是A*算法,其缺点在于动态扩展节点过多,会占用大量计算机内存,影响寻路速率.通过改良提出JPS跳点算法,减少内存的消耗,该算法存在跳点数量多,计算冗余等问题.论文将Bresenham算法和JPS跳点算法结合,在使用JPS跳点算法之前,首先用Bresenham算法求出起点和终点之间的直线路径,并记录该直线路径中碰到障碍物节点的前一节点,其次用JPS跳点算法求出两个点的路径,最后将路径加以拼接,以达到减少跳点的数量和离线搜索的节点数量.仿真结果表明该算法可以有效减少跳点数量的生成,减少离线搜索的节点数量.
关键词：Bresenham算法JPS算法A*算法路径规划
分类号：TP399(计算技术、计算机技术)
资助基金：陕西省教育厅科研计划项目(21JP049)
论文发表日期：2023-12-20
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：6( 2846-2851 )
英文信息