游戏开发 · 文章

+ 有更新

游戏算法(寻路篇1),从洪水填充开始,了解BFS。

有更新更新于 2026年11月10日

这篇文章在发布后更新过正文内容。

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

问题:怪物怎么是走到玩家身边的?

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

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

为什么从 BFS 讲起

后面要讲的 Dijkstra、A*、流场寻路,本质上都是 BFS 的变体:换一种队列、加一个代价、加一个启发值。把 BFS 吃透,后面会轻松很多。


往水里滴下一滴墨水

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

  • 第 1 秒,墨水染到距离 S 为 1 的所有格子

  • 第 2 秒,染到距离为 2 的所有格子

  • ……

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

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

在格子上拖动画墙 / 擦墙;拖动 S、G 改变起点和终点。试试单步执行,观察赭黄色的边界如何推进

画面中各种颜色的含义:

图例

含义

沙色渐变

已访问的格子,颜色越深离起点越近,数字是到起点的步数

赭黄方块

边界(frontier):已发现、等待展开的格子

墨色方框

当前正在展开的格子

朱红线

找到的最短路径

几个值得做的小实验:

  1. 单步执行几次,注意赭黄色的边界总是一层“等距线”——这就是“一圈一圈”的直观体现。

  2. 运行结束后画一堵墙,路径会立即重新计算。试着把 G 完全围住,看看会发生什么。

  3. 把 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 求的是步数最少的路径,它默认每一步的代价都相同。如果地图上有沼泽、道路这类“走起来快慢不同”的地形,BFS 就不再正确——这正是 下一篇 Dijkstra要解决的问题。


在游戏中的应用

  • 策略游戏的移动范围:从单位出发做 BFS,限制最大距离,就是《火焰纹章》式的可移动格子高亮。

  • 洪水填充:画图软件的油漆桶、扫雷翻开空白区域、判断两块区域是否连通。

  • 一对多寻路:从玩家出发做一次完整的 BFS,所有怪物都可以直接沿着距离递减的方向走过来,不必各自寻路。这个思路在后面的“流场寻路”中会发扬光大。

  • AI 感知:声音沿着走廊传播多远,就是一次带距离上限的 BFS。


延伸阅读

  • Amit Patel,Introduction to the A* Algorithm:本系列寻路部分的灵感来源,强烈推荐

  • Introduction to Algorithms(CLRS)第 22 章:图的基本算法

版权声明

本文内容版权归作者或相关权利人所有。转载、引用或其他使用请遵循相应授权条款,并保留本文链接。

XuYi,《游戏算法(寻路篇1),从洪水填充开始,了解BFS。》,https://xuyi.dev/2026-11-10-v3x2ia

Comments

评论

正在加载评论…