JPS（Jump Point Search）算法是基于 A-star 算法进行改进得来的寻路算法，又名「跳点搜索」或「拐点寻路」。文章参考资料附上了论文链接。
概念
传统的 A-star 在遍历的时候，将遍历到的节点放入 openlist，然后通过优先级遍历 openlist 中的节点，在搜索到目标的时候，就能从openlist 中获得路径。
但是由于 A-star 的遍历机制，最终获得的路径会保留了完整的每个节点的路径。而改进的 JPS 算法，选择只保留关键点——也就是选择拐弯的地方保留，在直线或斜向上的中间路径点进行删节。
如图所示，左边是传统 A-star，右边是 JPS。
JPS 提出了两个新的概念，因此在 JPS 如何运作前，要先了解这两个概念——强迫邻居和跳点。
强迫邻居
强迫邻居的定义如下：
节点 x 的8个邻居中有障碍，且 x 的父节点 p 经过x 到达 n 的距离代价比不经过 x 到达的 n 的任意路径的距离代价小，则称 n 是 x 的强迫邻居。
看上去可能稍微有点绕，但可以从直观上理解：有节点 x、n、p，有以下三种条件：
- x 是从 p 走过来的。
- x 周围 8 个邻居中有障碍。
- 不论怎么走，p 不经过 x 到达 n 都比经过 x 到达 n 代价大。
那么就称 n 是 x 的强迫邻居。
定义看上去好像和 p 没什么关系，实际上 p 代表的是现在已经找到的路径，而 x 是 p 到达 n 的必经之地（因为要尽可能走最短，而定义上保证了 p 就是走最短必然经过的节点）。
如图，黑色表示障碍，4 和 6 是上面定义中的节点 p，中心的 x 就是定义的节点 x，而红圈圈出的就是强迫邻居。
强迫邻居的性质决定了，只要当前路径要到 x 的强迫邻居，就必须经过 x。
跳点
跳点的概念基于强迫邻居，同样的，对于 x 有以下条件：
- x 是起点或终点。
- x 至少有一个强迫邻居
- 父节点在 x 的斜向的同时，x 水平或竖直方向上有满足前两个条件的点
满足上面三个条件之一的就是跳点。
我感觉叫拐点也没问题，这里的跳点就是上面图中 openlist 保留的拐点
当从斜向方向到达一个节点时，如果它沿着分解后的水平或垂直方向能遇到一个跳点，那么它本身也是跳点。这种传递性是JPS能跳起来的关键。
算法
JPS 算法步骤如下：
- 选择点：openlist 取权值（代价）最低的节点作为接下来开始搜索的点。 这个和 A-star 一样。
- 搜索：
- 先进行水平和竖直搜索。水平和竖直搜索是沿直线方向一直搜索下去，直到遇到跳点或者障碍。
- 后进行斜向搜索。斜向搜索是只沿着四个斜方向搜索一步。
- 搜索结果：如果斜方向没有搜索结果，则斜方向前进一步，重新上面的搜索过程。
- 搜索结束：如果所有方向都完成了搜索，则认为当前节点搜索完毕，将其移除出openlist，加入closelist。
- 下一个点：回到步骤1, 直到 openlist 为空或者找到终点。
具体的搜索示例可以见参考资料 JPS/JPS+ 寻路算法 - KillerAery - 博客园，里面有附图的示例。
另外参考资料还附注了其改进版本 JPS+，大致思路是先对地图数据进行预处理标记，从而进一步加速寻路速度，但是由于对地图可修改性不友好，而且我懒得写，所以就不写了，感兴趣的可以看看参考资料。