Part of the Pristone Academy AI Technical Track
A* finds the shortest path without checking the whole map.
The trick is one small idea: always expand the cell that looks best, where “best” is cost so far plus a guess of what's left.
Searching a map, without searching all of it.
Give a computer a grid, a start, and a goal, and the simplest way to guarantee the shortest path is to expand outward from the start in every direction until you bump into the goal. That is exactly what breadth-first search and Dijkstra's algorithm do. They work — but on a big map they waste enormous effort exploring cells that lead away from where you're going.
A* is the fix. It keeps the shortest-path guarantee, but it stops searching blindly. Before expanding a cell, it asks a second question: roughly how much farther is the goal from here? That single hint — the heuristic — lets it lean toward the goal and skip most of the map. It is the standard algorithm behind game characters that walk around obstacles, GPS routing, and robot navigation.
One score decides everything: f = g + h.
A* keeps a frontier of cells it has reached but not yet expanded. Each one carries a score, and A* always expands the cell with the smallest score:
Cost so far
g(n) is the real distance already travelled from the start to cell n — the part you know for certain.
Guess of what's left
h(n) is the heuristic: an estimate of the distance from n to the goal. On a grid, the row-and-column gap, or the straight-line distance.
Best-looking total
f(n) = g + h is the estimated total cost of a path that goes through n. Expanding the smallest f each time is what makes A* aim at the goal yet still refuse any route that isn't actually shortest.
Don't just read it — run it. In the grid below, pick A* (A-star) and press Play. Draw walls with your mouse, drop a new start or goal, then watch the search stretch toward the goal instead of ballooning outward. Every blue cell is one A* expanded; the green trail is the shortest path it found.
Balance cost so far with a guess of what's left. Fast and still finds the shortest path.
Heuristic: Sum of the row and column gaps. Admissible on a 4-direction grid, so A* stays optimal and beelines to the goal.
A* blends the two: cost so far + a guess of what's left. It beelines yet stays shortest.
Frontier structure: Priority by g + h. Draw walls or costly weights with your mouse, drop a new Start / Goal, toggle diagonal moves, then press Play. Switch the heuristic to Zero to watch A* flood like Dijkstra.
Four things worth trying in your own hands, each teaching one idea:
With h = 0 there is no pull toward the goal, so A* has no reason to prefer any direction and floods outward exactly like Dijkstra. This is the clearest way to feel what the heuristic actually buys you.
Press Race and compare cells expanded on the same grid. A* and Dijkstra find paths of equal cost, but A* usually expands a fraction as many cells. Greedy expands even fewer — and sometimes returns a longer route.
The Weights tool marks cells that cost more to cross, like mud. Now the shortest path isn't the fewest steps — it's the cheapest total. Watch A* route around the expensive squares.
Turn on diagonal movement and the path can cut corners. Pair it with the Euclidean heuristic, which measures straight-line distance and fits eight-direction movement better than Manhattan.
A heuristic that never lies too big keeps A* honest.
Here is the subtle part. A* is only guaranteed to find the shortest path if its heuristic is admissible: it never overestimates the true distance remaining. Manhattan and Euclidean distance on a grid are both admissible — the real path can only be as long or longer than a straight line — so A* stays optimal.
If the heuristic overestimates, A* may rush to the goal and miss a cheaper detour, returning a path that works but isn't shortest. If it underestimates (all the way down to zero), A* stays optimal but does more work. So the heuristic is a dial between two extremes: h = 0 is Dijkstra (safe, slow), and a bigger, still-admissible guess is a faster A* that keeps the guarantee.
A* = Dijkstra + a hint. The hint (the heuristic) points it at the goal so it explores less, and as long as the hint never overestimates, the path it returns is still guaranteed to be the shortest.
Choosing to use A* comes down to two questions.
A* is only as good as its guess. If you can cheaply estimate the remaining distance — straight-line on a map, grid distance on a board — A* shines. With no usable estimate, you fall back to Dijkstra.
If any reasonable path will do, Greedy best-first is faster still. If you need the genuinely shortest (or cheapest) route, A* with an admissible heuristic is the sweet spot: fast and provably optimal.
Frequently asked questions
More free lessons
What AI actually is, and how learning from data differs from following rules.
How a machine sorts a pile of points into clean groups with no labels.
How a machine keeps the few directions that matter and throws away the rest.
The self-attention idea behind every modern transformer and LLM.
How AI redistributes work across the layers of a job — and where humans stay scarce.
Curious who's behind these lessons? See the proof of work.