Pathfinding Visualizer

About

Every search algorithm on this page answers the same question: which cell should I look at next? They all keep a frontier of cells they know how to reach, repeatedly take one out, and add its neighbours. The only real difference between them is the rule for choosing which frontier cell comes out first. That one rule decides whether the search is fast, whether the route is optimal, and whether weighted terrain is understood at all.

Draw walls, drop mud (entering a mud cell costs 5 instead of 1), move the start and goal, then run. When a run finishes the board stays live: drag the goal around and the result recomputes instantly, which is the quickest way to build intuition for how each rule behaves.

Turn on Race to run two algorithms on the same board side by side. They advance one expansion per tick together, so whichever finishes first genuinely examined fewer cells. The stats bar also reports whether each route is optimal, by comparing its cost with an exact Dijkstra run on the same board.

For the theory behind these ideas, read the Search and Optimization lesson. The Travelling Salesman lab covers the other half of the story: problems where the search space is far too big for exhaustive search.

How it works

The board is a graph. Each open cell is a node, and each move to a neighbouring open cell is an edge. Moving into a normal cell costs 1, moving into mud costs 5, and with diagonals enabled a diagonal move costs √2 times the cell's cost. Diagonals cannot cut past the corner of a wall.

Three numbers per cell

g(n) is the cheapest known cost from the start to n. h(n) is a heuristic guess of the remaining cost from n to the goal. f(n) = g(n) + w·h(n) is A*'s estimate of the total cost of the best route throughn. Hover over any cell to see its numbers.

The rule that picks the next cell

• BFS uses a queue: first discovered, first expanded. It spreads in rings of equal step count and ignores mud.
• DFS uses a stack: it dives down one corridor until it hits a dead end, then backtracks. Its routes are usually terrible.
• Dijkstra picks the smallest g. It spreads in rings of equal cost, so it walks around mud when that is cheaper.
• Greedy best-first picks the smallest h. It races towards the goal and gets trapped behind walls.
• A* picks the smallest g + h: Dijkstra's care about cost so far, plus greedy's sense of direction.
• Bidirectional Dijkstra grows two cost rings, one from each end, and stops once no route through the frontiers can beat the best meeting point found. Two small circles cover less area than one big one.

Why colour by g-cost

Switch the colour mode to g-cost with V. For Dijkstra the colours form clean contour lines of equal travel cost, bending around mud. For A* the same contours appear, but only in the narrow band the heuristic allowed the search to explore.

Algorithms compared

Dijkstra published his shortest-path algorithm in 1959. A* came from Peter Hart, Nils Nilsson and Bertram Raphael at SRI in 1968, built to plan routes for Shakey, one of the first mobile robots. Their key result: if h never overestimates the true remaining cost, the first time A* expands the goal it has found an optimal route.

BFS is often called "optimal" in textbooks, and it is, for unweighted graphs. Add mud and it will happily plough straight through a swamp because it counts steps, not cost. Try it: the stats bar will flag the route as more expensive than optimal.

DFS is included because it is the natural first idea and it teaches by failure. It is complete on a finite grid, it uses very little memory, and its routes are often absurd. Real systems use DFS for exhaustive tasks such as maze generation (the randomized DFS maze here) and backtracking search, not for shortest paths.

Heuristics

A heuristic is an educated guess of the cost still to go. It is what turns blind search into informed search, and its quality decides how much work A* has to do.

Admissible: never overestimate

A heuristic is admissible if h(n) is never more than the true remaining cost. Admissibility is what lets A* stop at the first goal it expands: no unexplored route can be cheaper than its optimistic estimate. h = 0 is admissible and turns A* back into Dijkstra. The closer an admissible h is to the truth, the fewer cells A* expands.

Consistent: estimates that agree with each step

A stronger property, consistency, requires h(n) ≤ step(n, m) + h(m) for every move. With a consistent heuristic A* never needs to re-open a cell it already expanded. All three distances here are consistent for the moves they are built for. Mud keeps them admissible because it only makes real costs larger.

Weighted A*: trade optimality for speed

Multiply the heuristic by w > 1 and A* becomes greedier. It expands fewer cells, and its route is guaranteed to cost at most w times the optimum. At w = 1 you get classic A*; as w grows it behaves more and more like greedy best-first. Game engines and robot planners use this dial when an answer now beats a perfect answer later.

Try this

1. 01The swamp testGenerate mud patches, then race BFS against Dijkstra. BFS finds a route with fewer steps; Dijkstra finds the cheaper one. Compare the path cost numbers.
2. 02Trap the greedy searchClear the board and draw a U-shaped wall around the goal, open away from the start. Greedy best-first dives into the U and has to crawl out; A* notices sooner.
3. 03Break admissibilityEnable diagonals, pick Manhattan and run A* on random walls. Then switch to octile. Does the Manhattan route cost more? How many fewer cells did it expand?
4. 04Turn the weight dialOn a large grid with random walls, run A* at w = 1, 1.5, 3 and 5. Watch nodes expanded fall while the route cost creeps above optimal, never by more than w times.
5. 05Two circles beat oneOn an empty large grid, race Dijkstra against bidirectional Dijkstra. Both are optimal; count how many cells each expands.
6. 06Live goalAfter any run finishes, drag the red goal around. The search recomputes instantly, so you can see exactly which walls make A* hesitate.