← back to legend
Physical / electrical concepts

A* search

Lee's flood with a sense of direction: explores cells closer to the target first, so it finds the same best path much faster.

How it looks

Drawing: a routing grid, not a part of CORE3588
partpartAB
A drawing of the search on a routing grid. Dark squares are the only ones A* had to look at (42); Lee's ripple filled 83 on the same puzzle. Both find a 19-step path.

How it works

partpart111122222223333333344444445555555666666777788899910101011111212131314141415151516161617171717181818181819191919191 + 16 = 171 + 18 = 19ABthe same puzzle as the Lee cardLee: 83 squares filled before reaching Bscore = steps walked so far + straight-line guess of steps leftalways expand the square with the lowest score firstA*: 42 squares looked at, path 19 steps (same length as Lee)

Where it fits

A* is the search inside most grid (lattice) routers, including Ants' first slice. What "best" means comes from the cost function: with via and bend prices added, A* finds the cheapest path, not just the shortest.

It still routes one connection at a time; conflicts between nets are settled by net ordering, rip-up and reroute or negotiated congestion.

← back to legend