diagnose.py: --negotiate, as the router

Every connection is routed N times on the empty board, where routes may
share cells at a price that doubles each round for every other net on a
cell, and a cell that stays shared gains history. The real routing then
pays that history on free cells, so the first routes stop taking the space
later routes (a fine-pitch part's escapes) have no way round. Off by
default.

The old history term never steered: it only accrued at rip-up fights,
after the first routes had claimed the contested space, and routed
connections are never revisited in later passes.

bench/diagnose.py

@@ -32,8 +32,10 @@ from freeroute.route.exact_router import route_board_exact
 from freeroute.route.grid_router import GridRouter, _ends_of
 from freeroute.route.pipeline import (
     _mm_to_board,
+    _net_widths_board,
     _rule_clearance_dsn,
     _rule_width_dsn,
+    _via_drill_board,
     _via_half_board,
 )
 
@@ -183,7 +185,8 @@ def _flood(router: GridRouter, pin, net_no: int, conns) -> tuple[int, Counter]:
 
 def diagnose(
     dsn_text: str, edge_clearance_mm: float | None, resolution: int = 2, shove: bool = False,
-    access_cost: float = 0.0,
+    access_cost: float = 0.0, hole_to_hole_mm: float = 0.25, seed: int | None = None,
+    negotiate: int = 0,
 ) -> dict:
     dsn = parse_dsn(dsn_text)
     names = {i + 1: n.name for i, n in enumerate(dsn.nets)}
@@ -199,6 +202,12 @@ def diagnose(
         resolution=resolution,
         shove=shove,
         access_cost=access_cost,
+        seed=seed,
+        negotiate=negotiate,
+        # the product's configuration: net-class widths and hole spacing
+        net_widths=_net_widths_board(dsn, scale),
+        via_drill=_via_drill_board(dsn, scale),
+        hole_to_hole=_mm_to_board(dsn, scale, hole_to_hole_mm) or 0,
     )
     routed = seen["router"]
     best = routed._diag_best
@@ -270,11 +279,14 @@ def main(argv: list[str] | None = None) -> int:
     ap.add_argument("--grid-resolution", type=int, default=2, metavar="K")
     ap.add_argument("--shove", action="store_true", help="as mckicad routes")
     ap.add_argument("--access-cost", type=float, default=0.0)
+    ap.add_argument("--seed", type=int, help="route in this shuffled order, as bench.py does")
+    ap.add_argument("--negotiate", type=int, default=0, metavar="N", help="as the router's --negotiate")
+    ap.add_argument("--hole-to-hole", type=float, default=0.25, metavar="MM")
     ap.add_argument("--json", type=Path, help="also write the full table here")
     args = ap.parse_args(argv)
 
     report = diagnose(args.dsn.read_text(), args.edge_clearance, args.grid_resolution, args.shove,
-                      args.access_cost)
+                      args.access_cost, args.hole_to_hole, args.seed, args.negotiate)
     for row in report["failures"]:
         extra = ""
         for w in row.get("walled", []):

bench/drc_check.sh

