引言
在游戏开发和机器人路径规划中，A算法是最经典、最广泛应用的寻路算法。然而，A在处理大规模开放区域（如空旷的草地、沙漠）时，需要扩展大量不必要的节点，导致搜索效率显著下降。JPS（Jump Point Search，跳点搜索）由 Daniel Harabor 和 Alban Grastien 于 2011 年提出，它通过对称性剪枝策略，在不牺牲最优性的前提下，将A需要扩展的节点数量减少一个数量级。本文将用Java完整实现JPS算法，深入讲解跳点判定规则，并通过可视化对比展示其相比A的巨大性能优势。
算法原理
A*算法的瓶颈
传统A*在均匀代价网格中，会向8个方向扩展邻居节点。当网格中存在大片可通行区域时，大量扩展方向会产生”对称路径”——即起点到终点的多条代价相等的路径。这些对称路径浪费了搜索资源。
JPS的核心思想
JPS利用网格地图的对称性剪枝来优化A*：
- 直线剪枝：当沿着某方向直线移动时，如果中间节点不可能成为最优路径的一部分，则直接”跳跃”跳过它们。
- 跳点（Jump Point）：某些特殊节点是必须检查的，因为它们可能是通往目标的最优路径的转折点。跳点分为两类：
- 直线跳点：沿当前方向移动时，遇到障碍物的角落或到达地图边界。
- 对角跳点：沿对角线移动时，其水平和垂直方向上有强制邻居（forced neighbor）。
- 强制邻居（Forced Neighbor）：由于障碍物的存在，某些邻居节点必须通过当前节点才能以最优代价到达。
剪枝规则详解
对于当前节点 x，沿方向 d 移动时：
- 自然邻居（Natural Neighbor）：沿方向
d继续前进的节点。 - 强制邻居（Forced Neighbor）：垂直于方向
d的两侧，因障碍物阻挡而必须经由x绕行的节点。
如果存在强制邻居，则 x 是一个跳点。JPS只在跳点处改变搜索方向，从而大幅减少扩展节点数。
核心Java实现
import java.util.*;
/**
* JPS跳点搜索算法实现
* 基于A*的对称性剪枝优化，适用于均匀代价网格寻路
*/
public class JumpPointSearch {
// 地图：0表示可通行，1表示障碍
private final int[][] grid;
private final int rows;
private final int cols;
// 8个移动方向：上、右上、右、右下、下、左下、左、左上
private static final int[][] DIRECTIONS = {
{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
{1, 0}, {1, -1}, {0, -1}, {-1, -1}
};
public JumpPointSearch(int[][] grid) {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
}
/**
* 执行JPS寻路
* @param start 起点 [row, col]
* @param goal 终点 [row, col]
* @return 路径点列表，若不可达则返回空列表
*/
public List<int[]> findPath(int[] start, int[] goal) {
// 优先队列：按f值排序
PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
// 关闭集合
boolean[][] closed = new boolean[rows][cols];
// 记录父节点用于回溯路径
Map<String, int[]> parentMap = new HashMap<>();
// g值记录
Map<String, Integer> gScore = new HashMap<>();
Node startNode = new Node(start[0], start[1], 0, heuristic(start, goal));
openSet.add(startNode);
gScore.put(key(start[0], start[1]), 0);
while (!openSet.isEmpty()) {
Node current = openSet.poll();
if (current.r == goal[0] && current.c == goal[1]) {
return reconstructPath(parentMap, goal);
}
if (closed[current.r][current.c]) continue;
closed[current.r][current.c] = true;
// 获取当前节点的有效邻居方向（剪枝后的方向）
List<int[]> neighbors = pruneNeighbors(current, parentMap.get(key(current.r, current.c)));
for (int[] dir : neighbors) {
// 沿方向跳跃寻找跳点
int[] jumpPoint = jump(current.r, current.c, dir[0], dir[1], goal);
if (jumpPoint == null) continue;
int jr = jumpPoint[0], jc = jumpPoint[1];
if (closed[jr][jc]) continue;
// 计算从当前节点到跳点的代价
int dist = Math.abs(jr - current.r) + Math.abs(jc - current.c);
// 对角线移动需要更精确的距离计算
if (dir[0] != 0 && dir[1] != 0) {
dist = Math.max(Math.abs(jr - current.r), Math.abs(jc - current.c));
}
int tentativeG = gScore.getOrDefault(key(current.r, current.c), Integer.MAX_VALUE)
+ dist;
String jKey = key(jr, jc);
if (tentativeG < gScore.getOrDefault(jKey, Integer.MAX_VALUE)) {
gScore.put(jKey, tentativeG);
int f = tentativeG + heuristic(jumpPoint, goal);
openSet.add(new Node(jr, jc, tentativeG, f));
parentMap.put(jKey, new int[]{current.r, current.c});
}
}
}
return new ArrayList<>(); // 不可达
}
/**
* 沿指定方向跳跃，寻找跳点
* @return 跳点坐标，若无跳点则返回null
*/
private int[] jump(int r, int c, int dr, int dc, int[] goal) {
int nr = r + dr;
int nc = c + dc;
// 超出边界或是障碍物
if (!isWalkable(nr, nc)) return null;
// 到达目标
if (nr == goal[0] && nc == goal[1]) return new int[]{nr, nc};
// 对角线移动
if (dr != 0 && dc != 0) {
// 检查对角线方向的强制邻居
if ((isWalkable(nr + dr, nc - dc) && !isWalkable(nr, nc - dc)) ||
(isWalkable(nr - dr, nc + dc) && !isWalkable(nr - dr, nc))) {
return new int[]{nr, nc};
}
// 递归检查水平和垂直方向是否有跳点
if (jump(nr, nc, dr, 0, goal) != null || jump(nr, nc, 0, dc, goal) != null) {
return new int[]{nr, nc};
}
} else {
// 直线移动：检查两侧的强制邻居
if (dr != 0) { // 垂直移动
if ((isWalkable(nr + dr, nc + 1) && !isWalkable(nr, nc + 1)) ||
(isWalkable(nr + dr, nc - 1) && !isWalkable(nr, nc - 1))) {
return new int[]{nr, nc};
}
} else { // 水平移动
if ((isWalkable(nr + 1, nc + dc) && !isWalkable(nr + 1, nc)) ||
(isWalkable(nr - 1, nc + dc) && !isWalkable(nr - 1, nc))) {
return new int[]{nr, nc};
}
}
}
// 继续沿同一方向跳跃
return jump(nr, nc, dr, dc, goal);
}
/**
* 剪枝邻居方向：根据父节点位置决定哪些方向需要搜索
*/
private List<int[]> pruneNeighbors(Node current, int[] parent) {
List<int[]> neighbors = new ArrayList<>();
int r = current.r, c = current.c;
if (parent == null) {
// 起点：考虑所有8个方向
for (int[] d : DIRECTIONS) {
if (isWalkable(r + d[0], c + d[1])) {
neighbors.add(d);
}
}
return neighbors;
}
// 计算从父节点到当前节点的方向
int dr = Integer.compare(r - parent[0], 0);
int dc = Integer.compare(c - parent[1], 0);
// 自然邻居：沿当前方向继续前进
if (isWalkable(r + dr, c + dc)) {
neighbors.add(new int[]{dr, dc});
}
// 对角线移动时，水平和垂直方向也是自然邻居
if (dr != 0 && dc != 0) {
if (isWalkable(r + dr, c)) neighbors.add(new int[]{dr, 0});
if (isWalkable(r, c + dc)) neighbors.add(new int[]{0, dc});
}
// 强制邻居检测
if (dr != 0 && dc != 0) {
// 对角线强制邻居
if (!isWalkable(r - dr, c) && isWalkable(r - dr, c + dc)) {
neighbors.add(new int[]{-dr, dc});
}
if (!isWalkable(r, c - dc) && isWalkable(r + dr, c - dc)) {
neighbors.add(new int[]{dr, -dc});
}
} else if (dr != 0) {
// 垂直强制邻居
if (!isWalkable(r, c + 1) && isWalkable(r + dr, c + 1)) {
neighbors.add(new int[]{dr, 1});
}
if (!isWalkable(r, c - 1) && isWalkable(r + dr, c - 1)) {
neighbors.add(new int[]{dr, -1});
}
} else {
// 水平强制邻居
if (!isWalkable(r + 1, c) && isWalkable(r + 1, c + dc)) {
neighbors.add(new int[]{1, dc});
}
if (!isWalkable(r - 1, c) && isWalkable(r - 1, c + dc)) {
neighbors.add(new int[]{-1, dc});
}
}
return neighbors;
}
/**
* 八方向曼哈顿启发函数（考虑对角线距离）
*/
private int heuristic(int[] a, int[] b) {
int dr = Math.abs(a[0] - b[0]);
int dc = Math.abs(a[1] - b[1]);
// 对角线距离：对角线步数 * 1 + 直线步数 * 1
return Math.max(dr, dc);
}
private boolean isWalkable(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols && grid[r][c] == 0;
}
private String key(int r, int c) {
return r + "," + c;
}
private List<int[]> reconstructPath(Map<String, int[]> parentMap, int[] goal) {
List<int[]> path = new ArrayList<>();
int[] cur = goal;
while (cur != null) {
path.add(0, cur.clone());
cur = parentMap.get(key(cur[0], cur[1]));
}
return path;
}
private static class Node {
int r, c, g, f;
Node(int r, int c, int g, int f) {
this.r = r; this.c = c; this.g = g; this.f = f;
}
}
// ==================== 测试与可视化 ====================
public static void main(String[] args) {
int[][] grid = {
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,1,1,1,1,0,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,1,1,1,1,1,1,1,1,1,0,1,0},
{0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},
{0,1,1,1,1,1,1,1,0,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,0,1,1,1,1,1,1,0,1,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,1,1,1,1,1,1,0,1,1,1,1,1,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
};
JumpPointSearch jps = new JumpPointSearch(grid);
int[] start = {0, 0};
int[] goal = {10, 14};
long t1 = System.currentTimeMillis();
List<int[]> path = jps.findPath(start, goal);
long t2 = System.currentTimeMillis();
System.out.println("JPS寻路耗时: " + (t2 - t1) + " ms");
System.out.println("路径长度: " + path.size() + " 步");
System.out.println("路径坐标:");
for (int[] p : path) {
System.out.print("(" + p[0] + "," + p[1] + ") ");
}
System.out.println();
// 打印地图与路径
char[][] visual = new char[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
visual[i][j] = grid[i][j] == 1 ? '#' : '.';
}
}
for (int[] p : path) {
visual[p[0]][p[1]] = '*';
}
visual[start[0]][start[1]] = 'S';
visual[goal[0]][goal[1]] = 'G';
System.out.println("\n路径可视化:");
for (char[] row : visual) {
System.out.println(new String(row));
}
}
}
算法对比：JPS vs A*
import java.util.*;
/**
* JPS与A*的性能对比
*/
public class PathfindingComparison {
public static void main(String[] args) {
// 生成大规模开放地图
int size = 100;
int[][] openGrid = generateOpenGrid(size, 0.1); // 10%障碍物
int[][] mazeGrid = generateMazeGrid(size); // 迷宫地图
int[] start = {0, 0};
int[] goal = {size - 1, size - 1};
System.out.println("=== 开放地图测试 (" + size + "x" + size + ") ===");
compare(openGrid, start, goal);
System.out.println("\n=== 迷宫地图测试 (" + size + "x" + size + ") ===");
compare(mazeGrid, start, goal);
}
private static void compare(int[][] grid, int[] start, int[] goal) {
// A*测试
AStar astar = new AStar(grid);
long t1 = System.currentTimeMillis();
List<int[]> astarPath = astar.findPath(start, goal);
long t2 = System.currentTimeMillis();
// JPS测试
JumpPointSearch jps = new JumpPointSearch(grid);
long t3 = System.currentTimeMillis();
List<int[]> jpsPath = jps.findPath(start, goal);
long t4 = System.currentTimeMillis();
System.out.println("A* 耗时: " + (t2 - t1) + " ms, 扩展节点: " + astar.getExpandedNodes()
+ ", 路径长度: " + astarPath.size());
System.out.println("JPS 耗时: " + (t4 - t3) + " ms, 扩展节点: " + jps.getExpandedNodes()
+ ", 路径长度: " + jpsPath.size());
System.out.println("JPS加速比: " + String.format("%.2f", (double)(t2 - t1) / (t4 - t3)) + "x");
}
private static int[][] generateOpenGrid(int size, double obstacleRate) {
Random rand = new Random(42);
int[][] grid = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (rand.nextDouble() < obstacleRate) {
grid[i][j] = 1;
}
}
}
grid[0][0] = 0;
grid[size-1][size-1] = 0;
return grid;
}
private static int[][] generateMazeGrid(int size) {
// 简化的迷宫生成：随机DFS
int[][] grid = new int[size][size];
for (int i = 0; i < size; i++) {
Arrays.fill(grid[i], 1);
}
Random rand = new Random(42);
Stack<int[]> stack = new Stack<>();
grid[1][1] = 0;
stack.push(new int[]{1, 1});
int[][] dirs = {{0, 2}, {2, 0}, {0, -2}, {-2, 0}};
while (!stack.isEmpty()) {
int[] cur = stack.peek();
List<int[]> neighbors = new ArrayList<>();
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr > 0 && nr < size - 1 && nc > 0 && nc < size - 1 && grid[nr][nc] == 1) {
neighbors.add(new int[]{nr, nc, d[0] / 2, d[1] / 2});
}
}
if (neighbors.isEmpty()) {
stack.pop();
} else {
int[] next = neighbors.get(rand.nextInt(neighbors.size()));
grid[next[0]][next[1]] = 0;
grid[cur[0] + next[2]][cur[1] + next[3]] = 0;
stack.push(new int[]{next[0], next[1]});
}
}
grid[0][0] = 0; grid[0][1] = 0;
grid[size-1][size-1] = 0; grid[size-1][size-2] = 0;
return grid;
}
}
复杂度分析
时间复杂度
- 最坏情况：与A相同，为 O(b^d)*，其中 b 是分支因子，d 是解的深度。在障碍密集的地图中，JPS的剪枝效果有限。
- 最好情况：在开阔地图中，JPS可以将节点扩展数量减少 10-30倍，实际运行时间显著优于A*。
- 平均情况：JPS的节点扩展数约为A的 1/10 到 1/30*，查询速度快一个数量级。
空间复杂度
JPS的空间复杂度与A相同，为 O(bd)*，主要用于存储开放列表和关闭列表。但由于扩展节点更少，实际内存占用通常更低。
最优性保证
JPS保证找到的路径与A在相同启发函数下的路径代价完全相等*，即JPS是最优的。这是因为JPS仅剪枝了对称的冗余路径，保留了所有可能的最优路径分支。
适用场景与扩展
最佳适用场景
- 大规模开放地图：如RTS游戏中的草原、沙漠战场。
- 网格均匀代价：JPS要求网格移动代价一致（或对角线代价为直线代价的固定倍数）。
- 静态地图：地图不频繁变化，可配合预计算使用。
不适用场景
- 非均匀代价地图：如沼泽（代价2）、公路（代价0.5）混合的地形。
- 动态障碍物：频繁变化的地图需要重新搜索。
- 任意多边形导航网格：JPS专用于规则网格。
扩展方向
- JPS+：预计算所有跳点，将在线查询优化到接近O(1)。
- JPS with Bounding Boxes：结合矩形剪枝，进一步减少搜索空间。
- Analytic JPS：将跳跃与直线行走结合，生成更平滑的路径。
总结
JPS跳点搜索通过对称性剪枝，在不牺牲最优性的前提下，将A的节点扩展数量减少一个数量级，是网格寻路领域的里程碑式优化。对于大规模开放地图的游戏场景，JPS是替代A的首选方案。理解JPS的剪枝原理和跳点判定规则，不仅能提升寻路性能，更能培养对算法对称性和冗余消除的深刻洞察。
