| 利用跳点搜索算法加速A*寻路 |
| |
| 引用本文： | 邱磊. 利用跳点搜索算法加速A*寻路[J]. 兰州理工大学学报, 2015, 41(3) |
| |
| 作者姓名： | 邱磊 |
| |
| 作者单位： | 武汉船舶职业技术学院电气与电子工程学院,湖北武汉,430050 |
| |
| 基金项目： | 湖北省自然科学基金，湖北省教育厅科学技术研究计划指导性项目 |
| |
| 摘 要： | 介绍广泛应用于游戏寻路中的标准A*算法,指出跳点搜索(JPS)算法使A*生成并扩展的节点数量很少,而且到达目标的速度很快.因为跳点搜索能够消除路径间的对称性,通过在直线和对角线方向上修剪节点来识别后继,在搜索时跳过了大量可能会添加到open列表和closed列表中的中间节点以及其他计算,这使搜索速度有了很大提升.在5个基准网格地图上测试A*+JPS对A*的相对加速比,实验结果表明:跳点搜索可将标准A*搜索的速度提高一个数量级甚至更多,并且速度收益的程度取决于基础网格地图的地貌,对于大的开放区域,跳点搜索更加高效.另外,跳点搜索对A*在节点扩展数量上的改进甚至比搜索时间的改进更加显著.无论从搜索时间还是从节点扩展数量上,A*+JPS都明显优于A*,利用跳点搜索算法可显著加速A*寻路.
|
| 关 键 词： | A*寻路 跳点搜索 网格 游戏 |
Speed-up of A* pathfinding with jump point search algorithm |
| |
| QIU Lei. Speed-up of A* pathfinding with jump point search algorithm[J]. Journal of Lanzhou University of Technology, 2015, 41(3) |
| |
| Authors: | QIU Lei |
| |
| Abstract: | |
| |
| Keywords: | A* pathfinding jump point search grid game |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
