JPS 跳点搜索

问题：A* 在空地上做了太多无用功

上一篇的优化让每次展开更便宜、展开得更少，但 A* 还有一种浪费，在空旷的网格上尤其严重。

从 A 走到 B，如果中间是一片空地，代价相同的最短路径往往有几十上百条：先斜后直、先直后斜、斜直交替……A* 无法区分它们，只能把这些路径上的格子统统加入开放列表、逐个展开。这就是路径对称性（path symmetry）。

JPS（Jump Point Search，跳点搜索）由 Daniel Harabor 和 Alban Grastien 在 2011 年提出。它的思路是：既然这些路径都一样好，那就只保留一种，沿着直线一口气“跳”过去，只在可能需要拐弯的格子停下。这些格子叫做跳点。

图 1.6左：A 到 B 之间代价相同的路径有很多条，朱红色是其中一条。右：横走到 x 时，身后的墙挡住了 p → n 的斜线，n 只能经过 x 最快到达，所以 x 必须停下来，n 是 x 的强迫邻居。

准备：8 方向网格

JPS 是为代价统一的 8 方向网格设计的，和前几篇的地图有两点不同：

• 8 方向移动：除了上下左右，还可以斜着走。直走代价 10，斜走代价 14（约等于 10√2，用整数避免浮点误差）。
• 没有地形代价：每个格子要么能走，要么是墙。

斜走还有一条规则：不能切墙角。从一个格子斜向移动时，两侧相邻的直走格子都必须能通行，否则单位的模型会穿过墙角。启发函数相应地换成八方向距离：先斜走 min(dx, dy) 步，再直走剩下的。

cpp/pathfinding/jps/jps.h

// 8 方向移动：直走代价 10，斜走代价 14（≈ 10√2，用整数避免浮点误差）
constexpr int kStraight = 10;
constexpr int kDiagonal = 14;

// 八方向距离（octile）：先斜走 min(dx, dy) 步，再直走剩下的
inline int octile(Cell a, Cell b) {
    int dx = std::abs(a.x - b.x), dy = std::abs(a.y - b.y);
    return kStraight * (dx + dy) + (kDiagonal - 2 * kStraight) * std::min(dx, dy);
}

// 从 c 朝 (dx, dy) 走一步是否合法。斜走时不允许切墙角：两侧的直走格子都必须可通行
inline bool canMove(const Grid& grid, Cell c, int dx, int dy) {
    if (!grid.passable({c.x + dx, c.y + dy})) return false;
    if (dx != 0 && dy != 0) return grid.passable({c.x + dx, c.y}) && grid.passable({c.x, c.y + dy});
    return true;
}

constexpr Cell kDirs8[8] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {-1, -1}, {1, -1}};

亲手试一试

图 1.7顶部切换 a* / jps，用 wall / erase 编辑地图，拖动 S、G 移动起点终点。深色格子是被展开的节点，浅色格子是被扫描过的格子，细线连向每个节点的父节点；路径上的圆圈是跳点。单独打开 ↗

在默认地图上：

算法	展开节点数	扫描格子数	路径代价
A*	125	—	28.4
JPS	17	355	28.4

几个值得做的小实验：

1. 切到 a*，观察起点附近：A* 把左边整个房间都展开了，每个格子都连着一条短短的“父节点线”。切回 jps，同一片区域只剩几条长长的直线。
2. 单步执行 JPS。每一步都会从当前跳点出发，沿几个方向扫出很长的直线，再在少数几个格子上停下。
3. 用 wall 在空地上随手画一些零散的墙点。墙点越碎，跳点越多，JPS 的优势越小。

跳跃

JPS 的核心是一个 jump 函数：从某个格子出发，沿一个方向一直走，直到遇到以下三种情况之一：

• 撞墙或走出地图：这个方向没有跳点，返回失败。
• 到达终点：终点本身就是跳点。
• 发现强迫邻居：这个格子必须停下来，它就是跳点。

强迫邻居

什么时候必须停下？看图 1.6 的右半部分。沿着中间一行向右走，从 p 走到 x。正常情况下，x 上方的格子 n 可以直接从 p 斜着到达，不需要经过 x，所以展开 x 时不必考虑它。

但如果 p 的上方是墙，从 p 斜着去 n 就会切墙角，不允许。到达 n 的最短路线只能经过 x，于是 x 就成了一个“岔路口”：需要停下来，把向上的方向也考虑进去。n 被称为 x 的强迫邻居（forced neighbor）。

判断条件非常简单：侧面的格子能走，而它身后那一格是墙。

斜着跳

斜着跳时，每走一步，都先沿它的两个直走分量（比如向右下跳时，分别向右、向下）各跳一次。只要任何一个方向能找到跳点，当前格子本身就是跳点，因为从这里拐弯可能通向一条更好的路线。

cpp/pathfinding/jps/jps.h

