Article
+ UpdatedGame Algorithms (Pathfinding Part 1) - Starting from Flood Fill to Understand BFS
Breadth-first search is the starting point of every grid pathfinding algorithm. Once you understand it, Dijkstra and A* are just additions on top.
The problem: how does a monster get to the player?
A top-down game, with the map divided into cells and some cells being walls. A monster stands at S, the player stands at G, and the monster needs to find a route around the walls with the fewest steps.
Walking straight toward the player doesn't work: as soon as a wall is in between, the monster gets stuck rubbing back and forth against it. We need a method that can “see the whole map”, and that is breadth-first search (BFS).
Why start with BFS
Dijkstra, A*, and flow-field pathfinding, which come later, are essentially all variants of BFS: swap the queue, add a cost, add a heuristic. Once you've fully digested BFS, everything after it gets much easier.
Drop a drop of ink into water
Imagine dropping a drop of ink at point S. Every second the ink spreads one cell up, down, left and right, and stops when it hits a wall.
At second 1, the ink reaches every cell at distance 1 from S
At second 2, it reaches every cell at distance 2
...
The first time the ink reaches a cell, it must have taken the shortest route, because a shorter route would have arrived earlier. That is the entire idea of BFS: visit cells ring by ring, from near to far.
When each cell gets colored, it only needs to remember one thing: which neighbor the ink came from. When the ink reaches G, walk backward along these records all the way to S and you have the shortest path.
Drag on the cells to draw / erase walls; drag S and G to move the start and goal. Try stepping through one step at a time and watch how the ochre frontier advances
What the colors in the picture mean:
Legend | Meaning |
|---|---|
Sand gradient | Visited cells. The darker the color, the closer to the start; the number is the step count from the start |
Ochre square | The frontier: cells that have been discovered and are waiting to be expanded |
Ink-colored box | The cell currently being expanded |
Vermilion line | The shortest path found |
A few small experiments worth trying:
Step a few times and notice that the ochre frontier is always a layer of “equidistant line”. That's the intuitive picture of “ring by ring”.
After the run finishes, draw a wall and the path is recomputed immediately. Try completely enclosing G and see what happens.
Drag G close to S and watch the
expandednumber: stopping as soon as the goal is found saves a lot of work.
Implementation
Map representation
We use the simplest possible grid: each cell is either a wall or open ground. To keep array access in the algorithm compact, 2D coordinates are mapped to a 1D index y * width + x.
// A cell coordinate on the grid
struct Cell {
int x = 0;
int y = 0;
friend bool operator==(Cell a, Cell b) = default;
};
// The simplest 2D grid map: every cell is either passable or a wall
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); }
// 2D coordinates <-> 1D index. Storing state in 1D arrays is more compact inside the algorithm
int index(Cell c) const { return c.y * width_ + c.x; }
Cell cellAt(int i) const { return {i % width_, i / width_}; }
// Visit the passable cells in the 4-neighborhood, in a fixed order: right, down, left, up
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_;
};The core loop
BFS needs three things:
A first-in, first-out queue
frontier: holds the cells that are “discovered but not yet expanded”An array
cameFrom: records where each cell was reached from, and doubles as the “has it been visited” markerA loop: take a cell from the front of the queue and add its unvisited neighbors to the back
// Breadth-first search: returns the shortest path (by step count) from start to goal, or empty if unreachable
inline std::vector<Cell> bfsPath(const Grid& grid, Cell start, Cell goal) {
if (!grid.passable(start) || !grid.passable(goal)) return {};
// cameFrom[i] records "which cell I walked here from"; -1 means not visited yet
std::vector<int> cameFrom(grid.size(), -1);
cameFrom[grid.index(start)] = grid.index(start);
std::deque<Cell> frontier{start}; // first-in, first-out queue: the frontier
while (!frontier.empty()) {
Cell current = frontier.front();
frontier.pop_front();
if (current == goal) break; // early exit: once the goal is found there's no need to keep spreading
grid.forEachNeighbor(current, [&](Cell next) {
int ni = grid.index(next);
if (cameFrom[ni] == -1) { // every cell is enqueued only once
cameFrom[ni] = grid.index(current);
frontier.push_back(next);
}
});
}
return reconstructPath(grid, cameFrom, start, goal);
}Two details to note:
Mark on enqueue, not on dequeue. Otherwise the same cell can be added to the queue by several neighbors, and in the worst case the queue balloons several times over.
breakas soon as the goal is found. If what you need is “the distance from the start to every cell” (for example, computing movement range), remove this line and let it run over the whole map.
Reconstructing the path
cameFrom forms a tree rooted at the start. Starting from the goal, follow the parent pointers back to the start, then reverse:
// Walk back along cameFrom from the goal to the start, then reverse to get the forward path
inline std::vector<Cell> reconstructPath(const Grid& grid, const std::vector<int>& cameFrom,
Cell start, Cell goal) {
if (cameFrom[grid.index(goal)] == -1) return {}; // the goal was never visited: unreachable
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;
}The stepping version
The demo uses the same logic, except the while loop is split into individual step() calls, so that each frame can run just a few steps and draw the intermediate state. In a game, this style is useful too: spread pathfinding across multiple frames to avoid a hitch within a single frame.
// A BFS you can step through: the logic is identical to bfsPath, except the while loop is split into individual step() calls,
// and distances are recorded as well to make visualization easier.
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);
}
}
// Run one step: take a cell from the front of the queue and expand its neighbors. Returns false when the search ends
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 = not visited
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;
};Complexity and common pitfalls
Suppose the map has V cells and E adjacency relations (with a 4-neighborhood, E ≤ 4V):
Time complexity
O(V + E): every cell is enqueued and dequeued at most onceSpace complexity
O(V): thecameFromarray plus the queue
Common traps:
Problem | Cause | Fix |
|---|---|---|
Duplicate cells in the queue | Marking as visited only on dequeue | Write |
The path is an L-shape, “horizontal first, then vertical”, and looks unnatural | The neighbor order is fixed | Alternate the neighbor order by |
Pathfinding hitches a frame on a large map | The whole search runs in one go | Use the stepping version to spread it across frames, or switch to A* |
A big array is |
| Reuse the buffer, and use a “generation number” instead of zeroing it |
The limits of BFS
BFS finds the path with the fewest steps, and assumes every step costs the same. If the map has terrain like swamps and roads where walking speed differs, BFS is no longer correct. That is exactly the problem the next article, on Dijkstra, solves.
Applications in games
Movement range in strategy games: run a BFS from a unit with a maximum distance limit, and you get the highlighted movable cells of a Fire Emblem-style game.
Flood fill: the paint bucket in drawing programs, revealing blank areas in Minesweeper, and checking whether two regions are connected.
One-to-many pathfinding: run one full BFS from the player, and every monster can simply walk in the direction of decreasing distance, with no need to pathfind individually. This idea gets developed further in “flow-field pathfinding” later.
AI perception: how far a sound travels along a corridor is just a BFS with a distance limit.
Further reading
Amit Patel, Introduction to the A* Algorithm: the inspiration for the pathfinding part of this series, highly recommended
Introduction to Algorithms (CLRS), Chapter 22: Elementary Graph Algorithms
Newsletter
Subscribe
Get an email when a new article is published. Unsubscribe anytime.
Copyright
Copyright of this article belongs to its author or rights holder. When reposting or quoting, please follow the applicable license terms and keep the link to this article.
XuYi, “Game Algorithms (Pathfinding Part 1) - Starting from Flood Fill to Understand BFS”, https://xuyi.dev/en/2026-11-10-v3x2ia
Comments
Comments
Loading comments…