Pathfinding: BFS, DFS, Dijkstra, A*

Four ways to explore

The four algorithms follow the same scheme: keep a frontier of cells to explore, take one out, add its neighbours. They only differ in the order in which the frontier is emptied.

What to observe

• BFS spreads in concentric rings: it finds the shortest path in number of cells, but ignores costs. On the "Costly terrain" map, it walks straight through the hard terrain.
• DFS rushes ahead then backtracks. It finds a path, often a very long one: it is meant for exploring (mazes, connected components, topological sort), not optimising.
• Dijkstra grows the frontier by increasing cost: it goes around hard terrain when the detour is cheaper. Without terrain, it behaves like BFS.
• A* adds to the cost already paid a heuristic $h(n)$, an estimate of the remaining cost — here the Manhattan distance $\lvert \Delta x \rvert + \lvert \Delta y \rvert$. It explores towards the goal first and visits far fewer cells, for the same optimal path.

Why A* stays optimal

A heuristic is admissible if it never overestimates the real remaining cost. Manhattan distance is: no move costs less than 1, and at least $\lvert \Delta x \rvert + \lvert \Delta y \rvert$ moves are needed. With $h = 0$, A* becomes Dijkstra again; with an overestimating heuristic, it runs faster but may miss the best path.

The table under the figure compares the four algorithms on the current map: same cost for Dijkstra and A*, very different numbers of explored cells.