// 从 c 开始沿 (dx, dy) 一直走，直到遇到一个"必须停下来考虑"的格子（跳点）。
// 找到时写入 *out 并返回 true；撞墙或走出地图返回 false。
bool jump(Cell c, int dx, int dy, Cell* out) {
    for (;;) {
        if (!grid_->passable(c)) return false;
        scanned_[grid_->index(c)] = 1;  // 仅用于统计和可视化
        ++scanCount_;
        if (c == goal_) {
            *out = c;
            return true;
        }
        if (dx != 0 && dy != 0) {
            // 斜走：每走一步，都先沿两个直走分量各跳一次，任何一个能找到跳点，c 就是跳点
            Cell unused;
            if (jump({c.x + dx, c.y}, dx, 0, &unused) || jump({c.x, c.y + dy}, 0, dy, &unused)) {
                *out = c;
                return true;
            }
            if (!canMove(*grid_, c, dx, dy)) return false;
        } else if (dx != 0) {
            // 横走：上方或下方的墙刚好在身后结束，说明从这里拐弯可能更短 —— 强迫邻居
            if ((grid_->passable({c.x, c.y - 1}) && !grid_->passable({c.x - dx, c.y - 1})) ||
                (grid_->passable({c.x, c.y + 1}) && !grid_->passable({c.x - dx, c.y + 1}))) {
                *out = c;
                return true;
            }
        } else {
            if ((grid_->passable({c.x - 1, c.y}) && !grid_->passable({c.x - 1, c.y - dy})) ||
                (grid_->passable({c.x + 1, c.y}) && !grid_->passable({c.x + 1, c.y - dy}))) {
                *out = c;
                return true;
            }
        }
        c = {c.x + dx, c.y + dy};
    }
}

关于切墙角

Harabor 和 Grastien 的原始论文允许切墙角，强迫邻居的判断条件与这里不同：在那种规则下，斜走也会产生强迫邻居。本文采用的是游戏中更常见的“不切墙角”规则，对应的判断条件参考了开源库 PathFinding.js。两种规则不能混用，否则会漏掉最优路径。

剪枝：从哪个方向来，就只看哪些方向

展开一个跳点时，也不需要尝试全部 8 个方向。从左边横着来的，没有必要再往回看；从左上斜着来的，只需要继续斜走，或者沿它的两个分量直走。

cpp/pathfinding/jps/jps.h

// 剪枝：只保留"经过 c 才更划算"的方向。起点没有来向，保留全部 8 个方向
int prunedDirections(Cell c, Cell* out) const {
    int n = 0;
    auto add = [&](int dx, int dy) {
        if (canMove(*grid_, c, dx, dy)) out[n++] = {dx, dy};
    };
    int ci = grid_->index(c);
    if (cameFrom_[ci] == ci) {
        for (Cell d : kDirs8) add(d.x, d.y);
        return n;
    }
    Cell p = grid_->cellAt(cameFrom_[ci]);
    int dx = (c.x > p.x) - (c.x < p.x);  // 来向，取符号
    int dy = (c.y > p.y) - (c.y < p.y);
    if (dx != 0 && dy != 0) {
        // 斜着来：继续斜走，以及它的两个直走分量
        add(dx, 0);
        add(0, dy);
        add(dx, dy);
    } else if (dx != 0) {
        // 横着来：继续向前，以及两侧（墙角消失后可能出现的"强迫邻居"）
        add(dx, 0);
        add(0, 1);
        add(0, -1);
        add(dx, 1);
        add(dx, -1);
    } else {
        add(0, dy);
        add(1, 0);
        add(-1, 0);
        add(1, dy);
        add(-1, dy);
    }
    return n;
}

换掉“邻居”，其余不变

有了 jump 和剪枝，JPS 的主循环和 A* 完全一样，只是后继节点不再是相邻的 8 个格子，而是沿各个方向跳到的跳点：

cpp/pathfinding/jps/jps.h

// JPS 的后继：先按"从哪个方向来"剪枝出值得探索的方向，再沿每个方向跳到下一个跳点
template <class F>
void forEachJumpPoint(Cell c, F&& visit) {
    Cell dirs[8];
    int n = prunedDirections(c, dirs);
    for (int i = 0; i < n; ++i) {
        Cell jp;
        if (jump({c.x + dirs[i].x, c.y + dirs[i].y}, dirs[i].x, dirs[i].y, &jp)) visit(jp);
    }
}

cpp/pathfinding/jps/jps.h

// 展开一个节点。搜索结束时返回 false
bool step() {
    while (!found_ && !open_.empty()) {
        std::pop_heap(open_.begin(), open_.end(), Worse{});
        Entry top = open_.back();
        open_.pop_back();
        int ci = grid_->index(top.cell);
        if (closed_[ci]) continue;  // 过期条目

        closed_[ci] = 1;
        current_ = top.cell;
        hasCurrent_ = true;
        ++expanded_;
        if (top.cell == goal_) {
            found_ = true;
            return false;
        }
        auto relax = [&](Cell next) {
            int ni = grid_->index(next);
            if (closed_[ni]) return;
            int g = top.g + octile(top.cell, next);  // 跳点可能很远，代价按八方向距离算
            if (g_[ni] < 0 || g < g_[ni]) {
                g_[ni] = g;
                cameFrom_[ni] = ci;
                push(next, g);
            }
        };
        if (mode_ == Grid8Mode::AStar) {
            for (Cell d : kDirs8) {
                if (canMove(*grid_, top.cell, d.x, d.y)) relax({top.cell.x + d.x, top.cell.y + d.y});
            }
        } else {
            forEachJumpPoint(top.cell, relax);
        }
        return true;
    }
    return false;
}

