分层寻路 HPA*

问题：地图越大，A* 越慢

A* 展开的格子数，大致与路径的长度和“绕路的程度”成正比。在一张 1024×1024 的地图上，一次横跨地图的寻路要展开几万甚至十几万个格子，耗时以毫秒计。开放世界、大型 RTS、模拟经营游戏的地图往往比这还大。

人类规划长途路线时不会这样做。从北京开车去广州，你会先决定“经过石家庄、郑州、武汉、长沙”，再分别规划每一段怎么开。HPA*（Hierarchical Path-Finding A*，Botea、Müller、Schaeffer，2004）正是把这种“先粗后细”的思路搬到了网格上。

思路：把地图切成簇

1. 分簇：把地图划分成 K×K 的正方形区域，称为簇（cluster）。
2. 找入口：相邻两个簇的公共边界上，两侧都能通行的连续区间，就是一个入口。
3. 建抽象图：在每个入口处放置过渡点。同一个入口两侧的过渡点之间连一条簇间边；同一个簇内的过渡点两两之间，算出只在簇内行走的最短代价，连一条簇内边。
4. 查询：把起点和终点临时接入抽象图，在这张小得多的图上跑 A*，最后把抽象路径的每一段换成格子路径。

前三步只与地图有关，可以预先计算。每次查询只需要做第 4 步。

图 1.10地图被分成 5×5 的簇（粗线）。圆点是过渡点，赭黄短线是跨越簇边界的簇间边；打开 graph 可以看到簇内边。单步执行：① 把 S、G 接入所在簇 ② 在抽象图上找路（朱红虚线）③ 逐段换成格子路径。编辑地形后抽象图会立即重建。单独打开 ↗

几个值得做的小实验：

1. 打开 graph，观察抽象图：整张地图 350 个格子，被压缩成了 52 个节点。
2. 单步执行，注意抽象路径（虚线）只经过过渡点，而细化后的格子路径（实线）在每个簇内部各自绕开障碍。
3. 用 wall 把某个入口堵死，这条边界上的过渡点会消失，路径改从其他入口通过。

预处理

入口与过渡点

扫描每一条簇边界，找出两侧都能通行的连续区间。入口较窄时，在中间放一个过渡点；入口较宽时（原论文的阈值是 6 格），在两端各放一个，让路径不必为了穿过一个宽敞的入口而绕到中间：

cpp/pathfinding/hpa/hpa.h

// 扫描一条簇边界：(x, y) 是边界内侧的第一个格子，(dx, dy) 沿边界前进，(ox, oy) 指向相邻簇
void scanBorder(int x, int y, int dx, int dy, int length, int ox, int oy) {
    constexpr int kWide = 6;  // 入口宽度达到它时，在两端各放一个过渡点，否则只在中间放一个
    int runStart = -1;
    for (int i = 0; i <= length; ++i) {
        Cell a{x + dx * i, y + dy * i}, b{a.x + ox, a.y + oy};
        bool open = i < length && grid_->passable(a) && grid_->passable(b);
        if (open && runStart < 0) runStart = i;
        if (!open && runStart >= 0) {
            int runEnd = i - 1;
            if (runEnd - runStart + 1 >= kWide) {
                addTransition(x + dx * runStart, y + dy * runStart, ox, oy);
                addTransition(x + dx * runEnd, y + dy * runEnd, ox, oy);
            } else {
                int mid = (runStart + runEnd) / 2;
                addTransition(x + dx * mid, y + dy * mid, ox, oy);
            }
            runStart = -1;
        }
    }
}
// 一个过渡点 = 边界两侧各一个节点 + 两条方向相反的簇间边（代价 = 进入对方格子的代价）
void addTransition(int x, int y, int ox, int oy) {
    Cell a{x, y}, b{x + ox, y + oy};
    int na = nodeFor(a), nb = nodeFor(b);
    nodes_[na].edges.push_back({nb, grid_->cost(b), -1});
    nodes_[nb].edges.push_back({na, grid_->cost(a), -1});
}

因为代价定义在“进入格子”上，从 a 走到 b 和从 b 走到 a 的代价可能不同，所以每个过渡点都对应两条方向相反、代价各自计算的边。

簇内边

对每个过渡点，在它所在的簇里做一次限定范围的 Dijkstra，就得到了它到同簇所有其他过渡点的代价：

cpp/pathfinding/hpa/hpa.h

