I · 寻路§ 1.3

A*：启发函数与 Open / Closed 表

Dijkstra 向四面八方均匀扩散，哪怕终点就在正前方。A* 给每个格子加上"离终点还有多远"的估计，让搜索朝着终点前进，同时仍然保证找到最便宜的路。

问题：Dijkstra 太“公平”了

上一篇的 Dijkstra 能找到代价最小的路径，但它有一个明显的浪费：它只关心“离起点多远”，完全不知道终点在哪儿。终点在正东方，它也会把西边的格子一视同仁地探索一遍。

在演示的默认地图上，Dijkstra 为了找一条 28 步的路，展开了 275 个格子，几乎是整张地图。如果一帧里有几十个单位要寻路，这个开销是承受不起的。

直觉上，搜索应该优先探索朝向终点的格子。A*（读作“A star”）就是在 Dijkstra 的基础上，加入了“离终点还有多远”的估计。

三种“最佳优先”

回顾一下：Dijkstra 用一个优先队列存放边界，每次取出某个值最小的格子。A* 的全部秘密，就在于这个“值”怎么算。

记 g(n) 为从起点到格子 n 已经花掉的代价，h(n) 为从 n 到终点估计还要花的代价：

算法	按什么排序	特点
Dijkstra	`g(n)`	只回头看，向所有方向均匀扩散，保证最优
贪心最佳优先（Greedy）	`h(n)`	只向前看，直奔终点，速度快但不保证最优
A*	`f(n) = g(n) + h(n)`	两者都看：经过 n 的整条路线估计要花多少

f(n) 的含义很直观：如果走经过 n 的路线，总共大概要花多少。每次展开 f 最小的格子，就是优先尝试“看起来总代价最低”的路线。

亲手试一试

图 1.3顶部右侧的三个按钮切换算法，左侧画笔编辑地形。格子里的数字是堆排序用的值：Dijkstra 显示 g，Greedy 显示 h，A* 显示 f = g + h。边界上数字最小的格子，就是下一个被展开的。单独打开 ↗

默认地图上有一堵开口朝向起点的 U 形墙，三种算法的表现：

算法	展开格子数	路径总代价
Dijkstra	275	28
Greedy	73	48
A*	126	28

几个值得做的小实验：

切到 greedy，单步执行。它笔直冲进 U 形墙里，撞墙之后才往外绕；又因为完全不看代价，最后直接蹚过了沼泽。
切到 a*。它同样会探进 U 形墙内部，因为从起点看过去，那里“看起来”离终点最近；但它会同时探索墙的上下两侧，最终找到和 Dijkstra 一样便宜的路线，展开的格子少了一半多。
用 erase 把 U 形墙擦掉。A* 现在几乎只展开路径上的格子；Dijkstra 依然铺满大半张图。
在 A* 模式下单步执行，留意每次被展开（墨色方框）的格子上的数字：它只增不减。这正是 A* 能保证最优的原因，后面会解释。

实现

启发函数

在 4 邻域网格上，从 a 走到 b 至少需要 |Δx| + |Δy| 步，这就是曼哈顿距离。我们的地图上每一步代价至少是 1，所以剩余代价至少是“步数 × 1”：

// 曼哈顿距离：4 邻域网格上，从 a 走到 b 至少需要的步数
inline int manhattan(Cell a, Cell b) { return std::abs(a.x - b.x) + std::abs(a.y - b.y); }

// 启发函数：对"从 c 到终点还要花多少"的估计。
// 每一步的代价至少是 1（平地），所以"至少的步数 × 1"永远不会高估真实代价。
inline int heuristic(Cell c, Cell goal) { return manhattan(c, goal) * 1; }

核心循环

和 Dijkstra 相比，只有入堆时的优先级变了：

// A*：在 Dijkstra 的基础上，按 f = g + h 排序。g 是已经花掉的代价，h 是对剩余代价的估计
inline std::vector<Cell> astarPath(const CostGrid& grid, Cell start, Cell goal) {
    if (!grid.passable(start) || !grid.passable(goal)) return {};

    std::vector<int> costSoFar(grid.size(), kUnreached);  // g
    std::vector<int> cameFrom(grid.size(), -1);

    struct Entry {
        int f;
        int g;
        int index;
    };
    // 小顶堆按 f 排序；f 相同时优先 g 大的，也就是离终点更近的
    auto worse = [](const Entry& a, const Entry& b) { return a.f != b.f ? a.f > b.f : a.g < b.g; };
    std::priority_queue<Entry, std::vector<Entry>, decltype(worse)> frontier(worse);

    int s = grid.index(start);
    costSoFar[s] = 0;
    cameFrom[s] = s;
    frontier.push({heuristic(start, goal), 0, s});

    while (!frontier.empty()) {
        Entry top = frontier.top();
        frontier.pop();
        if (top.g > costSoFar[top.index]) continue;  // 过期条目

        Cell current = grid.cellAt(top.index);
        if (current == goal) break;

        grid.forEachNeighbor(current, [&](Cell next) {
            int ni = grid.index(next);
            int g = top.g + grid.cost(next);
            if (g < costSoFar[ni]) {
                costSoFar[ni] = g;
                cameFrom[ni] = top.index;
                frontier.push({g + heuristic(next, goal), g, ni});  // 唯一的区别：排序时加上 h
            }
        });
    }
    return reconstructPath(grid, cameFrom, start, goal);
}

