0.目的

A*在搜索过程中对对称路径的搜索，造成了算法的效率低下。JPS的提出就是为了打破搜索过程中的对称路径，从而提高搜索算法的效率。

1.概述

JPS算法里只有跳点才会被加入openlist里，排除了大量不必要的点，最后找出来的最短路径也是由跳点组成。这也是 JPS高效的主要原因。

除了扩展节点的方法不同，JPS 算法流程和 A* 算法流程几乎是一样的：

唯一的区别在于： A* 在扩展一个节点的时候会将其周围的所有邻居(除了障碍物和自身)都加入到 openlist 中，而 JPS 在扩展节点时，会根据前面介绍的规则，只将那些我们感兴趣的节点加入到 openlist 中，从而加快了搜索的效率。

2. 算法流程

将起点加入openset
循环做如下操作

• 从openset取出代价消耗最小的一点，设为current；若没有点，证明无路可走
• current从openset中移除，加入到closed中
• 若current就是目标点，寻路结束，沿父亲节点回溯生成路径
• 判断current目前的移动方向
• 如果是轴向移动：若当前方向可走，沿当前方向寻找跳点；
• 若左后方不可走，左方可走，沿左前、左方找跳点；
• 若右后方不可走，沿右前、右方找跳点；
• 如果是对角线移动：若当前方向可走，沿当前方向寻找跳点；
• 若方向的两个轴向分量可走，则沿轴向分量寻找跳点；
• 找到的跳点是否在openset中，是的话更新代价，不是的话加入openset

简单概括，假如方向是往右上角方向，则判断右方、上方、右上方，寻找跳点，如果邻居中有强迫邻居，当前点是跳点。

2.1 强迫邻居点

如果节点n是x的邻居，并且节点n的邻居有阻挡（不可行走的格子），并且从parent(x)、x、n的路径长度比其他任何从parent(x)到n且不经过x的路径短，其中parent(x)为路径中x的前一个点，则n为x的强迫邻居，x为n的跳点

2.2 跳点

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

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

3.总结

JPS是比A*更加快速的搜索算法，在保留A算法的框架的同时，进一步优化了 A算法寻找后继节点的操作，同等条件下，JPS比A*快几十倍。