游戏开发 · 文章
+ 有更新游戏算法(寻路篇1),从洪水填充开始,了解BFS。
这篇文章在发布后更新过正文内容。
广度优先搜索是所有网格寻路算法的起点。理解了它,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):已发现、等待展开的格子 |
墨色方框 | 当前正在展开的格子 |
朱红线 | 找到的最短路径 |
几个值得做的小实验:
单步执行几次,注意赭黄色的边界总是一层“等距线”——这就是“一圈一圈”的直观体现。
运行结束后画一堵墙,路径会立即重新计算。试着把 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数组加队列
常见的坑:
问题 | 原因 | 解决 |
|---|---|---|
队列里出现重复格子 | 出队时才标记已访问 | 入队时立即写 |
路径呈“先横后竖”的 L 形,看起来不自然 | 邻居遍历顺序固定 | 按 |
寻路在大地图上卡一帧 | 一次性跑完整个搜索 | 用单步版本分帧执行,或换 A* |
每次寻路都 |
| 复用缓冲区,用“代数编号”代替清零 |
BFS 的局限
BFS 求的是步数最少的路径,它默认每一步的代价都相同。如果地图上有沼泽、道路这类“走起来快慢不同”的地形,BFS 就不再正确——这正是 下一篇 Dijkstra要解决的问题。
在游戏中的应用
策略游戏的移动范围:从单位出发做 BFS,限制最大距离,就是《火焰纹章》式的可移动格子高亮。
洪水填充:画图软件的油漆桶、扫雷翻开空白区域、判断两块区域是否连通。
一对多寻路:从玩家出发做一次完整的 BFS,所有怪物都可以直接沿着距离递减的方向走过来,不必各自寻路。这个思路在后面的“流场寻路”中会发扬光大。
AI 感知:声音沿着走廊传播多远,就是一次带距离上限的 BFS。
延伸阅读
Amit Patel,Introduction to the A* Algorithm:本系列寻路部分的灵感来源,强烈推荐
Introduction to Algorithms(CLRS)第 22 章:图的基本算法
Newsletter
订阅更新
新文章发布时收到邮件通知,随时可退订。
版权声明
本文内容版权归作者或相关权利人所有。转载、引用或其他使用请遵循相应授权条款,并保留本文链接。
XuYi,《游戏算法(寻路篇1),从洪水填充开始,了解BFS。》,https://xuyi.dev/2026-11-10-v3x2ia
Comments
评论
正在加载评论…