注意 costSoFar 存的仍然是 g，判断“是否找到更便宜的路”也仍然比较 g。h 只影响展开顺序，不影响路径代价的计算。

Open 表与 Closed 表

很多教材会用 Open 表和 Closed 表来描述 A*：

Open 表：已经发现、还没展开的格子，也就是我们的 frontier 堆。
Closed 表：已经展开过的格子。

在我们的实现中，没有显式的 Closed 表：costSoFar 加上“跳过过期条目”已经起到了同样的作用。已展开的格子不会被再次展开，除非找到了更便宜的路，而在启发函数满足下文“一致性”条件时，这不会发生。

启发函数决定了一切

A* 的正确性和效率都取决于 h。

可采纳性：不能高估

如果 h 从不高估真实的剩余代价，就称它是可采纳的（admissible），这时 A* 保证找到最优路径。

直觉是这样的：最优路线上的每个格子，f 都不超过最优代价 C。如果 h 高估了，最优路线上某个格子的 f 就可能虚高，被排到后面；而一条较差的路线反而先到达终点。

一致性：不能“跳变”

更强的条件叫一致性（consistent）：对任意相邻格子 n 和 m，有 h(n) ≤ cost(n→m) + h(m)。也就是说，走一步之后，估计值的减少量不超过这一步的实际代价。

满足一致性时，沿着任何路线 f 都只增不减，格子第一次出堆时的 g 就是最终答案，与 Dijkstra 的性质完全一样。曼哈顿距离在我们的地图上满足一致性：每走一步，曼哈顿距离最多减 1，而代价至少是 1。

h 的大小是一个旋钮

h = 0：A* 退化为 Dijkstra。最优，但最慢。
h 恰好等于真实剩余代价：A* 只展开最优路径上的格子，完美但不现实。
h 在 0 和真实值之间：越接近真实值，展开越少，仍然最优。
h 大于真实值：展开更少，但不再保证最优；h 远大于 g 时就退化成了 Greedy。

最后一条并非一无是处：很多游戏宁可要一条“差不多好”的路换取速度，这就是下一篇要讲的加权 A*。

常见网格的启发函数

移动方式	启发函数	公式（dx、dy 为坐标差的绝对值，D 为最小单步代价）
4 方向	曼哈顿距离	`D × (dx + dy)`
8 方向，斜走代价 √2	八方向距离（octile）	`D × (dx + dy) + (√2 − 2) × D × min(dx, dy)`
8 方向，斜走代价 1	切比雪夫距离	`D × max(dx, dy)`
任意方向	欧几里得距离	`D × √(dx² + dy²)`

选择的原则是：和实际的移动规则匹配。在 4 方向网格上用欧几里得距离也是可采纳的，但它比曼哈顿距离小，A* 会展开更多格子。

单步版本

演示里三种算法共用一份代码，只有排序的依据不同：

// 三种"最佳优先"搜索共用一份代码，区别只在于堆按什么排序：
//   Dijkstra：g        只看已经花掉的
//   Greedy  ：h        只看离终点还有多远
//   A*      ：g + h    两者都看
enum class SearchMode { Dijkstra, Greedy, AStar };

class BestFirstStepper {
public:
    BestFirstStepper(const CostGrid& grid, Cell start, Cell goal, SearchMode mode)
        : grid_(&grid), start_(start), goal_(goal), mode_(mode),
          costSoFar_(grid.size(), kUnreached), cameFrom_(grid.size(), -1), closed_(grid.size(), 0) {
        if (grid.passable(start) && grid.passable(goal)) {
            int s = grid.index(start);
            costSoFar_[s] = 0;
            cameFrom_[s] = s;
            push(s, 0);
        }
    }

    int priority(Cell c, int g) const {
        switch (mode_) {
            case SearchMode::Dijkstra: return g;
            case SearchMode::Greedy: return heuristic(c, goal_);
            case SearchMode::AStar: return g + heuristic(c, goal_);
        }
        return g;
    }

