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

（2）如果从 parent(x)到 x 是对角线移动，n 是 x 的邻居，若有从 parent(x)到 n 的路径不经过 x 且路径长度小于从 parent(x)经过 x 到 n 的路径，则走到 x 后下一个点不会走到 n（相关证明见论文）。
【最快速的寻路算法 Jump Point Search】规则三：只有跳点才会加入 openset，因为跳点会改变行走方向，而非跳点不会改变行走方向，最后寻找出来的路径点也都是跳点。寻路具体流程如下：
一，若 current 当前方向是直线方向：（1）如果 current 左后方不可走且左方可走（即左方是强迫邻居），则沿 current 左前方和左方寻找不在 closedset 的跳点；（2）如果 current 当前方向可走，则沿 current 当前方向寻找不在 closedset 的跳点；（3）如果 current 右后方不可走且右方可走（右方是强迫邻居），则沿 current 右前方和右方寻找不在 closedset 的跳点；
二，若 current 当前方向为对角线方向：（1）如果 current 当前方向的水平分量可走（例如 current 当前为东北方向，则水平分量为东，垂直分量为北），则沿 current 当前方向的水平分量寻找不在 closedset 的跳点；（2）如果 current 当前方向可走，则沿 current 当前方向寻找不在 closedset 的跳点；（3）如果 current 当前方向的垂直分量可走（例如 current 当前为东北方向，则水平分量为东，垂直分量为北），则沿 current 当前方向的垂直分量寻找不在 closedset 的跳点。JPS 寻找跳点的过程有三种优化：一，位运算；二；预处理；三；剪枝中间跳点。

文章插图

图2.1.1 A*和JPS的算法流程图对比
2.2 JPS 算法举例

文章插图

表2.2.1 A*和JPS的寻路消耗对比
下面举例说明 JPS 具体的寻路流程。示例如图 2.2.1 所示，5*5 的网格，黑色代表阻挡区，S 为起点，E 为终点。
JPS 要寻找从 S 到 E 的最短路径，首先初始化将起点 S 加入 openset 。从 openset 取出 F 值最小的点 S，并从 openset 删除，加入 closedset，S 的当前方向为空，则沿八个方向寻找跳点，在该图中从 S 出发只有下、右、右下三个方向可走，但向下搜索到 D 遇到边界，向右搜索到 F 遇到阻挡，因此都没有找到跳点，然后沿右下方向寻找跳点，在 G 点，根据上文定义二的第（3）条，parent(G)为 S，praent(G)到 S 为对角线移动，并且 G 经过垂直方向移动（向下移动）可以到达跳点 I，因此 G 为跳点。
将 G 加入 openset 。从 openset 取出 F 值最小的点 G，并从 openset 删除，加入 closedset，因为 G 当前方向为对角线方向（从 S 到 G 的方向），因此在右（当前方向水平分量）、下（当前方向垂直分量）、右下（当前方向）三个方向寻找跳点，在该图中从 G 出发只有向下可走，因此向下寻找跳点，根据上文定义二的第（2）条找到跳点 I，将 I 加入 openset 。从 openset 取出 F 值最小的点 I，并从 openset 删除，加入 closedset，因为 I 的当前方向为直线方向（从 G 到 I 的方向），在 I 点时 I 的左后方不可走且左方、前方可走，因此沿左、左前、前寻找跳点，但左前、前都遇到边界，只有向左寻找到跳点 Q（根据上文定义二的第（2）条）），因此将 Q 加入 openset 。
从 openset 取出 F 值最小的点 Q，并从 openset 删除，加入 closedset，因为 Q 的当前方向为直线方向，Q 的左后方不可走且左方、前方可走，因此沿左、左前、前寻找跳点，但左前、前都遇到边界，只有向左寻找到跳点 E（根据上文定义二的第（1）条）），因此将 E 加入 openset 。从 openset 取出 F 值最小的点 E，因为 E 是目标点，因此寻路结束，路径是 S、G、I、Q、E 。
注意，本文不考虑从 H 能走到 K 的情况，因为对角线有阻挡，如果需要 H 到 K 能直接到达，则路径是 S、G、H、K、M、P、E，修改跳点的计算方法即可，但在游戏中如果 H 到 K 能直接到达，则会穿越 H 右边的阻挡。

文章插图

图2.2.1
上述的 JPS 寻路效率是明显快于 A*的，原因在于：在从 S 到 A 沿垂直方向寻路时，在 A 点，如果是 A*算法，会将 F、G、B、H 都加入 openset，但是在 JPS 中这四个点都不会加入 openset 。对 F、G、H 三点而言，因为从 S、A、F 的路径长度比 S、F 长，所以从 S 到 F 的最短路径不是 S、A、F 路径，同理 S、A、G 也不是最短路径，根据上文规则二的第（1）条，走到 A 后不会走到 F、G，所以 F、G 不会加入 openset，虽然 S、A、H 是 S 到 H 的最短路径，但因为存在 S、G、H 的最短路径且不经过 A，据上文规则二的第（1）条，从 S 走到 A 后，下一个走的点不会是 H，因此 H 也不会加入 openset；对 B 点而言，根据上文规则三，B 不是跳点，也不会加入 openset，直接走到 C 即可。