Interactive demo
Breadth-First Search
Breadth-first search (BFS) explores a grid like a wave: first every cell one step away, then two steps, then three. The first time it reaches the goal, it has found a path with the fewest steps.
Draw walls or mud on the grid and drag the start and the goal. Once a search is finished, every change is searched again right away. Paint some mud between start and goal: BFS walks straight through it, because every step counts the same.
Playback
- Expanded
- –
- Frontier (max.)
- –
- Path cost
- –
Press Play or Next Step to start the search.
Grid
Options
Legend
- Start (drag to move)
- Goal (drag to move)
- Wall
- Mud
- Frontier (open list)
- Visited (closed list)
- Expanded right now
- Path
Properties
Optimal
Conditionally
Fewest steps, which is only the cheapest path without mud and diagonal moves.
Weighted cells
No
Every step counts the same, mud is crossed like open ground.
Heuristic
No
Does not know where the goal is and spreads evenly in all directions.
Any angle
No
Moves from cell to cell, straight or diagonally.
All pathfinding algorithms compared
| Algorithm | Optimal | Weighted cells | Heuristic | Any angle |
|---|---|---|---|---|
| Breadth-First Search this page | Without mud and diagonals | No | No | No |
| Depth-First Search | No | No | No | No |
| Dijkstra's Algorithm | Yes | Yes | No | No |
| Bidirectional Search | Yes | Yes | No | No |
| Greedy Best-First Search | No | No | Yes | No |
| A* Search | With weight 1 and an admissible heuristic | Yes | Yes | No |
| Jump Point Search | Without mud | No | Yes | No |
| Theta* | No | Shortcuts over open ground only | Yes | Yes |
1. A queue
- Put the start into a queue.
- Take the oldest cell out of the queue and look at its neighbors.
- Every neighbor not seen yet remembers where it came from and joins the end of the queue.
- Repeat until the goal is taken out. Following the parents back gives the path.
2. Fewest steps
Because the queue is first in, first out, cells leave it in the order of their step count. That makes BFS optimal when every step costs the same. With mud or diagonal steps (√2), the fewest steps are not the cheapest path.
3. Where it is used
BFS is simple and needs no estimate of the distance. It finds shortest paths in unweighted graphs, such as the fewest moves in a puzzle, friends of friends in a network or the area of a flood fill in a paint program.