--reserve-escapes: keep a way out open for every fine-pitch pin

Before routing, each crowded pin gets the shortest way from its pad to
open board, found against pads, keepouts and earlier escapes. While the
pin still has connections to route, no other net may put a trace or a
via there, nor within clearance of it; the reservation lifts once the
pin is routed.

src/freeroute/cli.py

@@ -30,8 +30,8 @@ from freeroute.ses import write_ses
 #: which optional flags each engine actually implements. Anything not listed for
 #: an engine is rejected by :func:`_validate` rather than quietly ignored.
 ENGINE_OPTIONS: dict[str, frozenset[str]] = {
-    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "escapes"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access"}),
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "escapes"}),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -46,6 +46,7 @@ _FLAG_NAMES = {
     "orders": "--orders",
     "promote": "--promote-failures",
     "access": "--access-cost",
+    "escapes": "--reserve-escapes",
 }
 
 
@@ -166,6 +167,12 @@ def build_parser() -> argparse.ArgumentParser:
         help="grid and exact engines: extra cost for a route to pass where it would close "
         "another pin's way out while that pin still has connections to route (default 0: off)",
     )
+    parser.add_argument(
+        "--reserve-escapes",
+        action="store_true",
+        help="grid and exact engines: before routing, reserve a way out for every fine-pitch "
+        "pin that no other net may use until that pin's connections are routed",
+    )
     parser.add_argument(
         "--jobs",
         type=int,
@@ -195,6 +202,7 @@ def main(argv: list[str] | None = None) -> int:
             ("orders", args.orders is not None),
             ("promote", args.promote_failures is not None),
             ("access", args.access_cost is not None),
+            ("escapes", args.reserve_escapes),
         )
         if asked
     ]
@@ -229,6 +237,7 @@ def main(argv: list[str] | None = None) -> int:
             "resolution": 2 if args.grid_resolution is None else args.grid_resolution,
             "heuristic_weight": args.heuristic_weight,
             "access_cost": args.access_cost or 0.0,
