I · 寻路§ 1.1

BFS：从洪水填充开始

广度优先搜索是所有网格寻路算法的起点。理解了它，Dijkstra 和 A* 只是在它上面做加法。

问题：怪物怎么走到玩家身边？

一个俯视角游戏，地图被划分成格子，有些格子是墙。怪物站在 S，玩家站在 G，怪物需要找到一条绕开墙、步数最少的路线。

直接朝玩家的方向走是不行的：一旦中间隔着一堵墙，怪物就会卡在墙边来回蹭。我们需要一种能“看清整张地图”的方法，这就是广度优先搜索（Breadth-First Search，BFS）。

直觉：往池塘里扔一颗石子

想象在 S 点滴下一滴墨水，墨水每一秒向上下左右扩散一格，遇到墙就停下。

第 1 秒，墨水染到距离 S 为 1 的所有格子
第 2 秒，染到距离为 2 的所有格子
……

墨水第一次到达某个格子时，走的一定是最短的路——因为更短的路线会更早到达。这就是 BFS 的全部思想：按距离由近到远，一圈一圈地访问格子。

每个格子被染色时，只需要记住一件事：我是从哪个邻居扩散过来的。等墨水到达 G，沿着这些记录一路倒着走回 S，就得到了最短路径。

亲手试一试

图 1.1在格子上拖动画墙 / 擦墙；拖动 S、G 改变起点和终点。试试单步执行，观察赭黄色的边界如何推进单独打开 ↗

画面中各种颜色的含义：

图例	含义
沙色渐变	已访问的格子，颜色越深离起点越近，数字是到起点的步数
赭黄方块	边界（frontier）：已发现、等待展开的格子
墨色方框	当前正在展开的格子
朱红线	找到的最短路径

几个值得做的小实验：

单步执行几次，注意赭黄色的边界总是一层“等距线”——这就是“一圈一圈”的直观体现。
运行结束后画一堵墙，路径会立即重新计算。试着把 G 完全围住，看看会发生什么。
把 G 拖到离 S 很近的地方，观察 expanded 数字：找到终点就提前停下，可以省下大量工作。

实现

地图表示

我们用一个最简单的网格：每个格子是墙或空地。为了让算法里的数组访问更紧凑，二维坐标会被映射成一维下标 y * width + x。

// 网格上的一个格子坐标
struct Cell {
    int x = 0;
    int y = 0;

    friend bool operator==(Cell a, Cell b) = default;
};

// 最简单的二维网格地图：每个格子要么可通行，要么是墙
class Grid {
public:
    Grid(int width, int height)
        : width_(width), height_(height), walls_(static_cast<size_t>(width * height), 0) {}

    int width() const { return width_; }
    int height() const { return height_; }
    int size() const { return width_ * height_; }

    bool inBounds(Cell c) const { return c.x >= 0 && c.x < width_ && c.y >= 0 && c.y < height_; }
    bool isWall(Cell c) const { return walls_[index(c)] != 0; }
    void setWall(Cell c, bool wall) { walls_[index(c)] = wall ? 1 : 0; }
    bool passable(Cell c) const { return inBounds(c) && !isWall(c); }

    // 二维坐标 <-> 一维下标，算法里用一维数组存储状态更紧凑
    int index(Cell c) const { return c.y * width_ + c.x; }
    Cell cellAt(int i) const { return {i % width_, i / width_}; }

    // 遍历 4 邻域中可通行的格子，顺序固定为：右、下、左、上
    template <class F>
    void forEachNeighbor(Cell c, F&& visit) const {
        static constexpr std::array<Cell, 4> kDirs{{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}};
        for (Cell d : kDirs) {
            Cell next{c.x + d.x, c.y + d.y};
            if (passable(next)) visit(next);
        }
    }

private:
    int width_;
    int height_;
    std::vector<uint8_t> walls_;
};

核心循环

BFS 需要三样东西：

一个先进先出队列 frontier：存放“已发现、还没展开”的格子
一个数组 cameFrom：记录每个格子是从哪里来的，同时充当“是否访问过”的标记
一个循环：从队首取格子，把它没访问过的邻居加入队尾

// 广度优先搜索：返回从 start 到 goal 的最短路径（按步数计），不可达时返回空
inline std::vector<Cell> bfsPath(const Grid& grid, Cell start, Cell goal) {
    if (!grid.passable(start) || !grid.passable(goal)) return {};

    // cameFrom[i] 记录"我是从哪个格子走过来的"，-1 表示还没访问过
    std::vector<int> cameFrom(grid.size(), -1);
    cameFrom[grid.index(start)] = grid.index(start);

    std::deque<Cell> frontier{start};  // 先进先出队列：边界
    while (!frontier.empty()) {
        Cell current = frontier.front();
        frontier.pop_front();
        if (current == goal) break;  // 提前退出：找到终点就不必继续扩散

        grid.forEachNeighbor(current, [&](Cell next) {
            int ni = grid.index(next);
            if (cameFrom[ni] == -1) {  // 每个格子只入队一次
                cameFrom[ni] = grid.index(current);
                frontier.push_back(next);
            }
        });
    }
    return reconstructPath(grid, cameFrom, start, goal);
}