@@ -0,0 +1,67 @@
+#!/usr/bin/env bash
+# Route one KiCad board with freeroute and judge the result with KiCad's DRC.
+#
+#   bench/drc_check.sh [--keep] <board.kicad_pcb> <out-dir> [freeroute args...]
+#
+# Copies the board (and its .kicad_pro) into <out-dir>, strips its tracks and
+# vias unless --keep is given (then they reach the router as fixed wiring),
+# exports the DSN through mckicad, routes, applies the session, and runs DRC
+# with zones refilled at every severity. Prints one line: time, copper added,
+# shorts, opens, hole problems (whatever severity the board gives them) and
+# the other errors. The source board is never touched.
+#
+# FREEROUTE (default: this checkout's .venv/bin/freeroute) and MCK (default
+# ~/claude/mckicad) pick the builds to judge.
+set -euo pipefail
+keep=0
+if [[ "${1:-}" == "--keep" ]]; then keep=1; shift; fi
+src="$1"; out="$2"; shift 2
+here="$(cd "$(dirname "$0")/.." && pwd)"
+FREEROUTE="${FREEROUTE:-$here/.venv/bin/freeroute}"
+MCK="${MCK:-$HOME/claude/mckicad}"
+rm -rf "$out"; mkdir -p "$out"
+cp "${src%.kicad_pcb}.kicad_pro" "$out/board.kicad_pro" 2>/dev/null || true
+
+if [[ $keep == 1 ]]; then
+    cp "$src" "$out/board.kicad_pcb"
+else
+    (cd "$MCK" && uv run --no-sync python - "$src" "$out/board.kicad_pcb" <<'EOF'
+import sys
+from mckicad.utils.sexp_tree import parse
+text = open(sys.argv[1]).read()
+spans = sorted((c.span for c in parse(text).children if c.tag in ("segment", "arc", "via")), reverse=True)
+for a, b in spans:
+    text = text[:a] + text[b:]
+open(sys.argv[2], "w").write(text)
+EOF
+    )
+fi
+
+(cd "$MCK" && uv run --no-sync python -c "
+from mckicad.utils.freerouting import FreeRoutingEngine
+assert FreeRoutingEngine().export_dsn_from_kicad('$out/board.kicad_pcb', '$out/board.dsn', {})") \
+    >/dev/null 2>&1 || { echo "$out: DSN export failed"; exit 1; }
+
+start=$(date +%s.%N)
+"$FREEROUTE" "$out/board.dsn" -do "$out/board.ses" "$@" >"$out/route.log" 2>&1 || true
+secs=$(python3 -c "print(round($(date +%s.%N)-$start,1))")
+[[ -s "$out/board.ses" ]] || { echo "$out: no session ($(tail -1 "$out/route.log"))"; exit 1; }
+
+(cd "$MCK" && uv run --no-sync python -c "
+from mckicad.utils.ses_apply import apply_ses_to_board as a
+r = a('$out/board.kicad_pcb', '$out/board.ses', '$out/board.kicad_pcb')
+print(r['segments_added'], r['vias_added'])" 2>/dev/null) >"$out/apply.txt"
+
+kicad-cli pcb drc --refill-zones --format json --severity-all \
+    -o "$out/drc.json" "$out/board.kicad_pcb" >/dev/null 2>&1 || true
+python3 - "$out" "$secs" <<'EOF'
+import collections, json, sys
+out, secs = sys.argv[1:]
+seg, via = open(f"{out}/apply.txt").read().split()
+d = json.load(open(f"{out}/drc.json"))
+errors = collections.Counter(v["type"] for v in d["violations"] if v.get("severity") == "error")
+other = collections.Counter(v["type"] for v in d["violations"] if v.get("severity") != "error")
+holes = {k: errors.pop(k, 0) + other.get(k, 0) for k in ("holes_co_located", "hole_to_hole")}
+print(f"{out}: {secs}s  {seg} seg {via} via  shorts {errors.pop('shorting_items', 0)}  "
+      f"opens {len(d.get('unconnected_items', []))}  holes {holes}  errors {dict(errors)}")
+EOF

src/freeroute/board/build.py

@@ -12,9 +12,10 @@ model. It mirrors what FreeRouting's ``Structure.create_board`` / ``Library`` /
 * padstacks x placement -> :class:`Pin` items
 * keepouts -> :class:`ObstacleArea` items
 
-Pad geometry: a rectangle pad becomes an exact :class:`IntBox`; a circle pad its
+Pad geometry: a rectangle pad becomes an exact :class:`IntBox`; a circle pad a
-bounding box (documented approximation pending an exact circle tile); a convex
+16-sided :class:`Simplex` drawn just outside it (its corners stand out by 2% of
-polygon pad an exact :class:`Simplex`. Every pad is placed centred on its pin
+the radius, where the bounding box's stood out by 41%); a convex polygon pad an
+exact :class:`Simplex`. Every pad is placed centred on its pin
 location, so it contains that location by construction. Component rotation is
 applied to the pin position; the pad tile itself is not rotated (irrelevant to
 the containment invariant, and pads are centre-symmetric in practice).
@@ -23,6 +24,7 @@ the containment invariant, and pads are centre-symmetric in practice).
 from __future__ import annotations
 
 import math
+import re
 
 from freeroute.dsn.model import DsnBoard
 from freeroute.dsn.shapes import Circle, Path, Polygon, Rectangle, Shape
@@ -38,6 +40,9 @@ from .transform import CoordinateTransform
 
 __all__ = ["build_board"]
 
+# DSN units per micrometre, for drills KiCad gives in um in via padstack names
+_DSN_PER_UM = {"um": 1.0, "mm": 0.001, "mil": 1 / 25.4, "inch": 1 / 25400}
+
 
 def build_board(dsn: DsnBoard) -> BasicBoard:
     """Construct a :class:`BasicBoard` from a parsed :class:`DsnBoard`."""
@@ -245,7 +250,7 @@ def _placed_pad_tile(shape: Shape, place, dsn_pin, transform: CoordinateTransfor
         r = round(transform.dsn_to_board(shape.diameter / 2))
         cx = round(transform.dsn_to_board(centre.x))
         cy = round(transform.dsn_to_board(centre.y))
-        return IntBox(cx - r, cy - r, cx + r, cy + r)
+        return _circle_tile(cx, cy, r)
     if isinstance(shape, Rectangle):
         x0, y0, x1, y1 = shape.coords[:4]
         corners = [(x0, y0), (x1, y0), (x1, y1), (x0, y1)]
@@ -264,15 +269,65 @@ def _placed_pad_tile(shape: Shape, place, dsn_pin, transform: CoordinateTransfor
     for x, y in corners:
         p = _to_board_offset(place, x, y, dsn_pin.rotation)
         pts.append(IntPoint(round(transform.dsn_to_board(p.x)), round(transform.dsn_to_board(p.y))))
-    if len(pts) >= 3:
+    # An oval's padded corners are not in outline order, and a mirrored
-        simplex = Simplex.from_corners(pts)
+    # part reverses the winding: take the convex hull, then either winding.
-        if not simplex.is_empty():
+    hull = _convex_hull(pts)
-            return simplex
+    if len(hull) >= 3:
+        for corners in (hull, hull[::-1]):
+            simplex = Simplex.from_corners(corners)
+            if not simplex.is_empty():
+                return simplex
     xs = [p.x for p in pts] or [0]
     ys = [p.y for p in pts] or [0]
     return IntBox(min(xs), min(ys), max(xs), max(ys))
 
 
+_CIRCLE_SIDES = 16
+
+
+def _circle_tile(cx: int, cy: int, r: int):
+    """A polygon around the circle, every side touching it. A square around a
+    big round pad (a mounting hole) puts phantom copper in its corners that
+    blocks legal routes past it; this stays outside the circle, so the router
+    is still never closer than KiCad measures."""
+    if r < 8:
+        return IntBox(cx - r, cy - r, cx + r, cy + r)
+    reach = r / math.cos(math.pi / _CIRCLE_SIDES)
+    corners = []
+    for k in range(_CIRCLE_SIDES):
+        a = (k + 0.5) * 2 * math.pi / _CIRCLE_SIDES
+        dx, dy = reach * math.cos(a), reach * math.sin(a)
+        # round away from the centre so the polygon never cuts into the circle
+        corners.append(IntPoint(cx + math.copysign(math.ceil(abs(dx)), dx),
+                                cy + math.copysign(math.ceil(abs(dy)), dy)))
+    corners = [IntPoint(int(p.x), int(p.y)) for p in corners]
+    for winding in (corners, corners[::-1]):
+        simplex = Simplex.from_corners(winding)
+        if not simplex.is_empty():
+            return simplex
+    return IntBox(cx - r, cy - r, cx + r, cy + r)
+
+
+def _convex_hull(pts: list[IntPoint]) -> list[IntPoint]:
+    """The convex hull of ``pts`` counter-clockwise, collinear points dropped."""
+    ps = sorted({(p.x, p.y) for p in pts})
+    if len(ps) < 3:
+        return [IntPoint(x, y) for x, y in ps]
+
+    def cross(o, a, b):
+        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
+
+    def half(points):
+        out: list[tuple[int, int]] = []
+        for p in points:
+            while len(out) >= 2 and cross(out[-2], out[-1], p) <= 0:
+                out.pop()
+            out.append(p)
+        return out[:-1]
+
+    return [IntPoint(x, y) for x, y in half(ps) + half(ps[::-1])]
+
+
 def _pad_tile(shape: Shape, transform: CoordinateTransform):
     """A board-relative pad tile from a DSN padstack shape (centred near origin)."""
     if isinstance(shape, Rectangle):
@@ -282,7 +337,7 @@ def _pad_tile(shape: Shape, transform: CoordinateTransform):
         r = round(transform.dsn_to_board(shape.diameter / 2))
         cx = round(transform.dsn_to_board(shape.center_x))
         cy = round(transform.dsn_to_board(shape.center_y))
-        return IntBox(cx - r, cy - r, cx + r, cy + r)  # bounding-box approximation
+        return _circle_tile(cx, cy, r)
     if isinstance(shape, (Polygon, Path)):
         coords = shape.coords
         pts = [
@@ -503,10 +558,15 @@ def _insert_wiring(dsn: DsnBoard, board: BasicBoard, transform: CoordinateTransf
         location = transform.dsn_to_board_point(via.x, via.y)
         pad = _pad_tile(max(padstack.shapes, key=_shape_extent), transform)
         box = pad.bounding_box()
+        drill = re.search(r"_([\d.]+):([\d.]+)_um", via.padstack)
+        drill_board = (
+            round(transform.dsn_to_board(float(drill.group(2)) * _DSN_PER_UM.get(dsn.unit, 1.0)))
+            if drill else 0
+        )
         board.insert(
             Via(
                 net_nos=[numbers[via.net]], fixed=True, padstack_name=via.padstack,
-                location=location, layers=sorted(layers or signal_layers),
+                drill=drill_board, location=location, layers=sorted(layers or signal_layers),
                 shape=IntBox(box.ll.x + location.x, box.ll.y + location.y,
                              box.ur.x + location.x, box.ur.y + location.y),
             )

src/freeroute/board/items.py

@@ -117,6 +117,8 @@ class Via(Item):
     #: layer indices the via's pads occupy, and the largest pad as a box
     layers: list[int] = field(default_factory=list)
     shape: object = None
+    #: drill diameter in board units, when the padstack name gives it
+    drill: int = 0
 
 
 @dataclass

src/freeroute/board/search_tree.py

@@ -188,6 +188,8 @@ class ShapeSearchTree:
         overlap). Static pad-vs-pad spacing in the source design is not counted.
         """
         for shape in self.all_shapes():
+            if not shape.routed:
+                continue  # a pair with routed copper is checked from that side
             expanded = shape.tile.offset(clearance)
             grown = None  # exact clearance region, built lazily only for diagonals
             for other in self.overlapping(expanded):

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", "rollback"}),
+    "grid": frozenset({"rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback"}),
-    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "rollback"}),
+    "exact": frozenset({"shove", "diagonal", "rip_up", "max_passes", "seed", "orders", "promote", "access", "negotiate", "rollback"}),
     "room": frozenset({"shove", "pack"}),
 }
 
@@ -46,6 +46,7 @@ _FLAG_NAMES = {
     "orders": "--orders",
     "promote": "--promote-failures",
     "access": "--access-cost",
+    "negotiate": "--negotiate",
     "rollback": "--no-rollback",
 }
 
@@ -167,6 +168,14 @@ 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(
+        "--negotiate",
+        type=int,
+        metavar="N",
+        help="grid and exact engines: before routing, N rounds of negotiation on the empty "
+        "board, where routes may share space at a price that rises where they compete; "
+        "the contested cells then cost extra in the real routing (default 0: off)",
+    )
     parser.add_argument(
         "--no-rollback",
         dest="rollback",
@@ -212,6 +221,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),
+            ("negotiate", args.negotiate is not None),
             ("rollback", not args.rollback),
         )
         if asked
@@ -247,6 +257,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,
+            "negotiate": args.negotiate or 0,
             "hole_to_hole_mm": args.hole_to_hole,
             "rollback": args.rollback,
         }
@@ -258,6 +269,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,
+            "negotiate": args.negotiate or 0,
             "hole_to_hole_mm": args.hole_to_hole,
             "rollback": args.rollback,
         }

src/freeroute/route/exact_router.py

@@ -38,6 +38,7 @@ from freeroute.geometry import (
     IntPoint,
     Polyline,
     PolylineShape,
+    Simplex,
     segment_box,
     segment_octagon,
     shove_segment,
@@ -98,6 +99,7 @@ def route_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     rollback: bool = True,
     net_widths: dict[int, int] | None = None,
     via_drill: int | None = None,
@@ -133,6 +135,7 @@ def route_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
         net_widths=net_widths,
         via_drill=via_drill,
@@ -154,7 +157,9 @@ def route_board_exact(
         net = pin.net_nos[0] if pin.net_nos else -1
         pin_layers = frozenset(layer for layer in pin.layers if layer in signal_layers)
         if pin_layers:
-            tree.insert(TreeShape(next(owner), net, pin_layers, box))
+            # a rotated pad is checked against its outline, not its box
+            exact = pin.shape if _is_rotated(pin.shape) else None
+            tree.insert(TreeShape(next(owner), net, pin_layers, box, exact=exact))
     for net, copper_layers, box in board.get_fixed_copper():
         on = frozenset(layer for layer in copper_layers if layer in signal_layers)
         if on and not box.is_empty():
@@ -204,7 +209,9 @@ def route_board_exact(
             for i, (box, box_layers) in enumerate(boxes)
             for layer in box_layers
         ) or _end_in_rule_area(tree, wires, wire_half) or (
-            outline is not None and not all(outline.box_clear(b, edge) for b, _ in boxes)
+            outline is not None and not _inside_outline(
+                outline, boxes[:wire_count], vias, (via_half or wire_half) + edge, edge
+            )
         ):
             rejected.append((net_no, *ends))
             continue  # exact-clearance conflict -> drop (may be recovered by shove)
@@ -667,6 +674,19 @@ def _copper_boxes(wires, vias, half_width, via_layers, via_half=None):
     return boxes
 
 
+def _inside_outline(outline, wire_boxes, vias, via_reach, edge) -> bool:
+    """Copper inside the board, ``edge`` from its outline. A via is round, as
+    the grid and KiCad take it: its square box would reach past a chamfered
+    corner where the via itself does not."""
+    return all(outline.box_clear(b, edge) for b, _ in wire_boxes) and all(
+        outline.point_clear(v, via_reach) for v in vias
+    )
+
+
+def _is_rotated(shape) -> bool:
+    return isinstance(shape, Simplex) and not shape.is_int_box()
+
+
 def _net_pins(board: BasicBoard, net_no: int, signal_layers) -> list[Pin]:
     return [
         pin

src/freeroute/route/grid_router.py

@@ -27,12 +27,14 @@ DRC-clean geometry, and blind/buried via spans.
 from __future__ import annotations
 
 import heapq
+import itertools
 import math
 import random
 
 from freeroute.board.board import BasicBoard
 from freeroute.board.items import ConductionArea, ObstacleArea, Pin, Via
-from freeroute.geometry import IntBox, IntPoint
+from freeroute.geometry import IntBox, IntPoint, Simplex
+from freeroute.geometry.octagon import overlaps_2d
 from freeroute.geometry.polyline import corner_box
 
 __all__ = ["GridRouter", "RouteResult", "route_board"]
@@ -123,6 +125,7 @@ class _Connection:
         "path",
         "narrow",
         "half",
+        "stubs",
     )
 
     def __init__(self, index: int, net_no: int, a: Pin, b: Pin) -> None:
@@ -138,6 +141,8 @@ class _Connection:
         self.via_cells: list[Cell] = []
         self.via_halo: list[Cell] = []
         self.halo_nodes: list[Node] = []
+        # each end's stub: its layer, its copper tiles, and the nodes it claims
+        self.stubs: list[tuple[int, list[IntBox], set[Node]]] = []
         # the pins and zones each end may use, and which pin the route ended
         # on (None when it ended on a zone)
         self.a_group: tuple[list[Pin], list] = ([a], [])
@@ -175,6 +180,7 @@ class GridRouter:
         seed: int | None = None,
         route_first: frozenset | None = None,
         access_cost: float = 0.0,
+        negotiate: int = 0,
         rollback: bool = True,
         net_widths: dict[int, int] | None = None,
         via_drill: int | None = None,
@@ -186,6 +192,15 @@ class GridRouter:
         # and the clearance around both) cost other nets this much extra, so
         # they route round a fine-pitch pin's way out instead of sealing it.
         self.access_cost = max(float(access_cost), 0.0)
+        # Negotiated congestion (PathFinder): before the real routing, every
+        # connection is routed this many times on the empty board, where routes
+        # may overlap at a price that grows where they compete. The cells that
+        # stay contested keep a history cost the real routing pays, so the first
+        # routes leave room around the places later routes have no way round.
+        self.negotiate = max(int(negotiate), 0)
+        self._history: dict[Node, float] = {}
+        self._present: dict[Node, dict[int, int]] | None = None
+        self._present_cost = 0.0
         self._doorways: dict[Node, list[tuple[int, int]]] = {}
         self._pending: dict[int, int] = {}
         # Rip-up as a transaction: the connections a rip-up route crosses are
@@ -229,7 +244,7 @@ class GridRouter:
             (dx, dy)
             for dx in range(-reach, reach + 1)
             for dy in range(-reach, reach + 1)
-            if (dx or dy) and math.hypot(dx, dy) * self.step < need
+            if (dx or dy) and max(abs(dx), abs(dy)) * self.step < need
         ]
         # A via's copper is wider than a trace. Another net's trace needs its
         # centre via_half + clearance + half_width from the via's centre, so a
@@ -268,6 +283,8 @@ class GridRouter:
         self._via_nets: dict[Cell, dict[int, int]] = {}  # routed via centres
         self._via_centres: list[IntPoint] | None = None  # cache for _hole_clear_at
         self._fixed_vias: dict[Cell, int] = {}
+        # fixed vias sit anywhere, not on cell centres: exact hole checks
+        self._fixed_holes: list[tuple[IntPoint, int]] = []
         self._fixed_via_points: set[tuple[int, IntPoint]] = set()
 
         if layers is None:
@@ -292,7 +309,10 @@ class GridRouter:
         self._zone_cells: dict[int, list[Node]] = {}
         # per-connection occupancy (owner = connection index)
         self._cell_owner: dict[Node, int] = {}
-        self._via_owner: dict[Cell, int] = {}
+        # every connection whose via covers a cell, in claim order: a via two
+        # connections share still blocks after the first of them is ripped,
+        # and a route through it must rip all of them
+        self._via_claims: dict[Cell, list[int]] = {}
         # trace halos: node -> indices of the connections claiming it
         self._halo: dict[Node, list[int]] = {}
         self._rasterize_obstacles()
@@ -301,6 +321,9 @@ class GridRouter:
             if isinstance(item, Via) and item.fixed and item.net_nos:
                 self._fixed_vias[self._cell_of(item.location)] = item.net_nos[0]
                 self._fixed_via_points.add((item.net_nos[0], item.location))
+                # its own drill, from KiCad's padstack name (Via[0-3]_500:250_um)
+                reach = self._via_drill // 2 + (item.drill or self._via_drill) // 2 + self._hole_gap
+                self._fixed_holes.append((item.location, reach))
         # Through-hole pads have holes too, and a route changes layer at one
         # for free, so no via (of any net) goes within hole spacing of one.
         # The DSN has no drill for a pad; its smaller half size stands in.
@@ -370,6 +393,19 @@ class GridRouter:
             shape.contains(IntPoint(c.x + dx, c.y + dy)) for dx in (-h, h) for dy in (-h, h)
         )
 
+    def _pad_cells(self, shape, box: IntBox, margin: int):
+        """Cells where a trace square ``margin`` wide around the centre overlaps
+        the pad: its box when it is one, else its exact (rotated) outline,
+        which is what the exact engine checks against."""
+        cells = self._cells_in_box(box, margin)
+        if not isinstance(shape, Simplex) or shape.is_int_box():
+            yield from cells
+            return
+        for cell in cells:
+            c = self._cell_center(cell)
+            if overlaps_2d(shape, IntBox(c.x - margin, c.y - margin, c.x + margin, c.y + margin)):
+                yield cell
+
     def _rasterize_obstacles(self) -> None:
         margin = self.clearance + self.half_width
         outline = self.board.outline
@@ -395,7 +431,7 @@ class GridRouter:
                     continue
                 net = item.net_nos[0] if item.net_nos else 0
                 pin_layers = [layer for layer in item.layers if layer in self.layers]
-                for cell in self._cells_in_box(box, margin):
+                for cell in self._pad_cells(item.shape, box, margin):
                     for layer in pin_layers:
                         self._pad_block.setdefault((*cell, layer), set()).add(net)
                 # Copper of the pin's own net: a trace inside it adds nothing,
@@ -494,9 +530,7 @@ class GridRouter:
         if owner is not None and conns[owner].net_no != net_no:
             blocking = owner
         else:
-            via_owner = self._via_owner.get(cell)
+            blocking = self._via_blocker(cell, net_no, conns)
-            if via_owner is not None and conns[via_owner].net_no != net_no:
-                blocking = via_owner
         if blocking is None:
             for i in self._halo.get(node, ()):
                 if conns[i].net_no != net_no:
@@ -511,6 +545,17 @@ class GridRouter:
             return None
         return self.rip_penalty * (1 + rip_count)
 
+    def _via_others(self, cell: Cell, net_no: int, conns: list[_Connection]) -> list[int]:
+        """Connections of other nets whose via covers ``cell``: all of them,
+        since two connections of a net can share one via."""
+        return [i for i in self._via_claims.get(cell, ()) if conns[i].net_no != net_no]
+
+    def _via_blocker(self, cell: Cell, net_no: int, conns: list[_Connection]) -> int | None:
+        """The other net's via connection on ``cell`` hardest to rip (the
+        penalty and the rip cap go by it), or None."""
+        others = self._via_others(cell, net_no, conns)
+        return max(others, key=lambda i: conns[i].rip_count) if others else None
+
     def _via_cells(self, cell: Cell) -> list[Cell]:
         """The cell a via sits in plus the neighbours its copper reaches."""
         r = self.via_reach
@@ -533,6 +578,26 @@ class GridRouter:
                     return False
         return self._holes_clear(cell, net_no)
 
+    def _near_path_via(self, node: Node, cell: Cell, came_from: dict) -> bool:
+        """A layer change earlier on the route that reaches ``node`` sits
+        within hole spacing of ``cell`` (and is not the same through via).
+        Committed vias are checked elsewhere; a route's own are not yet
+        committed while it is searched. Looks back far enough to cover the
+        hole spacing twice over, not along the whole route."""
+        limit = 4 * (math.ceil(self._hole_need / self.step) + 1)
+        need = self._hole_need / self.step
+        steps = 0
+        while node in came_from and steps < limit:
+            prev = came_from[node]
+            changes_layer = prev[:2] == node[:2] and prev[2] != node[2]
+            if changes_layer and node[:2] != cell and (
+                math.hypot(node[0] - cell[0], node[1] - cell[1]) < need
+            ):
+                return True
+            node = prev
+            steps += 1
+        return False
+
     def _via_nets_at(self, cell: Cell) -> set[int]:
         nets = {net for net, n in self._via_nets.get(cell, {}).items() if n > 0}
         fixed = self._fixed_vias.get(cell)
@@ -545,6 +610,12 @@ class GridRouter:
         and no through-hole pad's hole within reach at all."""
         if cell in self._tht_block:
             return False
+        if self._fixed_holes:
+            here = self._cell_center(cell)
+            for loc, reach in self._fixed_holes:
+                d = math.hypot(loc.x - here.x, loc.y - here.y)
+                if d < reach and d > self.step:  # beyond its own cell: too close
+                    return False
         if self._via_nets_at(cell) - {net_no}:
             return False
         cx, cy = cell
@@ -558,18 +629,19 @@ class GridRouter:
         return self.half_width if conn.narrow else self._net_half.get(conn.net_no, self.half_width)
 
     def _spread_for(self, half: int) -> list[tuple[int, int]]:
-        """Cells a trace of ``half`` also needs free: those whose centre is
+        """Cells a trace of ``half`` also needs free: every cell out to its
-        within its extra half width (plus half a cell, for the grid)."""
+        extra half width, rounded up to whole cells. Blocks, halos and via
+        footprints are sized for a default-width trace, and copper is checked
+        as boxes, so anything within that square could be too close."""
         extra = half - self.half_width
         if extra <= 0:
             return []
-        reach = math.ceil(extra / self.step) + 1
+        reach = math.ceil(extra / self.step)
-        limit = extra + self.step / 2
         return [
             (dx, dy)
             for dx in range(-reach, reach + 1)
             for dy in range(-reach, reach + 1)
-            if (dx or dy) and math.hypot(dx, dy) * self.step <= limit
+            if dx or dy
         ]
 
     def _halo_for(self, half: int) -> list[tuple[int, int]]:
@@ -582,7 +654,7 @@ class GridRouter:
                 (dx, dy)
                 for dx in range(-reach, reach + 1)
                 for dy in range(-reach, reach + 1)
-                if (dx or dy) and math.hypot(dx, dy) * self.step < need
+                if (dx or dy) and max(abs(dx), abs(dy)) * self.step < need
             ]
         return offsets
 
@@ -603,8 +675,8 @@ class GridRouter:
         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)
+        starts = self._group_ends(conn.a_group, conn.net_no, conns, allow_ripup)
-        goals = self._group_ends(conn.b_group, conn.net_no, conns)
+        goals = self._group_ends(conn.b_group, conn.net_no, conns, allow_ripup)
         if not starts or not goals:
             return None
         # A start that is already an end joins at once, except that ending on
@@ -625,10 +697,19 @@ class GridRouter:
         came_from: dict[Node, Node] = {}
         # a stub costs its length, so the nearest cell wins unless it is blocked
         # a pin end costs its stub; a zone or plane end is entered normally
-        goal_stub = {n: self._stub_cost(p, n) for n, p in goals.items() if isinstance(p, Pin)}
+        # (and in rip-up mode the rip penalty of whatever lies on it)
+        goal_stub = {
+            n: self._stub_cost(p, n) + self._end_penalty(p, n, net_no, allow_ripup, conns)
+            for n, p in goals.items()
+            if isinstance(p, Pin)
+        }
         for s in sorted(starts):
             pin = starts[s]
-            g_score[s] = self._stub_cost(pin, s) if isinstance(pin, Pin) else 0.0
+            g_score[s] = (
+                self._stub_cost(pin, s) + self._end_penalty(pin, s, net_no, allow_ripup, conns)
+                if isinstance(pin, Pin)
+                else 0.0
+            )
             heapq.heappush(open_heap, (g_score[s] + self._h(s, goal_cell), s))
 
         # Via footprints are checked lazily: a layer change goes on the heap as
@@ -653,6 +734,8 @@ class GridRouter:
                     pin = ends.get(node)
                     if ok and isinstance(pin, Pin) and self._walled(node):
                         ok = self._via_fits_at(pin.location, net_no)
+                if ok and self._near_path_via(source, cell, came_from):
+                    ok = False  # too close to a via earlier on this same route
                 if ok:
                     self._relax(source, target, g_via, goal_cell, g_score, came_from, open_heap)
                 continue
@@ -664,6 +747,8 @@ class GridRouter:
                     ok = via_ok.get(cell)
                     if ok is None:
                         ok = via_ok[cell] = self._via_placeable(cell, net_no, conns)
+                    if ok and self._near_path_via(current, cell, came_from):
+                        ok = False
                 else:
                     ok = True
                 if ok:
@@ -692,6 +777,8 @@ class GridRouter:
                         continue
                     if self._doorways:
                         enter += self._access(nxt, net_no)
+                    if self._history or self._present is not None:
+                        enter += self._congestion(nxt, net_no)
                 step = 1.0 if dx == 0 or dy == 0 else math.sqrt(2)
                 self._relax(
                     current, nxt, base + step + enter, goal_cell, g_score, came_from, open_heap
@@ -704,9 +791,12 @@ class GridRouter:
                     if layer == cl:
                         continue
                     nxt = (cx, cy, layer)
-                    if g_via < g_score.get(nxt, math.inf):
+                    g_layer = g_via
+                    if self._history or self._present is not None:
+                        g_layer += self._congestion(nxt, net_no)
+                    if g_layer < g_score.get(nxt, math.inf):
                         heapq.heappush(
-                            open_heap, (g_via + self._h(nxt, goal_cell), nxt, g_via, current)
+                            open_heap, (g_layer + self._h(nxt, goal_cell), nxt, g_layer, current)
                         )
         return None
 
@@ -755,24 +845,52 @@ class GridRouter:
             math.hypot(loc.x - point.x, loc.y - point.y) < reach for loc, reach in self._tht_holes
         )
 
+    def _stub_points(self, pin_location: IntPoint, cell: Cell) -> list[IntPoint]:
+        """The stub's corners, from the pin to its cell centre.
+
+        The direct segment is fine for 45-degree routing. Orthogonal routing
+        leaves the pin straight along the axis it is further off the cell on
+        and jogs across to the centre at the end: an L of two flush boxes,
+        which is what the exact check sees. A single slanted segment is
+        checked as its bounding box there, and a 1 mm trace to a column
+        0.1 mm off a 1.27 mm pitch pin's centreline then lands inside the
+        clearance of the pad next door, though the straight exit clears it.
+        """
+        end = self._cell_center(cell)
+        dx, dy = end.x - pin_location.x, end.y - pin_location.y
+        if not self._orthogonal or dx == 0 or dy == 0:
+            return [pin_location, end]
+        if abs(dx) >= abs(dy):
+            return [pin_location, IntPoint(end.x, pin_location.y), end]
+        return [pin_location, IntPoint(pin_location.x, end.y), end]
+
     def _stub_cells(self, pin_location: IntPoint, cell: Cell, half: int | None = None) -> list[Cell]:
         """Cells where another net's trace would come too close to the stub."""
         from freeroute.board.outline import _point_segment
 
-        end = self._cell_center(cell)
+        points = self._stub_points(pin_location, cell)
+        end = points[-1]
         reach = (half or self._cur_half) + self.half_width + self.clearance
         box = IntBox(
             min(pin_location.x, end.x), min(pin_location.y, end.y),
             max(pin_location.x, end.x), max(pin_location.y, end.y),
         )
+        legs = list(zip(points, points[1:], strict=False))
         return [
             c
             for c in self._cells_in_box(box, reach)
-            if _point_segment(self._cell_center(c), pin_location, end) < reach
+            if min(_point_segment(self._cell_center(c), a, b) for a, b in legs) < reach
         ]
 
     def _stub_clear(
-        self, pin: Pin, cell: Cell, layer: int, net_no: int, conns, keepouts_only: bool = False
+        self,
+        pin: Pin,
+        cell: Cell,
+        layer: int,
+        net_no: int,
+        conns,
+        keepouts_only: bool = False,
+        allow_ripup: bool = False,
     ) -> bool:
         keepouts = self._keepout_boxes.get(layer)
         if keepouts:
@@ -780,9 +898,9 @@ class GridRouter:
             # engine will: its copper grown by clearance must miss every keepout
             from freeroute.geometry.polyline import Polyline, PolylineShape
 
-            end = self._cell_center(cell)
+            points = self._stub_points(pin.location, cell)
-            if end != pin.location:
+            if points[-1] != pin.location:
-                for tile in PolylineShape(Polyline([pin.location, end]), self._cur_half).tiles():
+                for tile in PolylineShape(Polyline(points), self._cur_half).tiles():
                     grown = tile.offset(self.clearance)
                     if any(k.overlaps(grown if needs else tile) for k, needs in keepouts):
                         return False
@@ -792,14 +910,58 @@ class GridRouter:
                     return False
         if keepouts_only:
             return True
-        for c in self._stub_cells(pin.location, cell):
+        owners = self._stub_owners(pin, cell, layer, net_no, conns)
-            owner = self._cell_owner.get((*c, layer))
+        # in rip-up mode a route on the stub is one more to rip, unless it may not be
-            if owner is not None and conns[owner].net_no != net_no:
+        return not owners or (
-                return False
+            allow_ripup and all(conns[i].rip_count < self.rip_cap for i in owners)
-            via_owner = self._via_owner.get(c)
+        )
-            if via_owner is not None and conns[via_owner].net_no != net_no:
+
-                return False
+    def _stub_tiles(self, pin_location: IntPoint, cell: Cell, half: int) -> list[IntBox]:
-        return True
+        """The stub's copper: its legs, and a square at each corner and at the
+        cell end, where the route carries on."""
+        points = self._stub_points(pin_location, cell)
+        tiles = [corner_box(point, half) for point in points[1:]]
+        if len(points) > 1 and points[-1] != pin_location:
+            from freeroute.geometry.polyline import Polyline, PolylineShape
+
+            tiles += PolylineShape(Polyline(points), half).tiles()
+        return tiles
+
+    def _stub_owners(
+        self, pin: Pin, cell: Cell, layer: int, net_no: int, conns, half: int | None = None
+    ) -> set[int]:
+        """Other nets' routes whose copper the stub from ``pin`` to ``cell`` would touch."""
+        owners: set[int] = set()
+        grown = None
+        for c in self._stub_cells(pin.location, cell, half):
+            node = (*c, layer)
+            owner = self._cell_owner.get(node)
+            if owner is not None and conns[owner].net_no != net_no and owner not in owners:
+                # Both stubs are off the grid, and each claims the cells a
+                # trace centred there would crowd, so two stubs side by side
+                # (neighbouring pins leaving straight) overlap in claims well
+                # before their copper comes near. Check those exactly.
+                other = [tiles for lay, tiles, nodes in conns[owner].stubs if node in nodes]
+                if other:
+                    if grown is None:
+                        grown = [
+                            t.offset(self.clearance)
+                            for t in self._stub_tiles(pin.location, cell, half or self._cur_half)
+                        ]
+                    if not any(g.overlaps(t) for tiles in other for t in tiles for g in grown):
+                        continue
+                owners.add(owner)
+            owners.update(self._via_others(c, net_no, conns))
+        return owners
+
+    def _end_penalty(self, pin: Pin, node: Node, net_no: int, allow_ripup: bool, conns) -> float:
+        """Rip-up cost of starting or ending on ``node``: the routes on its
+        cell and on the stub to it, each at the penalty entering it would cost."""
+        if not allow_ripup:
+            return 0.0
+        owners = self._stub_owners(pin, node[:2], node[2], net_no, conns)
+        owners |= self._crossed_owners([node], net_no, conns)
+        return sum(self.rip_penalty * (1 + conns[i].rip_count) for i in owners)
 
     def _zone_nodes(self, zone) -> list[Node]:
         """Cells of a zone where a via of this net fits inside its copper; for a
@@ -847,11 +1009,13 @@ class GridRouter:
                 return zone.name or "zone"
         return ""
 
-    def _group_ends(self, group, net_no: int, conns) -> dict[Node, Pin | None]:
+    def _group_ends(
+        self, group, net_no: int, conns, allow_ripup: bool = False
+    ) -> dict[Node, Pin | None]:
         """End nodes of a group, each mapped to its pin (None for a zone cell)."""
         ends: dict[Node, Pin | None] = {}
         for pin in group[0]:
-            for node in sorted(self._end_nodes(pin, net_no, conns)):
+            for node in sorted(self._end_nodes(pin, net_no, conns, allow_ripup)):
                 ends.setdefault(node, pin)
         for zone in group[1]:
             plane = zone.layer in self._power_layers
@@ -873,10 +1037,13 @@ class GridRouter:
             return (dx + dy) / self.step
         return math.hypot(dx, dy) / self.step
 
-    def _end_nodes(self, pin: Pin, net_no: int, conns) -> set[Node]:
+    def _end_nodes(self, pin: Pin, net_no: int, conns, allow_ripup: bool = False) -> set[Node]:
         """Nodes a route may start or end on for ``pin``: the nearest cell and
         its neighbours, where the cell is enterable and the stub to it is clear.
-        A crowded fine-pitch pin gets more than one way out."""
+        A crowded fine-pitch pin gets more than one way out. In rip-up mode a
+        cell or stub another route is on counts as enterable, as it does
+        everywhere else, or a pin whose only way out another net has taken
+        could never have it back."""
         layers = [layer for layer in pin.layers if layer in self.layers]
         cx, cy = self._cell_of(pin.location)
         nodes: set[Node] = set()
@@ -885,16 +1052,16 @@ class GridRouter:
             if not (0 <= cell[0] < self.cols and 0 <= cell[1] < self.rows):
                 continue
             for layer in layers:
-                if (dx or dy) and self._enter_cost(cell, layer, net_no, False, conns) is None:
+                if (dx or dy) and self._enter_cost(cell, layer, net_no, allow_ripup, conns) is None:
                     continue
-                if self._stub_clear(pin, cell, layer, net_no, conns):
+                if self._stub_clear(pin, cell, layer, net_no, conns, allow_ripup=allow_ripup):
                     nodes.add((*cell, layer))
         # Also offer exact escape stubs: a fine-pitch pin's nearby cells can be
         # a pocket inside its own pad that leads nowhere (the grid columns miss
         # the narrow legal band past the pad tip). The stub's length is its
         # cost, so it is only taken where a short step would not do.
         if self._orthogonal and self._crowded(pin, net_no) and self._trapped(pin, net_no, nodes):
-            nodes |= self._escape_nodes(pin, net_no, conns, layers, (cx, cy))
+            nodes |= self._escape_nodes(pin, net_no, conns, layers, (cx, cy), allow_ripup)
         if not nodes:  # nothing clear: fall back to the nearest cell, as before
             nodes = {(cx, cy, layer) for layer in layers}
             if self._keepout_boxes and not any(
@@ -960,14 +1127,16 @@ class GridRouter:
         self._trapped_cache[key] = trapped
         return trapped
 
-    def _escape_nodes(self, pin: Pin, net_no: int, conns, layers, origin: Cell) -> set[Node]:
+    def _escape_nodes(
+        self, pin: Pin, net_no: int, conns, layers, origin: Cell, allow_ripup: bool = False
+    ) -> set[Node]:
         """For a pin walled in on the grid (a fine-pitch pin whose legal band
         the grid columns miss): look along each axis for the first open cell
-        whose straight stub from the pin clears every other net's pad by the
+        whose stub from the pin clears every other net's pad by the full
-        full margin, measured exactly rather than on the grid."""
+        clearance, checked on the stub's copper tiles as the exact engine
-        from freeroute.board.outline import _segment_box
+        will rather than on the grid."""
+        from freeroute.geometry.polyline import Polyline, PolylineShape
 
-        margin = self.half_width + self.clearance
         reach = self._escape_cells
         near = [
             (p.shape.bounding_box(), set(p.layers))
@@ -979,24 +1148,33 @@ class GridRouter:
         ]
         cx, cy = origin
         nodes: set[Node] = set()
-        for dx, dy in _NEIGHBOURS[:4]:
+        # the pin's own column or row and the one either side: two pins side
+        # by side can then jog apart at the end of their straight exits
+        for (dx, dy), side in itertools.product(_NEIGHBOURS[:4], (0, -1, 1)):
+            sx, sy = (side, 0) if dx == 0 else (0, side)
+            nodes_before = len(nodes)
             for k in range(2, reach + 1):
-                cell = (cx + dx * k, cy + dy * k)
+                cell = (cx + dx * k + sx, cy + dy * k + sy)
                 if not (0 <= cell[0] < self.cols and 0 <= cell[1] < self.rows):
                     break
-                end = self._cell_center(cell)
+                grown = [
+                    tile.offset(self.clearance)
+                    for tile in PolylineShape(
+                        Polyline(self._stub_points(pin.location, cell)), self._cur_half
+                    ).tiles()
+                ]
                 for layer in layers:
-                    if self._enter_cost(cell, layer, net_no, False, conns) is None:
+                    if self._enter_cost(cell, layer, net_no, allow_ripup, conns) is None:
                         continue
                     if any(
-                        layer in box_layers and _segment_box(pin.location, end, box) < margin
+                        layer in box_layers and any(g.overlaps(box) for g in grown)
                         for box, box_layers in near
                     ):
                         continue
-                    if self._stub_clear(pin, cell, layer, net_no, conns):
+                    if self._stub_clear(pin, cell, layer, net_no, conns, allow_ripup=allow_ripup):
                         nodes.add((*cell, layer))
-                if any(n[:2] == cell for n in nodes):
+                if len(nodes) > nodes_before:
-                    break  # the first open cell along this axis is enough
+                    break  # the first open cell along this line is enough
         return nodes
 
     def _relax(self, current, nxt, tentative, goal_cell, g_score, came_from, open_heap):
@@ -1046,19 +1224,24 @@ class GridRouter:
         conn.via_halo = []
         for cell in conn.via_cells:
             for c in self._via_cells(cell):
-                if c not in self._via_owner:
+                claims = self._via_claims.setdefault(c, [])
-                    self._via_owner[c] = conn.index
+                if conn.index not in claims:
+                    claims.append(conn.index)
                     conn.via_halo.append(c)
         ends = ((conn.a_end, wire_segs[0], 0), (conn.b_end, wire_segs[-1], -1)) if wire_segs else ()
+        conn.stubs = []
         for pin, (layer, cells), at in ends:
             if not isinstance(pin, Pin):
                 continue  # ended on a zone or a plane: no stub
             cell = cells[at]
+            claimed: set[Node] = set()
             for c in self._stub_cells(pin.location, cell, half):
                 node = (*c, layer)
                 if node not in self._cell_owner:
                     self._cell_owner[node] = conn.index
                     conn.trace_cells.append((c, layer))
+                    claimed.add(node)
+            conn.stubs.append((layer, self._stub_tiles(pin.location, cell, half), claimed))
         # A pin inside a wire keepout can only leave by a via. Its stub to the
         # cell centre would be track inside the keepout, so the via goes on
         # the pin itself (a via in its own pad) and the stub is left out.
@@ -1076,9 +1259,9 @@ class GridRouter:
                 continue
             points = [self._cell_center(c) for c in cells]
             if idx == 0 and isinstance(conn.a_end, Pin):
-                points.insert(0, conn.a_end.location)
+                points[0:0] = self._stub_points(conn.a_end.location, cells[0])[:-1]
             if idx == len(wire_segs) - 1 and isinstance(conn.b_end, Pin):
-                points.append(conn.b_end.location)
+                points.extend(self._stub_points(conn.b_end.location, cells[-1])[-2::-1])
             points = _simplify(points)
             if len(points) >= 2:
                 conn.wires.append((layer, points))
@@ -1094,8 +1277,11 @@ class GridRouter:
             if self._cell_owner.get((*cell, layer)) == conn.index:
                 del self._cell_owner[(*cell, layer)]
         for cell in conn.via_halo:
-            if self._via_owner.get(cell) == conn.index:
+            claims = self._via_claims.get(cell)
-                del self._via_owner[cell]
+            if claims is not None and conn.index in claims:
+                claims.remove(conn.index)
+            if claims is not None and not claims:
+                del self._via_claims[cell]
         conn.via_halo = []
         for node in conn.halo_nodes:
             claims = self._halo.get(node)
@@ -1105,6 +1291,7 @@ class GridRouter:
                     del self._halo[node]
         conn.halo_nodes = []
         conn.trace_cells = []
+        conn.stubs = []
         for cell in conn.via_cells:
             count = self._via_nets.get(cell)
             if count and count.get(conn.net_no):
@@ -1118,15 +1305,26 @@ class GridRouter:
         conn.rip_count += 1
         self._settle(conn, +1)
 
-    def _crossed_owners(self, path: list[Node], net_no: int, conns: list[_Connection]) -> set[int]:
+    def _crossed_owners(
+        self, path: list[Node], net_no: int, conns: list[_Connection], spread=None
+    ) -> set[int]:
+        """Connections whose copper or clearance ``path`` crosses; a trace
+        wider than the default crosses them on its ``spread`` cells too."""
+        spread = self._spread if spread is None else spread
+        if spread:
+            path = list(
+                dict.fromkeys(
+                    (x + dx, y + dy, layer)
+                    for x, y, layer in path
+                    for dx, dy in ((0, 0), *spread)
+                )
+            )
         owners: set[int] = set()
         for cx, cy, cl in path:
             owner = self._cell_owner.get((cx, cy, cl))
             if owner is not None and conns[owner].net_no != net_no:
                 owners.add(owner)
-            via_owner = self._via_owner.get((cx, cy))
+            owners.update(self._via_others((cx, cy), net_no, conns))
-            if via_owner is not None and conns[via_owner].net_no != net_no:
-                owners.add(via_owner)
             for i in self._halo.get((cx, cy, cl), ()):
                 if conns[i].net_no != net_no:
                     owners.add(i)
@@ -1176,6 +1374,74 @@ class GridRouter:
                 return self.access_cost
         return 0.0
 
+    # --- negotiated congestion --------------------------------------------
+
+    def _congestion(self, node: Node, net_no: int) -> float:
+        """History of a contested cell, plus while negotiating the price of
+        sharing it with the other nets on it now."""
+        cost = self._history.get(node, 0.0)
+        if self._present is not None:
+            users = self._present.get(node)
+            if users:
+                others = len(users) - (1 if net_no in users else 0)
+                cost += self._present_cost * others
+        return cost
+
+    def _footprint(self, path: list[Node]) -> set[Node]:
+        """The nodes a route claims: its cells and their clearance halo on
+        its layer, and every via's footprint on all layers."""
+        wire_segs, via_cells = _split_path(path)
+        halo = [(0, 0), *self._halo_offsets]
+        nodes: set[Node] = set()
+        for layer, cells in wire_segs:
+            for cx, cy in cells:
+                for dx, dy in halo:
+                    nodes.add((cx + dx, cy + dy, layer))
+        for cell in via_cells:
+            for c in self._via_cells(cell):
+                for layer in self.layers:
+                    nodes.add((*c, layer))
+        return nodes
+
+    def _negotiate(self, order: list[_Connection], conns: list[_Connection]) -> None:
+        """Route every connection on the empty board ``self.negotiate`` times,
+        letting routes share cells at a price: the number of other nets on a
+        cell times a factor that doubles every round, plus the cell's history,
+        which grows by one for every extra net each round it stays shared.
+        Only the history is kept; the board is left empty."""
+        present: dict[Node, dict[int, int]] = {}
+        claimed: dict[int, set[Node]] = {}
+        ends = [(c, c.a_end, c.b_end) for c in conns]
+        self._present, self._present_cost = present, 0.5
+        try:
+            for _ in range(self.negotiate):
+                for conn in order:
+                    for node in claimed.pop(conn.index, ()):
+                        users = present[node]
+                        users[conn.net_no] -= 1
+                        if not users[conn.net_no]:
+                            del users[conn.net_no]
+                    path = self._search(conn, allow_ripup=False, conns=conns)
+                    if path is None:
+                        continue
+                    nodes = self._footprint(path)
+                    claimed[conn.index] = nodes
+                    for node in nodes:
+                        users = present.setdefault(node, {})
+                        users[conn.net_no] = users.get(conn.net_no, 0) + 1
+                shared = 0
+                for node, users in present.items():
+                    if len(users) > 1:
+                        shared += 1
+                        self._history[node] = self._history.get(node, 0.0) + len(users) - 1
+                if not shared:
+                    break
+                self._present_cost *= 2
+        finally:
+            self._present = None
+            for conn, a_end, b_end in ends:  # the search picks ends; undo that
+                conn.a_end, conn.b_end = a_end, b_end
+
     # --- passes -------------------------------------------------------------
 
     def route(self) -> RouteResult:
@@ -1199,6 +1465,8 @@ class GridRouter:
         if self.route_first:
             # stable: the promoted keep their order among themselves, as do the rest
             order.sort(key=lambda c: (c.net_no, *_ends_of(c)) not in self.route_first)
+        if self.negotiate:
+            self._negotiate(order, conns)
         for _ in range(passes):
             changed = False
             for conn in order:
@@ -1237,7 +1505,16 @@ class GridRouter:
             path = self._search(conn, allow_ripup=True, conns=conns)
             if path is None:
                 return False
-            victims = [conns[i] for i in sorted(self._crossed_owners(path, conn.net_no, conns))]
+            crossed = self._crossed_owners(
+                path, conn.net_no, conns, self._spread_for(self._conn_half(conn))
+            )
+            # and the routes on the stubs from the pins to the path's ends
+            for end, node in ((conn.a_end, path[0]), (conn.b_end, path[-1])):
+                if isinstance(end, Pin):
+                    crossed |= self._stub_owners(
+                        end, node[:2], node[2], conn.net_no, conns, self._conn_half(conn)
+                    )
+            victims = [conns[i] for i in sorted(crossed)]
             if self.rollback:
                 return self._ripup_transaction(conn, path, victims, conns)
             for victim in victims:
@@ -1586,6 +1863,7 @@ def route_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     rollback: bool = True,
     net_widths: dict[int, int] | None = None,
     via_drill: int | None = None,
@@ -1608,6 +1886,7 @@ def route_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
         net_widths=net_widths,
         via_drill=via_drill,

src/freeroute/route/pipeline.py

@@ -118,6 +118,7 @@ def route_dsn_board(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
 ) -> tuple[RouteResult, int, list[str]]:
@@ -143,6 +144,7 @@ def route_dsn_board(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
         net_widths=_net_widths_board(dsn, scale),
         via_drill=_via_drill_board(dsn, scale),
@@ -196,6 +198,7 @@ def build_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
 ) -> RoutingResult:
@@ -205,6 +208,7 @@ def build_routing_result(
         edge_clearance_mm=edge_clearance_mm, resolution=resolution, seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         hole_to_hole_mm=hole_to_hole_mm,
         rollback=rollback,
     )
@@ -225,6 +229,7 @@ def route_dsn_board_exact(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
 ) -> tuple[ExactRouteResult, int, list[str]]:
@@ -254,6 +259,7 @@ def route_dsn_board_exact(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         rollback=rollback,
         net_widths=_net_widths_board(dsn, scale),
         via_drill=_via_drill_board(dsn, scale),
@@ -276,6 +282,7 @@ def build_exact_routing_result(
     seed: int | None = None,
     route_first: frozenset | None = None,
     access_cost: float = 0.0,
+    negotiate: int = 0,
     hole_to_hole_mm: float = 0.25,
     rollback: bool = True,
 ) -> RoutingResult:
@@ -293,6 +300,7 @@ def build_exact_routing_result(
         seed=seed,
         route_first=route_first,
         access_cost=access_cost,
+        negotiate=negotiate,
         hole_to_hole_mm=hole_to_hole_mm,
         rollback=rollback,
     )

tests/route/test_fixed_wiring.py

@@ -91,3 +91,18 @@ def test_a_fanned_out_signal_is_routed_from_its_via():
     assert sig in exact.result.routed_net_numbers
     assert not exact.result.vias.get(sig), "the fan-out via is already there"
     assert {names[layer] for layer, _ in exact.result.wires[sig]} == {"B.Cu"}
+
+
+def test_the_session_never_repeats_copper_already_on_the_board():
+    # the JAR writes the DSN's wiring back into its session, and an applier
+    # then adds it a second time on top of itself; freeroute writes only
+    # what it routed
+    from freeroute.route.pipeline import build_exact_routing_result
+
+    fixed_vias = {(5000.0, -11500.0), (10000.0, -11500.0)}
+    fixed_paths = {(5000.0, -10000.0, 5000.0, -11500.0), (10000.0, -10000.0, 10000.0, -11500.0),
+                   (2000.0, -2000.0, 8000.0, -2000.0)}
+    result = build_exact_routing_result(parse_dsn(_FANOUT), resolution=2)
+    for net in result.nets:
+        assert not {(v.x, v.y) for v in net.vias} & fixed_vias
+        assert not {tuple(w.coords) for w in net.wires} & fixed_paths

tests/route/test_grid_exact_agreement.py

@@ -0,0 +1,284 @@
+"""The grid must not believe copper legal that the exact check then refuses.
+
+Each case is one way the two used to disagree on roomba-ESP12E: a rotated oval
+pad modelled as an inflated box (and opened to its own net), a via shared by
+two connections of a net losing its footprint when one of them is ripped, and
+a wider net class searched as if it were the default width.
+"""
+
+from __future__ import annotations
+
+import math
+
+import pytest
+
+from freeroute.board import build_board
+from freeroute.dsn import parse_dsn
+from freeroute.geometry import IntBox, Simplex
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import (
+    _rule_clearance_dsn,
+    _rule_width_dsn,
+    _via_half_board,
+    build_exact_routing_result,
+)
+
+# --- rotated oval pads -------------------------------------------------------
+
+
+def _socket_dsn(rotation: float, layout: str) -> str:
+    """A 1x4 2.54 mm socket strip (rect pin 1, oval pins 2-4) at ``rotation``,
+    each pin its own net, routed to a small SMD pad 0.9 mm away."""
+    cx, cy = 100000, -100000
+    t = math.radians(rotation)
+    ax = (math.cos(t), math.sin(t))
+    perp = (-math.sin(t), math.cos(t))
+    places = []
+    for i in range(4):
+        px, py = cx + 2540 * i * ax[0], cy + 2540 * i * ax[1]
+        side = 1 if i % 2 == 0 else -1
+        if layout == "y":
+            tx, ty = px, py + side * 9000
+        else:
+            tx, ty = px + side * 8000 * perp[0], py + side * 8000 * perp[1]
+        places.append(f"(place T{i + 1} {round(tx)} {round(ty)} front 0)")
+    nets = " ".join(f"(net N{i} (pins P3-{i + 1} T{i + 1}-1))" for i in range(4))
+    return f"""(pcb socket (parser) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal)) (layer B.Cu (type signal))
+    (boundary (path pcb 0  125000 -115000  85000 -115000  85000 -75000  125000 -75000
+      125000 -115000))
+    (via "Via[0-1]_800:400_um")
+    (rule (width 300) (clearance 250)))
+  (placement
+    (component S (place P3 {cx} {cy} front {rotation}))
+    (component T {" ".join(places)}))
+  (library
+    (image S (pin R 1 0 0) (pin O 2 2540 0) (pin O 3 5080 0) (pin O 4 7620 0))
+    (image T (pin t 1 0 0))
+    (padstack O (shape (path F.Cu 1727.2 0 -152.4 0 152.4))
+      (shape (path B.Cu 1727.2 0 -152.4 0 152.4)) (attach off))
+    (padstack R (shape (rect F.Cu -863.6 -1016 863.6 1016))
+      (shape (rect B.Cu -863.6 -1016 863.6 1016)) (attach off))
+    (padstack t (shape (rect F.Cu -500 -500 500 500)) (attach off))
+    (padstack "Via[0-1]_800:400_um" (shape (circle F.Cu 800)) (shape (circle B.Cu 800))
+      (attach off)))
+  (network {nets}
+    (class c N0 N1 N2 N3 (circuit (use_via "Via[0-1]_800:400_um"))
+      (rule (width 300) (clearance 250)))))"""
+
+
+def test_a_rotated_oval_pad_is_its_outline_not_its_bounding_box():
+    board = build_board(parse_dsn(_socket_dsn(60, "y")))
+    oval = next(p for p in board.get_pins() if p.component_ref == "P3" and p.name == "2")
+    assert isinstance(oval.shape, Simplex) and not oval.shape.is_int_box()
+    box = oval.shape.bounding_box()
+    assert oval.shape.contains(oval.location)
+    assert not oval.shape.contains(box.ll) and not oval.shape.contains(box.ur)
+
+
+@pytest.mark.parametrize("layout", ["y", "perp"])
+def test_routes_leaving_a_rotated_socket_pass_the_exact_check(layout):
+    result = build_exact_routing_result(
+        parse_dsn(_socket_dsn(60, layout)), resolution=2, shove=True
+    )
+    assert result.unrouted == []
+
+
+# --- a via two connections share --------------------------------------------
+
+_SHARED_VIA = """(pcb shared (parser) (resolution um 10) (unit um)
+  (structure
+    (layer Top (type signal)) (layer Bottom (type signal))
+    (boundary (path pcb 0  0 0  20000 0  20000 -20000  0 -20000  0 0))
+    (via "Via[0-1]_800:400_um")
+    (rule (width 300) (clearance 250)))
+  (library
+    (padstack p (shape (rect Top -400 -400 400 400)) (attach off))
+    (padstack "Via[0-1]_800:400_um" (shape (circle Top 800)) (shape (circle Bottom 800))
+      (attach off))
+    (image PAD (pin p 1 0 0)))
+  (placement (component PAD
+    (place G1 3000 -5000 front 0) (place G2 3000 -15000 front 0)
+    (place G3 17000 -10000 front 0) (place S1 3000 -10000 front 0)
+    (place S2 17000 -3000 front 0)))
+  (network (net GND (pins G1-1 G2-1 G3-1)) (net SIG (pins S1-1 S2-1))))"""
+
+
+def _line(a, b, layer):
+    (x, y), (x1, y1) = a, b
+    out = [(x, y, layer)]
+    while x != x1:
+        x += 1 if x1 > x else -1
+        out.append((x, y, layer))
+    while y != y1:
+        y += 1 if y1 > y else -1
+        out.append((x, y, layer))
+    return out
+
+
+def test_a_shared_via_keeps_its_footprint_when_one_user_is_ripped():
+    dsn = parse_dsn(_SHARED_VIA)
+    s = dsn.resolution.value
+    router = GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        via_half=_via_half_board(dsn, s),
+    )
+    conns = router._conns = router._build_connections()
+    gnd = [c for c in conns if len({c.a.component_ref, c.b.component_ref} & {"G1", "G2", "G3"})]
+    sig = next(c for c in conns if c not in gnd)
+    first, second = gnd
+    g3 = router._cell_of(next(p for p in router.board.get_pins() if p.component_ref == "G3").location)
+    via = (g3[0] - 10, g3[1])
+
+    def through_via(conn):
+        a, b = router._cell_of(conn.a.location), router._cell_of(conn.b.location)
+        return _line(a, via, 0) + _line(via, b, 1)
+
+    router._commit(first, through_via(first))
+    router._commit(second, through_via(second))
+    footprint = [c for c in router._via_cells(via) if c != via]
+    router._rip(first)
+
+    assert second.routed and via in second.via_cells
+    assert all(router._via_claims.get(c) == [second.index] for c in footprint)
+    # another net still keeps its distance from the via that is left
+    assert all(router._enter_cost_base(c, 0, sig.net_no, False, conns) is None for c in footprint)
+
+
+def test_a_route_through_a_shared_via_rips_every_user():
+    """Two connections of a net share a via. Another net routed through it
+    in rip-up mode has to rip both, or the one left keeps its via under the
+    new trace and the exact check throws one of them out."""
+    dsn = parse_dsn(_SHARED_VIA)
+    s = dsn.resolution.value
+    router = GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        via_half=_via_half_board(dsn, s),
+    )
+    conns = router._conns = router._build_connections()
+    gnd = [c for c in conns if len({c.a.component_ref, c.b.component_ref} & {"G1", "G2", "G3"})]
+    sig = next(c for c in conns if c not in gnd)
+    first, second = gnd
+    g3 = router._cell_of(next(p for p in router.board.get_pins() if p.component_ref == "G3").location)
+    via = (g3[0] - 10, g3[1])
+
+    def through_via(conn):
+        a, b = router._cell_of(conn.a.location), router._cell_of(conn.b.location)
+        return _line(a, via, 0) + _line(via, b, 1)
+
+    router._commit(first, through_via(first))
+    router._commit(second, through_via(second))
+    # the via's copper alone: footprint cells no trace or trace halo covers
+    crossing = [
+        node
+        for c in router._via_cells(via)
+        for node in ((*c, 0), (*c, 1))
+        if node not in router._cell_owner and node not in router._halo
+    ]
+    assert crossing
+
+    assert router._crossed_owners(crossing, sig.net_no, conns) == {first.index, second.index}
+
+
+# --- a wider net class --------------------------------------------------------
+
+_WIDE = """(pcb wide (parser) (resolution um 10) (unit um)
+  (structure
+    (layer F.Cu (type signal))
+    (boundary (path pcb 0  0 0  20000 0  20000 -10000  0 -10000  0 0))
+    (rule (width 300) (clearance 250)))
+  (placement (component S (place P1 2000 -5000 front 0) (place P2 18000 -5000 front 0)
+     (place Q1 10000 {ylo} front 0) (place Q2 10000 {yhi} front 0)
+     (place Q3 10000 -1000 front 0) (place Q4 10000 -9000 front 0)))
+  (library (image S (pin pad 1 0 0)) (padstack pad (shape (rect F.Cu -600 -600 600 600)) (attach off)))
+  (network (net PWR (pins P1-1 P2-1)) (net SIG (pins Q1-1 Q3-1)) (net SIG2 (pins Q2-1 Q4-1))
+    (class Power PWR (rule (width 500) (clearance 250)))))"""
+
+
+@pytest.mark.parametrize("resolution", [1, 2])
+@pytest.mark.parametrize("gap", [900, 1000, 1075])
+def test_a_wide_net_past_pads_it_does_not_fit_between_is_not_refused(gap, resolution):
+    # 0.3 mm fits the gap between the two pads, 0.5 mm does not: the grid
+    # must see that, rather than lay it wide and have the exact check drop it
+    ylo, yhi = -5000 - gap // 2 - 600, -5000 + gap // 2 + 600
+    result = build_exact_routing_result(
+        parse_dsn(_WIDE.format(ylo=ylo, yhi=yhi)), resolution=resolution
+    )
+    assert result.unrouted == []
+
+
+def _wide_router():
+    dsn = parse_dsn(_WIDE.format(ylo=-6050, yhi=-3950))
+    s = dsn.resolution.value
+    pwr = next(i for i, net in enumerate(dsn.nets, 1) if net.name == "PWR")
+    return GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        resolution=2,
+        net_widths={pwr: 5000},
+    ), pwr
+
+
+def test_a_wide_trace_keeps_clear_of_a_default_one_at_the_grid_diagonal():
+    router, _pwr = _wide_router()
+    # 0.5 mm against 0.3 mm needs 0.25 + 0.25 + 0.15 = 0.65 mm between centres,
+    # on either axis, since the exact check compares boxes
+    need = 2500 + router.clearance + router.half_width
+    for dx, dy in [(2, 2), (2, 1), (1, 2)]:
+        assert max(dx, dy) * router.step < need
+        assert (dx, dy) in router._halo_for(2500)
+
+
+def test_a_wide_rip_up_route_counts_what_its_extra_width_crosses():
+    router, pwr_net = _wide_router()
+    conns = router._conns = router._build_connections()
+    pwr = next(c for c in conns if c.net_no == pwr_net)
+    other = next(c for c in conns if c.net_no != pwr_net)
+    # a default-width trace two cells from the wide route's path
+    x, y = 20, 5
+    router._commit(other, _line((x - 3, y + 2), (x + 3, y + 2), 0))
+    path = _line((x - 3, y), (x + 3, y), 0)
+    spread = router._spread_for(2500)
+    assert other.index not in router._crossed_owners(path, pwr.net_no, conns)
+    assert other.index in router._crossed_owners(path, pwr.net_no, conns, spread)
+
+
+def test_a_pad_cell_check_uses_the_rotated_outline():
+    board = build_board(parse_dsn(_socket_dsn(60, "y")))
+    router = GridRouter(board, trace_width=3000, clearance=2500, resolution=2)
+    oval = next(p for p in board.get_pins() if p.component_ref == "P3" and p.name == "2")
+    box = oval.shape.bounding_box()
+    margin = router.clearance + router.half_width
+    exact = set(router._pad_cells(oval.shape, box, margin))
+    boxed = set(router._cells_in_box(box, margin))
+    assert exact < boxed
+    for cell in boxed - exact:
+        c = router._cell_center(cell)
+        square = IntBox(c.x - margin, c.y - margin, c.x + margin, c.y + margin)
+        assert oval.shape.intersection(square).dimension() != 2
+
+
+def test_a_via_by_a_chamfered_corner_is_judged_round():
+    """The grid keeps a via's centre its radius plus the edge clearance from
+    the outline. The exact check used the via's square, whose corner reaches
+    past a 45-degree chamfer where the round via does not."""
+    from freeroute.board.outline import BoardOutline
+    from freeroute.geometry import IntBox, IntPoint
+    from freeroute.route.exact_router import _inside_outline
+
+    # a 10 mm square with its lower-left corner cut at 45 degrees
+    outline = BoardOutline([IntPoint(*p) for p in
+                            [(30, 0), (100, 0), (100, 100), (0, 100), (0, 30)]])
+    half, edge = 4, 1
+    via = IntPoint(19, 20)  # its centre 6.4 from the chamfer x + y = 30
+    square = IntBox(via.x - half, via.y - half, via.x + half, via.y + half)
+    assert not outline.box_clear(square, edge)  # the square's corner: 0.7 away
+    assert _inside_outline(outline, [], [via], half + edge, edge)
+    # 4.2 from the chamfer: the round via itself is too close
+    assert not _inside_outline(outline, [], [IntPoint(18, 18)], half + edge, edge)

tests/route/test_negotiate.py

@@ -0,0 +1,65 @@
+"""--negotiate: PathFinder-style rounds on the empty board before routing."""
+
+from __future__ import annotations
+
+from pathlib import Path
+
+import pytest
+
+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, route_dsn_board
+
+FIXTURES = Path(__file__).resolve().parent.parent / "dsn" / "fixtures"
+
+
+def _router(name, negotiate):
+    dsn = parse_dsn((FIXTURES / name).read_text())
+    s = dsn.resolution.value
+    return GridRouter(
+        build_board(dsn),
+        trace_width=round(_rule_width_dsn(dsn) * s),
+        clearance=round(_rule_clearance_dsn(dsn) * s),
+        negotiate=negotiate,
+    )
+
+
+def test_negotiation_leaves_the_board_empty_and_the_ends_as_they_were():
+    router = _router("true_density.dsn", 3)
+    conns = router._conns = router._build_connections()
+    ends = [(c.a_end, c.b_end) for c in conns]
+    router._negotiate(list(conns), conns)
+    assert router._history  # a dense board has contested cells
+    assert not router._cell_owner and not router._halo and not router._via_claims
+    assert not any(c.routed for c in conns)
+    assert [(c.a_end, c.b_end) for c in conns] == ends
+    assert router._present is None
+
+
+def test_sharing_is_priced_only_for_other_nets():
+    router = _router("true_density.dsn", 1)
+    node = (3, 4, 0)
+    router._history[node] = 2.0
+    router._present, router._present_cost = {node: {7: 1, 9: 2}}, 0.5
+    assert router._congestion(node, 7) == pytest.approx(2.5)  # one other net
+    assert router._congestion(node, 5) == pytest.approx(3.0)  # two other nets
+    router._present = None
+    assert router._congestion(node, 5) == pytest.approx(2.0)  # history only, after
+
+
+@pytest.mark.parametrize("name", ["ripup_needed.dsn", "true_density.dsn", "kicad_routable.dsn"])
+def test_negotiated_routing_keeps_the_occupancy_honest(name):
+    """Only routed connections hold cells afterwards, as without negotiation."""
+    router = _router(name, 3)
+    router.route()
+    conns = router._conns
+    assert all(conns[i].routed for i in router._cell_owner.values())
+    assert all(conns[i].routed for claims in router._halo.values() for i in claims)
+
+
+def test_option_reaches_the_router_and_is_off_by_default():
+    text = (FIXTURES / "kicad_routable.dsn").read_text()
+    plain, _, _ = route_dsn_board(parse_dsn(text))
+    again, _, _ = route_dsn_board(parse_dsn(text), negotiate=0)
+    assert plain.unrouted == again.unrouted

tests/route/test_real_board_geometry.py

@@ -51,19 +51,22 @@ def test_routes_keep_edge_clearance_at_a_rounded_corner():
                 assert outline.edge_distance(p) >= half + 500 * scale - 1
 
 
-@pytest.mark.parametrize(("resolution", "escape"), [(1, 2), (4, 5)])
+@pytest.mark.parametrize("resolution", [1, 4])
-def test_every_pin_of_a_half_millimetre_pitch_row_escapes(resolution, escape):
+def test_every_pin_of_a_half_millimetre_pitch_row_escapes(resolution):
     # Five 0.3 mm pads at 0.5 mm pitch, each wired to its own pad 8 mm away.
     # Between two neighbours a trace's centre has a legal band only 0.15 mm
-    # wide. At resolution 1 the 0.4 mm grid misses most bands; at 4 its
+    # wide. At resolution 4 the 0.1 mm columns cannot miss it. At resolution
-    # 0.1 mm columns cannot, and every pin gets out, as the JAR manages.
+    # 1 the 0.4 mm grid misses most bands, but a stub leaves its pin straight
+    # along the band and jogs to the column only past the pads, so every pin
+    # gets out there too, as the JAR manages (only 2 did before).
     places = " ".join(f"(place R{i} {6000 + 500 * i} -6000 front 0)" for i in range(5))
     places += " " + " ".join(f"(place F{i} {6000 + 500 * i} -14000 front 0)" for i in range(5))
     nets = " ".join(f"(net N{i} (pins R{i}-1 F{i}-1))" for i in range(5))
     result, _, _ = route_dsn_board_exact(
         parse_dsn(_dsn(f"(component P {places})", nets)), resolution=resolution
     )
-    assert len(result.routed_net_numbers) == escape
+    assert len(result.routed_net_numbers) == 5
+    assert result.drc_clean
 
 
 def test_resolution_one_has_no_halo_so_the_grid_is_unchanged():

tests/route/test_rollback.py

@@ -31,7 +31,7 @@ def test_occupancy_only_holds_routed_connections(name):
     router, _ = _routed_router(name)
     conns = router._conns
     assert all(conns[i].routed for i in router._cell_owner.values())
-    assert all(conns[i].routed for i in router._via_owner.values())
+    assert all(conns[i].routed for claims in router._via_claims.values() for i in claims)
     assert all(conns[i].routed for claims in router._halo.values() for i in claims)
 
 

tests/route/test_straight_pin_exits.py

@@ -0,0 +1,58 @@
+"""Pins of a 1.27 mm pitch row routed at 1.0 mm (the RN2483 module on the
+TTN Enschede mote). A trace centre has to stay within 0.06 mm of a pin's
+centreline to pass its neighbours, which no grid column hits, so a route
+leaves each pin straight along that line and only jogs to its column once
+past the pads. FreeRouting routes this row in full the same way."""
+
+from __future__ import annotations
+
+import pytest
+
+from freeroute.board import build_board
+from freeroute.board.items import Pin
+from freeroute.dsn import parse_dsn
+from freeroute.geometry import IntPoint
+from freeroute.route.grid_router import GridRouter
+from freeroute.route.pipeline import route_dsn_board_exact
+
+
+def _row(x0: int, pins: int = 6, skew: int = 3000) -> str:
+    places = " ".join(f"(place R{i} {x0 + 1270 * i} -5000 front 0)" for i in range(pins))
+    places += " " + " ".join(
+        f"(place T{i} {x0 + 1270 * i + skew} -15000 front 0)" for i in range(pins)
+    )
+    nets = " ".join(f"(net N{i} (pins R{i}-1 T{i}-1))" for i in range(pins))
+    return f"""(pcb t (parser) (resolution um 10) (unit um)
+  (structure (layer F.Cu (type signal)) (layer B.Cu (type signal))
+    (boundary (path pcb 0 0 0 30000 0 30000 -20000 0 -20000 0 0))
+    (via "Via[0-1]_600:400_um") (rule (width 1000) (clearance 200)))
+  (placement (component P {places}))
+  (library (image P (pin pad 1 0 0))
+    (padstack pad (shape (rect F.Cu -508 -762 508 762)) (attach off))
+    (padstack "Via[0-1]_600:400_um" (shape (circle F.Cu 600)) (shape (circle B.Cu 600))
+      (attach off)))
+  (network {nets}))"""
+
+
+@pytest.mark.parametrize("x0", [5000, 5150, 5300])
+def test_every_pin_of_a_row_leaves_straight_and_routes(x0):
+    # three offsets of the row against the grid; before, 2 or 3 of 6 routed
+    result, _, _ = route_dsn_board_exact(parse_dsn(_row(x0)), resolution=2)
+    assert len(result.routed_net_numbers) == 6
+    assert result.drc_clean
+
+
+def test_a_walled_in_pin_may_escape_to_the_column_either_side():
+    # two pins side by side leaving the same way can then jog apart
+    board = build_board(parse_dsn(_row(5000)))
+    router = GridRouter(board, trace_width=10000, clearance=2000, orthogonal=True, resolution=2)
+    router._conns = router._build_connections()
+    pin = next(
+        p for p in board.get_items()
+        if isinstance(p, Pin) and p.location == IntPoint(50000 + 2 * 12700, -50000)
+    )
+    net = pin.net_nos[0]
+    cx, cy = router._cell_of(pin.location)
+    nodes = router._escape_nodes(pin, net, router._conns, [0], (cx, cy))
+    columns = {x for x, y, _ in nodes if y != cy}
+    assert {cx - 1, cx, cx + 1} <= columns

tests/route/test_via_spacing.py

@@ -56,7 +56,7 @@ def test_connections_sharing_a_plane_via_write_it_once():
     assert len(set(vias)) == len(vias), "a shared via written more than once"
 
 
-def _router(dsn_text):
+def _router(dsn_text, via_drill_um=300):
     from freeroute.board import build_board
     from freeroute.route.grid_router import GridRouter
     from freeroute.route.pipeline import _rule_clearance_dsn, _rule_width_dsn
@@ -66,7 +66,7 @@ def _router(dsn_text):
     return GridRouter(
         build_board(dsn), trace_width=round(_rule_width_dsn(dsn) * s),
         clearance=round(_rule_clearance_dsn(dsn) * s), resolution=2, orthogonal=True,
-        via_drill=300 * s, hole_to_hole=250 * s,
+        via_drill=via_drill_um * s, hole_to_hole=250 * s,
     ), s
 
 
@@ -98,3 +98,39 @@ def test_a_via_in_a_pad_keeps_hole_spacing_from_a_fixed_via():
     router, s = _router(text)
     assert not router._hole_clear_at(IntPoint(3400 * s, -3000 * s))  # 0.4 mm < 0.55 mm
     assert router._hole_clear_at(IntPoint(3600 * s, -3000 * s))
+
+
+def test_hole_spacing_from_a_fixed_via_is_measured_from_where_it_really_is():
+    # a fixed via off the grid with its own 0.25 mm drill, and the router's
+    # via a smaller 0.2 mm one (the flight controller's case): a new via needs
+    # its centre 0.1 + 0.125 + 0.25 = 0.475 mm away, measured exactly, where
+    # one rule for all vias gave 0.2 + 0.25 = 0.45 from the cell centres
+    text = _THT.replace("(network (net SIG (pins J1-1))))",
+                        "(network (net SIG (pins J1-1)) (net GND))\n"
+                        "  (wiring (via \"Via[0-1]_500:250_um\"  3030 -3030 (net GND) (type route))))")
+    text = text.replace(
+        '(attach off)))\n  (network',
+        '(attach off))\n    (padstack "Via[0-1]_500:250_um" (shape (circle F.Cu 500)) '
+        '(shape (circle B.Cu 500)) (attach off)))\n  (network',
+    )
+    router, s = _router(text, via_drill_um=200)
+    via = next(v for v in router.board.get_items() if getattr(v, "drill", 0))
+    assert via.drill == 250 * s
+    loc = via.location
+    for cell in [(x, y) for x in range(router.cols) for y in range(router.rows)]:
+        c = router._cell_center(cell)
+        d = math.hypot(c.x - loc.x, c.y - loc.y)
+        if router.step * 1.5 < d < 470 * s:
+            assert not router._holes_clear(cell, 1), f"{d / s:.0f} um from the fixed via"
+        elif 560 * s < d < 700 * s and cell not in router._tht_block:
+            assert router._holes_clear(cell, 1)
+
+
+def test_a_route_keeps_its_own_vias_apart():
+    # a route that changed layer at (10, 10) may not change layer again one
+    # cell away; the same cell is the same through via, and far is fine
+    router, _s = _router(_THT)
+    came_from = {(10, 10, 1): (10, 10, 0), (11, 10, 1): (10, 10, 1), (12, 10, 1): (11, 10, 1)}
+    assert router._near_path_via((12, 10, 1), (11, 10), came_from)
+    assert not router._near_path_via((12, 10, 1), (10, 10), came_from)
+    assert not router._near_path_via((12, 10, 1), (40, 10), came_from)

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"],
+        "negotiate": ["--negotiate", "2"],
         "rollback": ["--no-rollback"],
     }
     for engine, options in ENGINE_OPTIONS.items():