摘要
介绍广泛应用于游戏寻路中的标准A*算法,指出跳点搜索(JPS)算法使A*生成并扩展的节点数量很少,而且到达目标的速度很快.因为跳点搜索能够消除路径间的对称性,通过在直线和对角线方向上修剪节点来识别后继,在搜索时跳过了大量可能会添加到open列表和closed列表中的中间节点以及其他计算,这使搜索速度有了很大提升.在5个基准网格地图上测试A*+JPS对A*的相对加速比,实验结果表明:跳点搜索可将标准A*搜索的速度提高一个数量级甚至更多,并且速度收益的程度取决于基础网格地图的地貌,对于大的开放区域,跳点搜索更加高效.另外,跳点搜索对A*在节点扩展数量上的改进甚至比搜索时间的改进更加显著.无论从搜索时间还是从节点扩展数量上,A*+JPS都明显优于A*,利用跳点搜索算法可显著加速A*寻路.
Standard A^＊ algorithm widely employed in game pathfinding is presented and it is pointed out that jump point search（JPS）algorithm will make the quantity of nodes very small for both A^＊generation and expansion and also make the speed very high to reach the goal.Because the jump point search can eliminate symmetry of paths and identify their successors by pruning nodes straight and diagonally,therefore a bunch of nodes,which would be added to the open list and closed list,will be jumped over and a lot of calculations can be avoided,so that the searching speed will be improved greatly.By measuring the relative speedup ratio of A^＊＋JPS to A^＊on five benchmark grid maps,it is shown by this experimental results that jump point search can improve the search time performance of A^＊by an order of magnitude or more,and the magnitude of the speed gains will be dependent on the topography of the benchmark grid map,and for large open areas,jump point search will be highly effective.Moreover,jump point search can make the improvement on the total expanded number of nodes even more noticeable than the improvement on the search time.As concerning whether the search time or the number of expanded nodes,A^＊＋JPS is superior to A^＊obviously,and the A^＊pathfinding can be speeded up more noticeably with the jump point search algorithm.
出处
《兰州理工大学学报》
CAS
北大核心
2015年第3期102-107,共6页
Journal of Lanzhou University of Technology
基金
湖北省自然科学基金(2012FFB4102)
湖北省教育厅科学技术研究计划指导性项目(B2014202)
