Gridless (Shape-Based) Routing
The idea
Gridded routers buy their speed from a fiction: that every wire sits on a track of fixed pitch and width. Where the fiction holds, the search space is small and every candidate position is legal by construction. Where it breaks, off-grid macro pins, analog devices, wires of non-standard width, the gridded model cannot even represent the answer. Gridless (shape-based) routing drops the lattice: the layout is stored as geometric shapes in a spatial structure (corner-stitched tile planes are the classic), and the router searches positions derived from the geometry itself:
corner pointscandidate turning positions generated where shapes end or spacing bands intersect, instead of at fixed grid crossings
Legality is checked against real geometry with real spacing rules, so any coordinate is reachable and any width routable. The price is the search space: shape corners vastly outnumber track crossings, and every candidate needs geometric queries instead of array lookups.
The recipe
Step 1 (model). Maintain the layout as shapes in a spatial data structure supporting fast region queries (corner stitching, tile trees).
Step 2 (generate). From the current point, generate candidate moves to the corner points and escape lines of nearby shapes, expanded by the required spacing, the gridless descendant of line-search escape points (Hightower's algorithm was gridless before the word existed).
Step 3 (search and legalize). Run A* (A-star) over the generated points, checking each candidate segment against the real shapes; the result needs no snapping because it was legal at birth.
Watch it work: the pin between the tracks
A macro pin at y = 4.45, between track 4 and track 5. The walkthrough steps through both models: first the gridded lattice, its route, and its blind spot at the off-grid pin; then the shape-based model built up piece by piece, the spacing band, the corner points and escape line generated from the geometry, and the search legs that meet the pin exactly.
Pros, cons, and the trade-off
Strengths
- Complete expressiveness: off-grid pins, arbitrary widths, and analog spacing constraints are first-class, not special cases.
- Legal by construction: candidates are checked against real geometry, so no post-route snapping or violation wave.
- No pitch quantization: wires sit exactly where the geometry wants them, which matters where every nanometer of spacing is negotiated.
Weaknesses
- Slow: geometric queries per candidate and a far larger candidate set; orders of magnitude behind gridded search on digital workloads.
- Complex tooling: spatial structures, incremental rule engines, and escape-point generation are hard to build and harder to make fast.
- Poor fit for uniform problems: on a standard-cell die where everything is on pitch, the generality buys nothing.
The trade-off
Gridded and gridless routing are the same search with different vocabularies: one enumerates a lattice, the other the geometry itself. The lattice wins wherever the design is regular, which is why digital detail routing is gridded; the geometry wins wherever the design is not, which is why analog routers never had a choice.
Is it actually used today?
The evidence for gridless routing splits by domain: analog and custom layout, digital detailed routing, and the academic lineage.
- Analog and custom layout: the routers in custom-design environments (Cadence Virtuoso's space-based router and peers) are shape-based, because analog constraints, symmetry, matching, arbitrary widths, do not quantize.
- Digital, at the edges: production detailed routers stay gridded for speed but carry gridless logic for off-grid pin access and local repair; open-source TritonRoute handles off-grid pin access as a special case within a gridded model.
- The lineage: gridless PCB (Printed Circuit Board) routers appeared in the mid-1980s; Cong's multilevel gridless work (MARS, 2001) is the standard full-chip academic reference, and corner stitching (Ousterhout, 1984) is the data structure that made the model practical.