Vibe Engines
ALGORITHMS · 06  /  A* SEARCH

The Ascent.

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

click a tile to play your move
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

  1. Score the start. g = 0, f = h(start). Put it in the open set (a priority queue).
  2. 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.
  3. Goal? If it's the goal, stop — the path is found. Otherwise mark it visited.
  4. 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.
  5. 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.

QUICK CHECK

Did it stick?

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.

RUN CARD

—

Next → the Pathfinder's priority queue is itself an algorithm: the binary heap. That's the engine behind every pop.

Finished this one? 0 / 7 Algorithms done

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →