| Algorithm | Explored | Path | Cost | Steps |
|---|
Show
Your finger draws
Start with
How to play
- Drag on the grid to draw walls. Drag S (start) and G (goal) to move them.
- Press Race! and watch all four search at the same speed.
- Check the table: who explored fewest cells, and who found the cheapest path?
| Do this | Phone | Keyboard |
|---|---|---|
| Draw walls / mud | Pick a tool, drag | 1 2 3 pick, arrows move, Space paints (on the grid) |
| Move start / goal | Drag S or G | S or G at the cursor |
| Race | Race! button | R |
| Clear walls | Button | X |
| View, presets, speed | Buttons, slider | Tab to them |
What's happening?
- Breadth-first spreads out in rings, like a ripple. It always finds the path with fewest squares, but looks everywhere.
- Dijkstra spreads out by cost, so it walks round mud (each mud square costs 5).
- A* is Dijkstra plus a guess: "how far is the goal as the crow flies?" It still finds the cheapest path, but explores far less.
- Greedy best-first only uses the guess. It's fast, but it can run into dead ends and take a worse path.
- Video games use A* to move characters round walls. Map apps use the same ideas on roads.
Try this: load the Trap and race. Greedy dives into the cup and then wades through mud. Now draw a wall to block the dry lane into the goal. Who wins now?