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.

to exploreexploredpath

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.