A ridge stands between the start and the goal — laid out as a clean isometric grid. You'll cross
it by instinct, then meet the Pathfinder, who folds one optimistic guess into
Dijkstra's flood and makes the whole search lean toward the goal.
Pathfinding, part three · after BFS (the flood) and Dijkstra (weighted flood) comes A* (flood with a compass).
THE GIST · 25 SECONDS
A* finds the shortest path by always expanding the frontier node with the smallest
f = g + h: g is the cost you've already paid to reach it, h is an
optimistic guess of the cost still left to the goal. The guess pulls the search toward
the goal, so A* finds the same answer as Dijkstra while exploring a fraction of the map — as
long as h never overestimates. That one condition is the whole shortest-path guarantee.
g(n)cost paid from start to n
h(n)estimated cost left to the goal
f = g + hestimated total — the ranking key
admissibleh never overestimates → optimal
① Climb by instinct → ② Heuristic vs blind flood → ③ Predict the lowest f → ④ Make h lie, lose the guarantee
StartGoalFrontierVisitedPath
click a tile to play your move
Couldn't initialise the 3D view in this browser — the theory, worked trace and quiz below still work.
UNDER THE HOOD
What you just flew, written down
You climbed it, watched the heuristic aim the search, predicted the next pop and then broke optimality. Here's the same machine as code.
How the Pathfinder thinks — five moves
Score the start.g = 0, f = h(start). Put it in the open set (a priority queue).
Pop the best. Remove the open node with the smallest f = g + h — the most promising place to be. Break f-ties toward the goal (smaller h); that one rule alone stops A* fanning out across flat ground.
Goal? If it's the goal, stop — the path is found. Otherwise mark it visited.
Relax neighbours. For each neighbour, a tentative g = g(current) + edge cost. If it's cheaper than what's recorded, update g, set f = g + h, remember we came from here, and push it.
Repeat until the goal pops or the open set empties (no path).
WHY THE GUESS WORKS
Ranking by g alone is Dijkstra — it floods outward evenly. Adding h makes a
node near the goal look cheaper, so the queue serves those first and the search drives
straight at the summit. Set h = 0 and you get Dijkstra back, exactly.
The algorithm
function aStar(start, goal, h):
open = PriorityQueue() # ordered by f
g[start] = 0
open.push(start, f = h(start))
while open not empty:
n = open.popMin() # smallest f = g + h
if n == goal: return path
visited.add(n)
for m in neighbours(n):
if m in visited: continue
t = g[n] + cost(n, m) # tentative g
if t < g[m]:
g[m] = t
cameFrom[m] = n
open.push(m, f = t + h(m))
return NO_PATH
TIMEO(b^d)heuristic quality decides it in practice
SPACEO(b^d)stores the frontier — the real limit
OPTIMAL?if h admissiblenever overestimates → shortest path
h = 0= Dijkstrano guess → uniform-cost flood
THE FAMILY, IN ONE LINE
f = g → Dijkstra (cost so far). f = h → greedy best-first (guess only,
fast but not optimal). f = g + h → A* (both — fast and optimal). f = g + w·h,
w>1 → weighted A* (faster, path ≤ w× optimal).
Solved by hand — A*'s first pops on the mountain above
Every expansion in order, with the cost so far g, the optimistic guess h, and the key f = g + h it was chosen by. Notice f never goes down — that's a consistent heuristic at work.
⚠ An overestimate breaks it
If h can overestimate the remaining cost, A* may skip a node on the true best route
and return a suboptimal path. That's exactly what Act 4 does by inflating h.
↔ Its relatives
Dijkstra = A* with h = 0. Greedy best-first ranks by h only — fast, not
optimal. Weighted A* trades a little optimality for speed. BFS is Dijkstra on an
unweighted graph.
★ Where you've used it
GPS and map routing, game character & unit pathfinding, robot motion planning, and
puzzle solvers like the 15-puzzle. The default when you need the cheapest route fast.
The picture: where the search actually went
The page’s grid (rows from the top; a wall is 1). Each expanded cell shows its pop order, f = g + h, and the two parts. The route has 6 steps and every cell on it has f = 6. The cells (2, 0), (2, 1) and (3, 0) are never touched, and the dead-end (0, 3) is expanded only because its f ties with the route.
Worked example, step by step
The grid is [[0,0,0,0],[1,1,0,1],[0,0,0,0],[0,1,1,0]] with 0 open and 1 a wall, from (0, 0) to (3, 3). Moves are up, down, left, right at cost 1, and h is the Manhattan distance to the goal. Ties on f go to the smaller g, then the smaller cell.
Pop
Cell (row, col)
g
h
f = g + h
1
(0, 0)
0
6
6
2
(0, 1)
1
5
6
3
(0, 2)
2
4
6
4
(0, 3)
3
3
6
5
(1, 2)
3
3
6
6
(2, 2)
4
2
6
7
(2, 3)
5
1
6
8
(3, 3)
6
0
6
Every f in the column is 6, which is also the true cost of the best route. That is what a good heuristic looks like: the optimistic estimate was exactly right from the start, so no pop ever had a higher f than the one before it. The search is not a straight line, though. At pop 4 it takes (0, 3), a dead end (the cell below it is a wall), because its f and g tie with (1, 2) and the tie goes to the smaller cell. That is one wasted pop, and the walls then make (1, 2) the only way on. The 8 pops compare with 10 for the same grid when h is set to 0, which is Dijkstra. On a maze this small the gap is slight; the next section shows it widening.
Complexity and trade-offs
Case
Time
Space
Why
A* with a good heuristic
O(b^d) worst case
O(b^d)
Both the open set and the best-g table grow with the cells touched. On an empty 20 × 20 grid, straight across, it expands 20 cells.
Same search, h = 0 (Dijkstra)
O((V + E) log V)
O(V)
No sense of direction, so it grows a disc around the start. The same 20 × 20 query expands 291 cells, and 19 steps are found by both.
Breadth-first search
O(V + E)
O(V)
Right answer on unit costs, still direction-blind. It is the cheapest choice when every step costs the same and no good h exists.
Greedy best-first (rank by h only)
same worst case
same worst case
Chases the goal and can be quick, but with g ignored it can return a longer route than the best.
Weighted A* (h times k)
fewer expansions
smaller open set
Trades the optimality guarantee for speed. With a 16-cell wall across the 20 × 20 grid: 252 expansions at k = 1 (cost 35), 138 at k = 3 (cost 35). The cost matched here, but a bound on the loss is all that is promised.
Here b is the branching factor and d the depth of the answer; a good heuristic cuts the effective b. With a consistent heuristic A* expands no more nodes than Dijkstra, apart from ties, and the memory bill is where it hurts: the open set can hold a whole frontier, which is why large searches switch to variants that bound memory. What you buy is entirely in the heuristic. On the 20 × 20 grid with a wall, Dijkstra expands 383 cells and A* 252 for the same 35-step answer. The cost of a better h is the time to compute it per node, so a cheap, slightly loose heuristic often beats an expensive tight one.
Common mistakes
A heuristic that can overestimate
Multiply Manhattan distance by 3 on this 5 × 5 grid (rows from the top, 1 = wall): [[0,0,0,0,0],[0,1,0,1,0],[1,1,0,0,0],[0,1,0,0,1],[0,1,1,0,0]]. The best route has 8 steps. With the inflated h A* returns 10, because it stops looking at cells whose inflated f looks too high. Admissible means never above the true remaining cost.
Manhattan distance when diagonal moves are allowed
With 8-way movement, Manhattan distance counts a diagonal step as 2, so it overestimates. On [[0,0,1,0,0],[1,1,0,0,1],[0,1,0,1,0],[0,0,0,0,0],[1,0,0,0,0]], corner to corner, Chebyshev distance gives 5 steps and Manhattan gives 6. Match the heuristic to the move set.
A heuristic that ignores cheaper terrain
If some cells cost 0.5 to enter, a unit-scale Manhattan h is no longer a lower bound. On a 5 × 5 map with half-cost “road” cells, h scaled by 0.5 finds 6, the unscaled one finds 6.5. Scale h by the cheapest possible step.
Not re-checking when a cheaper route to a cell appears
If a cell is marked visited the first time it is reached, a longer first route locks out a shorter later one. Keep the best g per cell and push again only when the new g is lower, as the page’s code does with best_g. The same check drops stale queue entries when they are popped.
Returning when the goal is first pushed
Cost is only final when the goal is popped. The first route to reach the goal is not always the cheapest. Take edges s → g (10), s → a (1), a → g (2): returning on the first push gives 10, while popping gives 3.
Where this shows up
Game movement
Grids and navigation meshes are the textbook home of A*. Units path around obstacles, with terrain costs on the edges and a straight-line distance as h. Because only one goal matters, aiming the search beats expanding in every direction.
Road routing
Straight-line distance on a map never exceeds the road distance, so it is a valid heuristic. Large routing systems add precomputed landmarks or hierarchies on top of this idea so the heuristic is tighter.
Robot motion planning
Planners search a grid or lattice of positions, with obstacles as walls and turning or travel cost on the edges. Anytime and weighted variants are used when an answer is needed within a deadline.
Puzzle solving
States are positions of a puzzle (the sliding-tile 15-puzzle is the classic), moves are edges, and h counts how far the tiles are from home. The same f = g + h ordering applies, with a state table in place of the grid.
RUN IT YOURSELF
A* search, in Python & TypeScript
The same A* search in both languages, running for real in your browser — Python via WebAssembly, TypeScript transpiled on the fly. Switch tabs to compare them, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter).
HOW TO READ THE CODE — 4 IDEAS
Each cell is ranked by f = g + h: g is the cost so far, h is an optimistic guess of the distance left (here, Manhattan) (step 1).
Always expand the cell with the smallest f — the heuristic steers the search toward the goal (step 2).
Expand walkable neighbours, keeping a route only if it is cheaper than any found before (steps 3–4).
With an admissible h (never overestimates), the first time the goal pops it is optimal; an empty queue means no path (step 5).
CPython · WebAssembly
1
1
▶ Watch it explained
A* Pathfinding: Time and Space Complexity, From First Principles
QUICK CHECK
Did it stick?
See every answer, with the reasoning
What does f(n) = g(n) + h(n) represent?
Answer: The estimated total cost of the cheapest path from start to goal through n — g is the cost already paid to reach n; h estimates the cost still left. Their sum is A*'s best guess at the total cost of a path that goes through n.
For A* to guarantee the shortest path, the heuristic must be…
Answer: admissible — it never overestimates the remaining cost — Admissibility (always optimistic, never an overestimate) is the exact condition that keeps a node on the true optimal path from being passed over.
If you set h(n) = 0 for every node, A* behaves exactly like…
Answer: Dijkstra's algorithm (uniform-cost search) — With no heuristic, f = g, so A* ranks purely by cost-so-far and floods outward evenly — that is Dijkstra.
Greedy best-first search (rank by h alone) is fast but…
Answer: it is not guaranteed to find the shortest path — Ignoring g means greedy can be lured down an expensive route that merely looks close to the goal. Keeping g (f = g + h) is what restores optimality.
FAQ
A* search, answered
What is the A* search algorithm?
A* is a best-first graph search that finds the shortest path by always expanding the open node with the smallest f(n) = g(n) + h(n) — the cost already paid plus an estimate of the cost left. The estimate aims the search at the goal, so A* finds the optimal path while exploring far fewer nodes than an uninformed search.
How is A* different from Dijkstra's algorithm?
Dijkstra is A* with h = 0: it ranks the frontier by cost-so-far alone and floods outward in all directions. A* adds the heuristic, biasing the frontier toward the goal so it explores a narrow corridor. With an admissible heuristic both return the same shortest path — A* just visits far less of the map.
What makes a heuristic admissible, and why does it matter?
A heuristic is admissible if it never overestimates the true remaining cost — it's always optimistic. That's the exact condition that guarantees A* returns the shortest path. If h could overestimate, A* might inflate f on the optimal route and settle for a worse one. Straight-line and Manhattan distance are common admissible choices.
What is the time and space complexity of A*?
Worst case is exponential, O(b^d), and memory is the real bottleneck because A* stores every node in the open and closed sets. In practice runtime is dominated by heuristic quality — a perfect h expands only the optimal path; h = 0 degrades to Dijkstra. Each min-f pop uses a priority queue at O(log n).
A* vs greedy best-first search?
Greedy best-first ranks by h alone — it charges at whatever looks closest and ignores the cost already paid, so it's fast but can be lured down an expensive path. Keeping g in the ranking (f = g + h) is what restores A*'s optimality guarantee.
Where is A* used in real life?
GPS and map routing, game pathfinding over grids and navigation meshes, robot motion planning, and AI puzzle solvers such as the 15-puzzle and Rubik's cube. It's the go-to whenever you need the cheapest route through a weighted graph and can estimate the remaining distance.