注意两处细节：

入队时就标记，而不是出队时才标记。否则同一个格子可能被多个邻居重复加入队列，最坏情况下队列会膨胀好几倍。
找到终点就 break。如果你需要的是“从起点到所有格子的距离”（比如计算移动范围），就去掉这一行，让它跑完整张图。

回溯路径

cameFrom 构成了一棵以起点为根的树。从终点出发，沿着父节点往回走到起点，再反转一下：

// 从终点沿着 cameFrom 一路回溯到起点，再反转得到正向路径
inline std::vector<Cell> reconstructPath(const Grid& grid, const std::vector<int>& cameFrom,
                                         Cell start, Cell goal) {
    if (cameFrom[grid.index(goal)] == -1) return {};  // 终点从未被访问：不可达

    std::vector<Cell> path;
    for (Cell c = goal; !(c == start); c = grid.cellAt(cameFrom[grid.index(c)])) {
        path.push_back(c);
    }
    path.push_back(start);
    std::reverse(path.begin(), path.end());
    return path;
}

单步版本

演示里用的是同一套逻辑，只是把 while 循环拆成了一次一次的 step()，以便每一帧只执行几步并把中间状态画出来。在游戏中，这种写法也很有用：把寻路分摊到多帧，避免一帧内卡顿。

// 可单步执行的 BFS：逻辑与 bfsPath 完全一致，只是把 while 循环拆成一次一次的 step()，
// 并额外记录距离，方便可视化。
class BfsStepper {
public:
    BfsStepper(const Grid& grid, Cell start, Cell goal)
        : grid_(&grid), start_(start), goal_(goal),
          cameFrom_(grid.size(), -1), distance_(grid.size(), -1) {
        if (grid.passable(start) && grid.passable(goal)) {
            cameFrom_[grid.index(start)] = grid.index(start);
            distance_[grid.index(start)] = 0;
            frontier_.push_back(start);
        }
    }

    // 执行一步：从队首取出一个格子并展开它的邻居。搜索结束时返回 false
    bool step() {
        if (done()) return false;
        current_ = frontier_.front();
        frontier_.pop_front();
        hasCurrent_ = true;
        ++expanded_;

        if (current_ == goal_) {
            found_ = true;
            return false;
        }
        int ci = grid_->index(current_);
        grid_->forEachNeighbor(current_, [&](Cell next) {
            int ni = grid_->index(next);
            if (cameFrom_[ni] == -1) {
                cameFrom_[ni] = ci;
                distance_[ni] = distance_[ci] + 1;
                frontier_.push_back(next);
            }
        });
        return !done();
    }

    bool done() const { return found_ || frontier_.empty(); }
    bool found() const { return found_; }
    bool hasCurrent() const { return hasCurrent_; }
    Cell current() const { return current_; }
    int expandedCount() const { return expanded_; }
    const std::deque<Cell>& frontier() const { return frontier_; }
    int distance(Cell c) const { return distance_[grid_->index(c)]; }  // -1 = 未访问
    std::vector<Cell> path() const {
        return found_ ? reconstructPath(*grid_, cameFrom_, start_, goal_) : std::vector<Cell>{};
    }

private:
    const Grid* grid_;
    Cell start_, goal_;
    std::vector<int> cameFrom_;
    std::vector<int> distance_;
    std::deque<Cell> frontier_;
    Cell current_{};
    bool hasCurrent_ = false;
    bool found_ = false;
    int expanded_ = 0;
};

复杂度与常见陷阱

设地图有 V 个格子、E 条相邻关系（4 邻域下 E ≤ 4V）：

时间复杂度 O(V + E)：每个格子最多入队、出队一次
空间复杂度 O(V)：cameFrom 数组加队列

常见的坑：

问题	原因	解决
队列里出现重复格子	出队时才标记已访问	入队时立即写 `cameFrom`
路径呈“先横后竖”的 L 形，看起来不自然	邻居遍历顺序固定	按 `(x + y) % 2` 交替邻居顺序，或后处理平滑路径
寻路在大地图上卡一帧	一次性跑完整个搜索	用单步版本分帧执行，或换 A*
每次寻路都 `new` 一大块数组	`cameFrom` 每次重新分配	复用缓冲区，用“代数编号”代替清零

在游戏中的应用

策略游戏的移动范围：从单位出发做 BFS，限制最大距离，就是《火焰纹章》式的可移动格子高亮。
洪水填充：画图软件的油漆桶、扫雷翻开空白区域、判断两块区域是否连通。
一对多寻路：从玩家出发做一次完整的 BFS，所有怪物都可以直接沿着距离递减的方向走过来，不必各自寻路。这个思路在后面的“流场寻路”中会发扬光大。
AI 感知：声音沿着走廊传播多远，就是一次带距离上限的 BFS。

练习

把 4 邻域改成 8 邻域（允许斜着走），路径有什么变化？斜穿墙角的问题该怎么处理？
修改 bfsPath，让它返回一张“每个格子到起点的距离”的表，并用它实现策略游戏的移动范围。
实现“多起点 BFS”：一开始把多个起点都放进队列。它可以用来解决什么问题？