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

摘要

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