基于在线图修剪的网格地图寻路

跳点搜索算法(JPS)是网格地图上最先进的图形修剪技术,由Daniel Harabor在2011年开发。它是A*的变种,提高了A*在等价网格上寻路的速度,当考虑当前节点的孩子可能被添加到OPEN集合时候,跳点搜索算法则直接从当前节点跳跃到了远处可见的节点。本文给出了跳点搜索算法的两个规则,并通过实证分析,将跳点搜索算法与两个先进的搜索空间约化算法进行了对比。结果显示:跳点搜索算法相对于Swamps(保持最优性的修剪技术)来说有显著地改进;同样,相对于很多情况下性能上占优的HPA*(次优寻路算法)也具有优越性。

Pathfinding on Grid Maps Based on Online Graph Pruning

Jump Point Search （JPS） is the state-of-the-art in graph pruning for grid maps which was developed in 2011 by Daniel Harabor. It＇ s the variant of A ＊ which can speed up A ＊ on grids with uniform cost. When considering children of the current node for possible inclusion in the OPEN set, Jump Point Search skips ahead to faraway nodes that are visible from the current node. In this paper, two rules of Jump Point Search algorithm are given, and also compared Jump Point Search with two state-of-the-art search space reduction algorithms by em- pirical analysis. Experimental results show that Jump Point Search report significant （optimality preserving pruning technique） ;and performance that is competitive with, nates, HPA ＊ （sub-optimal pathfinding algorithm）. improvement over Swamps and in many cases domi-nates, HPA ＊ （sub-optimal pathfinding algorithm）.