|
|
JPS（Jump Point Search）寻路算法，即跳点搜索算法，是一种基于A*算法的网格寻路算法，在性能上相较于AStar具有很高的提升，不过只针对网格地图的寻路，非常适合作为于2D网格地图型寻路手段。本篇文章会大概的讲一下JPS算法的原理，然后再通过我自己的理解方式给出一个新的解释，最后给出一份C#版本的实现。
（阅读博客之前应该首先了解和学习A*算法）
1.关于A*算法的缺陷
A*算法是一种启发式搜索算法，本质上是对迪杰斯特拉算法的改善。迪杰斯特拉算法是一种全局搜索算法，本来是为了在图（Graph）型的地图中进行最短路径的搜索，不过在网格型地图下效率非常差，它在移动到一个新的点位时，会将所有的点位加入到待移动的队列中。然后逐一的计算和终点的距离，然后更新一张记录距离和来源的表，当移动到最终点的时候，根据所更新的表来查询路径。
类似于迪杰斯特拉算法，A*算法也会在移动到一个新的点时，将该点可以移动到的其他所有点位加入待判断的队列。不同的就是，AStar增加了一个启发式的手段，在将目标点周围的点位（Neighbors）加入队列时，它会计算待加入的点位和起点的距离，然后再下次搜索的时候优先处理那些距离终点更近的点。
这个距离就是Cost，Cost分为两个部分，第一个部分是已经确定的部分，也就是从起点移动到当前点，一共走了多少步或者多少距离。第二部分是预估的部分，也就是当前点移动到终点，还需要走多远。第二个部分是预估的，因为计算距离的方式，以及从当前点到终点之间是否存在障碍都是不清楚的。
看起来迪杰斯特拉算法和A*算法最大的区别就是，AStar算法引入了一个预估价值，而迪杰斯特拉只记录从起点走到当前点所消耗的成本。
计算距离的方式在2D网格世界中主要是两类，曼哈顿距离（Manhattan Distance）或者欧拉距离（Euler Distance），不过在目标寻路问题中，它可以是任意可以表达距离的抽象概念。
尽管如此，A*算法在非2D矩阵网格式的其他地图里仍有卓越的表现。只是在2D网格地图中，有更好的方式。
1.1 冗余的判断
当移动到一个新的点位时（2D网格地图），A*算法会将九宫格内的其他8个点位没有去过的点都加入到当前的队列，其中会产生部分冗余的判断。
假设当前位置的上一个位置位于当前节点的左侧，如下图所示。那么可以考虑考虑有哪些节点是可以不用判断的。
在思考这个问题之前，我们需要解决一个疑惑，那就是为什么只考虑向右移动？这是因为右移动在网格地图中是可以等效到其他水平或垂直方向的。如果地图只允许水平或者垂直移动，那么研究一个方向就可以拓展到其他方向。
如果允许对象斜向移动，那么则再考虑斜向移动时。（以下的算法研究过程中，我们暂且认为对象是支持斜向移动的，但斜向移动的情况后面再说）
对于上图所描述的周围的点位，首先可以排除父节点，因为父节点是已经到访过的节点。其次，可以将父节点的上下两个节点排除。
排除上下两个节点的理由非常重要，它是辅助理解JPS算法的关键，理由其实非常微妙，因为这两个节点可以由父节点到达，将父节点走到当前节点视为一条路线，那么从父节点走到上节点也是一条路线。也就是说，当前节点和上节点（下节点同理）其实是父节点的一个岔路口，它最终会形成两条类似的通路。从起点到终点，最短的路线可能有多条，但是我们只需要一条。这就是我们排除那些可以由父节点到达的节点的理由。
那么同理，当前节点的上下两个节点也可以删除，因为它们并不绝对依赖当前节点，完全可以由父节点斜向移动到达，所以我们也排除了上下节点。
最后的右上节点和右下节点也可以排除，不过这并不是因为它们可以由父节点直接到达，而是由于移动到N会产生冗余的路径。对于下图来说，移动到N可以通过P->B->N的路线，或者P->X->N的路线。但是这两条路线的消耗是相等的，而且我们已经移动到了X节点，所以此时再选择P->B->N路线其实会走更远的路。于是右上节点（图中的N节点）和右下节点也被我们排除了，最后留给我们的就只有最后的右节点了。
因为右节点对于父节点来说是不可直接到访，并且如果不通过X来到达右节点的话，那么路径的消耗会更大（因为我们已经到达了X节点）
这些对于A*算法来说都是冗余的判断。所以撇开有障碍的情况，JPS算法在水平和纵向上只会探索一条笔直的线路。
2.JPS算法的基本原理
2.1 从A*的冗余判断到强制邻居
通过对A*算法的冗余节点判断，大概了解了一点JPS的前缀知识，那么现在要进入正题了，回到上述的问题当中，虽然判断都是正确的。但是它基于一个非常理想的环境即当前节点X周围的其他所有节点都是空的。但事实情况是，很有可能周围是存在其他障碍物的。
对于存在障碍物的情况下，上述的对于其他点的判断就有可能是不正确的。所以我们需要列举所有的情况，来看看哪些情况是会产生影响的。
不过为了简单期间，这次我们只观察当前节点上侧的情况，下侧则同理。
1.当前节点的左上节点为障碍物的情况如下图所示
父节点的上节点为障碍物时并不影响到上述的冗余判断，因为这个节点已经被判断为了冗余节点，即使它是空白的也不需要进行检测。更何况它已经是一个障碍物了。
2.当前节点的上节点为障碍物时如下图所示
（ps：当两个点同时为障碍物时并不影响到它们在这个九宫格当中的关系，所以可以分开处理）
当遇到这个情况时，之前的判断就会产生问题，回到前面的那张图。我们说，对于节点N来说，由于已经选择了路线P->X->N，因而路线P->B->N可以不用考虑，从这个角度出发，N节点被我们抛弃了。一旦B不是通路，那么PBN这条路线就会被锁死，我觉得现在疑问点在于，既然已经选择了PXN的路线，为什么还要在乎PBN路线呢？
这个就是最核心的点了，我们其实并没有选择PXN的路线，而是由于PBN和PXN都是通路，导致X并不是由P到达N 的必经之路，因而对于X来说，N节点没有添加到待判断节点的必要
所以PBN路线被锁死时，N的性质就会发生变化，它变成了P必须经由X才能到达的点位（至于为什么不能通过P下侧的点位绕过X是因为默认要找最短的路线）既然N是一个必须经由X才能到达的路线，那么可以认定，N就必须加入到X节点下一步的判断列表中。
此时对于节点N，JPS算法会将其认定为强制邻居。
3.当右上节点是障碍物时
如果右上节点是障碍物，同第一点，它不会影响到之前的对冗余节点判断。
2.2 斜向移动时的强制邻居
知道了强制邻居，或者理解了强制邻居的原理，那么JPS搜索算法就算是理解了1/3了，现在我们来解决第二个部分，也就是JPS算法探索的方式。
不过我们差点忘了一个非常非常重要的东西，就是斜向移动。如果X并不是通过水平或者纵向移动到的，那么它又该如何判断呢？先给出一张图
对于上图，可以按照之前的思路来解决问题。那些不强制依赖当前节点的点都可以被排除。首先就可以排除父节点和父节点可以直接接触到的两个节点。
那么，在没有障碍物的情况下，左上和左下节点也被排除了。
留给X节点的会有3个节点，右节点，上节点，和右上节点。因为这些节点是必须依赖X才能到达的（在要求最短路径的情况下），不过还是那个问题，如下图所示，当B节点为障碍物时，会产生一个新的强制邻居点N。
因为PBN路线被锁死了，所以N节点也得开放为X节点要判断的下一个节点。
2.3 不断地重复这些判断
上面的斜向是朝着右上方，而直线则是朝着右侧移动。但是它们是可以直接被套用为任何一个方向的，整合上面两种处理，就是JPS寻路算法的搜索方式了。
上图中，我将起点至于左下角，如果全图都是空白的，那么利用我们前面讲到的水平和纵向移动时只朝着给定方向前进，斜向移动时朝着斜向方向和斜向方向的分向进行探索。结合两点就形成了JPS算法的基本探索手段。
在这个例图中，给定的方向是右上，所以分量方向就是右侧和上侧。以及，它的顺序主要是由斜向角点的顺序来的，在最初的时候，父节点会向右和上进行不间断的探索（注意和A*算法不同的是，它只是不断地前进，并不会来到一个新的节点后将周围的节点全部加入待判断队列）
如果在水平和纵向的判断中我们找到了目标节点，那么算法就可以中止运行了。如果没有的话，那么它会将当前位置向给定的方向，即右上移动一格，并重复向右和上的分量方向进行不断地探索。
并最终铺满全图，所以在没有障碍物地情况下，JPS算法通过这种方式来找到全图中地任何一个位置。
2.4 当遇到强制邻居时
很愉快，现在我们知道了强制邻居，又知道了将分析强制邻居的那种步进法则不断重复可以形成上面的探索方式。那么当我们真正遇到强制邻居的时候会发生什么呢？如下图所示
在下图中，在当前节点移动到X的时候，在位置N会找到一个强制邻居。如果忘记了强制邻居是怎么找到的，可以回顾下图
因为节点X是通过父节点P到达的，方向是右侧，所以当节点X的下方出现障碍物时，节点N无法再通过父节点P直接移动到了，因而N被判断为一个强制邻居。
这样思考的方式太不人性化了，我觉得是很多人学习JPS算法时的一个究极障碍，现在我们通过另外的方式来对X和N的关系进行探究。刚才已经了解了，如果没有障碍物时，可以很轻松的从起点前往全图的任何一个点位。
但是如果我们把刚才的障碍物加上呢？
这样的话，就没有办法移动到全图的所有位置了，而刚才的X和N就是关键，N为X提供了一个新的方向，也就是说，X应该作为一个新的起点，向XN方向做同样的斜向探索运动，如下图所示
这样一来，即使存在障碍物，也可以探索完全图了。不过别着急，我们还得判断X是否是直接被连接到起始节点的。我们将从起点S出发的斜向移动路径画出来，发现它其实并没有直接连接到X
而是连接到了X的前面一个节点P，所以S其实是无法直接连接到X的，因为在只允许水平纵向斜向移动的网格世界里，S到X的直接连接路线是无效的。所以S走到X的路线其实是S->P->X，到这里我们可以给P和X一个新的称呼，它们就是跳点（Jump Point）
那么至此，所有的分析都完成了。JPS搜索算法的过程其实就是在重复上述过程中不断寻找新的跳点，并按照跳点到强制邻居的方向继续探索。
下面，我们通过C#来实现JPS算法，算法的demo我已经上传到了Github，大家随时可以下载下来进行学习和探索，Github的链接在文章末尾。（尽管如此，我仍然呼吁大家不要下载，而是通过理解算法的本质，然后自己手写一遍）
3.JPS算法C#实现
3.1 算法描述
在开始之前，我们应该构建起一个对算法的重点描述，以备后续查询。
当然，此处的描述不太适合用伪代码表示，因为实在是太麻烦了，不是很容易表达清楚，所以我就直接用白话文描述了。不用担心，在真正开始构建代码的时候我仍然会仔细介绍每一个步骤。
1.获取起点S和终点E
2.从起点S向上下左右四个方向移动，如果遇到跳点，则将跳点直接加入跳点表，
跳点方向由前进方向和强制邻居方向共同决定
3.从起点S向左上、右上、左下、右下四个角点方向移动，每次移动一格，移动之后记当前
位置为parent，接着向角点方向的分量方向循环探索（右上的分量方向是右和上）
如果向右或者向上或者移动到当前位置时，三者有一者发现了跳点，则记录当前点parent为跳点，加入跳点表
方向由当前前进方向（比如之前是右上就还是右上）和强制邻居共同决定。
4.只要跳点表不为空
取出一个损耗最低的跳点，如果跳点为终点，退出循环
将跳点按照给定的方向循环检测。
补充：起点S和终点E均可以被视为跳点（但真实检测的时候往往不会检测起点）上述描述中还有部分点没有说明，比如什么时候，以及如何计算cost，包括当所有跳点都查询完毕了，最终的路线是怎么得出的。这些我们留到代码细节中完善。
3.2 准备工作
虽然是C#实现的，但却是在Unity中，那么在这个 案例中，除了C#自身的功能之外，还用到了Unity自带的结构体，Vector2Int，也就是整型向量，它的属性主要是两个int类值。
public struct Vector2Int{
public int x;
public int y;
// other code...
}
首先我们需要定义网格的接口，因为在不同的游戏引擎或者不同的程序中，网格可能是通过不同的方式来实现的。对于一个网格，所需的接口只有两个。如下所示：
public interface IGrid{
bool isMovable(Vector2Int pos); // 检查目标点位是否可移动
bool isWall(Vector2Int pos); // 检查目标点是否是墙体或者是否不可移动
}
那么除了定义网格接口，我们还需要提供一个针对C#的优先级队列实现，我自己实现了一套，不过这里就不放出来了，我仍然通过接口的形式来定义这个优先级队列。
public interface IPriorityQueue<T>{
bool notEmpty{get;}
T get();
void set(T obj, int priority);
void clear();
}
接着，准备一个静态类来应对一些常用的函数和常量，我们需要定义所有的方向和每个方向的垂直方向，垂直方向是可以算出来的，但是这个玩意很常用，如果每次都算的话，太麻烦了。所以可以将它们作为静态变量存储在一个字典中。
public static class JpsUtils{
public static readonly Vector2Int left = Vector2Int.left;
public static readonly Vector2Int right = Vector2Int.right;
public static readonly Vector2Int up = Vector2Int.up;
public static readonly Vector2Int down = Vector2Int.down;
public static readonly Vector2Int upRight = Vector2Int.one;
public static readonly Vector2Int upLeft = new Vector2Int(-1, 1);
public static readonly Vector2Int downRight = new Vector2Int(1, -1);
public static readonly Vector2Int downLeft = new Vector2Int(-1, -1);
public static Dictionary<Vector2Int, Vector2Int[]> verticalDirLut;
public static void init(){
// 将常用的方向加入到一个字典中，通过方向来索引它的垂线方向
verticalDirLut = new Dictionary<Vector2Int, Vector2Int[]>();
Vector2Int[] horizontalLines = new Vector2Int[]{left, right};
Vector2Int[] verticalLines = new Vector2Int[]{up, down};
verticalDirLut.Add(left, verticalLines);
verticalDirLut.Add(right, verticalLines);
verticalDirLut.Add(up, horizontalLines);
verticalDirLut.Add(down, horizontalLines);
}
/// <summary> 判断当前方向是否为一个直线方向 </summary>
public static bool isLineDireaction(Vector2Int direaction){
return direaction.x * direaction.y == 0;
}
public static int manhattan(Vector2Int p1, Vector2Int p2){
/* 曼哈顿距离 */
return Mathf.Abs(p1.x - p2.x) + Mathf.Abs(p1.y - p2.y);
}
public static int euler(Vector2Int p1, Vector2Int p2){
/* 欧拉距离 */
int dx = p1.x - p2.x;
int dy = p1.y - p2.y;
return dx * dx + dy * dy;
}
}
准备工作的最后就是实现一个跳点对象，来存储一些关键性信息。
public class JpsNode{
/* 跳点, 跳点会记录当前自身需要查询的方向以及父跳点的位置 */
public Vector2Int pos;
public List<Vector2Int> parents;
public Vector2Int[] direactions;
public int cost;
public JpsNode(Vector2Int parent, Vector2Int pos, Vector2Int[] dirs, int cost){
this.pos = pos;
this.direactions = dirs;
this.cost = cost;
this.parents = new List<Vector2Int>();
this.parents.Add(parent);
}
}
对于跳点来说有4个属性，首先是跳点的位置pos，其次是它的父节点的位置parents，这里父节点是一个列表，这是由于一个跳点可能存在多个父节点。directions是该跳点要继续探索的方向，有可能是横纵方向也有可能是斜向。cost是从起点开始走到当前节点所走过的步数，为了简单起见，我在这里所设置的cost计算方式认为无论斜向移动还是横纵移动，消耗都只增加1，这会带来一些问题，不过不是很严重。
3.3 JPS算法实现
加一个类，然后之后我们所有的函数都会在这个类里
public class JPS{
// code..
}
首先是准备一些所需要的参数或者对象，包括优先队列、路径查找表、起点终点。
public class JPS{
private Dictionary<Vector2Int, JpsNode> lut;
private IPriorityQueue<JpsNode> nodes;
private Vector2Int start;
private Vector2Int end;
private IGrid env;
public JPS(){
lut = new Dictionary<Vector2Int, JpsNode>();
// nodes = new ???<JpsNode>(); 优先队列可以自己实现
}
}
其中Lut是我们已经到访过的跳点，注意是到访过而非扫描过，把一个点当作跳点加入跳点表它就已经算到访过了。然后我们为其追加唯一的对外函数，find，通过该函数来查询一条路线。
public void find(IGrid env, Vector2Int s, Vector2Int e){
this.lut.Clear();
this.nodes.clear();
this.env = env;
this.start = s;
this.end = e;
// other codes..
}
剩下的代码暂时先不处理，下面来实现一些基础的函数，首先是追加跳点用的函数。
private void addPoint(Vector2Int parent, Vector2Int p, Vector2Int[] dirs, int fcost){
/* 追加一个新的跳点
@parent: 跳点的父节点
@p: 跳点的位置
@dirs: 跳点应该扫描的方向
@fcost: 从起点到跳点的消耗 */
if(lut.ContainsKey(p)){
lut[p].parents.Add(parent);
}else{
JpsNode node = new JpsNode(parent, p, dirs, fcost);
lut.Add(p, node);
nodes.set(node, fcost + JpsUtils.euler(p, end));
}
}
添加跳点时，如果跳点已经被访问过了，那么直接给跳点增加它的新的父节点，parent，也就是说，当一个已经被访问过的跳点再一次被访问时，它其实是被另外的节点也当成了跳点，所以它有多个父节点。
3.3.1 直线移动
完成了该函数后，来看第一个非常重要的函数，也就是testForceNeighborsInLine检测横纵向移动时是否遇到强制邻居。
private List<Vector2Int> testForceNeighborsInLine(Vector2Int p, Vector2Int d){
/* 检查给定的目标点和方向是否存在强制邻居, 该函数只适用于横纵搜索
@p: 点X
@d: 方向PX，P为X的父节点*/
List<Vector2Int> directions = new List<Vector2Int>();
foreach(Vector2Int vd in JpsUtils.verticalDirLut[d]){
Vector2Int blockPt = vd + p;
if(env.isWall(blockPt) && env.isMovable(blockPt + d))directions.Add(vd + d);
}
return directions;
}
这个函数的实现非常特殊的一个点在于，它的返回值是一个方向的列表，调用该函数的对象需要通过判断列表是否为空来认定当前是否存在强制邻居。另外，它只针对横纵方向的强制邻居检测。
实现原理很简单，我们用下面的图来讲解一下它的原理。
N为强制邻居要满足两个条件，B为障碍且N为空，于是我们先获取PX方向的垂线方向，在函数中我用vd表示，先计算B的位置，然后计算N的位置，将vd和X当前的位置相加我们可以获得B的位置。将B的位置叠加P移动到X的方向d后可以得到N的位置
很显然，N的位置为
注意方向 是函数的第二个参数d，得到B和N的位置后，只要满足B为障碍，N为可移动的位置，就可以认定N是强制邻居，此时我们应该将方向XN加入列表。方向XN可以通过  获得。不过这个方向再计算一次会产生一些计算冗余。我们可以简单将公式往前推一下。
vd是查询出来的，无需计算，而 是该函数的参数也不需要计算。直接叠加即可，否则我们还需要存  的位置。
有了该函数，就可以开始编写沿着某个横纵方向进行跳跃的函数了。
private bool testLine(Vector2Int parent, Vector2Int d, int fcost){
/* 从当前点p开始沿着直线方向d进行循环移动, 遇到跳点、墙体、地图边缘时退出循环，如果该函数是因为
跳点退出函数的，那么返回true，否则为false
@parent：从parent的下一个位置开始检测（这表示当前节点正处于parent）
@d：前进的方向
@fcost：从起点到parent节点的总消耗*/
Vector2Int p = parent + d;
while(env.isMovable(p)){
if(p == end){
/* 找到终点时将终点加入openset */
addPoint(parent, p, new Vector2Int[0], 0);
return true;
}
fcost ++;
List<Vector2Int> directions = testForceNeighborsInLine(p, d);
if(directions.Count > 0){
directions.Add(d);
addPoint(parent, p, directions.ToArray(), fcost);
return true;
}
p += d;
}
return false;
}
这个函数不复杂，但是需要解读，首先第一个点就是要知道parent是一个已经被访问过的点，也就是检测的目标是从下一个点parent+d开始的，d是水平或者垂直方向。
进入while循环的条件是env.isMovable(p)，这表示，只要下一个节点不是障碍或者不是地图边缘，就可以继续移动。当移动到新的位置p时，需要进行两个检测。
- 当前节点p是否为终点，如果是，则以最低的消耗加入跳点表然后返回真值表示找到跳点
- 检测当前节点是否在该方向上存在强制邻居，由于testLine函数是横纵移动，所以检测用的是只针对横纵方向的函数testForceNeighborsInLine，是否存在强制邻居由返回的一个方向列表来决定。因为同时要检测两个方向是否存在强制邻居。具体请看下面的案例。
如果从起点向右连续移动时，遇到了两个强制邻居1和2，这就说明这两个点对于起点来说都是不可到达的，于是必须将X视为一个跳点，并朝着X1方向，X2方向，和X原来的前进方向继续移动。也就是说，除了起点之外，一个跳点最大要向三个方向移动。
所以在上述代码中，如果我们已经知道了directions不为空，也就是存在强制邻居时，会将X原来前进的方向也一并加入跳点方向表，然后中断当前的跳跃，下次当跳点X被重新取出时，会根据跳点X找到的方向来继续探索。
3.3.2 角点/斜向移动
每次向角点方向移动到新节点X时，都会向角点的分量方向进行横纵探索，而且任意分量方向找到跳点时，当前节点X也会被视为跳点，被加入跳点表。所以先准备一个函数用于进行纵向探索来简化斜向移动函数的复杂。
private bool diagonalExplore(Vector2Int p, Vector2Int d, int cost){
/* 朝着角点的分量方向进行探索
@p: 斜向移动后的点位p
@d: 斜向方向
@cost: 走到点p时所消耗的成本 */
bool _1 = testLine(p, new Vector2Int(d.x, 0), cost);
bool _2 = testLine(p, new Vector2Int(0, d.y), cost);
return _1 || _2;
}
注意分量分向的拆法比较简单，现有一个方向  已经确认为斜向方向，那么分量方向则不必为0，所以可以简单的通过  和  来表示其分量方向。
接着就是检测斜向移动时是否遇到跳点了，这个函数其实很复杂，但我通过增加参数将其简化了。
private List<Vector2Int> testForceNeighborsInDiagonal(Vector2Int X, Vector2Int B, Vector2Int D, Vector2Int mask){
/* 检查给定地目标点和方向是否存在强制邻居, 该函数只适用于斜向搜索
只要检测到一边就可以退出函数了，因为只可能存在一边
@X: 移动到的点X，
@B：X点侧边的障碍物
@D: X - parent
@mask: 方向遮罩 */
List<Vector2Int> directions = new List<Vector2Int>();
B += D * mask;
if(env.isMovable(B)){
directions.Add(B - X);
}
return directions;
}
首先返回值还是一个List<Vector2Int>类型，但是这次却没有直接检测它的上下两个垂线方向，而是通过参数给定了一个目标方向，要理解这个点，先观察下列情况。
为什么障碍物点B不是在这个函数里计算，而是通过其他的函数传递过来的。以及为什么只用检查一边，主要就是因为当两个点位都为障碍物时，系统默认无法从S前进到X。
也就是说，在斜向移动时，程序应该事先判断是否可以移动，那么这个时候就是要判断移动的方向的分量方向位置是否为障碍物，所以这个时候我们就已经把障碍物的位置计算出来了，这个判断和判断移动后是否遇到强制邻居判断的位置和内容是一致的，因为判断强制邻居也要求X左侧是一个障碍物。
所以在上层函数进行斜向移动时，我们需要先获取障碍物B1和B2的位置，进行判断。结果有4个
- B1和B2均为空，此时不需要进行本次移动的跳点判断。直接调用diagonalExplore进行横纵方向的检测即可
- B1和B2均不为空，本次移动无效，直接终止该角点方向的移动。
- B1为空而B2不为空，移动是有效的，而且需要单独检测B2方向是否存在强制邻居
- 同情况3，只不过被检测的是B1
所以一旦调用了函数testForceNeighborsInDiagonal函数，我们就已经确认了只存在一边是强制邻居的情况，因而只判断一个方向即可。另外障碍物的位置B应该是手动传递，并且函数并不知道到底是B是属于哪边的，所以要增加一个方向遮罩来帮助其计算。
对这个函数其他的疑问，都可以在testDiagonal中解惑，来看一下这个最复杂的函数。
private void testDiagonal(Vector2Int parent, Vector2Int p, Vector2Int d, int fcost){
/* 斜向移动，每次斜向移动一格，并检查斜向分量是否存在跳点。
@parent: 斜向移动最初的起点，parent必是一个跳点，否则它不会触发testDiagonal函数
@p: 当前移动到的点p
@d: 斜向的方向
@fcost: 消耗 */
// 计算障碍物1和障碍物2的位置
Vector2Int b1 = new Vector2Int(p.x + d.x, p.y);
Vector2Int b2 = new Vector2Int(p.x, p.y + d.y);
if(env.isMovable(b1)){
if(env.isMovable(b2)){
/* 情况1，B1和B2均为空，可以移动且本次移动不需要检测斜向的跳点 */
p += d;
if(env.isMovable(p)){
//新的位置不是障碍物
fcost ++;
if(p == end){
addPoint(parent, p, null, fcost);
return;
}
if(diagonalExplore(p, d, fcost)){
addPoint(parent, p, new Vector2Int[]{d}, fcost);
return;
}
testDiagonal(parent, p, d, fcost); // 递归该函数
}
}else{
// 情况3，b1可以移动，而b2不可移动
// code..
}
}else{
if(env.isMovable(b2)){
// 情况4，b2可以移动，而b1不可移动
// codes..
}else{
// 情况2，两者均不可移动，什么都不做
// code..
}
}
}
现在看到的是第一部分，也就是上面说的情况中的第一种，如果b1和b2均为空的话，那只需要进行两个最基本的检测，也就是要移动的点位X是否为空，如果X是障碍物，那么也不会继续检测了。
如果P不为空，那么开始检测p是否为终点，注意检测是否为终点不能早于障碍物的检测，因为如果两个障碍物都是切实存在的，那么即使只有一墙之隔，它也是无法接触的。
如果不是终点，则继续向左右两个方向进行探索。如果两个方向有任何一个方向存在跳点，那么当前点也会被视为跳点。
如果啥都没有，则继续递归（其实可以循环，但是会搞得非常复杂）
接着我们看看有障碍的情况如何处理。
else{
// 情况3，b1可以移动，而b2不可移动
p += d;
if(env.isMovable(p)){
fcost ++;
if(p == end){
addPoint(parent, p, null, fcost);
return;
}
List<Vector2Int> dirs = testForceNeighborsInDiagonal(p, b2, d, Vector2Int.up);
if(diagonalExplore(p, d, fcost) || dirs.Count > 0){
dirs.Add(d);
addPoint(parent, p, dirs.ToArray(), fcost);
return;
}
testDiagonal(parent, p, d, fcost);
}
}
接着刚才的函数，在情况3中，前面是差不多的，移动+检测p是否为空+检测p是否为终点。那么后面唯一不同的是，这次我们利用了testForceNeighborInDiagonal函数检测当前角点方向是否存在强制邻居。
如果存在强制邻居亦或是横纵方向有任何一个方向存在跳点，那么自身都会被认定为跳点，从而中断当前的递归。所以其实就是多了一个对强制邻居的判断。
那么同理，情况4中也是一样的。只是参数略有不同罢了。这个函数的完全体就是下面这样
private void testDiagonal(Vector2Int parent, Vector2Int p, Vector2Int d, int fcost){
/* 斜向移动，每次斜向移动一格，并检查斜向分量是否存在跳点。
@parent: 斜向移动最初的起点，parent必是一个跳点，否则它不会触发testDiagonal函数
@p: 当前移动到的点p
@d: 斜向的方向
@fcost: 消耗 */
// 计算障碍物1和障碍物2的位置
Vector2Int b1 = new Vector2Int(p.x + d.x, p.y);
Vector2Int b2 = new Vector2Int(p.x, p.y + d.y);
if(env.isMovable(b1)){
if(env.isMovable(b2)){
/* 情况1，B1和B2均为空，可以移动且本次移动不需要检测斜向的跳点 */
p += d;
if(env.isMovable(p)){
//新的位置不是障碍物
fcost ++;
if(p == end){
addPoint(parent, p, null, fcost);
return;
}
if(diagonalExplore(p, d, fcost)){
addPoint(parent, p, new Vector2Int[]{d}, fcost);
return;
}
testDiagonal(parent, p, d, fcost); // 递归该函数
}
}else{
// 情况3，b1可以移动，而b2不可移动
p += d;
if(env.isMovable(p)){
fcost ++;
if(p == end){
addPoint(parent, p, null, fcost);
return;
}
List<Vector2Int> dirs = testForceNeighborsInDiagonal(p, b2, d, Vector2Int.up);
if(diagonalExplore(p, d, fcost) || dirs.Count > 0){
dirs.Add(d);
addPoint(parent, p, dirs.ToArray(), fcost);
return;
}
testDiagonal(parent, p, d, fcost);
}
}
}else{
if(env.isMovable(b2)){
// 情况4，b2可以移动，而b1不可移动
p += d;
if(env.isMovable(p)){
fcost ++;
if(p == end){
addPoint(parent, p, null, fcost);
return;
}
List<Vector2Int> dirs = testForceNeighborsInDiagonal(p, b1, d, Vector2Int.right);
if(diagonalExplore(p, d, fcost) || dirs.Count > 0){
dirs.Add(d);
addPoint(parent, p, dirs.ToArray(), fcost);
return;
}
testDiagonal(parent, p, d, fcost);
}
}else{
// 情况2，两者均不可移动，什么都不做
// code..
}
}
}
其实我自己在实现的过程中，要更加简略一点，这里方便大家理解，虽然情况4和情况3代码几乎一致，但是我还是贴出来了。因为我们要明确这四种情况。
那么到此为止，核心的部分就算是结束了，剩下的就是将上述函数组织到find函数里了。
3.3.3 完善JPS算法
那么这个时候，find函数的返回值就不是void而是Vector2Int[]类型了。
public Vector2Int[] find(IGrid env, Vector2Int s, Vector2Int e){
this.env = env;
this.start = s;
this.end = e;
this.lut.Add(s, new JpsNode(s, s, new Vector2Int[0], 0)); // 直接将起点加入到查找表
// 起点是一个特殊的跳点，也是唯一一个全方向检测的跳点，其他跳点最多拥有三个方向
Vector2Int[] dirs = new Vector2Int[]{
JpsUtils.up,
JpsUtils.down,
JpsUtils.left,
JpsUtils.right,
JpsUtils.upLeft,
JpsUtils.upRight,
JpsUtils.downLeft,
JpsUtils.downRight,
};
JpsNode S = new JpsNode(s, s, dirs, 0);
nodes.set(S, 0);
while(nodes.notEmpty){
JpsNode node = nodes.get();
if(node.pos == end)return completePath();
foreach(Vector2Int d in node.direactions){
if(JpsUtils.isLineDireaction(d)){
testLine(node.pos, d, node.cost);
}else{
testDiagonal(node.pos, node.pos, d, node.cost);
}
}
}
return null;
}
这里主要分为三块，第一块是，我们直接将起点加入了查找表，第二块是，我们都知道跳点有自己要查询的方向列表，而且每个跳点最多只有三个方向。那么前面说的唯一的例外就是起点了，它是需要检测全方向的。所以进一步利用空间换时间的话，可以把这些方向存为一个只读变量，只是如果寻路压力不大的话，没这个必要。
最后创建一个新的JpsNode，并将节点丢入跳点表。
第三块就是循环了，只要跳点表不为空且没有找到终点，那么就会不断循环，唯一需要注意的就是当拿到一个节点的某个方向时，需要检查这个方向是角点/斜向方向还是横纵/直线方向，分别用testLine函数和testDiagonal函数来处理它们。
当循环结束时，我们将得到一个查找表，它是一个Dictionary<Vector2Int, JpsNode>类型，由于JpsNode也会存储自己的父节点。所以这个查找表实际上构成了一个由跳点构成的图（Graph），此时可以通过构建一个迷你的迪杰斯特拉算法或者A*算法来明确最终的路线。
因为它已经是Graph类型了，对于一个数量级为  的地图，它的跳点数量也只会是  数量级的，所以不需要担心最后的这个迪杰斯特拉算法或者A*算法所产生的消耗。
我们通过构建最后的函数completePath来找到最终的路线。
public Vector2Int[] completePath(){
Dictionary<Vector2Int, Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>();
HashSet<Vector2Int> closedSet = new HashSet<Vector2Int>();
Queue<JpsNode> openSet = new Queue<JpsNode>();
openSet.Enqueue(lut[end]);
while(openSet.Count > 0){
JpsNode node = openSet.Dequeue();
closedSet.Add(node.pos);
foreach(Vector2Int pos in node.parents){
if(closedSet.Contains(pos))continue;
cameFrom.Add(node.pos, pos);
if(pos == start)return _trace(cameFrom);
openSet.Enqueue(lut[pos]);
}
}
return null;
}
private Vector2Int[] _trace(Dictionary<Vector2Int, Vector2Int> cameFrom){
List<Vector2Int> path = new List<Vector2Int>();
Vector2Int current = end;
while(current != start){
path.Add(current);
current = cameFrom[current];
}
path.Add(start);
return path.ToArray();
}
下面是一些测试的过程。
我构建了一个简单的地图，绿色为起点，红色为终点。
通过JPS算法，可以找到一条最短的路径（可能会有多条最短的路径，但是JPS只会找到一条）
上传到知乎时似乎给图片压缩了一下，导致部分节点看不清楚
其中蓝色标记的就是跳点，黄色的则是我们最终的路线。不过这并不代表它只探索过这些区域，其实如果将查找表中的所有节点都绘制出来，应该是下面这样的。
可以看见，它最初的时候走的是下面的路线，因为在没有检测到障碍的时候，下面的路线的预估的成本最低，最有可能实现找到一条路径。但是当它遇到障碍时，这条路线就会终止。并回头继续迭代其他的路线。我们也可以将它到访过的每个点位都标记出来。
其实JPS算法是极有可能重复探索某些点位的，不过这么做没啥问题，因为重复探索不是因为要检查终点，而是构建点与点之间的衔接关系。
4.JPS算法补充
其中还有一些我觉得可以在补充讲解地方，在下面列出来。
4.1 角点/斜向方向的强制邻居检测
关于testForceNeighborsInDiagonal函数是如何检测角点的，可以看下面的例图。
首先我们要明确的是，我们已经掌握了4个参数，即P父节点位置，X当前节点位置，B障碍物点位置和PX方向，即角点前进的方向，那么我们要得到位置N该如何计算呢？
其实N就等于B的位置叠加PX的分量方向。先列出下列公式
其中  表示方向 的某个分量，但具体是哪个分量，我们是不清楚的。所以需要由上级函数来明确到底是X分量还是Y分量。如果是X分量，我们应该给予一个遮罩  ，如果是Y分量，遮罩则是 ，这样这个遮罩乘以方向之后，就得到了分量方向。
比如在上图中，可以直接确定遮罩为 ，而PX方向则是  ，所以两者相乘得到结果为  ，这个值就是  ，公式如下：
其中  由上级对象指定的遮罩。有了位置N之后，也可以顺利成章的计算NX的方向了，直接用N的位置减去X的位置即可。
那么回头来看我们的testForceNeighborsInDiagonal函数，所有的一切就非常清晰了。
private List<Vector2Int> testForceNeighborsInDiagonal(Vector2Int X, Vector2Int B, Vector2Int D, Vector2Int mask){
/* 检查给定地目标点和方向是否存在强制邻居, 该函数只适用于斜向搜索
只要检测到一边就可以退出函数了，因为只可能存在一边
@X: 移动到的点X，
@B：X点侧边的障碍物
@D: X - parent
@mask: 方向遮罩 */
List<Vector2Int> directions = new List<Vector2Int>();
B += D * mask;
if(env.isMovable(B)){
directions.Add(B - X);
}
return directions;
}
4.2 禁止在障碍边缘斜向移动
还记得斜向移动的4种情况吗，在下面的情况下，X会被判断为一个跳点，但是这样的检测方式会允许S->X路线称为可能，但是这种贴墙角移动的方式会让人感到不愉快。如果禁止这种移动会发生什么？或者是否允许对JPS算法做这种改变？
答案是允许的，不会对寻路造成影响，产生的改变有两个，第一是之前的角点移动中的4种情况会坍缩为1种，也就是只有当两边都没有障碍物时，这条路线才是可行的。
第二是直线移动时，检测强制邻居的函数会发生改变。
原本我们需要判断B的位置在X的垂线方向，但是如果不允许斜向移动的话，那么B的位置会跑到P的垂线方向，也就是当P的垂线方向为障碍物，X的垂线方向为通路时，通路位置才会被判断为强制邻居。如下图所示：
之前的testForceNeighborsInLine函数就会变成下面这样
private List<Vector2Int> testForceNeighborsInLine(Vector2Int p, Vector2Int d){
/* 检查给定的目标点和方向是否存在强制邻居, 该函数只适用于直线搜索*/
List<Vector2Int> directions = new List<Vector2Int>();
foreach(Vector2Int vd in JpsUtils.verticalDirLut[d]){
Vector2Int blockPt = vd + p;
if(env.isWall(blockPt) && env.isEmpty(blockPt + d)){
directions.Add(vd + d);
directions.Add(vd);
}
}
return directions;
}
注意这里参数中的p不再是X了，而是父节点P。对于跳点X来说，它最大可能要检测5个方向。
5.总结
OK，以上就是所有关于JPS算法的部分了，研究这个算法花了三天的时间，着实不容易。对于本次用到的代码，其实只有一个简单的cs文件，因为这里面并没有实现IGrid和IPriorityQueue<T>，至于实验环境可以通过Unity来构建。代码我已经贴到了GitHub了，有需要的可以自行下载。 |
本帖子中包含更多资源
您需要 登录 才可以下载或查看，没有账号？立即注册
×
|
窥视卡
雷达卡
发表于 2022-4-21 10:01
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