--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 = {}
@@ -357,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
@@ -383,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
 
@@ -767,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:
@@ -820,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)
@@ -1002,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(
@@ -1017,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)