本文章由mosya提供
JPS算法概述
JPS（Jump Point Search）算法是一种用于路径规划的优化算法，主要用于网格地图中的最短路径搜索。它是A*算法的改进版本，通过跳过不必要的节点来大幅提高搜索效率。
JPS算法的核心思想是通过“跳跃”来跳过那些不会影响最终路径的节点，从而减少需要处理的节点数量。相比于A*算法，JPS算法在网格地图中的表现尤为出色，尤其是在大规模地图中。
(如果对A星算法不了解的，建议先了解A星算法)
为什么需要JPS算法？
A*算法的局限性: A星算法在扩展节点时会把所有相邻的节点考虑进去，当地图比较大时，开放列表（open list） 中的节点数量会很多，导致搜索效率较低，而在两点之间如果没有障碍物时，那么中间的节点对我们来说是没有用的，这些节点不必添加到开放列表（open list）。
JPS的优势: JPS算法通过“跳跃”跳过那些不会影响最终路径的节点，减少了需要处理的节点数量，从而提高了搜索效率。
JPS算法原理
基本概念
强制邻居（Forced Neighbors）: 在某些情况下，节点必须检查特定的邻居节点，这些节点被称为强制邻居。
什么样的点可以作为强制邻居:
节点X的邻居节点有障碍物，且X的父节点P经过X到达N的距离代价，比不经过X到大N的任一路径的距离代价都小，则称N是X的强迫邻居。
(前面的是官方说法，我个人的理解是从节点A开始往方向m搜错，如果搜索到节点B时，垂直于m方向上有障碍物C，那么从障碍物C开始往搜索方面搜索到的第一个节点D则是B的强制邻居，对斜对角搜索还存疑惑的话，请往下看斜对角的搜索规则)
跳跃点（Jump Points）: 跳跃点是指在搜索过程中需要进一步扩展的节点，它们通常是路径中的关键点。(我个人理解为可以加到openList中的节点)
什么样的节点可以作为跳点：
(1)节点 A 是起点、终点(2)节点A 至少有一个强迫邻居.(3)父节点在斜方向(斜向搜索)，节点A的水平或者垂直方向上有满足 (1)、(2) 的节点
搜索规则
JPS算法通过以下规则来确定跳跃点：
直线跳跃: 在当前方向上一直移动，直到遇到障碍物或边界。
对角线跳跃: 在对角线方向上移动，直到遇到障碍物或边界。(斜对角方向上搜索相当于做两个方向上的直线跳跃)
强制邻居检查: 在移动过程中，如果发现强制邻居，则当前节点为跳跃点。
算法步骤
1.初始化
起点和终点：确定起点（Start）和终点（Goal）的位置。
网格信息：提供一个网格或地图信息，标明每个位置是否可通行。这个网格通常以二维数组或类似的数据结构表示。
启发式函数：计算当前节点到目标节点的启发式值，通常使用曼哈顿距离或欧几里得距离。
2. 使用A*的基本框架
类似A*算法，初始化开放列表（open list）和关闭列表（closed list）。
将起点添加到开放列表中，起点的G值为0，F值为G + H（其中H是启发式值）。
循环执行以下步骤，直到找到路径或没有可行路径为止。
3. 扩展节点
从开放列表中选择F值最小的节点作为当前节点。
将当前节点添加到关闭列表中。
对当前节点的相邻节点进行扩展，找到所有的邻居。
4. 跳跃搜索（核心步骤）
通过跳跃（Jumping）来避免逐个节点检查，从而大大减少计算量。跳跃的核心是跳过不必要的节点，只检查关键的跳点。
跳点搜索：在每个方向（上下左右或对角线）上进行跳跃。当沿着某个方向跳跃时：
检查障碍物：如果跳跃会碰到障碍物（不可通行区域），则停止跳跃。
强制邻居：如果跳跃到某个节点后，它的邻居是一个必须扩展的节点（即强制邻居），则该节点被认为是一个“跳点”。
到达目标：如果跳跃到目标节点，则结束跳跃并返回目标。
方向检查：
在水平或垂直方向跳跃时，如果遇到障碍物，检查相邻的两个方向。如果有强制邻居，则返回跳点。
在对角线方向跳跃时，如果跳跃到相邻的水平或垂直方向遇到障碍物，则在这些方向上分别跳跃，确保包含所有强制邻居。
5. 更新开放列表
如果找到一个有效的跳点并且该跳点不在关闭列表中，将其加入开放列表，并计算其G值、H值和F值。
如果该跳点已经在开放列表中，检查新的G值是否更小。如果更小，则更新该跳点的父节点和G值。
6. 路径回溯
一旦终点被扩展，表示找到了路径。通过回溯父节点从终点到起点，得到完整路径。
如果开放列表为空，说明没有找到可行路径。
7. 终止条件
如果找到路径，返回路径。
如果开放列表为空并且没有找到目标，说明没有可行路径，算法终止。
算法模拟演示图
演示图说明
1.绿色方格为加入关闭列表（closed list）中的节点，红色方格为终点，棕色方格为障碍物，蓝色方格为强制跳点
2.箭头代表从某个加入关闭列表（closed list）节点出发的搜索方向
3.在此图中，从S开始搜索，当沿G5方向搜索并搜索到G3时，发现J3是强制邻居，则G3是跳点，同理沿F7搜索时M1是强制邻居，F4是跳点，O1是强制邻居，F6是跳点，然后搜索完毕，将S加入关闭列表（closed list），然后从G3，F4，F6中根据A星算法中的路径消耗的计算公式找出消耗最少的节点继续搜索，这里应该是G3，然后循环以上操作直至找到终点为止
JPS算法实现
using System.Collections.Generic;
using UnityEngine;
public class JPSPathfinder : MonoBehaviour
{
public int gridWidth; // 网格宽度
public int gridHeight; // 网格高度
public Vector2Int start; // 起点坐标
public Vector2Int end; // 终点坐标
public bool[,] walkableGrid; // 是否可通行的网格（true为可通行）
private readonly Vector2Int[] directions = {
new Vector2Int(0, 1), // 上
new Vector2Int(1, 0), // 右
new Vector2Int(0, -1), // 下
new Vector2Int(-1, 0), // 左
new Vector2Int(1, 1), // 右上
new Vector2Int(1, -1), // 右下
new Vector2Int(-1, 1), // 左上
new Vector2Int(-1, -1) // 左下
};
void Start()
{
// 测试网格大小和初始化
gridWidth = 10;
gridHeight = 10;
walkableGrid = new bool[gridWidth, gridHeight];
for (int x = 0; x < gridWidth; x++)
{
for (int y = 0; y < gridHeight; y++)
{
walkableGrid[x, y] = true; // 初始化为全部可通行
}
}
// 设置障碍物
walkableGrid[4, 4] = false;
walkableGrid[4, 5] = false;
// 设置起点和终点
start = new Vector2Int(0, 0);
end = new Vector2Int(9, 9);
// 执行JPS寻路
List<Vector2Int> path = FindPath(start, end);
// 打印结果
if (path != null)
{
Debug.Log("Path found:");
foreach (var node in path)
{
Debug.Log(node);
}
}
else
{
Debug.Log("No path found.");
}
}
// 核心寻路方法
public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal)
{
PriorityQueue<Node> openList = new PriorityQueue<Node>();
HashSet<Vector2Int> closedList = new HashSet<Vector2Int>();
openList.Enqueue(new Node(start, 0, Heuristic(start, goal)));
while (openList.Count > 0)
{
Node current = openList.Dequeue();
// 如果找到终点，则返回路径
if (current.Position == goal)
{
return RetracePath(current);
}
closedList.Add(current.Position);
foreach (var direction in directions)
{
Vector2Int jumpPoint = Jump(current.Position, direction, goal);
if (jumpPoint == Vector2Int.zero) continue; // 无效跳点
if (closedList.Contains(jumpPoint)) continue;
float gCost = current.G + Vector2Int.Distance(current.Position, jumpPoint);
Node successor = new Node(jumpPoint, gCost, gCost + Heuristic(jumpPoint, goal), current);
openList.Enqueue(successor);
}
}
return null; // 无路径
}
// 跳点搜索
private Vector2Int Jump(Vector2Int current, Vector2Int direction, Vector2Int goal)
{
Vector2Int next = current + direction;
// 检查边界和是否可通行
if (!IsWalkable(next)) return Vector2Int.zero;
// 如果到达目标点，返回目标点
if (next == goal) return next;
// 如果发现强制邻居，返回当前点
if (HasForcedNeighbors(next, direction))
{
return next;
}
// 递归跳跃
if (IsDiagonal(direction))
{
if (Jump(next, new Vector2Int(direction.x, 0), goal) != Vector2Int.zero ||
Jump(next, new Vector2Int(0, direction.y), goal) != Vector2Int.zero)
{
return next;
}
}
return Jump(next, direction, goal); // 继续向该方向跳跃
}
// 判断强制邻居
private bool HasForcedNeighbors(Vector2Int position, Vector2Int direction)
{
if (!IsDiagonal(direction))
{
if (direction.x != 0) // 水平方向
{
return (!IsWalkable(position + new Vector2Int(0, 1)) && IsWalkable(position + new Vector2Int(direction.x, 1))) ||
(!IsWalkable(position + new Vector2Int(0, -1)) && IsWalkable(position + new Vector2Int(direction.x, -1)));
}
else // 垂直方向
{
return (!IsWalkable(position + new Vector2Int(1, 0)) && IsWalkable(position + new Vector2Int(1, direction.y))) ||
(!IsWalkable(position + new Vector2Int(-1, 0)) && IsWalkable(position + new Vector2Int(-1, direction.y)));
}
}
return false; // 对角线方向无需强制邻居检查
}
// 判断是否为对角线方向
private bool IsDiagonal(Vector2Int direction)
{
return direction.x != 0 && direction.y != 0;
}
// 判断节点是否可通行
private bool IsWalkable(Vector2Int position)
{
return position.x >= 0 && position.x < gridWidth &&
position.y >= 0 && position.y < gridHeight &&
walkableGrid[position.x, position.y];
}
// 计算启发值（曼哈顿距离）
private float Heuristic(Vector2Int a, Vector2Int b)
{
return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}
// 回溯路径
private List<Vector2Int> RetracePath(Node node)
{
List<Vector2Int> path = new List<Vector2Int>();
while (node != null)
{
path.Add(node.Position);
node = node.Parent;
}
path.Reverse();
return path;
}
// 节点类
private class Node
{
public Vector2Int Position; // 节点位置
public float G; // 起点到当前节点的代价
public float F; // 总代价（G + H）
public Node Parent; // 父节点
public Node(Vector2Int position, float g, float f, Node parent = null)
{
Position = position;
G = g;
F = f;
Parent = parent;
}
}
// 优先队列
private class PriorityQueue<T> where T : Node
{
private readonly List<T> elements = new List<T>();
public int Count => elements.Count;
public void Enqueue(T item)
{
elements.Add(item);
elements.Sort((a, b) => a.F.CompareTo(b.F)); // 按F值排序
}
public T Dequeue()
{
T item = elements[0];
elements.RemoveAt(0);
return item;
}
}
}
使用说明
创建一个空的Unity对象，将上述脚本附加到该对象上。
设置网格的大小、障碍物、起点和终点。
点击播放，脚本会在控制台输出找到的路径。你可以在游戏视图中绘制路径进行可视化。
代码说明
起点和终点：通过start和end指定。
障碍物设置：通过walkableGrid设置不可通行的格子。
优先队列：用于实现A*的效率提升。
跳点逻辑：实现了跳点搜索的关键逻辑，包括强制邻居检测和递归跳跃。
参考资料:JPS(jump point search)寻路算法_jps算法-CSDN博客
