Article

+ Updated

Game 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:

  1. 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”.

  2. After the run finishes, draw a wall and the path is recomputed immediately. Try completely enclosing G and see what happens.

  3. Drag G close to S and watch the expanded number: 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” marker

  • A 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.

  • break as 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 once

  • Space complexity O(V): the cameFrom array plus the queue

Common traps:

Problem

Cause

Fix

Duplicate cells in the queue

Marking as visited only on dequeue

Write cameFrom immediately on enqueue

The path is an L-shape, “horizontal first, then vertical”, and looks unnatural

The neighbor order is fixed

Alternate the neighbor order by (x + y) % 2, or smooth the path in post-processing

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 new-ed on every search

cameFrom is reallocated every time

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

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…