1. 概述

JPS （Jump Point Search），又名跳点搜索算法，是由澳大利亚两位教授于 2011年提出的基于栅格的寻路算法。是对A*算法的一个改进。JSP优化了A/搜索后继节点的操作。A\的处理是把周边能搜索到的格子，加进OpenList，然后在OpenList中弹出最小值。JPS先用一种更高效的方法来搜索需要加进OpenList的点，然后在OpenList中弹出最小值。JPS完整地保留了A*的框架。

只针对于路径的对称性，在A*算法中，介绍了一些简单的优化方法，例如，通过人为地加入某些规则使原本对称的节点计算出的f(n)有微小的偏差，使A*有一定的倾向性。而 JPS 的本质也是打破平衡性，它是一个更系统的方法。

2. 算法详解

2.1 数据结构

寻路过程中需要保存有效点的集合，分为可探索点集合openList，已探索点集合closeList。同A*算法，g(n)为起点经过其他点到当前点的代价和，h(n)为到目标点的代价，f(n)为当前点的与起点终点间价值的和，即f(n)=g(n) + h(n)。

2.2 强迫邻居

JPS算法主要考虑当前节点需要考虑的下一个节点是否应该被考虑。例如下图所示：

假设x节点为当前节点，考虑x节点的8邻域节点且终点目标在x节点的右侧。那么，x节点要考虑的节点仅包含5号节点，其余节点不需要再被扩展。规则为：如果x的下一个节点能够从x的父节点扩展得到，那么x节点就不需要扩展该节点。例如，节点3，可以从x的父节点4，通过路径4 -> 2 -> 3到达，与路径4 -> x -> 5代价一样，因此，节点3不需要被考虑扩展。同理，节点1、2、3、4、6、7和8都不惜要再被扩展。

同理，对于斜对角线情况，对于当前节点x，其父节点为6，那么对于节点2, 5和3，需要被考虑进行扩展，因为坐着几个节点从x的父节点6到达的成本高于从x到达的成本。其余结点。例如1, 4, 7, 8就不需要再被扩展。

接下来，我们在考虑包含障碍物的空间。如下图所示：

在上述图中，黑色为障碍物，节点x为当前节点，节点4为节点x的父节点，此时，除了节点5需要被考虑扩展以外，节点3也需要被考虑。原因在于节点3不能够通过节点4以低成本的方式绕过x到达。同理，对于右侧的图例，节点1也需要被扩展考虑。

2.3 跳点

在路径上改变移动方向的点就是跳跃点。当前点x是跳跃点满足以下三个条件之一：

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

不是跳跃点的节点都可以在扩展时不被考虑。如下图所示：

对于节点X和节点y，都是跳跃点，那么节点x和节点y之间的节点就不需要被扩展。

对于对角线情况，如下图所示：

对于节点x和节点y，二者都是跳跃点。但是，在进行斜对角线跳跃前，都需要先进行竖直和水平方向的跳跃检测。从上图中可以看出，节点x和节点y之间的节点进行水平和竖直方向跳跃都失败了，没有找到跳跃点。直到运行到节点y。

2.4 算法原理

第一步，open list取一个权值最低的节点，然后开始搜索
先进行直线搜索（4/8个方向，跳跃搜索），然后再斜向搜索（4个方向，只搜索一步）。如果期间某个方向搜索到跳点或者碰到障碍（或边界），则当前方向完成搜索，若有搜到跳点就添加进open list
若斜方向没完成搜索，则斜方向前进一步
若所有方向已完成搜索，则认为当前节点搜索完毕，将当前节点移除于open list，加入close list
重复取open list权值最低节点搜索，直到open list为空或者找到终点

下面结合实际情况进行讲解。如下图所示：