What you are looking at
A chip's router connects millions of pin pairs with wires that ride on a grid of routing tracks, dodging macros and every wire already placed. This page is that problem, shrunk to one metal layer: colored dots are pin pairs (nets), gray cells are blockages, and Run routes the nets one at a time.
Four classic algorithms
The Lee algorithm (1961) is breadth-first wavefront expansion: rings radiate from the source until they touch the target, then the path traces back. Its guarantee is total: if any path exists, Lee finds one, and it is shortest. Its cost is that the wave floods everywhere.
A* (A-star) keeps the shortest-path guarantee but steers the search using a distance estimate to the target (here: Manhattan distance, which never overestimates, so optimality survives). Switch algorithms and watch the cells explored counter: same wirelength, a fraction of the work. That ratio is why production routers are A*-family, not pure Lee.
Two more classics from the same lineage are in the toolbar. Hadlock (1977) expands cells by detour number (how many moves a cell's best path has spent walking away from the target); since path length = Manhattan distance + 2 × detours, minimal detours still means a shortest path, found with remarkably few cells settled. Soukup (1978) simply sprints straight toward the target and only falls back to a Lee-style escape wave when it hits an obstacle: very fast, but the shortest-path guarantee is gone. Run all four on the Macro maze and compare both counters: that two-axis comparison (wirelength vs cells explored) is the whole design space of maze routing.
Net order is a real problem
Each routed net becomes an obstacle for the nets after it. Load the Shared channel preset: both nets want the central gap, the first one takes it, and the second pays a detour. Press Swap net order and the winner changes. Sequential routing is inherently order-dependent, and with tight resources a late net can fail outright (draw a wall with one gap and try to push two nets through it).
Real routers answer this with rip-up and reroute (tear out the offender, try again in a new order) and with negotiated congestion schemes in the PathFinder family, where nets bid for contested resources over several iterations and prices rise on congestion.
From this toy to a real router
Scale this grid to a few billion cells across 10-15 metal layers (vias connect layers, each layer prefers one direction), price bends and vias instead of counting steps, and split the job into a coarse capacity-planning pass and an exact track-level pass: that is global and detailed routing, e.g. FastRoute and TritonRoute inside OpenROAD. The algorithmic skeleton on this page survives all of it.
Things to try
- Macro maze preset: run Lee, then A*. Compare cells explored at equal wirelength.
- Draw a wall with a single gap, add two nets that both need it. One will fail. Swap the order: the other fails. That is why rip-up and reroute exists.
- Build a spiral around a pin and watch Lee flood it.