Finding the Way Out: BFS and A* in a Maze
The maze generation article built a maze by carving a random depth-first path through a grid of rooms. This article finds the way back out: from the entrance in the top left corner to the exit in the bottom right, using the same maze. Two classic algorithms do that job, breadth-first search and A*, and the interesting part is not so much how they work as when one of them is actually better than the other.
Breadth-first search
Breadth-first search (BFS) starts at the entrance and explores the maze in rings of increasing distance: first every cell one step away, then every cell two steps away, and so on. It keeps a frontier, a queue of cells that have been found but not explored yet, and always explores the cell that was found first.
If that sounds familiar, it is the flood fill algorithm again, with a queue instead of a stack. The fill spreads outward evenly instead of running off in long stripes, and that one change is what makes BFS find the shortest path: since cells are explored in order of their distance from the start, the first time BFS reaches the exit, it got there along the shortest possible route. To recover that route, every cell remembers which neighbor it was found from, and following those links backward from the exit leads straight back to the entrance.
A*
BFS has no idea where the exit is. It spreads in every direction equally, including away from the goal. A* fixes that by picking the next cell to explore based on two numbers:
g: the number of steps from the start to the cell, exactly as in BFS,h: an estimate of the steps still needed to reach the exit.
A* always explores the frontier cell with the lowest f = g + h next,
so it prefers cells that are both close to the start and, as far as the
estimate can tell, close to the goal. Here the estimate is the Manhattan
distance, |x - exitX| + |y - exitY|: the number of steps it would take
if there were no walls at all. Walls can only ever make the real path
longer, never shorter, so the estimate never overestimates. That property
is what guarantees that A* still finds the shortest path, just like BFS.
When several cells have the same f, this implementation picks the one
with the smaller h, the one estimated to be closer to the exit. That
small tie-breaking rule turns out to matter quite a bit, as the numbers
below show.
Implementation
#include "plot.hpp"
#include <stdint.h>
#include <stdlib.h>
// false: breadth-first search, true: A*
const bool ASTAR = false;
// Extra walls to knock down after generating the maze. 0 gives the
// perfect maze from the maze generation article (exactly one path);
// anything above 0 adds loops, so there are shorter and longer routes.
const int EXTRA_OPENINGS = 30;
const uint32_t SEED = 1;
const int MW = 19, MH = 14;
const int GW = 2 * MW + 1, GH = 2 * MH + 1;
const int CELL = 15;
enum { WALL, UNVISITED, ON_STACK, OPEN };
int grid[GH][GW];
// ---- Maze generation (same as in the maze generation article) ----
uint32_t rng = SEED;
uint32_t next_random() {
rng ^= rng << 13;
rng ^= rng >> 17;
rng ^= rng << 5;
return rng;
}
void generate_maze() {
static int sx[MW * MH], sy[MW * MH];
int top = -1;
for (int y = 0; y < GH; y++)
for (int x = 0; x < GW; x++)
grid[y][x] = (x % 2 == 1 && y % 2 == 1) ? UNVISITED : WALL;
top++; sx[top] = 1; sy[top] = 1; grid[1][1] = ON_STACK;
while (top >= 0) {
int x = sx[top], y = sy[top];
int dx[4] = {2, -2, 0, 0}, dy[4] = {0, 0, 2, -2};
int options[4], n = 0;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx > 0 && nx < GW && ny > 0 && ny < GH && grid[ny][nx] == UNVISITED)
options[n++] = k;
}
if (n == 0) {
grid[y][x] = OPEN;
top--;
if (top >= 0) grid[(y + sy[top]) / 2][(x + sx[top]) / 2] = OPEN;
continue;
}
int k = options[next_random() % n];
grid[y + dy[k] / 2][x + dx[k] / 2] = ON_STACK;
top++; sx[top] = x + dx[k]; sy[top] = y + dy[k]; grid[sy[top]][sx[top]] = ON_STACK;
}
grid[1][0] = OPEN; // entrance
grid[GH - 2][GW - 1] = OPEN; // exit
// Knock down random inner walls that sit between two rooms.
int count = EXTRA_OPENINGS;
while (count > 0) {
int x = 1 + next_random() % (GW - 2);
int y = 1 + next_random() % (GH - 2);
bool between = (x % 2 == 0 && y % 2 == 1) || (x % 2 == 1 && y % 2 == 0);
if (between && grid[y][x] == WALL) {
grid[y][x] = OPEN;
count--;
}
}
}
// ---- The search ----
const int SX = 0, SY = 1; // start: the entrance
const int TX = GW - 1, TY = GH - 2; // target: the exit
enum { NEW, FRONTIER, EXPLORED };
int state[GH][GW];
int cost[GH][GW]; // steps from the start
int parentX[GH][GW]; // where we came from, to rebuild the path
int parentY[GH][GW];
bool onPath[GH][GW];
// The frontier: cells that have been found but not explored yet.
int frontX[GW * GH];
int frontY[GW * GH];
int frontCount = 0;
int frontHead = 0; // BFS only: index of the oldest entry
bool found = false;
bool done = false;
int exploredCount = 0;
int estimate(int x, int y) {
return abs(x - TX) + abs(y - TY); // Manhattan distance to the exit
}
// The only real difference between BFS and A*: which cell to explore next.
int pick_next() {
if (!ASTAR) return frontHead++; // BFS: the one found first
// A*: lowest cost-so-far + estimated cost-to-go. On a tie, prefer the
// one that is estimated to be closer to the exit.
int best = 0;
for (int i = 1; i < frontCount; i++) {
int fi = cost[frontY[i]][frontX[i]] + estimate(frontX[i], frontY[i]);
int fb = cost[frontY[best]][frontX[best]] + estimate(frontX[best], frontY[best]);
if (fi < fb || (fi == fb && estimate(frontX[i], frontY[i]) < estimate(frontX[best], frontY[best])))
best = i;
}
return best;
}
bool frontier_empty() {
return ASTAR ? frontCount == 0 : frontHead == frontCount;
}
void add_to_frontier(int x, int y, int fromX, int fromY, int newCost) {
state[y][x] = FRONTIER;
cost[y][x] = newCost;
parentX[y][x] = fromX;
parentY[y][x] = fromY;
frontX[frontCount] = x;
frontY[frontCount] = y;
frontCount++;
}
void step() {
if (frontier_empty()) { done = true; return; }
int i = pick_next();
int x = frontX[i], y = frontY[i];
if (ASTAR) { // remove it by moving the last entry into its place
frontCount--;
frontX[i] = frontX[frontCount];
frontY[i] = frontY[frontCount];
}
state[y][x] = EXPLORED;
exploredCount++;
if (x == TX && y == TY) {
// Walk the parent links back to the start to mark the path.
while (!(x == SX && y == SY)) {
onPath[y][x] = true;
int px = parentX[y][x], py = parentY[y][x];
x = px; y = py;
}
onPath[SY][SX] = true;
found = done = true;
return;
}
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < 0 || nx >= GW || ny < 0 || ny >= GH) continue;
if (grid[ny][nx] == WALL || state[ny][nx] != NEW) continue;
add_to_frontier(nx, ny, x, y, cost[y][x] + 1);
}
}
void setup() {
PlotCanvas(640, 480);
generate_maze();
add_to_frontier(SX, SY, SX, SY, 0);
}
void frame() {
for (int n = 0; n < 2 && !done; n++) step();
PlotBackground(250, 250, 250);
int ox = (640 - GW * CELL) / 2;
int oy = 480 - GH * CELL - 8; // leave room for the status line on top
for (int y = 0; y < GH; y++) {
for (int x = 0; x < GW; x++) {
if (grid[y][x] == WALL) PlotColor(40, 44, 52); // wall
else if (onPath[y][x]) PlotColor(220, 60, 60); // the path found
else if (state[y][x] == EXPLORED || (done && state[y][x] == FRONTIER))
PlotColor(70, 170, 90); // explored
else if (state[y][x] == FRONTIER) PlotColor(220, 60, 60); // frontier
else PlotColor(30, 100, 200); // not reached
PlotFilledRectangle(ox + x * CELL, oy + y * CELL,
ox + x * CELL + CELL - 1, oy + y * CELL + CELL - 1);
}
}
if (done) {
PlotColor(40, 44, 52);
PlotText(ox, 8, found ? "%s: path %d cells, explored %d cells"
: "%s: no path, explored %d cells",
ASTAR ? "A*" : "BFS",
found ? cost[TY][TX] + 1 : exploredCount, exploredCount);
}
}
The first part is the maze generator from the previous article, unchanged, with the same seed, so this is exactly the same maze. After generating it, the program can knock down a few extra walls at random, which adds loops (more on that below).
The search itself keeps the frontier in one array. pick_next is the only
place where BFS and A* differ: BFS takes the oldest entry, A* scans the
frontier for the lowest f. Blue cells have not been reached yet, red
cells are on the frontier, and green cells have been explored. Once the
exit is reached, the path is traced back through the parent links and
shown in red, together with a status line that says how long the path is
and how many cells had to be explored to find it.
There are two switches at the top: ASTAR chooses the algorithm, and
EXTRA_OPENINGS sets how many extra walls to knock down. Try all four
combinations with "Compile & Run".
When A* helps, and when it doesn't
With the defaults, BFS on a maze with 30 extra openings, the search fans out evenly and explores almost the entire maze before it reaches the exit. Switching to A* on the same maze gives a very different picture:
maze (SEED = 1) |
shortest path | explored by BFS | explored by A* |
|---|---|---|---|
| 30 extra openings | 77 cells | 560 of 563 | 259 |
perfect (EXTRA_OPENINGS = 0) |
205 cells | 257 of 533 | 256 |
With loops, A* explores less than half as many cells as BFS for the same 77-cell path, steering toward the exit instead of searching every corner of the maze. Without the tie-breaking rule, plain A* explores 329 cells: still far better than BFS, but much less focused.
In the perfect maze from the previous article, A* explores 256 cells instead of 257: practically no difference. The reason is that there is not much to save. A perfect maze has exactly one path from the entrance to the exit, and for this maze, it is 205 cells long. Any algorithm has to explore at least those 205 cells, so BFS only wastes 52 cells on side branches to begin with. A depth-first maze like this one, with its long, winding corridors, also keeps leading A* away from the straight line it is estimating, so the estimate is not much help. Averaged over 200 different seeds, A* explores 297.1 cells in the perfect maze instead of BFS's 334.0, about 11 % fewer. With 30 extra openings, the average drops from 525.4 cells for BFS to 276.7 for A*, almost half.
In every one of those 400 runs, BFS and A* found paths of exactly the same length. A* does not find a better path, it finds the same shortest path with less work, and how much less depends entirely on how much room the maze leaves for shortcuts.
Conclusion
This finishes a small arc of articles that all turned out to be about the same thing. Flood fill visits every cell reachable from a starting point. Maze generation uses a random depth-first search to build a spanning tree. Breadth-first search is flood fill with a queue, which turns "everything reachable" into "the shortest path". And A* is breadth-first search with a sense of direction: the same frontier, just explored in a smarter order.