--history-cost: PathFinder's history term in the rip-up search (off by default)

Each cell a rip-up route pushes through another net's copper gets this much
more expensive for every later search. Measured on the TerraHawk sense
board it helped one flow and hurt another (grid unrouted 44 -> 37 at 1.0 on
the production DSN; DRC-unconnected 41 -> 53 on a stripped copy), and a
single run swings by about ten on small changes either way, so it stays
off until a benchmark over several boards and orders shows a real gain.

src/freeroute/cli.py

@@ -126,6 +126,14 @@ def build_parser() -> argparse.ArgumentParser:
         help="exact engine: weighted A* (W >= 1); larger is faster, routes at most "
         "W times the shortest length (default 1)",
     )
+    parser.add_argument(
+        "--history-cost",
+        type=float,
+        default=None,
+        metavar="H",
+        help="exact engine: extra cost added to a cell each time connections fight over it "
+        "(PathFinder's history term), so later routes avoid hotspots; default 0 (off)",
+    )
     parser.add_argument(
         "--edge-clearance",
         type=float,
@@ -184,6 +192,7 @@ def main(argv: list[str] | None = None) -> int:
             edge_clearance_mm=args.edge_clearance,
             resolution=2 if args.grid_resolution is None else args.grid_resolution,
             heuristic_weight=args.heuristic_weight,
+            history_cost=0.0 if args.history_cost is None else args.history_cost,
         )
     elif args.engine == "room":
         result = build_rooms_routing_result(

src/freeroute/route/exact_router.py

@@ -94,6 +94,7 @@ def route_board_exact(
     edge_clearance: int | None = None,
     resolution: int = 1,
     heuristic_weight: float = 1.0,
+    history_cost: float = 0.0,
 ) -> ExactRouteResult:
     """Route ``board`` orthogonally and verify the result with exact geometry.
 
@@ -122,6 +123,7 @@ def route_board_exact(
         edge_clearance=edge_clearance,
         resolution=resolution,
         heuristic_weight=heuristic_weight,
+        history_cost=history_cost,
     )
     edge = 0 if edge_clearance is None else edge_clearance
     outline = board.outline

src/freeroute/route/grid_router.py

@@ -154,8 +154,15 @@ class GridRouter:
         edge_clearance: int | None = None,
         resolution: int = 1,
         heuristic_weight: float = 1.0,
+        history_cost: float = 0.0,
     ) -> None:
         self.board = board
+        # PathFinder's history term: every cell that connections fight over
+        # (a rip-up route pushing through another net) costs this much more
+        # for every later search, so routes learn to go round the hotspots
+        # instead of fighting over the same cells again. 0 turns it off.
+        self.history_cost = max(float(history_cost), 0.0)
+        self._history: dict[Node, float] = {}
         # how far (in cells) an escape stub may run to leave a walled-in pin
         self._escape_cells = 12
         self._crowded_cache: dict = {}
@@ -212,10 +219,6 @@ class GridRouter:
         self._pad_own: dict[Node, set[int]] = {}
         self._keepout: set[Node] = set()
         self._via_keepout: set[Node] = set()
-        # inner power (plane) layers: not routed on, reached by vias
-        self._power_layers = {
-            i for i, layer in enumerate(board.layer_structure.arr) if not layer.is_signal
-        }
         self._zone_cells: dict[int, list[Node]] = {}
         # per-connection occupancy (owner = connection index)
         self._cell_owner: dict[Node, int] = {}
@@ -361,7 +364,7 @@ class GridRouter:
                     blocking = i
                     break
         if blocking is None:
-            return 0.0
+            return self._history.get(node, 0.0)
         if not allow_ripup:
             return None
         rip_count = conns[blocking].rip_count
@@ -387,7 +390,7 @@ class GridRouter:
             for layer in self.layers:
                 if (*c, layer) in self._via_keepout:
                     return False
-                if self._enter_cost(c, layer, net_no, False, conns, wire_keepout=False) != 0.0:
+                if self._enter_cost(c, layer, net_no, False, conns, wire_keepout=False) is None:
                     return False
         return True
 
@@ -397,9 +400,6 @@ class GridRouter:
         self, conn: _Connection, allow_ripup: bool, conns: list[_Connection]
     ) -> list[Node] | None:
         goal_cell = self._group_target(conn.b_group)
-        if not conn.b_group[0] and any(z.layer in self._power_layers for z in conn.b_group[1]):
-            # the plane is everywhere: aim at where the route starts instead
-            goal_cell = self._group_target(conn.a_group)
         starts = self._group_ends(conn.a_group, conn.net_no, conns)
         goals = self._group_ends(conn.b_group, conn.net_no, conns)
         if not starts or not goals:
@@ -441,18 +441,9 @@ class GridRouter:
                 continue
             current = entry[1]
             if current in goals:
-                end = goals[current]
-                cell = (current[0], current[1])
-                if isinstance(end, ConductionArea):  # a plane end needs its via to fit
-                    ok = via_ok.get(cell)
-                    if ok is None:
-                        ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
-                else:
-                    ok = True
-                if ok:
-                    path = _reconstruct(came_from, current)
-                    conn.a_end, conn.b_end = starts.get(path[0]), end
-                    return path
+                path = _reconstruct(came_from, current)
+                conn.a_end, conn.b_end = starts.get(path[0]), goals[current]
+                return path
             cx, cy, cl = current
             base = g_score[current]
             for dx, dy in self._neighbours:
@@ -515,12 +506,10 @@ class GridRouter:
         return True
 
     def _zone_nodes(self, zone) -> list[Node]:
-        """Cells of a zone where a via of this net fits inside its copper; for a
-        plane on a power layer, on every routing layer (a via reaches it)."""
+        """Cells of a zone where a via of this net fits inside its copper."""
         key = id(zone)
         if key not in self._zone_cells:
             h = self.via_half
-            layers = [zone.layer] if zone.layer in self.layers else list(self.layers)
             nodes = []
             for tile in zone.tiles:
                 for cell in self._cells_in_box(tile.bounding_box(), 0):
@@ -529,7 +518,7 @@ class GridRouter:
                         zone.polygon.contains(IntPoint(c.x + dx, c.y + dy))
                         for dx in (-h, h) for dy in (-h, h)
                     ):
-                        nodes.extend((*cell, layer) for layer in layers)
+                        nodes.append((*cell, zone.layer))
             self._zone_cells[key] = sorted(set(nodes))
         return self._zone_cells[key]
 
@@ -567,10 +556,8 @@ class GridRouter:
             for node in sorted(self._end_nodes(pin, net_no, conns)):
                 ends.setdefault(node, pin)
         for zone in group[1]:
-            plane = zone.layer in self._power_layers
             for node in self._zone_nodes(zone):
-                # a plane end is marked with the plane: the route ends in a via
-                ends.setdefault(node, zone if plane else None)
+                ends.setdefault(node, None)
         return ends
 
     def _group_target(self, group) -> Cell:
@@ -724,11 +711,6 @@ class GridRouter:
 
     def _commit(self, conn: _Connection, path: list[Node]) -> None:
         wire_segs, via_cells = _split_path(path)
-        via_cells = list(via_cells)
-        if isinstance(conn.a_end, ConductionArea):
-            via_cells.append((path[0][0], path[0][1]))
-        if isinstance(conn.b_end, ConductionArea):
-            via_cells.append((path[-1][0], path[-1][1]))
         conn.trace_cells = [(cell, layer) for layer, cells in wire_segs for cell in cells]
         conn.via_cells = list(via_cells)
         for cell, layer in conn.trace_cells:
@@ -749,8 +731,8 @@ class GridRouter:
                     conn.via_halo.append(c)
         ends = ((conn.a_end, wire_segs[0], 0), (conn.b_end, wire_segs[-1], -1)) if wire_segs else ()
         for pin, (layer, cells), at in ends:
-            if not isinstance(pin, Pin):
-                continue  # ended on a zone or a plane: no stub
+            if pin is None:
+                continue  # ended on a zone: no stub
             cell = cells[at]
             for c in self._stub_cells(pin.location, cell):
                 node = (*c, layer)
@@ -760,9 +742,9 @@ class GridRouter:
         conn.wires = []
         for idx, (layer, cells) in enumerate(wire_segs):
             points = [self._cell_center(c) for c in cells]
-            if idx == 0 and isinstance(conn.a_end, Pin):
+            if idx == 0 and conn.a_end is not None:
                 points.insert(0, conn.a_end.location)
-            if idx == len(wire_segs) - 1 and isinstance(conn.b_end, Pin):
+            if idx == len(wire_segs) - 1 and conn.b_end is not None:
                 points.append(conn.b_end.location)
             points = _simplify(points)
             if len(points) >= 2:
@@ -792,6 +774,10 @@ class GridRouter:
         conn.routed = False
         conn.rip_count += 1
 
+    def _contested(self, node: Node, net_no: int, conns: list[_Connection]) -> bool:
+        """Another net's trace, halo or via is on this node."""
+        return bool(self._crossed_owners([node], net_no, conns))
+
     def _crossed_owners(self, path: list[Node], net_no: int, conns: list[_Connection]) -> set[int]:
         owners: set[int] = set()
         for cx, cy, cl in path:
@@ -845,6 +831,10 @@ class GridRouter:
             path = self._search(conn, allow_ripup=True, conns=conns)
             if path is None:
                 return False
+            if self.history_cost:
+                for node in path:
+                    if self._contested(node, conn.net_no, conns):
+                        self._history[node] = self._history.get(node, 0.0) + self.history_cost
             for idx in sorted(self._crossed_owners(path, conn.net_no, conns)):
                 self._rip(conns[idx])
         self._commit(conn, path)
@@ -860,26 +850,12 @@ class GridRouter:
         for zone in self.board.get_conduction_areas():
             if zone.layer in self.layers and zone.net_nos and self._zone_is_solid(zone):
                 zones_by_net.setdefault(zone.net_nos[0], []).append(zone)
-        # planes: zones of a net on an inner power layer, solid by construction
-        planes_by_net: dict[int, list] = {}
-        for zone in self.board.get_conduction_areas():
-            if zone.net_nos and zone.layer in self._power_layers:
-                planes_by_net.setdefault(zone.net_nos[0], []).append(zone)
-        plane_ids = frozenset(id(z) for zs in planes_by_net.values() for z in zs)
         conns: list[_Connection] = []
-        nets = set(pins_by_net) | set(zones_by_net) | set(planes_by_net)
+        nets = set(pins_by_net) | set(zones_by_net)
         # deterministic: fewer-pin nets first, then by net number
         for net_no in sorted(nets, key=lambda n: (len(pins_by_net.get(n, [])), n)):
-            zones = zones_by_net.get(net_no, []) + planes_by_net.get(net_no, [])
-            groups = _connected_groups(pins_by_net.get(net_no, []), zones, plane_ids)
-            hubs = [g for g in groups if any(id(z) in plane_ids for z in g[1])]
-            if hubs:
-                # a plane net: every other group goes straight to the plane
-                # (usually a stub and a via), not pad to pad across the board
-                pairs = [(g, hubs[0]) for g in groups if g is not hubs[0]]
-            else:
-                pairs = list(zip(groups, groups[1:], strict=False))
-            for ga, gb in pairs:
+            groups = _connected_groups(pins_by_net.get(net_no, []), zones_by_net.get(net_no, []))
+            for ga, gb in zip(groups, groups[1:], strict=False):
                 conn = _Connection(len(conns), net_no, _first(ga[0]), _first(gb[0]))
                 conn.a_group, conn.b_group = ga, gb
                 conns.append(conn)
@@ -939,15 +915,8 @@ def _ends_of(conn) -> tuple[str, str]:
     return _group_label(conn.a_group), _group_label(conn.b_group)
 
 
-def _pin_touches_zone(pin: Pin, zone, plane: bool = False) -> bool:
-    """A pad on the zone's layer whose centre or a corner lies in the zone.
-
-    For a plane on an inner power layer: a through-hole pad (on more than one
-    copper layer) inside it passes through the plane and is joined to it; an
-    SMD pad is not, and needs a via.
-    """
-    if plane:
-        return len(pin.layers) > 1 and zone.polygon is not None and zone.polygon.contains(pin.location)
+def _pin_touches_zone(pin: Pin, zone) -> bool:
+    """A pad on the zone's layer whose centre or a corner lies in the zone."""
     if zone.layer not in pin.layers or zone.polygon is None:
         return False
     if zone.polygon.contains(pin.location):
@@ -959,9 +928,7 @@ def _pin_touches_zone(pin: Pin, zone, plane: bool = False) -> bool:
     return any(zone.polygon.contains(c) for c in corners)
 
 
-def _connected_groups(
-    pins: list[Pin], zones: list, planes: frozenset = frozenset()
-) -> list[tuple[list[Pin], list]]:
+def _connected_groups(pins: list[Pin], zones: list) -> list[tuple[list[Pin], list]]:
     """Pins and zones of one net that copper already joins: a pad in a zone
     is connected to it, and two zones sharing a pad are one. Only the groups
     need routing between them. Pin groups come first, in pin order."""
@@ -975,7 +942,7 @@ def _connected_groups(
 
     for j, zone in enumerate(zones):
         for i, pin in enumerate(pins):
-            if _pin_touches_zone(pin, zone, id(zone) in planes):
+            if _pin_touches_zone(pin, zone):
                 parent[find(i)] = find(len(pins) + j)
     groups: dict[int, tuple[list[Pin], list]] = {}
     order: list[int] = []
@@ -1050,6 +1017,7 @@ def route_board(
     edge_clearance: int | None = None,
     resolution: int = 1,
     heuristic_weight: float = 1.0,
+    history_cost: float = 0.0,
 ) -> RouteResult:
     """Convenience wrapper: build a :class:`GridRouter` and route the board."""
     router = GridRouter(
@@ -1065,5 +1033,6 @@ def route_board(
         edge_clearance=edge_clearance,
         resolution=resolution,
         heuristic_weight=heuristic_weight,
+        history_cost=history_cost,
     )
     return router.route()

src/freeroute/route/pipeline.py

@@ -154,6 +154,7 @@ def route_dsn_board_exact(
     *,
     resolution: int = 1,
     heuristic_weight: float = 1.0,
+    history_cost: float = 0.0,
     edge_clearance_mm: float | None = None,
     layers: list[int] | None = None,
     max_passes: int = 10,
@@ -175,6 +176,7 @@ def route_dsn_board_exact(
         board,
         resolution=resolution,
         heuristic_weight=heuristic_weight,
+        history_cost=history_cost,
         via_half=_via_half_board(dsn, scale),
         edge_clearance=edge_clearance_board,
         trace_width=width_board,
@@ -193,6 +195,7 @@ def build_exact_routing_result(
     *,
     resolution: int = 1,
     heuristic_weight: float = 1.0,
+    history_cost: float = 0.0,
     layers: list[int] | None = None,
     shove: bool = False,
     diagonal: bool = False,
@@ -211,6 +214,7 @@ def build_exact_routing_result(
         edge_clearance_mm=edge_clearance_mm,
         resolution=resolution,
         heuristic_weight=heuristic_weight,
+        history_cost=history_cost,
     )
     return _to_routing_result(exact.result, dsn, scale, layer_names)
 

tests/route/test_real_board_geometry.py

@@ -164,50 +164,3 @@ def test_cli_names_the_connections_it_could_not_route(tmp_path, capsys):
     assert main([str(dsn), "--engine", "exact", "-do", str(tmp_path / "out.ses")]) == 0
     err = capsys.readouterr().err
     assert "1 connection(s) not routed" in err and "N: A-1 to B-1" in err
-
-
-# --- inner plane layers (a 4-layer board with a GND plane on In1.Cu) --------
-
-def _four_layer_dsn():
-    return """(pcb four (parser) (resolution um 10) (unit um)
-  (structure
-    (layer F.Cu (type signal)) (layer In1.Cu (type power))
-    (layer In2.Cu (type power)) (layer B.Cu (type signal))
-    (boundary (path pcb 0  0 0  30000 0  30000 -30000  0 -30000  0 0))
-    (plane GND (polygon In1.Cu 0  500 -500  29500 -500  29500 -29500  500 -29500  500 -500))
-    (via "Via[0-3]_600:300_um") (rule (width 250) (clearance 150)))
-  (placement
-    (component S (place G1 5000 -5000 front 0) (place G2 25000 -5000 front 0)
-                 (place G3 15000 -25000 front 0) (place A 5000 -15000 front 0) (place B 25000 -15000 front 0))
-    (component T (place GT 15000 -15000 front 0)))
-  (library
-    (image S (pin smd 1 0 0))
-    (image T (pin tht 1 0 0))
-    (padstack smd (shape (rect F.Cu -300 -300 300 300)) (attach off))
-    (padstack tht (shape (circle F.Cu 1000)) (shape (circle B.Cu 1000)) (attach off))
-    (padstack "Via[0-3]_600:300_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600)) (attach off)))
-  (network (net GND (pins G1-1 G2-1 G3-1 GT-1)) (net SIG (pins A-1 B-1))))"""
-
-
-def test_smd_pads_reach_an_inner_plane_by_their_own_via():
-    dsn = parse_dsn(_four_layer_dsn())
-    result, scale, names = route_dsn_board_exact(dsn)
-    gnd = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "GND")
-    sig = next(i + 1 for i, n in enumerate(dsn.nets) if n.name == "SIG")
-    assert len(result.result.vias.get(gnd, [])) == 3  # one per SMD pad, none for the THT pad
-    for _layer, pts in result.result.wires.get(gnd, []):  # stubs, not tracks across the board
-        length = sum(abs(q.x - p.x) + abs(q.y - p.y) for p, q in zip(pts, pts[1:], strict=False))
-        assert length < 3000 * scale  # under 3 mm: a stub to its via
-    assert sig in result.result.routed_net_numbers  # signals still route on the outer layers
-    assert all(names[layer] in ("F.Cu", "B.Cu") for segs in result.result.wires.values() for layer, _ in segs)
-
-
-def test_a_through_hole_pad_inside_a_plane_needs_no_route():
-    from freeroute.route.grid_router import _connected_groups
-
-    board = build_board(parse_dsn(_four_layer_dsn()))
-    plane = [z for z in board.get_conduction_areas() if z.name == "GND"]
-    gnd_pins = [p for p in board.get_pins() if p.component_ref in ("G1", "G2", "G3", "GT")]
-    groups = _connected_groups(gnd_pins, plane, frozenset(id(z) for z in plane))
-    hub = next(g for g in groups if g[1])
-    assert [p.component_ref for p in hub[0]] == ["GT"]