Pathfinding

Draw a maze and watch three search algorithms explore it very differently.

0 explored

Click or drag on the grid to draw walls, then run the search.

startgoalwallexploredfrontierpath

Start. The frontier holds the cells known but not yet explored.

Breadth-first

Only the frontier lines differ between the three

  1. frontier ← queue containing start
  2. while frontier is not empty:
  3. cell ← frontier.removeOldest() ▸ FIFO
  4. if cell is goal: return path
  5. for each open neighbour not seen:
  6. mark seen; frontier.add(neighbour)
  7. return no path

Breadth-first

Shortest path guaranteed

Explores in rings, one step out at a time, using a queue. On an unweighted grid the first time it reaches the goal is necessarily by a shortest route — but it looks everywhere at that distance first.

About

All three algorithms run the same loop and differ only in which cell they take from the frontier next — which is the entire lesson.