基于跳点搜索算法的网格地图寻路

等价网格环境下的寻路问题普遍存在于机器人、电子游戏等应用领域.其中,最先进的技术都被分层寻路算法所主导,这些算法速度快且内存开销较小,但通常返回的路径都是次优的.本文提出了一个新颖的、特定于网格的搜索策略,该策略速度快、最优且无需内存开销,其算法可以描述为一个宏算符,该宏算符识别和有选择地扩展网格地图上的仅仅某些节点,我们称之为跳点,连接两个跳点的路径上的中间节点将不再被扩展.我们将证明该方法计算出的解总是优解的;然后,进行了深入的实证分析,并将我们的方法与其他文献上的相关工作做对比.我们发现利用跳点进行搜索能将A＊算法的速度提高一个数量级甚至更多;同时,我们报告了跳点搜索相对于当前最先进的技术而言有明显的改进.

Pathfinding on Grid Maps based on Jump Point Search

Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A ＊ by an order of magnitude and more and report significant improvement over the current state of the art.