+            "reserve_escapes": args.reserve_escapes,
         }
     elif args.engine == "grid":
         options = {
@@ -238,6 +247,7 @@ def main(argv: list[str] | None = None) -> int:
             "edge_clearance_mm": args.edge_clearance,
             "resolution": 1 if args.grid_resolution is None else args.grid_resolution,
             "access_cost": args.access_cost or 0.0,
+            "reserve_escapes": args.reserve_escapes,
         }
     if args.engine == "room":
         result = build_rooms_routing_result(

src/freeroute/route/exact_router.py

@@ -98,6 +98,7 @@ def route_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    reserve_escapes: bool = False,
 ) -> ExactRouteResult:
     """Route ``board`` orthogonally and verify the result with exact geometry.
 
@@ -129,6 +130,7 @@ def route_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        reserve_escapes=reserve_escapes,
     )
     edge = 0 if edge_clearance is None else edge_clearance
     outline = board.outline

src/freeroute/route/grid_router.py

@@ -159,6 +159,7 @@ class GridRouter:
         seed: int | None = None,
         route_first: frozenset | None = None,
         access_cost: float = 0.0,
+        reserve_escapes: bool = False,
     ) -> None:
         self.board = board
         # Pin access: while a pin still has connections to route, the cells
@@ -168,6 +169,12 @@ class GridRouter:
         self.access_cost = max(float(access_cost), 0.0)
         self._doorways: dict[Node, list[tuple[int, int]]] = {}
         self._pending: dict[int, int] = {}
+        # Escape reservations: before routing, every crowded (fine-pitch) pin
+        # gets a short way out to open board, and while it still has
+        # connections to route no other net may use those cells (nor come
+        # within clearance of them).
+        self.reserve_escapes = bool(reserve_escapes)
+        self._reserved: dict[Node, list[tuple[int, int]]] = {}
         # None keeps the deterministic order; a seed shuffles which connection
         # routes first, to measure how much a result owes to the order
         self.seed = seed
@@ -371,6 +378,10 @@ class GridRouter:
         node = (*cell, layer)
         if wire_keepout and node in self._keepout:
             return None
+        if self._reserved:
+            for pin_id, owner_net in self._reserved.get(node, ()):
+                if owner_net != net_no and self._pending.get(pin_id, 0) > 0:
+                    return None  # another pin's reserved way out
         pads = self._pad_block.get(node)
         if pads and any(n != net_no for n in pads) and net_no not in self._pad_own.get(node, ()):
             return None
@@ -901,7 +912,6 @@ class GridRouter:
         done: set[int] = set()
         for conn in conns:
             for pin in self._group_pins(conn):
-                self._pending[id(pin)] = self._pending.get(id(pin), 0) + 1
                 if id(pin) in done:
                     continue
                 done.add(id(pin))
@@ -919,6 +929,76 @@ class GridRouter:
                 for node in cells:
                     self._doorways.setdefault(node, []).append(claim)
 
+    def _count_pending(self, conns: list[_Connection]) -> None:
+        """How many unrouted connections each pin is an end of."""
+        for conn in conns:
+            for pin in self._group_pins(conn):
+                self._pending[id(pin)] = self._pending.get(id(pin), 0) + 1
+
+    def _reserve_escapes(self, conns: list[_Connection]) -> None:
+        """Give every crowded pin a way out before anything is routed."""
+        blocked: set[Node] = set()  # earlier escapes and their clearance
+        spread = [(0, 0), *self._halo_offsets]
+        seen: set[int] = set()
+        for conn in conns:
+            for pin in self._group_pins(conn):
+                if id(pin) in seen or not self._crowded(pin, conn.net_no):
+                    continue
+                seen.add(id(pin))
+                path = self._escape_path(pin, conn.net_no, conns, blocked)
+                if not path:
+                    continue
+                claim = (id(pin), conn.net_no)
+                for x, y, layer in path:
+                    for dx, dy in spread:
+                        node = (x + dx, y + dy, layer)
+                        if 0 <= node[0] < self.cols and 0 <= node[1] < self.rows:
+                            self._reserved.setdefault(node, []).append(claim)
+                            blocked.add(node)
+
+    def _escape_path(self, pin: Pin, net_no: int, conns, blocked: set[Node]) -> list[Node]:
+        """The shortest way from a pin to a cell clear of other nets' pads,
+        against pads, keepouts and earlier escapes only (breadth first, on
+        the pin's own layers, at most ``2 * _escape_cells`` long)."""
+        starts = [n for n in self._end_nodes(pin, net_no, conns) if n not in blocked]
+        came: dict[Node, Node | None] = dict.fromkeys(starts)
+        frontier = list(starts)
+        limit = 2 * self._escape_cells
+        for _depth in range(limit):
+            nxt: list[Node] = []
+            for node in frontier:
+                if node not in starts and self._open_ground(node, net_no):
+                    path = [node]
+                    while came[path[-1]] is not None:
+                        path.append(came[path[-1]])
+                    return path[::-1]
+                x, y, layer = node
+                for dx, dy in self._neighbours:
+                    n = (x + dx, y + dy, layer)
+                    if n in came or n in blocked:
+                        continue
+                    if not (0 <= n[0] < self.cols and 0 <= n[1] < self.rows):
+                        continue
+                    if not self._static_open(n, net_no):
+                        continue
+                    came[n] = node
+                    nxt.append(n)
+            frontier = nxt
+            if not frontier:
+                break
+        return []
+
+    def _open_ground(self, node: Node, net_no: int) -> bool:
+        """Clear of every other net's pad by a full trace spacing all round."""
+        x, y, layer = node
+        for dx, dy in self._halo_offsets:
+            n = (x + dx, y + dy, layer)
+            if not (0 <= n[0] < self.cols and 0 <= n[1] < self.rows):
+                return False
+            if not self._static_open(n, net_no):
+                return False
+        return True
+
     def _settle(self, conn: _Connection, delta: int) -> None:
         if not self._pending:
             return
@@ -941,8 +1021,12 @@ class GridRouter:
         self._conns = conns
         if not conns:
             return RouteResult(self.half_width)
+        if self.access_cost or self.reserve_escapes:
+            self._count_pending(conns)
         if self.access_cost:
             self._build_doorways(conns)
+        if self.reserve_escapes:
+            self._reserve_escapes(conns)
 
         passes = self.max_passes if self.rip_up else 1
         best_count = -1
@@ -1189,6 +1273,7 @@ def route_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    reserve_escapes: bool = False,
 ) -> RouteResult:
     """Convenience wrapper: build a :class:`GridRouter` and route the board."""
     router = GridRouter(
@@ -1207,5 +1292,6 @@ def route_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        reserve_escapes=reserve_escapes,
     )
     return router.route()

src/freeroute/route/pipeline.py