    bool step() {
        while (!heap_.empty()) {
            std::pop_heap(heap_.begin(), heap_.end(), Worse{});
            Entry top = heap_.back();
            heap_.pop_back();
            if (top.g > costSoFar_[top.index]) continue;

            current_ = grid_->cellAt(top.index);
            hasCurrent_ = true;
            closed_[top.index] = 1;
            ++expanded_;
            if (current_ == goal_) {
                found_ = true;
                return false;
            }
            grid_->forEachNeighbor(current_, [&](Cell next) {
                int ni = grid_->index(next);
                int g = top.g + grid_->cost(next);
                if (g < costSoFar_[ni]) {
                    costSoFar_[ni] = g;
                    cameFrom_[ni] = top.index;
                    closed_[ni] = 0;  // Greedy 可能找到已展开格子的更短路，需要重新打开
                    push(ni, g);
                }
            });
            return !done();
        }
        return false;
    }

    bool done() const { return found_ || liveFrontierSize() == 0; }
    bool found() const { return found_; }
    bool hasCurrent() const { return hasCurrent_; }
    Cell current() const { return current_; }
    int expandedCount() const { return expanded_; }
    int cost(Cell c) const { return costSoFar_[grid_->index(c)]; }
    bool closed(Cell c) const { return closed_[grid_->index(c)] != 0; }

    template <class F>
    void forEachFrontier(F&& visit) const {
        for (const Entry& e : heap_) {
            if (e.g == costSoFar_[e.index] && !closed_[e.index]) visit(grid_->cellAt(e.index));
        }
    }
    int liveFrontierSize() const {
        int n = 0;
        forEachFrontier([&](Cell) { ++n; });
        return n;
    }
    std::vector<Cell> path() const {
        return found_ ? reconstructPath(*grid_, cameFrom_, start_, goal_) : std::vector<Cell>{};
    }

private:
    struct Entry {
        int f;
        int g;
        int index;
    };
    struct Worse {
        bool operator()(const Entry& a, const Entry& b) const { return a.f != b.f ? a.f > b.f : a.g < b.g; }
    };
    void push(int index, int g) {
        heap_.push_back({priority(grid_->cellAt(index), g), g, index});
        std::push_heap(heap_.begin(), heap_.end(), Worse{});
    }

    const CostGrid* grid_;
    Cell start_, goal_;
    SearchMode mode_;
    std::vector<int> costSoFar_;
    std::vector<int> cameFrom_;
    std::vector<char> closed_;
    std::vector<Entry> heap_;
    Cell current_{};
    bool hasCurrent_ = false;
    bool found_ = false;
    int expanded_ = 0;
};

复杂度与常见陷阱

最坏情况下（例如终点不可达，或启发函数毫无帮助），A* 和 Dijkstra 一样，复杂度为 O((V + E) log V)。实际表现完全取决于启发函数的质量。

问题	原因	解决
路径不是最短的	`h` 高估了，例如地图上有代价 0.5 的道路，却仍用“步数 × 1”	`h` 乘以地图上的最小单步代价
A* 和 Dijkstra 一样慢	`h` 太小（相对代价单位），例如代价都是 10 的倍数，`h` 却按步数算	让 `h` 和代价使用同一单位
空旷地图上展开了一大片	`f` 相同时随意选择	`f` 相同时优先 `g` 大的
终点不可达时卡顿	A* 会搜遍整个连通区域才确认找不到	预先用洪水填充给区域编号，编号不同直接返回
用了 Closed 表后路径偶尔变差	启发函数不一致，已关闭的格子其实还能变便宜	使用一致的启发函数，或允许重新打开
斜走穿过墙角	8 方向移动时没有检查两侧	斜走时要求两个相邻的直走格子都可通行

在游戏中的应用

几乎所有游戏的单位寻路：从《星际争霸》到今天的商业引擎，A* 都是默认选择。Unity 的 NavMesh、Unreal 的 Recast/Detour，底层都是在导航网格上跑 A*。
非网格的图：路点图、道路网络、导航网格，A* 都适用，只需要换一种“邻居”和“启发函数”。
不只是空间寻路：GOAP（目标导向行为规划）用 A* 在“世界状态”空间里搜索动作序列，第三卷会讲到。
解谜游戏：推箱子、华容道这类谜题的自动求解，也是在状态空间上跑 A*。

练习

把 heuristic 改为返回 0，验证展开格子数和 Dijkstra 相同。再改为曼哈顿距离 × 5，观察路径和展开数的变化。
把地图改为 8 方向移动（直走代价 10、斜走代价 14），实现八方向距离的启发函数，并处理“斜走穿墙角”的问题。
实现“区域编号”预处理：用洪水填充给每个连通区域编号，让 A* 在起点和终点不连通时立即返回。
在演示中把 U 形墙改成开口朝向终点，比较三种算法的表现。