// 限定在一个矩形区域（簇）内的 Dijkstra。
// reverse = true 时沿反方向搜索：得到的是"从各个格子走到 source"的代价（地形代价不对称，进入格子才付费）
struct Rect {
    int x0, y0, x1, y1;  // 包含 [x0, x1) × [y0, y1)
    bool contains(Cell c) const { return c.x >= x0 && c.x < x1 && c.y >= y0 && c.y < y1; }
    int width() const { return x1 - x0; }
    int index(Cell c) const { return (c.y - y0) * width() + (c.x - x0); }
    Cell cellAt(int i) const { return {x0 + i % width(), y0 + i / width()}; }
    int size() const { return width() * (y1 - y0); }
};

struct LocalSearch {
    std::vector<int> cost;    // 按 Rect::index 存储
    std::vector<int> parent;  // 正向搜索时的来路（局部下标），-1 表示无
};

inline LocalSearch boundedDijkstra(const CostGrid& grid, Rect r, Cell source, bool reverse = false) {
    LocalSearch s{std::vector<int>(r.size(), kHpaInf), std::vector<int>(r.size(), -1)};
    if (!r.contains(source) || !grid.passable(source)) return s;
    using Entry = std::pair<int, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> open;
    s.cost[r.index(source)] = 0;
    open.push({0, r.index(source)});
    while (!open.empty()) {
        auto [c, i] = open.top();
        open.pop();
        if (c > s.cost[i]) continue;
        Cell cur = r.cellAt(i);
        grid.forEachNeighbor(cur, [&](Cell n) {
            if (!r.contains(n)) return;
            int ni = r.index(n);
            int nc = c + (reverse ? grid.cost(cur) : grid.cost(n));
            if (nc < s.cost[ni]) {
                s.cost[ni] = nc;
                s.parent[ni] = i;
                open.push({nc, ni});
            }
        });
    }
    return s;
}

cpp/pathfinding/hpa/hpa.h

// 预处理：找出所有入口，放置过渡点，再计算每个簇内过渡点之间的代价，并缓存对应的格子路径
void build(const CostGrid& grid, int clusterSize) {
    grid_ = &grid;
    k_ = clusterSize;
    cols_ = (grid.width() + k_ - 1) / k_;
    rows_ = (grid.height() + k_ - 1) / k_;
    nodes_.clear();
    paths_.clear();
    nodeAt_.assign(grid.size(), -1);
    byCluster_.assign(cols_ * rows_, {});

    // 1. 入口：相邻两个簇的公共边界上，两侧都能走的连续区间
    for (int cy = 0; cy < rows_; ++cy) {
        for (int cx = 0; cx < cols_; ++cx) {
            Rect r = clusterRect(cx, cy);
            if (r.x1 < grid.width()) scanBorder(r.x1 - 1, r.y0, 0, 1, r.y1 - r.y0, 1, 0);   // 右边界
            if (r.y1 < grid.height()) scanBorder(r.x0, r.y1 - 1, 1, 0, r.x1 - r.x0, 0, 1);  // 下边界
        }
    }
    // 2. 簇内边：同一个簇里的过渡点两两之间，只在簇内搜索的最短代价和路径
    for (int id = 0; id < static_cast<int>(nodes_.size()); ++id) {
        Rect r = clusterRectOf(nodes_[id].cluster);
        LocalSearch s = boundedDijkstra(grid, r, nodes_[id].cell);
        for (int other : byCluster_[nodes_[id].cluster]) {  // 只和同一个簇里的节点比较
            if (other == id) continue;
            int c = s.cost[r.index(nodes_[other].cell)];
            if (c == kHpaInf) continue;
            paths_.push_back(tracePath(r, s, nodes_[other].cell));
            nodes_[id].edges.push_back({other, c, static_cast<int>(paths_.size()) - 1});
        }
    }
}

注意第二个高亮行：在计算簇内边的同时，把对应的格子路径也缓存下来。这样查询时，每一段抽象路径都可以直接换成现成的格子路径，不需要再搜索。

一个让预处理慢了 30 倍的错误

最初的实现里，计算簇内边时遍历了整张图的所有节点，再跳过不在同一个簇里的。在 1024×1024 的地图上，抽象图有十几万个节点，这个两两比较让预处理花了 16.8 秒。改成只遍历同一个簇里的节点后，降到了 0.5 秒。分层结构的意义就在于“局部”，任何一步退化成全局遍历，优势就没了。

查询

cpp/pathfinding/hpa/hpa.h