注意代价的计算：跳点可能离当前节点很远，但两者之间一定是一段纯直线或纯斜线，所以代价就是两点之间的八方向距离。

搜索得到的是跳点序列，交给单位使用前，可以把它展开成逐格的路径；如果单位本来就沿直线移动，直接使用跳点也可以。

cpp/pathfinding/jps/jps.h

// 把跳点序列展开成逐格的路径：相邻两个跳点之间一定是一段纯直线或纯斜线
inline std::vector<Cell> expandJumpPath(const std::vector<Cell>& jumpPoints) {
    std::vector<Cell> path;
    if (jumpPoints.empty()) return path;
    path.push_back(jumpPoints.front());
    for (size_t i = 1; i < jumpPoints.size(); ++i) {
        Cell a = jumpPoints[i - 1], b = jumpPoints[i];
        int dx = (b.x > a.x) - (b.x < a.x), dy = (b.y > a.y) - (b.y < a.y);
        while (!(a == b)) {
            a = {a.x + dx, a.y + dy};
            path.push_back(a);
        }
    }
    return path;
}

实测：JPS 不是总能赢

在两种 256×256 的地图上，用同一批起终点对比 A* 和 JPS：

地图	A* 展开	JPS 展开	JPS 扫描	JPS 相对 A* 的速度
房间：大片空地 + 矩形障碍	1534	63	13531	约 2~3 倍
噪声：每格 25% 概率是墙	3917	2049	13284	约 1~1.5 倍

两点值得注意：

• 在房间地图上，JPS 展开的节点少了 24 倍，速度却只快了 2~3 倍。原因在“扫描”那一列：JPS 省掉了堆操作，但跳跃时要逐格检查墙，扫描的格子数甚至远多于 A* 展开的格子。这些检查比堆操作便宜得多，但并不是免费的。
• 在零碎障碍很多的地图上，到处都是强迫邻居，跳不了多远就要停下，JPS 几乎退化成 A*。

测试环境

Apple M3，Apple clang 21，-O2，取 5 次运行中最快的一次，多次运行之间波动较大，表中给出的是范围。代码在 cpp/pathfinding/jps/jps_bench.cpp。为了与 A* 公平比较，这里的两种实现都没有使用上一篇的缓冲区复用。

常见陷阱

问题	原因	解决
路径偶尔不是最短的	强迫邻居规则与切墙角规则不匹配	两者必须配套：允许切墙角就用原论文的规则
在带地形代价的地图上结果错误	JPS 依赖“直线上每一步代价相同”的对称性	只用于代价统一的网格；有地形时用 A*
比 A* 还慢	地图障碍零碎，跳点密集	先在真实地图上测量；考虑预处理版本 JPS+
斜着跳时栈溢出	递归实现的 jump 在大地图上层数很深	直走用循环，只有斜走调用一层直走跳跃（本文写法）
单位沿跳点走时穿墙	跳点之间是直线或斜线，但单位按任意角度直线移动	跳点之间只沿 8 个方向走，或者先展开成逐格路径

在游戏中的应用

• 网格类游戏：Roguelike、战棋、塔防、俯视角射击，只要地图是代价统一的网格，JPS 都可以直接替换 A*，路径完全相同。
• JPS+：离线预计算每个格子在 8 个方向上到下一个跳点（或墙）的距离，运行时直接查表，通常还能比 JPS 再快数倍。代价是地图改变后需要重新计算受影响的部分，适合静态地图。
• 可破坏地形：地图会频繁变化时，JPS 不需要任何预处理，比 JPS+ 和下一篇的导航网格更容易维护。

练习

1. 把 canMove 改为允许切墙角，然后修改强迫邻居的判断条件，使单元测试中“JPS 代价等于 A* 代价”仍然成立。
2. 实现 JPS+ 的预处理：对每个格子、每个直走方向，记录到下一个跳点或墙的距离。
3. 运行 jps_bench.cpp，逐步提高噪声地图的墙密度（5%、10%、20%、30%），画出 JPS 与 A* 的速度比随密度的变化。
4. 给演示加一个“只显示跳点”的开关，隐藏扫描过的格子。哪种显示方式更能说明 JPS 的工作原理？

延伸阅读

• Daniel Harabor、Alban Grastien，Online Graph Pruning for Pathfinding on Grid Maps（AAAI 2011）：JPS 的原始论文
• Daniel Harabor，Jump Point Search：作者本人的博客文章，图解了跳点与强迫邻居
• Steve Rabin、Fernando Silva，JPS+: An Extreme A* Speed Optimization for Static Uniform Cost Grids，收录于 Game AI Pro 2
• PathFinding.js：包含多种切墙角规则下的 JPS 实现，可以在浏览器里直接对比