最快速的寻路算法 Jump Point Search _寻路算法

作者：runzhiwang，腾讯 TEG 后台开发工程师

本文介绍一种跳点搜索算法 JPS 以及其四个优化算法，其寻路速度最快可是 A*算法的 273 倍。文中的 JPS-Bit 和 JPS-BitPrune 都支持动态阻挡。

1.引言寻路算法用途众多，例如在游戏和地图中。A*算法已经众所周知，对于其优化也是层出不穷，然而性能并没有取得突破性进展。本文介绍 JPS 的效率、多线程、内存、路径优化算法。为了测试搜索算法的优化性能，实验中设置游戏场景使得起点和终点差距 200 个格子，需要寻路 10000 次。
结果发现，A*寻路总时间约 2.6074x1011 纳秒（一秒为 109 纳秒）；基础版 JPS 寻路总时间 1.7037x1010 纳秒；利用位运算优化的 JPS（下文称 JPS-Bit）寻路总时间 3.2364x109 纳秒；利用位运算和剪枝优化的 JPS（下文称 JPS-BitPrune）寻路总时间 2.3703x109 纳秒；利用位运算和预处理的 JPS（下文称 JPS-BitPre）寻路总时间 2.0043x109 纳秒；利用位运算、剪枝和预处理三个优化的 JPS（下文称 JPS-BitPrunePre）寻路总时间 9.5434x108 纳秒。
其中的预处理在一些文章被称为 JPS+ 。本文的 JPS-Bit 和 JPS-BitPrune 都支持动态阻挡。本文解决了绝大部分开源 JPS 存在的潜在 BUG：穿越阻挡，在图 2.2.1 中，从 H 走到 K 时，穿越 H 右边阻挡。
上述结果表明，寻路 200 个格子的路径，JPS 的五个版本，平均消耗时间分别为 1.7 毫秒、0.32 毫秒、0.23 毫秒、0.02 毫秒、0.095 毫秒，寻路速度分别为 A*算法的 15 倍、81 倍、110 倍、130 倍、273 倍，大幅度超越 A*算法，标志着寻路已经不会成为性能的瓶颈。
事实上，在 2012 到 2014 年举办的三届（目前为止只有三届）基于 Grid 网格寻路的比赛 GPPC（The Grid-Based Path Planning Competition）中，JPS 已经被证明是基于无权重格子，在没有预处理的情况下寻路最快的算法。
本文接下来介绍 JPS 基础版本以及四个优化算法；然后解读 GPPC2014 的比赛，介绍 GPPC 的比赛地图数据，并从寻路时间、路径长度、消耗内存、失败率等方面比较 22 个参赛寻路算法的优劣。
2.JPS 算法2.1 算法介绍JPS 又名跳点搜索算法（Jump Point Search），是由澳大利亚两位教授于 2011 年提出的基于 Grid 格子的寻路算法。JPS 算法在保留 A*算法的框架的同时，进一步优化了 A*算法寻找后继节点的操作。为了说明 JPS 在 A*基础上的具体优化策略，我们在图 2.1.1 中给出 A*和 JPS 的算法流程图对比。由图 2.1.1 看出，JPS 与 A*算法主要区别在后继节点拓展策略上，不同于 A*算法中直接获取当前节点所有非关闭的可达邻居节点来进行拓展的策略，JPS 根据当前结点 current 的方向、并基于搜索跳点的策略来扩展后继节点，遵循“两个定义、三个规则” 。
定义一，强迫邻居（forced neighbour）：如果节点 n 是 x 的邻居，并且节点 n 的邻居有阻挡（不可行走的格子），并且从 parent(x)、x、n 的路径长度比其他任何从 parent(x)到 n 且不经过 x 的路径短，其中 parent(x)为路径中 x 的前一个点，则 n 为 x 的强迫邻居，x 为 n 的跳点，例如图 2.2.1 中，寻找从 S 到 E 的路径时，K 为 I 的强迫邻居（I 为 K 的跳点）。这里不认为从 H 到 K 能走，因为对角线有阻挡（这点和论文不一致，但和代码一致，因为如果 H 到 K 能直接到达，会走进 H 右边的阻挡区，大部分的 JPS 开源代码根据论文都认为 H 到 K 能直接到达，所以存在穿越阻挡的情况），如果需要 H 到 K 可走，则 K 为 H 的强迫邻居（H 为 K 的跳点）。
定义二，跳点（jump point）：（1）如果点 y 是起点或目标点，则 y 是跳点，例如图 2.2.1 中，S 是起点也是跳点，E 是目标点也是跳点；
（2）如果 y 有强迫邻居则 y 是跳点，例如 I 是跳点，请注意此类跳点和强迫邻居是伴生关系，从定义一强迫邻居的定义来看 n 是强迫邻居，x 是跳点，二者的关系是伴生的，例如图 2.2.1 中 K 的邻居只有 I 是跳点，M 虽然也是 K 的邻居，但 M 不是跳点，因为 K 不是 M 的强迫邻居；
（3）如果 parent(y)到 y 是对角线移动，并且 y 经过水平或垂直方向移动可以到达跳点，则 y 是跳点，例如图 2.2.1 中 G 是跳点，因为 parent(G)为 S，S 到 G 为对角线移动，从 G 到跳点 I 为垂直方向移动，I 是跳点，所以 G 也是跳点。
规则一：JPS 搜索跳点的过程中，如果直线方向（为了和对角线区分，直线方向代表水平方向和垂直方向，且不包括对角线等斜线方向，下文所说的直线均为水平方向和垂直方向）、对角线方向都可以移动，则首先在直线方向搜索跳点，再在对角线方向搜索跳点。规则二：（1）如果从 parent(x)到 x 是直线移动，n 是 x 的邻居，若有从 parent(x)到 n 的路径不经过 x 且路径长度小于或等于从 parent(x)经过 x 到 n 的路径，则走到 x 后下一个点不会走到 n；