Breadth-first search
Explores the map in order of distance from the start. Cells wait in a first-in, first-out queue, so the ones found first are expanded first and the search spreads in rings: every cell one move away, then two moves away, until the goal reaches the front of the queue.
How it works- Put the start in the queue.
- Take the oldest cell. If it is the goal, stop.
- Queue each free neighbour not seen yet, noting where it came from.
- Follow those notes back from the goal to read off the path.
- Path
- Fewest moves. Every move costs 1, so the first time the goal comes out of the queue no shorter path exists.
- Cost
- Expands every cell closer to the start than the goal, in every direction.
- Best for
- Small or unweighted grids where the shortest route in moves matters.