基于打破对称性的快速寻路算法

Fast Pathfinding Algorithm Based on Breaking Symmetry

基于Java实现了跳点搜索算法,给出了算法实现的过程.实验结果表明:跳点搜索算法找到了一条从起始节点到目标节点的最优路径,且能够有效地识别和消除网格地图上的路径对称性,大幅度减少了节点扩展的数量.对比A*、宽度优先搜索、最佳优先搜索和Dijkstra可知,在所求解的路径长度一致的情况下,跳点搜索在平均搜索时间上显著快于其他算法.因此,跳点搜索是快速、高效的.

Jump Point Search （JPS）algorithm is implemented in Java,and the implementation procedures of JPS algorithm is given.Experimental results show that an optimal path has been found by JPS algorithm from start node to goal node,which could identify and eliminate path symmetries on grid maps effectively, so it reduces nodes number expanded by a large margin.Comparing JPS with A＊,Breadth First Search, Best First Search and Dijkstra,the results show that JPS is faster over them more pronounced on condition of the path length being computed are uniform.For these reasons,JPS algorithm is fast and effective.