JPS(jump point search)寻路算法

大家好，欢迎来到IT知识分享网。

JPS(jump point search)寻路算法

JPS（jump point search）跳跃点寻路算法是对AStar寻路算法的一个改进。

AStar 算法在扩展节点时会把所有相邻的节点考虑进去，当地图比较大时，openList 中的节点数量会很多，搜索效率较低。

可以看到JPS 算法不是每个节点都紧密连接的，而是跳跃性的或者说只有需要转弯的节点(也叫拐点)才会被考虑，所以叫跳跃点(Jump Point)。

dirList = { 
   }; if(A没有父节点) { 
    dirList = { 
    上(0, 1), 下(0, -1), 左(-1, 0), 右(1, 0), 左上(-1, 1), 右上(1, 1), 右下(1, -1), 左下(-1, -1) }; } else { 
    父节点为 P PA = (horizontalDir,verticalDir) // P 到 A 方向的 坐标偏移 // 从父节点到 A 节点 方向分解的水平 horizontalDir、垂直方向verticalDir  // 如父节点 P 到节点 A 的方向 PA 斜向右上（1， 1）则 horizontalDir= 1、verticalDir = 1 // 如父节点 P 到节点 A 的方向 PA 向右（1， 0）则 horizontalDir=1 、verticalDir= 0 if(horizontalDir != 0) { 
    dirList.Add((horizontalDir, 0)); } if(verticalDir != 0) { 
    dirList.Add((0, verticalDir )); } if(horizontalDir != 0 && verticalDir != 0) { 
    //斜向 PA(X,Y)搜索 dirList.Add((horizontalDir, verticalDir )); } foreach(Node N in A 的所有强制邻居) { 
    // AN 节点 A 到其强制邻居节点的偏移，一定是斜向的 dirList.Add(AN); } } foreach (方向 dir in dirList) { 
    节点B = A while(true) { 
    B += dir //向前迈进一步 if(B 是跳点) { 
    给B赋权值并且将跳点加入 openList break; } if(B是障碍物、地图边界) { 
    break; } } } 

三.回到步骤二继续搜索

G3向右搜索发现节点J3是 J1 的强迫邻居，则J1是跳点，将节点J3加入到J1的强迫邻居列表中，将 J1添加到 openList，将 J1标记为蓝色
由于不是斜向搜索发现的跳点，则继续
G3向下搜索到边界，斜向迈进一步到达 G4
G4向右搜索到达边界，向下搜索到达边界，G4不是跳点，则斜向迈进一步到达G5
G5向右搜索到达边界，向下搜索到达边界，G5到达边界，则搜索结束。
将G3加入到 closedList 中

8看上图
取出openList 中权值最小的节点此时 openList ={F4, J1}，F4权值最小，将F4取出，将F4标记为绿色
F4的父方向是S，则SF4方向为右上(1, 1)
SF4可以分解为 水平向右(1, 0)和垂直向上(0, 1)两个方向
则SF4斜向搜索需要搜索的方向为 水平向右(1, 0)、垂直向上(0, 1)和斜向右上(1, 1)三个方向

F4向右搜索发现 节点M1 是节点 J2的强迫邻居，则J2是跳点，将节点M1加入到J2的强迫邻居列表中，将 J2加入到 openList，并将 J2标记为蓝色
由于不是斜向搜索发现的跳点，则继续
F4向上搜索到达边界，斜向迈进一步到达F5
F5向右搜索到达边界，F5向上搜索到达边界，F5不是跳点，则斜向迈进一步到达F6
F6向右搜索发现节点O1是K1的强迫邻居，则F6是跳点，则将 F6加入到 openList，将F6标记为蓝色，
由于F6为 SF4 发起的斜向搜索，所以是在 SF4斜向搜索的时候发现了跳点F6，则不再继续向下搜索了，也不在继续斜向搜索，SF4斜向搜索停止
将F4加入到 closedList

13看上图
从openList中取出权值最小的节点，此时 openList ={ J3，M1}, 节点J3权值最小，则取出J3，并将J3标记为绿色
J3父方向是 J1，则J1F3方向为斜向右上 (1, 1)
J1J3分解为水平向右(1, 0)和垂直(0, 1)两个方向
J3向右索索到边界，向上搜索到M1，M1已经在openList中，如果从J3到M1 的权值比 M1当前权值更小，则更新M1的权值，斜向迈进一步到达N1
N1向右搜索到边界，向上搜索到边界，斜向迈进一步到达N2
N2向右搜索到边界，向上搜索到边界，斜向迈进一步到达N3
。。。直到到达边界

到这里已经触摸到终点E了，接下来再将 P2取出来就能搜索到终点E 了，不再说明了，搜索成功结束

此处是代码实现连接，Unity辅助展示，核心逻辑与引擎无关、与语言无关

判断水平、垂直方向(水平向右、水平向左、竖直向上、竖直向下)的强制邻居

CheckHVForceNeighbour 

判断斜向(左上、左下、右上、右下)的强制邻居

CheckDiagonalForceNeighbour 

先来看水平方向逻辑

先看前置接点P和当前节点X 处于横向水平关系时
从上图可看出从 P 到 X 是水平方向，X 的强制邻居有分别是 N1、N2
组成部分是：
(1)P、X、O1、N1
(2)P、X、O2、N2

已知：P、X 坐标
如何求得 O1、N1、O2、N2 的坐标？
P 指向 X 的方向 dir = (1, 0)
(1.1)公式1：
O1坐标 = X + (Abs(dir.Y) * 1, Abs(dir.X) * 1)
O1坐标 = X + (0, 1)

(1.2)公式2：
N1 坐标 = O1坐标 + dir
N1 坐标 = O1 坐标 + (1, 0)

(2.1)公式3：
O2 坐标 = X + (Abs(dir.Y) * -1, Abs(dir.X) * -1)
O2 坐标 = X + (0, -1)
(2.2)公式4：
N2 坐标 = O2 坐标 + dir
N2 坐标 = O2 坐标 + (1, 0)

同理水平向左、竖直向上、竖直向下 也都是使用 公式1、公式2、公式3、公式4
公式1和公式3的区别在于
公式1 乘以 1 -> (Abs(dir.Y) * 1, Abs(dir.X) * 1)
公式3 乘以 -1 -> (Abs(dir.Y) * -1, Abs(dir.X) * -1)

公式2 和 公式4 相同

再来看斜向逻辑

先看前置接点P和当前节点X 处于斜向关系
从上图可看出从 P 到 X 是斜向左上，X 的强制邻居有分别是 N1、N2
组成部分是：
(1)P、X、O1、N1
(2)P、X、O2、N2

已知：P、X 坐标
如何求得 O1、N1、O2、N2 的坐标？
P 指向 X 的方向 dir = (-1, 1)
(1.1)公式1：
O1坐标 = X + (dir.X, 0)
O1坐标 = X + (-1, 0)

(1.2)公式2：
N1 坐标 = O1 坐标 + (dir.X, 0)
N1 坐标 = O1 坐标 + (-1, 0)

(2.1)公式3：
O2 坐标 = X + (0, dir.Y)
O2 坐标 = X + (0, 1)

(1.2)公式4：
N2 坐标 = O2 坐标 + (0, dir.Y)
N2 坐标 = O2 坐标 + (0, 1)

同理水平向左、竖直向上、竖直向下 也都是使用 公式1、公式2、公式3、公式4

如有错误之处请指出，感谢