JPS/JPS+ 寻路算法

概念
- 强迫邻居（Forced Neighbour）
- 跳点（Jump Point）
JPS 寻路算法（Jump Point Search）
- 实现原理
- 示例过程
JPS+（Jump Point Search Plus）
- 预处理
- 示例过程
总结
参考

概念

JPS（jump point search）算法实际上是对A* 寻路算法的一个改进，因此在阅读本文之前需要先了解A*算法。A* 算法在扩展节点时会把节点所有邻居都考虑进去，这样openlist中点的数量会很多，搜索效率较慢。

若不了解A*算法，可以参考博主以前写的一篇文章 A* 寻路算法 – KillerAery – 博客园

例如在无遮挡情况下（往往会有多条等价路径），而我们希望起点到终点实际只取其中一条路径，而该路径外其它节点可以没必要放入openlist（不希望加入没必要的邻居）。

其次我们还希望直线方向上中途的点不用放入openlist，如果只放入每段直线子路径的起点和终点，那openlist又可以少放很多没必要的节点：

可以看到 JPS 算法搜到的节点总是“跳跃性”的，这是因为这些关键性的节点都是需要改变行走方向的拐点，因此这也是 Jump Point 命名的来历。

在介绍JPS等算法具体实现前，我们必须先掌握下面的概念。

强迫邻居（Forced Neighbour）

强迫邻居：节点 x 的8个邻居中有障碍，且 x 的父节点 p 经过x 到达 n 的距离代价比不经过 x 到达的 n 的任意路径的距离代价小，则称 n 是 x 的强迫邻居。

看定义也许十分晦涩难懂。直观来说，实际就是因为前进方向（父节点到 x 节点的方向为前进方向）的某一边的靠后位置有障碍物，因此想要到该边靠前的空位有最短的路径，就必须得经过过 x 节点。

可能的情况见图示，黑色为障碍，红圈即为强迫邻居：

（左图为直线方向情况下的强迫邻居，右图为斜方向情况下的强迫邻居）

跳点（Jump Point）

跳点：当前点 x 满足以下三个条件之一：

节点 x 是起点/终点。
节点 x 至少有一个强迫邻居。
如果父节点在斜方向（意味着这是斜向搜索），节点x的水平或垂直方向上有满足条件a，b的点。

节点y的水平或垂直方向是斜向向量的拆解，比如向量d=(1,1)，那么水平方向则是(1,0)，并不会往左搜索，只会看右边，如果向量d=(-1,-1)，那么水平方向是(-1,0)，只会搜索左边，不看右边，其他同理。

下图举个例子，由于黄色节点的父节点是在斜方向，其对应分解成向上和向右两个方向，因为在右方向发现一个蓝色跳点，因此黄色节点也应被判断为跳点：

JPS 寻路算法（Jump Point Search）

实现原理

JPS 算法和A* 算法非常相似，步骤大概如下：

openlist取一个权值最低的节点，然后开始搜索。（这些和A*是一样的）
搜索时，先进行 直线搜索（4/8个方向，跳跃搜索），然后再 斜向搜索（4个方向，只搜索一步）。如果期间某个方向搜索到跳点或者碰到障碍（或边界），则当前方向完成搜索，若有搜到跳点就添加进openlist。

跳跃搜索是指沿直线方向一直搜下去（可能会搜到很多格），直到搜到跳点或者障碍（边界）。一开始从起点搜索，会有4个直线方向（上下左右），要是4个斜方向都前进了一步，此时直线方向会有8个。

若斜方向没完成搜索，则斜方向前进一步，重复上述过程。

因为直线方向是跳跃式搜索，所以总是能完成搜索。

若所有方向已完成搜索，则认为当前节点搜索完毕，将当前节点移除于openlist，加入closelist。
重复取openlist权值最低节点搜索，直到openlist为空或者找到终点。