@@ -83,6 +83,7 @@ def route_dsn_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    reserve_escapes: bool = False,
 ) -> tuple[RouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard`; return the board-unit result, the scale,
     and the layer names. ``layers`` restricts routing to those signal-layer
@@ -106,6 +107,7 @@ def route_dsn_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        reserve_escapes=reserve_escapes,
     )
     return result, scale, [layer.name for layer in dsn.layers]
 
@@ -149,6 +151,7 @@ def build_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    reserve_escapes: bool = False,
 ) -> RoutingResult:
     """Route ``dsn`` (grid track) and convert to a DSN-unit RoutingResult."""
     route, scale, layer_names = route_dsn_board(
@@ -156,6 +159,7 @@ def build_routing_result(
         edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        reserve_escapes=reserve_escapes,
     )
     return _to_routing_result(route, dsn, scale, layer_names)
 
@@ -174,6 +178,7 @@ def route_dsn_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    reserve_escapes: bool = False,
 ) -> tuple[ExactRouteResult, int, list[str]]:
     """Route a parsed :class:`DsnBoard` with the exact-geometry (orthogonal,
     DRC-verified) track; return the exact result, the scale, and layer names.
@@ -201,6 +206,7 @@ def route_dsn_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        reserve_escapes=reserve_escapes,
     )
     return exact, scale, [layer.name for layer in dsn.layers]
 
@@ -219,6 +225,7 @@ def build_exact_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    reserve_escapes: bool = False,
 ) -> RoutingResult:
     """Route ``dsn`` (exact track) and convert to a DSN-unit RoutingResult."""
     exact, scale, layer_names = route_dsn_board_exact(
@@ -234,6 +241,7 @@ def build_exact_routing_result(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        reserve_escapes=reserve_escapes,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

tests/route/test_escapes.py

@@ -0,0 +1,65 @@
+"""--reserve-escapes: a crowded pin keeps a way out until it is routed."""
+
+from __future__ import annotations
+
+from pathlib import Path
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import (
+    _rule_clearance_dsn,
+    _rule_width_dsn,
+    build_exact_routing_result,
+)
+
+SMD = (Path(__file__).resolve().parent.parent / "dsn" / "fixtures" / "smd_demo.dsn").read_text()
+
+
+def _router():
+    dsn = parse_dsn(SMD)
+    s = dsn.resolution.value
+    router = GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        orthogonal=True,
+        resolution=2,
+        reserve_escapes=True,
+    )
+    conns = router._build_connections()
+    router._conns = conns
+    router._count_pending(conns)
+    router._reserve_escapes(conns)
+    return router, conns
+
+
+def test_a_reserved_escape_is_closed_to_other_nets_and_open_to_its_own():
+    router, conns = _router()
+    assert router._reserved
+    node, claims = next(iter(router._reserved.items()))
+    pin_id, owner = claims[0]
+    other = next(c.net_no for c in conns if c.net_no != owner)
+    cell, layer = node[:2], node[2]
+    assert router._enter_cost(cell, layer, other, True, conns) is None  # even for rip-up
+    assert router._enter_cost(cell, layer, owner, False, conns) is not None or node in router._keepout
+
+
+def test_the_escape_is_released_once_its_pin_is_routed():
+    router, conns = _router()
+    node, claims = next(iter(router._reserved.items()))
+    other = next(c.net_no for c in conns if c.net_no != claims[0][1])
+    cell, layer = node[:2], node[2]
+    assert router._enter_cost(cell, layer, other, False, conns) is None
+    for c in conns:  # every connection routed: no pin is pending any more
+        router._settle(c, -1)
+    released = router._enter_cost(cell, layer, other, False, conns)
+    reserved, router._reserved = router._reserved, {}
+    assert released == router._enter_cost(cell, layer, other, False, conns)
+    router._reserved = reserved
+
+
+def test_reserving_escapes_loses_nothing_on_the_demo_board():
+    plain = build_exact_routing_result(parse_dsn(SMD), resolution=2)
+    reserved = build_exact_routing_result(parse_dsn(SMD), resolution=2, reserve_escapes=True)
+    assert len(reserved.unrouted) <= len(plain.unrouted)

tests/test_cli.py

@@ -158,6 +158,7 @@ def test_cli_supported_combinations_are_accepted(tmp_path):
         "orders": ["--orders", "2"],
         "promote": ["--promote-failures", "2"],
         "access": ["--access-cost", "5"],
+        "escapes": ["--reserve-escapes"],
     }
     for engine, options in ENGINE_OPTIONS.items():
         for option in options: