A* pathfinding

A* finds the shortest route between two points by being permanently curious about the cheapest thing it has not tried yet — and slightly impatient, because it also has a guess about how far is left to go.

Heuristic weight 1.0 A* — shortest path guaranteed Speed Allow diagonal moves

Expanded: 0
Frontier: 0
Path steps: —
Path cost: —

Drag on the grid to draw or erase walls. Drag either endpoint to move it.

What the algorithm is doing

Every cell the search has reached carries three numbers. g is what it actually cost to get there from the start. h is the estimate of what remains — here, the distance to the goal if the walls were not there. Their sum, f = g + h, is the algorithm's best guess at the total cost of a route through that cell.

A* keeps every reached-but-unexplored cell in a queue ordered by f, and repeatedly expands the cheapest one. That is the whole algorithm. The two shades on the grid are that queue made visible: the outlined cells are the frontier it is choosing from, and the filled ones are cells it has already committed to and will not revisit.

Because h never overestimates the true remaining distance — you cannot get there faster than a straight line — the first time A* expands the goal, no shorter route can still be hiding in the queue. That property is called admissibility, and it is the reason the answer is not merely good but provably shortest.

Why the weight slider is the interesting control

The queue is really ordered by f = g + w·h, where w is how far the guess is trusted. Sliding it is the fastest way to feel what the heuristic buys:

w = 0 throws the guess away. The cost so far is the only thing that matters, so the search fans out in a disc in every direction — this is exactly Dijkstra's algorithm. It finds the shortest path and wastes a great deal of work proving it.
w = 1 is A*. The explored region stretches into an ellipse pointed at the goal. Still shortest, and typically a fraction of the expansions.
w > 1 over-trusts the guess. The search drives at the goal and usually gets there very fast, but it will now walk past a shortcut without noticing — the path it returns is no longer guaranteed to be the shortest one.

Build a maze, then run it at 0, at 1, and at 2, and watch the expanded counter against the path cost. That trade — search effort against solution quality — is the entire design space, and it is why the same algorithm shows up in route planners, in games, and in the informative-path-planning work on the rest of this site.