02 · Pathfinding
A* · Dijkstra · BFS · DFS · same grid · same start & goal · who reaches first?
Click + drag on any panel to paint walls · drag the S or G square to move start / goal · right-click drag (or click on existing walls) to erase. Any edit auto-restarts all four algorithms.
What you're watching
All four algorithms share the same world: identical grid, identical walls, identical start (S) and goal (G). When you paint a wall on any panel it appears on all four — the only thing that differs is each algorithm's exploration strategy.
Cells turn light blue as the
algorithm expands (visits) them, light red while they sit on
the frontier waiting to be expanded, and red
once the algorithm picks them as part of the final shortest path.
The two stats above each panel — expanded and
path length — let you compare efficiency after a run.
The four algorithms
BFS queue · O(V + E)
Breadth-first search expands all neighbours at distance k before expanding any at distance k + 1. On an unweighted grid this guarantees the shortest path in cell-count. Visually it spreads outward from the start in concentric "ripples" — beautiful but expensive: it explores nearly every cell at the goal's distance, regardless of direction.
DFS stack · O(V + E)
Depth-first search goes as deep as possible down one branch before backtracking. It almost never finds the shortest path on a grid — and when it does, that's a coincidence. Included as a cautionary tale: DFS is the right choice for many problems (cycle detection, topological sort, Tarjan SCC) but pathfinding is not one of them.
Dijkstra priority queue · O((V + E) log V)
Dijkstra's algorithm generalises BFS to handle weighted edges by always expanding the cell with the lowest cost-so-far. On an unweighted grid (every step costs 1) Dijkstra is BFS — the visual exploration patterns are essentially identical. The important thing is what changes when you add weights: BFS breaks, Dijkstra still works.
A* priority queue + heuristic · same upper bound
A* is Dijkstra plus a heuristic: instead of expanding by
g (cost so far), it expands by
f = g + h where h is an admissible
estimate of remaining distance to the goal. With Manhattan distance
on a 4-neighbour grid, h is admissible and tight, so A*
ploughs efficiently toward the goal — usually expanding a fraction
of the cells BFS / Dijkstra would touch. When walls force a detour
you'll see A* "spread out" temporarily as the heuristic gets
misleading, then re-focus.
f value. This
implementation breaks ties by adding a tiny multiple of the
cross-product between (start → goal) and (current → goal) to the
priority key — favouring cells that lie close to the straight line
between start and goal. The result is visibly straighter paths
without affecting correctness.
What I learned writing this
-
BFS and Dijkstra look identical on an unweighted grid because they are.
When every step costs 1, "smallest
f" reduces to "first added" — same FIFO order, same exploration. The interesting differences only show up the moment edge weights stop being equal. - A* without tie-breaking produces ugly paths. Mathematically correct, visually chaotic. The cross-product tie-breaker is one of those tiny tricks that turns a working algorithm into a presentable one.
- "Expanded count" is a fairer efficiency metric than wall-clock. Wall-clock conflates algorithm complexity with priority-queue implementation. Counting node expansions tells you how cleverly the algorithm pruned; counting time tells you how well your code plus runtime managed the data structures.
- Sharing world state between four panels was the right call. Earlier draft had each panel maintain its own walls; debugging "why do BFS and DFS disagree on the same maze?" was confusing because they weren't on the same maze. Single source of truth fixed it.