Explore / Methods & Algorithms / Routing / A* (A-star) Search

A* (A-star) Search

Routing industry global + detailed 1968 Hart, Nilsson, Raphael shortest path guaranteed explores little generalizes to real costs
Open in the maze lab →

The idea

Keep Lee's grid and guarantee but stop expanding blindly. Maintain a priority queue ordered by

f = g + h
  • f the cell's priority in the queue: settle lowest first
  • g cost of the cheapest path the search has found so far to this cell; provably optimal once the cell is settled
  • h estimate of the remaining cost from this cell to the target

Always settle the queue's cheapest cell; when the target is settled, the traced path is optimal, provided h never overestimates (admissibility). On a unit grid the Manhattan distance is such an estimate, and the search leans hard toward the target: cells pointing away carry large f and wait in the queue, mostly forever.

How the queue is built

g is not known in advance; it is computed incrementally during the search. Each pop removes the queue entry with the minimum f. At that point the entry's g value is optimal: every remaining entry has f at least as large, h never overestimates, and edge costs are non-negative, so no path through any remaining entry can reach the popped cell at lower cost. Each push inserts the popped cell's unvisited neighbors into the queue, assigning g by accumulation (the parent's g plus the edge cost) and h by evaluating the distance estimate. If a neighbor is already queued with a larger g, its entry is updated in place (relaxation).

The two quantities depend on disjoint inputs. g depends only on the source and the edges traversed; Dijkstra's algorithm computes the same quantity with no target information. h depends only on the coordinates of the current cell and of the target, both available before the search begins.

The exact recipe, one iteration at a time:

Step 1: Pop. Take the queue's head, the entry with the smallest f anywhere. Its g is now final.

Step 2: Inherit g. Every free, unsettled neighbor n of the popped cell gets its g from the cell that just found it:

g(n) = g(popped) + 1
  • n the neighbor cell being discovered
  • g(popped) the just-settled cell's final cost, known from Step 1
  • + 1 the cost of the single step between them (unit grid)

Step 3: Compute h. From the target's coordinates alone, no search knowledge needed:

h(n) = |x_T − x_n| + |y_T − y_n|
  • x_n, y_n the neighbor cell's coordinates
  • x_T, y_T the target pin's coordinates, known in advance

Step 4: File by f. The entry (n, g, h, f = g + h) joins the queue in sorted position. If n is already queued from an earlier, more expensive discovery, update that entry instead: lower its g and f and repoint its parent to the cheaper route (this update is called relaxation).

Step 5: Repeat. Until the popped cell is the target itself.

Watch the loop run below, with every g and h computed explicitly in the caption: grid on the left, the actual queue on the right.

The family portrait, visible live in the maze lab: Lee is A with h = 0 (no guidance, maximal flood); Hadlock is in effect A with the sharpest admissible unit-grid estimate (detour counting); A* with Manhattan distance sits between on pure grids, and pulls far ahead the moment costs stop being uniform.

Why production routers are A*-shaped

Real routing cost is not step count. A via between layers costs more than a straight step; a wrong-way segment on a layer with a preferred direction costs more still; a bend costs; a congested edge in negotiated-congestion schemes costs a price that rises every iteration. A* absorbs all of it: g becomes accumulated weighted cost, h any lower bound (usually distance times cheapest per-unit cost), and optimality-within-the-model survives.

Pros, cons, and the trade-off

Strengths

  • Optimal with an admissible estimate: admissibility preserves the shortest-path guarantee on any non-negative cost graph.
  • Cost-general: vias, bends, layer direction, congestion prices, timing weights: anything expressible as edge cost slots in unchanged. This is why it won.
  • Efficient: exploration concentrates along the corridor the estimate points down.
  • Extensible: bidirectional, multi-source and multi-sink (route to a whole partial net), and windowed variants are all standard engineering.

Weaknesses

  • Estimate quality is everything: on heavily weighted graphs a plain distance bound is weak, and the search fattens back toward Dijkstra.
  • Priority-queue overhead: per-cell work exceeds Lee's plain queue; on tiny uniform grids Hadlock is leaner.
  • Speed temptations cost optimality: production implementations sometimes use inflated (inadmissible) estimates, trading the guarantee for runtime, deliberately.
  • Still two-pin per search: multi-terminal nets arrive via Steiner decomposition.

The trade-off

A* is the compromise that ended the argument: it keeps Lee's guarantee whenever the estimate is admissible, approaches Hadlock's economy on pure grids, and, unlike either, carries arbitrary real-world costs. Everything else in this family is now a special case or a teaching example.

Is it actually used today?

The verifiable evidence comes from the open-source toolchain, where the code and documentation can actually be read; the commercial evidence is inference from architecture and patents.

  • Open-source detailed routing: TritonRoute documents an A-based search; Dr. CU runs Dijkstra (A with a zero estimate) over a sparse grid graph.
  • Open-source global routing: FastRoute's point-to-point engine is cost-weighted maze search of exactly this family.
  • Open-source FPGA (Field-Programmable Gate Array) routing: VPR (Versatile Place and Route) documents its router as A*-directed expansion under PathFinder cost updates.
  • Commercial routers: proprietary and uninspectable. Consistent literature and industry description point to the same A*-family kernels, but for closed tools that is inference, not inspection.
  • The caveat: production versions everywhere are heavily engineered variants (multi-sink targets, search windows, sometimes deliberately inadmissible estimates), so "A*" names the kernel, not a textbook implementation.

References and further reading