// 查询：把起点和终点临时接入抽象图，在抽象图上跑 A*，再把每一段换成格子路径
std::vector<Cell> findPath(Cell start, Cell goal, HpaStats* stats = nullptr,
                           std::vector<Cell>* abstractPath = nullptr) const {
    HpaStats st;
    if (!grid_->passable(start) || !grid_->passable(goal)) return {};

    const int n = static_cast<int>(nodes_.size());
    const int S = n, G = n + 1;  // 起点、终点的临时编号
    auto cellOf = [&](int id) { return id == S ? start : id == G ? goal : nodes_[id].cell; };

    // 1. 插入：起点到所在簇各过渡点的代价（正向搜索），各过渡点到终点的代价（反向搜索）
    const int cs = clusterOf(start), cg = clusterOf(goal);
    Rect rs = clusterRectOf(cs), rg = clusterRectOf(cg);
    LocalSearch fromStart = boundedDijkstra(*grid_, rs, start);
    LocalSearch toGoal = boundedDijkstra(*grid_, rg, goal, /*reverse=*/true);
    st.cellsSearched += rs.size() + rg.size();

    // 2. 抽象图上的 A*，启发函数为曼哈顿距离
    std::vector<int> g(n + 2, kHpaInf), from(n + 2, -1);
    std::vector<char> closed(n + 2, 0);
    using Entry = std::pair<int, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> open;
    auto h = [&](int id) { Cell c = cellOf(id); return std::abs(c.x - goal.x) + std::abs(c.y - goal.y); };
    g[S] = 0;
    open.push({h(S), S});
    while (!open.empty()) {
        int u = open.top().second;
        open.pop();
        if (closed[u]) continue;
        closed[u] = 1;
        ++st.abstractExpanded;
        if (u == G) break;
        auto relax = [&](int v, int c) {
            if (c != kHpaInf && !closed[v] && g[u] + c < g[v]) {
                g[v] = g[u] + c;
                from[v] = u;
                open.push({g[v] + h(v), v});
            }
        };
        if (u == S) {
            for (int id : clusterNodes(cs)) relax(id, fromStart.cost[rs.index(nodes_[id].cell)]);
            if (cs == cg) relax(G, fromStart.cost[rs.index(goal)]);  // 同一个簇：也可以直接走过去
        } else {
            for (const Edge& e : nodes_[u].edges) relax(e.to, e.cost);
            if (nodes_[u].cluster == cg) relax(G, toGoal.cost[rg.index(nodes_[u].cell)]);
        }
    }
    if (stats) *stats = st;
    if (g[G] == kHpaInf) return {};

    std::vector<int> ids;
    for (int v = G; v != -1; v = from[v]) ids.push_back(v);
    std::reverse(ids.begin(), ids.end());
    if (abstractPath) {
        abstractPath->clear();
        for (int id : ids) abstractPath->push_back(cellOf(id));
    }

    // 3. 拼接：每一段都已经有现成的格子路径，不需要再搜索
    std::vector<Cell> result{start};
    for (size_t i = 1; i < ids.size(); ++i) {
        int u = ids[i - 1], v = ids[i];
        std::vector<Cell> seg;
        if (u == S) {
            seg = tracePath(rs, fromStart, cellOf(v));  // 起点所在簇的正向搜索树
        } else if (v == G) {
            // 反向搜索树里，每个格子的 parent 是"离终点更近的下一步"
            for (int k = rg.index(cellOf(u)); k != -1; k = toGoal.parent[k]) seg.push_back(rg.cellAt(k));
        } else {
            const Edge& e = edgeBetween(u, v);
            seg = e.path >= 0 ? paths_[e.path] : std::vector<Cell>{cellOf(u), cellOf(v)};
        }
        result.insert(result.end(), seg.begin() + 1, seg.end());
    }
    return result;
}

查询分三步：

1. 插入：起点和终点通常不在过渡点上。在起点所在的簇里正向搜索一次，得到起点到各过渡点的代价；在终点所在的簇里反向搜索一次，得到各过渡点到终点的代价。如果起点和终点在同一个簇，还要考虑直接走过去。
2. 抽象搜索：在抽象图上跑 A*。抽象图的节点数远少于格子数，搜索很快。
3. 拼接：抽象路径的每一段都已经有现成的格子路径（预处理缓存的，或插入时搜索树里的），直接首尾相连。

不必一次细化完

单位在一开始只需要知道前几步怎么走。很多实现只细化抽象路径的第一段，单位边走边细化后面的部分。如果中途目标改变，后面那些还没细化的段就省下来了。

实测：快多少，差多少？

HPA* 找到的路径不一定是最短的：路径被强制经过过渡点，而过渡点的位置是预先固定的。下面是在两种地图上，用 300 组随机起终点和 1.4 的 A*（Pathfinder）对比：

地图	方法	预处理	每次查询	路径比最优多出（平均 / 最坏）
256×256 房间	A*	—	67 μs	—
	HPA*，K = 16	9 ms	24 μs	1.6% / 30%
1024×1024 房间	A*	—	1757 μs	—
	HPA*，K = 16	140 ms	206 μs	1.0% / 13%
	HPA*，K = 32	212 ms	138 μs	1.9% / 50%
1024×1024 噪声	A*	—	11.6 ms	—
	HPA*，K = 32	1.6 s	1.4 ms	2.2% / 9%

“房间”地图是大片空地加随机矩形障碍，“噪声”地图是每格 20% 概率是墙、另有森林和沼泽。

几点观察：

• 地图越大，HPA 的优势越明显*：256×256 时快 2.8 倍，1024×1024 时快 8~13 倍。A* 的代价随地图增大而增长，HPA* 的抽象图则小得多。
• 簇的大小是一个权衡：簇越大，抽象图越小，但插入起终点时要搜索的格子更多（K² 个），路径也被迫经过更少的过渡点，质量下降。K = 16 左右通常是不错的起点。
• 零碎障碍多的地图上入口也多：噪声地图的抽象图节点数是房间地图的 3 倍以上，预处理也慢得多。

测试环境

Apple M3，Apple clang 21，-O2。代码在 cpp/pathfinding/hpa/hpa_bench.cpp，可以传入地图边长，例如 ./hpa_bench 1024。

常见陷阱

问题	原因	解决
短距离寻路明显绕远	起点和终点离得很近，却被迫经过远处的过渡点	起终点在同一个或相邻的簇时，直接用 A*（单元测试中，代价小于 20 的短路径平均多走 16%，最坏多走 3.7 倍）
路径在簇边界处有不自然的折角	路径必须经过过渡点	对结果做 1.4 的路径平滑
修改一个格子就要重建整张抽象图	预处理是全局的	只重建该格子所在的簇，以及与它相邻的边界上的入口
内存占用很大	缓存了所有簇内边的格子路径	不缓存，查询时在簇内重新搜索；或只缓存常用的边
地图特别大时抽象图仍然太大	只有两层	再往上叠一层：把簇组合成更大的簇，在更高层的抽象图上搜索

在游戏中的应用

• 大型开放世界：先在区域之间规划路线，只为玩家附近的区域加载和细化格子路径。
• RTS 的流场 + 分层：上一篇提到的《最高指挥官 2》，就是先在分块之间寻路，再只为经过的分块计算流场。
• 导航网格的分层：Detour 等库把导航网格分成若干块（tile），在块之间也有一层抽象，原理相同。

卷一小结：该用哪种寻路算法？

寻路卷到这里就结束了。最后用一张表回顾这八章：

场景	推荐	章节
代价统一的小网格，或者需要“到所有格子的距离”	BFS	1.1
有地形代价，或需要一对多的距离表	Dijkstra / Dijkstra 地图	1.2
一般的点到点寻路	A*	1.3
同时寻路的单位很多，可以接受稍差的路径	加权 A* + 缓冲区复用	1.4
代价统一的 8 方向网格，空地较多	JPS	1.5
3D 场景、任意形状的可行走区域	导航网格 + 漏斗算法	1.6
大量单位去同一个目的地	流场	1.7
超大地图上的长距离寻路	HPA*（或导航网格分块）	1.8

它们并不互相排斥。一个真实的游戏往往会组合使用：导航网格负责全局路线，流场驱动大批单位，A* 处理少量特殊单位，再加上局部避让防止单位互相碰撞。局部避让与转向，会在第三卷“游戏 AI”中讲到。

练习

1. 在 findPath 中加入短距离的回退：起点和终点所在的簇相同或相邻时，直接调用 A*。重新运行单元测试，比较“代价小于 20”那一组的平均多走比例。
2. 实现局部更新：修改一个格子后，只重建它所在的簇、以及相邻簇共享边界上的入口。
3. 把 kWide 从 6 改为 3 和 12，用 hpa_bench.cpp 比较抽象图大小、查询速度和路径质量。
4. 给 HPA* 加上第二层抽象：把 4×4 个簇组成一个大簇，在大簇之间先搜索一次。

延伸阅读

• Adi Botea、Martin Müller、Jonathan Schaeffer，Near Optimal Hierarchical Path-Finding（Journal of Game Development，2004）：HPA* 的原始论文
• Nathan Sturtevant，Memory-Efficient Abstractions for Pathfinding（AIIDE 2007）：《龙腾世纪：起源》使用的分层寻路方案
• Amit Patel，Amit’s A* Pages: Map Representations：网格、路点图、导航网格与分层表示的对比