跳点搜索算法的原理解释及性能分析

跳点搜索算法的原理解释及性能分析

邱磊，刘辉玲，雷建龙

【摘 要】给出了跳点搜索（Jump Point Search,JPS）算法的原理，分析了邻居裁剪规则，并试着用图来解释该算法而不诉诸于其原始研究论文中提出的基本数学证明.通过3个实验综合分析了JPS的性能优势，实验结果表明：同等地图尺寸下JPS扩展的节点数与障碍物密度成正比，与查看的邻居数成反比；随着地图尺寸的增加，JPS相比于其他典型寻路算法，在时间效率上优势更加显著；地图环境的对称性越高，JPS较之于A*的优势越明显.总之，JPS保持了A*的最优性，可将A*提速一个数量级甚至更多，该算法更适合需要快速寻路的领域.

【期刊名称】新疆大学学报（自然科学版）

【年(卷),期】2016(033)001

【总页数】8

【关键词】寻路；跳点搜索；A*；网格；环境对称性

基金项目：湖北省自然科学基金项目（2012FFB4102）；湖北省教育厅科学技术研究计划指导性项目（B2014202）；湖北省教育厅人文社会科学研究青年项目（15Q263）.

0 引言

A*算法通过裁剪代价较高的邻居而发现最优路径，这不利于游戏开发和机器人寻路.跳点搜索(JPS)[1]是一种新的寻路算法，是对A*搜索算法的优化.它通过图裁剪来减少搜索过程的对称性，能让搜索在网格上直线长“跳”，而不是普通A*的小步移动.JPS跳过了无用节点，保留了关键的“跳点”.JPS擅长应用在等价网格地图上大的开放区域.在这些开放的区域，JPS能略过或跳过大量使用传统A*算法将被扩展的中间节点.然而，JPS通常要比A*评估更多的障碍物，但大多数情况下

，JPS的额外评估要比A*的额外列表操作快得多.在最坏情况下，在搜索时间上JPS与A*也能打成平手；至于大型的开放空间，JPS生成最优路径要远快于A*.跳点搜索算法比传统的A*不仅提升了性能而且降低了内存成本，跳点搜索算法将是游戏与机器人领域人工智能的未来，甚至可以应用在全球定位系统、仿真等领域.

本文的创新点如下：1）主要特色是采用图的方式，对JPS算法进行了直观的描述和解释，对算法赋予直观的物理含义，是对理论方法的一种拓展；2）既使用了规则的2D方形网格地图又使用了测试库中的基准地图来表示寻路环境进行仿真实验，使JPS算法的性能分析结论更具说服力；3）对同等地图尺寸与变化地图尺寸下JPS的性能均进行了比较分析.本文待解决的问题如下：1）拟尝试用图来解释JPS算法而不诉诸于在其研究论文中给出的基本数学证明；2）拟结合仿真实验分别从同等地图尺寸下障碍物密度的变化对JPS扩展节点数和查看邻居数的影响、地图尺寸的变化对JPS与其它典型寻路算法的时间效率趋势的比较影响，以及基准地图环境的对称性特征对JPS算法与A*算法的比较