How a game character finds its way
When you click somewhere in a strategy game, your unit threads through walls and around lakes. Most games do this with an algorithm called A* (“A-star”). Let’s build the intuition by playing with it.
1. The world is a grid
Draw walls by dragging on the grid below. Drag the green start or red goal to move them. Then press Find path.
2. Breadth-first: ask everyone
The simplest idea is to spread out evenly in every direction, like ripples in a pond. It always finds the shortest path — but it wastes time exploring away from the goal. Watch how many squares go blue.
3. Greedy: always head for the goal
The opposite idea: always step towards the goal “as the crow flies”. It’s fast in open fields, but walls fool it — it happily walks into dead ends and ends up with long, silly routes.
4. A*: the best of both
A* scores each square as distance walked so far + guess of distance left. The first part keeps it honest; the second points it at the goal. As long as the guess never overestimates, A* finds the shortest path while exploring far fewer squares than breadth-first. Compare the numbers under the grid.
That guess is called a heuristic. On a grid where you move up, down, left and right, the classic choice is the Manhattan distance: how many blocks across plus how many blocks down.