JPS4让4连通网格寻路更快，尤其适合密集障碍物场景。
Jump Point Search Pathfinding in 4-connected Grids
- 基于跳点机制与规范排序，动态剪枝搜索空间。
- 在高障碍密度地图上比A*快数倍，路径仍最优。
- 适合视频游戏等需高效寻路的实时系统。
本文提出JPS4，一种针对4连通网格地图的新型寻路算法。JPS4在原始为8连通环境设计的跳点搜索（JPS8）基础上改进，通过规范排序与后继节点函数实现在线图剪枝，显著减少不必要的节点扩展。其核心思想是利用跳点——位于障碍物拐角处的特殊节点——来重置规范排序，从而跳过障碍物区域，确保在复杂环境中仍能发现最优路径。论文分析了JPS4的最优性，并在多种网格地图上对比其与经典A*算法的性能。基准测试显示，在高障碍密度场景下JPS4显著优于A*；而在开阔地图上，A*仍具优势。总体而言，JPS4为4连通网格寻路提供了一种高效替代方案，特别适用于视频游戏开发。
原文摘要 · Abstract (English)
This work introduces JPS4, a novel pathfinding algorithm for 4-connected grid maps. JPS4 builds upon the Jump Point Search (JPS8) algorithm, originally designed for 8-connected environments. To achieve efficient pathfinding on 4-connected grids, JPS4 employs a canonical ordering and a successor function that enable online graph pruning. This reduces the search space by minimizing unnecessary node expansions. The core concept of JPS4 as well as JPS8 lies in the utilization of jump points. Strategically placed at obstacle corners, jump points prevent the search from overlooking crucial sections of the state space. They essentially reinitialize the canonical ordering, allowing exploration beyond obstacles. This mechanism ensures JPS4 finds optimal paths even in complex environments. The paper further explores the optimality of JPS4 and compares its performance against the established A* algorithm on various grid maps. Benchmarking results demonstrate that JPS4 significantly outperforms A* in scenarios with high obstacle density. However, A* remains more efficient on open maps. Overall, JPS4 presents itself as a promising alternative to A* for pathfinding on 4-connected grids, particularly applicable in video game development.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。