下面结合图片更好说明过程2和3：首先我们从openlist取出绿色的节点，作为搜索的开始，先进行直线搜索，再斜向搜索，没有找到任何跳点。

斜方向前进一步后，重复直线搜索和斜向搜索过程，仍没发现跳点。

斜方向前进两步后，重复直线搜索和斜向搜索过程，仍没发现跳点。

斜方向前进了三步后（假设当前位置为 x），在水平直线搜索上发现了一个跳点（紫色节点为强迫邻居）。

于是 x 也被判断为跳点，添加进openlist。斜方向结束，绿色节点的搜索过程也就此结束，被移除于openlist，放入closelist。

示例过程

下面展示JPS算法更加完整的过程：
假设起点为绿色节点，终点为红色节点。

重复直线搜索和斜向搜索过程，斜方向前进了3步。在第3步判断出黄色节点为跳点（依据是水平方向有其它跳点），将黄色跳点放入openlist，然后斜方向搜索完成，绿色节点移除于openlist，放入closelist。

对openlist下一个权值最低的节点（即黄色节点）开启搜索，在直线方向上发现了蓝色节点为跳点（依据是紫色节点为强迫邻居），类似地，放入openlist。

由于斜方向还没结束，继续前进一步。最后一次直线搜索和斜向搜索都碰到了边界，因此黄色节点搜索完成，移除于openlist，放入closelist。

对openlist下一个权值最低的节点（原为蓝色节点，下图变为黄色节点）开启搜索，直线搜索碰到边界，斜向搜索无果。斜方继续前进一步，仍然直线搜索碰到边界，斜向搜索无果。

由于斜方向还没结束，继续前进一步。

最终在直线方向上发现了红色节点为跳点，因此蓝色节点先被判断为跳点，只添加蓝色节点进openlist。斜方向完成，黄色节点搜索完成。

最后openlist取出的蓝色节点开启搜索，在水平方向上发现红色节点，判断为终点，算法完成。

回忆起跳点的第三个判断条件（如果父节点在斜方向，节点x的水平或垂直方向上有满足条件a，b的点），会发现这个条件判断是最复杂的。在寻路过程中，它使寻路多次在水平节点上搜到跳点，也只能先添加它本身。其次，这也是算法中需要使用到递归的地方，是JPS算法性能瓶颈所在。

JPS+（Jump Point Search Plus）

JPS+ 本质上也是 JPS寻路，只是加上了预处理来改进，从而使寻路更加快速。

预处理

我们首先对地图每个节点进行跳点判断，找出所有主要跳点：

然后对每个节点进行跳点的直线可达性判断，并记录好跳点直线可达性：

若可达还需记录号跳点直线距离：

类似地，我们对每个节点进行跳点斜向距离的记录：

剩余各个方向如果不可到达跳点的数据记为0或负数距离。如果在对应的方向上移动1步后碰到障碍（或边界）则记为0，如果移动n+1步后会碰到障碍（或边界）的数据记为负数距离-n

最后每个节点的8个方向都记录完毕，我们便完成了JPS+的预处理过程：

以上预处理过程需要有一个数据结构存储地图上每个格子8个方向距离碰撞或跳点的距离。

示例过程

做好了地图的预处理之后，我们就可以使用JPS+算法了。大致思路与JPS算法相同，不过这次有了预处理的数据，我们可以更快的进行直线搜索和斜向搜索。

在某个搜索方向上有：

对于正数距离 n（意味着距离跳点 n 格），我们可以直接将n步远的节点作为跳点添加进openlist
对于0距离（意味着一步都不可移动），我们无需在该方向搜索；
对于负数距离 -n（意味着距离边界或障碍 n 格），我们直接将n步远的节点进行一次跳点判断（有可能满足跳点的第三条件，不过得益于预处理的数据，这步也可以很快完成）。

如下图示，起始节点通过已记录的向上距离，直接将3步远的跳点添加进openlist，而不再像以前需要迭代三步（还每步都要判断是否跳点）：