Playground

Watch three searches find a path

Each algorithm keeps an open set and always expands the "best" node in it. The only difference is what "best" means: smallest g, smallest h, or smallest g + h.

New to this?Start with the 7-node walkthrough →
  1. 1
    Pick an algorithm

    Dijkstra, Greedy or A* in the panel on the right.

  2. 2
    Press play

    Or press Space. Step with ← and → to watch one expansion at a time.

  3. 3
    Change the grid

    Drag to draw walls and drag the markers. Once a run finishes, results update as you edit.

The start node is alone in the open set. Press play, or step with →.

0/227

Drag on the grid to draw walls · drag a wall to erase · drag the green start or the target to move them · Space play · ←→ step

Things to try

Greedy takes the bait

No. 1

With the default trap, switch to Greedy. It rushes into the cup because h only says "closer". Compare its cost in the Compare table.

Dijkstra floods

No. 2

Switch to Dijkstra. It ignores h and expands in rings. A* reaches the same cost with far fewer expansions.

Break admissibility

No. 3

Turn on diagonals but keep Manhattan. It overestimates diagonal moves, and on some grids the path stops being the shortest.

Between A* and Greedy

No. 4

Raise A*'s weight on h. At 1 it's A*; as the weight grows it acts more like Greedy, doing less work for longer paths.