Jump Point Search (JPS) 是一种优化的路径规划算法，主要用于加速A*搜索算法在网格地图上的性能。它通过减少要评估的节点数量来实现这一目标。以下是对JPS算法的详细解释：
基本思想
JPS利用了路径规划中的对称性，跳过不必要的节点，直接跳到关键节点（即“跳点”）。这些跳点是那些需要转向或者是障碍物边缘的节点。
算法步骤
初始设置：与A*类似，JPS使用启发式函数来评估节点的优先级。它维护一个开放列表（open list）来存储待评估的节点和一个封闭列表（closed list）来存储已评估的节点。
跳跃扩展：从当前节点开始，沿着八个可能的方向（水平、垂直和对角线）“跳跃”，而不是一步步移动。跳跃过程会跳过一系列连续的自由节点，直到遇到以下三种情况之一：
障碍物：跳跃被阻挡。跳点：跳跃到达的节点是一个跳点。目标节点：跳跃到达目标节点。
确定跳点：在跳跃过程中，通过检查节点的邻居来决定是否某个节点是跳点。跳点满足以下条件之一：
强制邻居：节点有一个或多个强制邻居，意思是该节点的某个邻居是一个非自由节点，而邻居的邻居是自由节点。路径转向：节点在某个方向上跳跃，需要转向另一个方向继续跳跃。
路径重建：一旦目标节点被访问，从目标节点反向追踪路径，类似于A*算法。
优点
效率：通过跳跃跳过大量不必要的节点评估，JPS显著加快了路径规划过程，尤其在开放区域效果更佳。路径优化：生成的路径与A*算法一致，路径最优。
代码实现
下面是JPS算法的一个简单实现，使用伪代码来展示主要逻辑：
// 检查节点是否是跳点
bool isJumpPoint(GridCell current, GridCell direction) {
// 检查是否存在强制邻居
if ((isFree(current + direction) && !isFree(current + perpendicular(direction))) ||
(isFree(current + perpendicular(direction)) && !isFree(current + direction))) {
return true;
}
return false;
}
// 进行跳跃
GridCell jump(GridCell current, GridCell direction) {
GridCell next = current + direction;
// 如果跳跃超出地图边界或遇到障碍物
if (!isValidCell(next) || isOccupied(next)) {
return invalidCell;
}
// 如果跳点是目标节点
if (next == goal) {
return next;
}
// 如果找到跳点
if (isJumpPoint(next, direction)) {
return next;
}
// 继续沿当前方向跳跃
return jump(next, direction);
}
// JPS主算法
void JPS(GridCell start, GridCell goal) {
openSet.emplace(0, start);
gScore[start] = 0;
while (!openSet.empty()) {
GridCell current = openSet.top().second;
openSet.pop();
if (current == goal) {
return reconstructPath(cameFrom, current);
}
for (const auto &direction : directions) {
GridCell jumpPoint = jump(current, direction);
if (jumpPoint != invalidCell) {
double tentative_gScore = gScore[current] + euclideanDistance(current, jumpPoint);
if (gScore.find(jumpPoint) == gScore.end() || tentative_gScore < gScore[jumpPoint]) {
cameFrom[jumpPoint] = current;
gScore[jumpPoint] = tentative_gScore;
double fScore_jumpPoint = tentative_gScore + euclideanDistance(jumpPoint, goal);
openSet.emplace(fScore_jumpPoint, jumpPoint);
}
}
}
}
}
关键函数
isJumpPoint：检查节点是否是跳点。jump：在给定方向上跳跃，直到找到跳点、遇到障碍物或超出地图边界。JPS：JPS算法主函数，与A*类似，但使用jump函数来代替一步步移动。
总结
Jump Point Search通过跳过不必要的节点评估，加速了路径规划过程，特别适合用于大规模、开放区域的网格地图。它在保持A*算法路径最优性的同时，大幅提高了效率。