Pathfinding
Breadth-First Search Visualiser
A queue, so the search spreads out evenly in all directions.
Breadth-first search: a queue, so cells come out in the order they went in. That spreads outwards evenly.
- Cells expanded
- 0
- In the queue
- 1
There are 303 cells to search on this board. The gap between that and the cells expanded is what a better search order buys you — walls and mud change it, so redraw the board and watch it move.
- Start
- End
- Wall
- Mud (costs 5)
- Waiting to be expanded
- Expanded
- Route
function bfs(grid, start, end) { const queue = [start]; const cameFrom = new Map([[start, null]]); while (queue.length > 0) { const cell = queue.shift(); // the oldest waiting cell if (cell === end) return path(cameFrom, end); for (const next of neighbours(grid, cell)) { if (cameFrom.has(next)) continue; cameFrom.set(next, cell); queue.push(next); } } return null; // the end is walled off}The highlighted line is the one that produced the picture on the left.
What Breadth-First Search does
Breadth-first search explores everything one step away, then everything two steps away, and so on. Because it never looks at a cell four steps out before it has finished the cells three steps out, the first time it reaches the goal it must have done so by the shortest route.
How it works, step by step
- Put the starting cell in a queue and record that it came from nowhere.
- Take the cell from the front of the queue — the one that has been waiting longest.
- If it is the goal, follow the recorded parents back to the start to rebuild the route.
- Otherwise add every unseen neighbour to the back of the queue, recording that it was reached from this cell.
What to watch for
- The visited area grows as a diamond, not a line. Every cell at the same distance is taken before anything further out.
- Each cell is only ever added once, because a cell already in `cameFrom` is skipped. That one check is what stops the search going round in circles.
- Put mud on the board. BFS walks straight through it, because it counts steps and not cost — compare that with Dijkstra on the same board.
- Change `queue.shift()` to `stack.pop()` and you have depth-first search. Nothing else differs.
Cost
| Time | O(cells + edges) |
|---|---|
| Extra space | O(cells) for the queue |
| Finds | Fewest steps |
| Handles costs | No — every step counts as 1 |
| Waiting list | Queue (first in, first out) |
When to reach for it
For the shortest route when every step costs the same: tile maps, friend-of-a-friend hops in a social graph, the fewest moves in a puzzle. If steps have different costs, you need Dijkstra instead.