Searching grids: BFS and A*

Introduction

Mazes, game maps, robot floor plans and flood-fill tools are all grids. A grid is a graph you never have to build: each open square is a node, and its neighbours are the squares up, right, down and left. Two small arrays list the moves:

int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};   // up, right, down, left

Grids are the friendliest graphs, because you can draw them and see the search happen. The same queue from the Data Structures course now solves mazes.

How it works

Breadth-first search is worked through in the Example section below: it spreads out from the start in rings. A* and the other variations here build on it.

A*: search towards the goal

BFS spreads out in every direction, even away from the goal. A* (A-star) visits squares in order of

f = g + h

where g is the number of steps from the start (known), and h is a guess of the steps left. On a 4-direction grid the natural guess is the Manhattan distance: |r − goal_r| + |c − goal_c|, the steps needed if there were no walls.

If h never overestimates (it is admissible), the first path A* finds is a shortest one, like BFS, but it usually visits far fewer squares. Map apps and games use A* (with extra tricks) for this reason. Open the DSA Lab's Grid pathfinding tool, draw a wall, and compare how many squares BFS, DFS and A* visit.

Useful variations

• Multi-source BFS: put several start squares in the queue at distance 0. It answers "how far is every square from the nearest exit (or fire, or shop)?" in one pass.
• 0-1 BFS: when some moves are free and others cost 1, use a double-ended queue: free moves go to the front.
• Weighted squares (mud costs 5, road costs 1): use Dijkstra, or A* with costs in g.

Syntax

int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};

for (int k = 0; k < 4; k++) {
    int nr = r + dr[k], nc = c + dc[k];
    /* first check that nr and nc are on the grid */
}

Example

When every step costs the same, breadth-first search finds the shortest path. It visits squares in rings: everything 1 step from the start, then 2 steps, and so on, so the first time it reaches a square is by a shortest route. dist[r][c] = -1 marks squares not reached yet.

#include <stdio.h>

#define R 3
#define C 5

const char *grid[R] = {"S.#..", "..#.#", "#...G"};
int dist[R][C];
int queue[R * C];                                 // squares waiting, as r * C + c
int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};   // up, right, down, left

int main(void) {
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) dist[r][c] = -1;   // -1: not reached yet
    int head = 0, tail = 0;
    queue[tail++] = 0;                                 // the start, (0, 0)
    dist[0][0] = 0;
    while (head < tail) {
        int r = queue[head] / C, c = queue[head] % C;
        head++;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;    // off the grid
            if (grid[nr][nc] == '#' || dist[nr][nc] != -1) continue;  // wall, or seen
            dist[nr][nc] = dist[r][c] + 1;
            queue[tail++] = nr * C + nc;
        }
    }
    printf("steps to G: %d\n", dist[2][4]);

    // Walk back from G: each step goes to a neighbour one step closer to S.
    int r = 2, c = 4;
    printf("path back:");
    while (dist[r][c] > 0) {
        printf(" (%d,%d)", r, c);
        for (int k = 0; k < 4; k++) {
            int pr = r + dr[k], pc = c + dc[k];
            if (pr >= 0 && pr < R && pc >= 0 && pc < C && dist[pr][pc] == dist[r][c] - 1) {
                r = pr;
                c = pc;
                break;
            }
        }
    }
    printf(" (%d,%d)\n", r, c);
    return 0;
}

The path itself comes from walking back from the goal: from a square at distance d, step to any neighbour at distance d − 1, until you reach the start. (Or store each square's parent when it is first reached.)

Each square enters the queue once and checks 4 neighbours, so BFS is O(R · C) for an R × C grid.

Line by line

1. grid holds the map, and dist will hold each square's distance from the start.
2. The queue stores one number per square, r * C + c, which is easy to split back apart.
3. Every dist starts at -1. The start goes in the queue with distance 0.
4. Each square taken from the queue tries four neighbours, skipping any that are off the grid, walls or already seen.
5. A new square gets a distance one larger, and joins the queue.
6. The last loop walks back from G, stepping each time to a neighbour one step closer to the start, and prints the route.

Expected result

steps to G: 6
path back: (2,4) (2,3) (2,2) (2,1) (1,1) (0,1) (0,0)

In the real world

Robot vacuum cleaners and warehouse robots plan routes on grids, and game characters find their way with A* on grids or similar maps. The paint-bucket tool in an image editor is a flood fill, which is the same search.

Common mistakes

• Marking a square visited when it is taken out of the queue instead of when it is put in: the same square then enters the queue many times.
• Checking grid[nr][nc] before checking that nr and nc are inside the grid.
• Using DFS for a shortest path: it finds a path, often a long one.
• An A* guess that can overestimate (for example, counting diagonal moves as 2 when they cost 1): the path may no longer be shortest.

Best practices

• Check the bounds before reading a square.
• Keep the row and column deltas in two arrays, rather than writing four copies of the same code.
• Test with no route, with the start next to the goal, and with a one-square grid.

Summary

A grid is a graph you do not have to build. BFS finds shortest paths in O(R · C) when steps cost the same, and A* adds an admissible guess so that it heads for the goal.

Mark lesson complete