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

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