KiCad - the KiCad Bridge

#!/usr/bin/env python3
"""Claude Fable 5.1's routing engine for the ESC G431 board: a grid maze router.

    python3 demo/routing/esc/ai_router.py BOARD-planes.kicad_pcb [--out plan.json] [--report report.json]
                                          [--nets NET,NET] [--no-planes] [--seed 0] [--verbose]

What it does
  * 0.1 mm grid over the Edge.Cuts outline, two signal layers (F.Cu, B.Cu), through vias between
    them (0.6 mm / 0.3 mm drill for signals, 0.8 mm / 0.4 mm on the wide power nets), KiCad's default rules for this board: 0.25 mm track, 0.2 mm
    clearance, 0.5 mm copper-to-edge, plus every per-pad or per-footprint `(clearance X)` override.
  * A* (octilinear, 8 neighbours) per connection. Costs: 10 per orthogonal cell, 14 diagonal,
    x1.25 on B.Cu (prefer F.Cu), +400 per via (heavily penalised), +4 per direction change.
  * Obstacles per layer for the net being routed: every pad and every committed segment/via of
    another net, dilated by (that item's clearance + half the track width + grid slop); the
    outline inset by the edge clearance; through pads on both layers. Own-net copper is free.
    A diagonal step is allowed only when one of its ends also clears the larger dilation that
    covers the midpoint of the step, so 45-degree segments never clip a corner.
  * Narrow pads (fine-pitch IC pins) are entered on their long axis: a 0.2 mm stub from the exact
    pad centre to an on-grid escape point beyond either pad end; the route starts there. Other
    pads are hit at their centre. Same-net pads that overlap (MOSFET source pads) form one cluster.
  * A net with N clusters is routed as a minimum spanning tree: Prim's order, each new cluster
    routed to ANY copper the net already has (pads, tracks, vias), so branches land on their own
    copper and junctions split the existing segment at an on-grid point.
  * Order: nets by MST length, shortest first; plane-net stubs last.
  * Widths: +VBAT and the phase nets (/DRV_SHA, /DRV_SHB, /DRV_SHC, which are also the MOSFET
    drain and source nets) try 1.0 mm, then 0.5, then 0.25; +5V and +12V try 0.5 then 0.25;
    everything else 0.25. A pad narrower than the width caps it (a 1.0 mm track never enters a
    0.35 mm pin). Fallback happens per connection when the wider route finds no path.
  * GND and +3V3 are plane nets (In1.Cu and In2.Cu): no traces. Each SMD pad gets the shortest
    stub to a spot where a via fits (Dijkstra to the first via-legal cell), through pads need
    nothing. If no spot fits within 6 mm the via goes in the pad (reported).
  * Rip-up and retry: when a connection fails on every width, a second search treats other nets'
    tracks as expensive instead of solid; the nets it crosses are ripped up (most recently routed
    first), the connection is routed again, and the ripped nets are re-queued. Bounded per net
    and globally.

Output: a JSON plan, a list of kicad_route_net calls: {"net", "width", "viaSize", "viaDrill",
"paths": [[...], ...]} where a waypoint is "REF.PAD", [x, y] or {"x", "y", "layer": "B.Cu"}
(a layer marker = a via there). write_copper.py applies it offline, route_live.py replays it.
"""
import argparse
import heapq
import json
import math
import os
import sys
import time
from collections import defaultdict

import numpy as np

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
from escboard import Board, Grid, F_CU, B_CU, LAYER_NAMES, RES  # noqa: E402

# ----------------------------------------------------------------------------- rules

RULES = {
    "track": 0.25, "clearance": 0.2, "via": 0.8, "drill": 0.4, "edge": 0.5,
    "stub": 0.2,               # escape stub width for narrow pins
    "narrow": 0.5,             # pads with a short side under this get an axis escape
    "escape": 0.45,            # escape point this far beyond the pad end (grows if blocked)
    "corridor": 0.5,           # reserved own-net corridor beyond the escape point (other nets keep out)
    "ic_zone": 2.0,            # soft-cost band around a fine-pitch IC (routes should not run along a pin row)
    "channel": 2.5,            # no via on the line of another reserved pin escape this far beyond the pad
    "planes": {"GND": "In1.Cu", "+3V3": "In2.Cu"},
    "wide": {"+VBAT": [1.0, 0.5, 0.25], "/DRV_SHA": [1.0, 0.5, 0.25], "/DRV_SHB": [1.0, 0.5, 0.25], "/DRV_SHC": [1.0, 0.5, 0.25]},
    "mid": {"+5V": [0.5, 0.25], "+12V": [0.5, 0.25]},
    "via_small": 0.6, "drill_small": 0.3,   # signal vias; the wide power nets keep 0.8 / 0.4
    "hole_to_hole": 0.25,      # KiCad's default hole-to-hole minimum: same-net vias may sit this close (drill edge to drill edge)
    "via_search_mm": 6.0,
}
SLOP = 0.05 * math.sqrt(2) + 1e-6   # half a cell diagonal: pads and stubs are off-grid
COST_ORTH, COST_DIAG, COST_VIA, COST_TURN = 10, 14, 250, 4
LAYER_MULT = {F_CU: 1.0, B_CU: 1.1}
SOFT_EXTRA = 80
ZONE_COST = 20      # per F.Cu cell inside a fine-pitch IC's escape band
VIA_WALL = 300      # per unrouted neighbour pin channel a via would wall in
HIST_COST = 12      # per cell per time a ripped-up route was there (contested corridors get pricier)
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
STEP = [COST_ORTH] * 4 + [COST_DIAG] * 4
INF = 1 << 30


def log(*a):
    print(*a, flush=True)


# ----------------------------------------------------------------------------- data

class Cluster:
    """Pads of one net in one footprint whose copper overlaps: routed once."""

    def __init__(self, idx, pads):
        self.idx = idx
        self.pads = pads
        self.primary = max(pads, key=lambda p: p.half_long * p.half_short)
        self.terminals = []      # [(layer, i, j)] cells a route may start or end at
        self.escapes = {}        # (layer, i, j) -> escape point (x, y) exact grid coords (stub end)
        self.corridors = {}      # (layer, i, j) -> corridor end (x, y) beyond the escape point
        self.connected = False
        self.allow = 0.25

    @property
    def xy(self):
        return self.primary.x, self.primary.y

    @property
    def key(self):
        return self.primary.key


class Route:
    def __init__(self, cells, width, start, end):
        self.cells = cells          # [(layer, i, j)]
        self.width = width
        self.start = start          # ("pad", Cluster, term) | ("escape", Cluster, term)
        self.end = end              # ("pad", Cluster, term) | ("escape", ...) | ("copper",) | ("via",)
        self.breaks = set()         # indices into cells where a segment must end (junctions)
        self.via_end = False        # a via at the last cell (plane stub, or a via in the target pad)
        self.via_end_layer = "B.Cu" # the layer the via switches to


class NetState:
    def __init__(self, idx, name, pads):
        self.idx, self.name, self.pads = idx, name, pads
        self.clusters = []
        self.routes = []
        self.widths = [RULES["track"]]
        self.plane = RULES["planes"].get(name)
        self.mst_len = 0.0
        self.used_escapes = set()    # (cluster idx, terminal)
        self.failed = []             # [(cluster key, reason)]
        self.rips = 0
        self.routed_order = None
        self.via_in_pad = []
        self.last_soft = []
        self.via = RULES["via_small"]
        self.drill = RULES["drill_small"]


def _seg_distance(x, y, ax, ay, bx, by):
    dx, dy = bx - ax, by - ay
    L2 = dx * dx + dy * dy
    if L2 < 1e-12:
        return math.hypot(x - ax, y - ay)
    t = max(0.0, min(1.0, ((x - ax) * dx + (y - ay) * dy) / L2))
    return math.hypot(x - (ax + t * dx), y - (ay + t * dy))


def _point_poly_distance(x, y, poly):
    """0 inside the polygon, else the distance to its boundary."""
    inside = False
    n = len(poly)
    best = float("inf")
    for k in range(n):
        ax, ay = poly[k]
        bx, by = poly[(k + 1) % n]
        if (ay > y) != (by > y):
            xint = ax + (y - ay) * (bx - ax) / (by - ay)
            if x < xint:
                inside = not inside
        d = _seg_distance(x, y, ax, ay, bx, by)
        if d < best:
            best = d
    return 0.0 if inside else best


def _route_segments(g, cells):
    """Straight runs of a cell path as exact segments (x0, y0, x1, y1), vias skipped."""
    out = []
    k = 0
    n = len(cells)
    while k < n - 1:
        L, i0, j0 = cells[k]
        m = k + 1
        if cells[m][0] != L:
            k = m
            continue
        di, dj = cells[m][1] - i0, cells[m][2] - j0
        while m + 1 < n and cells[m + 1][0] == L and (cells[m + 1][1] - cells[m][1], cells[m + 1][2] - cells[m][2]) == (di, dj):
            m += 1
        a = g.to_xy(i0, j0)
        b = g.to_xy(cells[m][1], cells[m][2])
        out.append((a[0], a[1], b[0], b[1]))
        k = m
    return out


# ----------------------------------------------------------------------------- router

class Router:
    def __init__(self, board, verbose=False):
        self.board = board
        self.verbose = verbose
        self.grid = Grid(board.bbox)
        g = self.grid
        self.H, self.W = g.H, g.W
        self.nets = {}
        self.net_ids = {}
        for k, (name, pads) in enumerate(sorted(board.nets.items())):
            self.net_ids[name] = k
            self.nets[name] = NetState(k, name, pads)
        # raw copper by layer: pads (+ reserved stubs) and routes, net id or -1
        self.pad_raw = {L: np.full((g.H, g.W), -1, dtype=np.int16) for L in (F_CU, B_CU)}
        self.pad_owner = {L: np.full((g.H, g.W), -1, dtype=np.int16) for L in (F_CU, B_CU)}
        self.route_raw = {L: np.full((g.H, g.W), -1, dtype=np.int16) for L in (F_CU, B_CU)}
        self.big_clr = {L: np.zeros((g.H, g.W), dtype=bool) for L in (F_CU, B_CU)}  # pads with a 0.6 override
        self.big_clr_val = RULES["clearance"]
        self.smd_pad_cells = {}   # net id -> bool mask (F.Cu smd pads) for via placement
        self.thru_cells = np.zeros((g.H, g.W), dtype=bool)   # every through pad: never a via site
        self.history = {L: np.zeros((g.H, g.W), dtype=np.int16) for L in (F_CU, B_CU)}   # contested cells (rip-ups)
        self.chan_count = np.zeros((g.H, g.W), dtype=np.int16)   # how many unrouted pin channels a via here would wall
        self.chan_lines = {}      # (net idx, cluster idx, term) -> (jj, ii) of the walled region
        self.vias = []            # [(i, j, net id, diameter, drill)]
        self.fp_index = {ref: n for n, ref in enumerate(sorted(board.footprints))}
        self.pad_cells = {}       # pad key -> (jj, ii)
        t0 = time.time()
        self._stamp_pads()
        self.inside, self.edge_dist = g.outline_distance(board.outline)
        self.inside_w = {}
        self.order = []
        self.rip_total = 0
        self.stats = defaultdict(int)
        self._build_clusters()
        self._build_ic_zones()
        log("router: %d x %d cells, %d pads stamped, %d nets to route, init %.1fs" % (
            g.W, g.H, len(board.pads), len([n for n in self.nets.values() if len(n.clusters) >= 2 or n.plane]), time.time() - t0))

    # -- stamping ------------------------------------------------------------------
    def _stamp_pads(self):
        g = self.grid
        for p in self.board.pads:
            nid = self.net_ids.get(p.net, -1)
            m = np.zeros((g.H, g.W), dtype=bool)
            for poly in p.polys:
                g.poly_mask(poly, m)
            if p.drill:
                jj, ii = g.disk_cells((p.x, p.y), p.drill / 2.0)
                m[jj, ii] = True
            jj, ii = np.nonzero(m)
            self.pad_cells[p.key] = (jj, ii)
            layers = [F_CU, B_CU] if p.thru else [F_CU if "F.Cu" in p.layers else B_CU]
            for L in layers:
                self.pad_raw[L][jj, ii] = nid
                self.pad_owner[L][jj, ii] = self.fp_index[p.ref]
                if p.clearance > RULES["clearance"]:
                    self.big_clr[L][jj, ii] = True
                    self.big_clr_val = max(self.big_clr_val, p.clearance)
            if not p.thru and nid >= 0:
                sm = self.smd_pad_cells.setdefault(nid, np.zeros((g.H, g.W), dtype=bool))
                sm[jj, ii] = True
            if p.thru:
                self.thru_cells[jj, ii] = True

    def inside_for(self, w):
        key = round(w, 3)
        if key not in self.inside_w:
            self.inside_w[key] = self.inside & (self.edge_dist >= RULES["edge"] + w / 2.0 + SLOP)
        return self.inside_w[key]

    def stamp_route(self, net, route, sign=1):
        """Add (sign=1) or remove (sign=-1) a route's copper from route_raw."""
        g = self.grid
        nid = net.idx if sign > 0 else -1
        cells = route.cells
        k = 0
        while k < len(cells) - 1:
            # straight run from k
            L, i0, j0 = cells[k]
            m = k + 1
            di, dj = cells[m][1] - i0, cells[m][2] - j0
            while m + 1 < len(cells) and cells[m + 1][0] == L and cells[m][0] == L and (cells[m + 1][1] - cells[m][1], cells[m + 1][2] - cells[m][2]) == (di, dj):
                m += 1
            if cells[m][0] == L:
                a = g.to_xy(i0, j0)
                b = g.to_xy(cells[m][1], cells[m][2])
                jj, ii = g.segment_cells(a, b, route.width / 2.0, 0.0 + 1e-6)
                self.route_raw[L][jj, ii] = nid
            k = m
        # vias: layer changes
        for k in range(1, len(cells)):
            if cells[k][0] != cells[k - 1][0] and cells[k][1:] == cells[k - 1][1:]:
                self._stamp_via(cells[k][1], cells[k][2], net, sign)
        if route.via_end:
            L, i, j = cells[-1]
            self._stamp_via(i, j, net, sign)
        if len(cells) == 1 and route.via_end:
            pass

    def _stamp_via(self, i, j, net, sign):
        g = self.grid
        nid = net.idx
        xy = g.to_xy(i, j)
        jj, ii = g.disk_cells(xy, net.via / 2.0, 0.0 + 1e-6)
        for L in (F_CU, B_CU):
            self.route_raw[L][jj, ii] = nid if sign > 0 else -1
        if sign > 0:
            self.vias.append((i, j, nid, net.via, net.drill))
        else:
            self.vias = [v for v in self.vias if not (v[0] == i and v[1] == j and v[2] == nid)]

    def via_gap(self, net, nid, dia, drill):
        """Centre-to-centre distance this net's via must keep from a via of (nid, dia, drill)."""
        if nid == net.idx:
            return (net.drill + drill) / 2.0 + RULES["hole_to_hole"] + SLOP
        return net.via / 2.0 + dia / 2.0 + RULES["clearance"] + SLOP

    def stamp_stub(self, net, cluster, term, sign=1):
        """Reserve or release the escape stub copper (exact pad centre to the on-grid escape point)."""
        g = self.grid
        L, i, j = term
        p = cluster.primary
        a = p.polys_centre
        b = g.to_xy(i, j)
        jj, ii = g.segment_cells(a, b, RULES["stub"] / 2.0, 1e-6)
        self.pad_raw[L][jj, ii] = net.idx if sign > 0 else -1
        if sign > 0:
            self.pad_owner[L][jj, ii] = self.fp_index[p.ref]
        kend = cluster.corridors.get(term)
        if kend is not None:
            jj, ii = g.segment_cells(b, kend, RULES["track"] / 2.0, 1e-6)
            self.pad_raw[L][jj, ii] = net.idx if sign > 0 else -1
            if sign > 0:
                self.pad_owner[L][jj, ii] = self.fp_index[p.ref]
        self._stamp_channel(net, cluster, term, sign)
        if sign < 0:
            # restore the pad itself
            pj, pi = self.pad_cells[p.key]
            self.pad_raw[L][pj, pi] = net.idx
            self.pad_owner[L][pj, pi] = self.fp_index[p.ref]

    def _stamp_channel(self, net, cluster, term, sign):
        """Count (or uncount) the region where a via would wall in this unrouted pin's straight path."""
        g = self.grid
        key = (net.idx, cluster.idx, term)
        if sign > 0 and key in self.chan_lines:
            return
        if sign < 0:
            hit = self.chan_lines.pop(key, None)
            if hit is not None:
                self.chan_count[hit[0], hit[1]] -= 1
            return
        L, i, j = term
        p = cluster.primary
        b = g.to_xy(i, j)
        ax, ay = p.long_axis
        cx, cy = p.polys_centre
        sgn = 1.0 if (b[0] - cx) * ax + (b[1] - cy) * ay > 0 else -1.0
        cend = (b[0] + sgn * round(ax, 6) * RULES["channel"], b[1] + sgn * round(ay, 6) * RULES["channel"])
        r = net.via / 2.0 + RULES["clearance"] + RULES["track"] / 2.0 + SLOP
        jj, ii = g.segment_cells(b, cend, r, 0.0)
        ok = self.inside_for(net.via)[jj, ii]
        jj, ii = jj[ok], ii[ok]
        self.chan_count[jj, ii] += 1
        self.chan_lines[key] = (jj, ii)

    # -- clusters and terminals ----------------------------------------------------
    def _build_clusters(self):
        g = self.grid
        for net in self.nets.values():
            if len(net.pads) < 2 and not net.plane:
                continue
            by_fp = defaultdict(list)
            for p in net.pads:
                by_fp[p.ref].append(p)
            clusters = []
            for ref, pads in by_fp.items():
                groups = []
                for p in pads:
                    mask = set(zip(*[a.tolist() for a in self.pad_cells[p.key]]))
                    merged = None
                    for gidx, (gpads, gcells) in enumerate(groups):
                        if mask & gcells:
                            if merged is None:
                                gpads.append(p)
                                gcells |= mask
                                merged = gidx
                            else:
                                groups[merged][0].extend(gpads)
                                groups[merged][1] |= gcells
                                groups[gidx] = None
                    groups = [x for x in groups if x is not None]
                    if merged is None:
                        groups.append(([p], set(mask)))
                for gpads, _ in groups:
                    clusters.append(Cluster(len(clusters), gpads))
            net.clusters = clusters
            if net.name in RULES["wide"]:
                net.widths = list(RULES["wide"][net.name])
                net.via, net.drill = RULES["via"], RULES["drill"]
            elif net.name in RULES["mid"]:
                net.widths = list(RULES["mid"][net.name])
            for c in clusters:
                self._terminals_for(net, c)
        # MOSFET drain/source nets get the wide treatment too
        for p in self.board.pads:
            if p.ref.startswith("Q") and p.name in ("1", "2", "3", "5") and p.net in self.nets:
                n = self.nets[p.net]
                if not n.plane and n.name not in RULES["wide"]:
                    n.widths = [1.0, 0.5, 0.25]
                    n.via, n.drill = RULES["via"], RULES["drill"]

    def _build_ic_zones(self):
        """Fine-pitch ICs (two or more escaped pins): the body interior on F.Cu is a keepout for nets
        without a pin on that IC; a band around the IC carries a soft cost for every net."""
        g = self.grid
        self.body_owner = np.full((g.H, g.W), -1, dtype=np.int16)
        self.ic_zone = np.zeros((g.H, g.W), dtype=bool)
        self.ic_nets = {}   # fp index -> set of net ids with a pin on it
        by_fp = defaultdict(list)
        for net in self.nets.values():
            for c in net.clusters:
                if c.escapes:
                    by_fp[c.primary.ref].append(c)
        for ref, clusters in by_fp.items():
            if len(clusters) < 2:
                continue
            fp = self.board.footprints[ref]
            inner = []
            for c in clusters:
                p = c.primary
                ax, ay = p.long_axis
                cx, cy = p.polys_centre
                sgn = 1.0 if (fp["x"] - cx) * ax + (fp["y"] - cy) * ay > 0 else -1.0
                inner.append((cx + sgn * ax * p.half_long, cy + sgn * ay * p.half_long))
            pads = [q for q in self.board.pads if q.ref == ref]
            xs = [pt[0] for pt in inner]
            ys = [pt[1] for pt in inner]
            if max(xs) - min(xs) < 1.0 or max(ys) - min(ys) < 1.0:
                continue
            i0, j0 = g.to_cell(min(xs), min(ys))
            i1, j1 = g.to_cell(max(xs), max(ys))
            idx = self.fp_index[ref]
            self.body_owner[j0:j1 + 1, i0:i1 + 1] = idx
            self.ic_nets[idx] = {self.net_ids[q.net] for q in pads if q.net in self.net_ids}
            m = int(round(RULES["ic_zone"] / RES))
            px = [q.x for q in pads]
            py = [q.y for q in pads]
            a0, b0 = g.to_cell(min(px), min(py))
            a1, b1 = g.to_cell(max(px), max(py))
            self.ic_zone[max(0, b0 - m):b1 + m + 1, max(0, a0 - m):a1 + m + 1] = True
            log("  ic %s: body keepout %.1f x %.1f mm for %d foreign nets, escape band +%d/cell" % (
                ref, (i1 - i0) * RES, (j1 - j0) * RES, len(self.nets) - len(self.ic_nets[idx]), ZONE_COST))

    def _terminals_for(self, net, c):
        g = self.grid
        p = c.primary
        md = p.min_dim
        c.allow = 1.0 if md >= 1.0 else (0.5 if md >= 0.5 else 0.25)
        if p.thru:
            i, j = g.to_cell(p.x, p.y)
            c.terminals = [(F_CU, i, j), (B_CU, i, j)]
            return
        L = F_CU if "F.Cu" in p.layers else B_CU
        narrow = md < RULES["narrow"] and p.half_long > p.half_short * 1.4
        if not narrow:
            i, j = g.to_cell(p.x, p.y)
            c.terminals = [(L, i, j)]
            return
        c.allow = 0.25
        cx, cy = p.polys_centre
        ax, ay = p.long_axis
        found = []
        for sgn in (1.0, -1.0):
            hit = None
            # a full corridor first; a shorter one when a neighbouring part sits close to the pin end
            for corridor in (RULES["corridor"], RULES["corridor"] / 2.0, 0.0):
                d = RULES["escape"]
                while d <= 1.6 and hit is None:
                    ex, ey = cx + sgn * ax * (p.half_long + d), cy + sgn * ay * (p.half_long + d)
                    i, j = g.to_cell(ex, ey)
                    # the corridor leaves the ON-GRID escape cell along the pin axis, so an axis-aligned
                    # pin row gets straight corridors that rasterise three cells wide, never four
                    bx, by = g.to_xy(i, j)
                    kx, ky = bx + sgn * round(ax, 6) * corridor, by + sgn * round(ay, 6) * corridor
                    if g.in_bounds(i, j) and self._escape_ok(net, p, L, i, j, (kx, ky)):
                        hit = ((L, i, j), sgn, (kx, ky) if corridor > 0 else None)
                    d += 0.1
                if hit is not None:
                    break
            if hit is not None:
                found.append(hit)
        c.terminals = [t for t, _, _ in found]
        for t, sgn, kend in found:
            c.escapes[t] = g.to_xy(t[1], t[2])
            if kend is not None:
                c.corridors[t] = kend
            self.stamp_stub(net, c, t, 1)
        if not found:
            i, j = g.to_cell(p.x, p.y)
            c.terminals = [(L, i, j)]

    def _escape_ok(self, net, p, L, i, j, corridor_end):
        """Exact geometry: the escape cell, the stub and the reserved corridor beyond it clear every
        pad of another footprint (same-footprint neighbours are the regular pin field, fine by
        construction), and the corridor end lies inside the outline."""
        g = self.grid
        if not self.inside_for(RULES["track"])[j, i]:
            return False
        b = g.to_xy(i, j)
        a = p.polys_centre
        checks = [(a, b, RULES["stub"] / 2.0)]
        if math.dist(b, corridor_end) > 1e-6:
            ki, kj = g.to_cell(*corridor_end)
            if not g.in_bounds(ki, kj) or not self.inside_for(RULES["track"])[kj, ki]:
                return False
            checks.append((b, corridor_end, RULES["track"] / 2.0))
        samples = []
        for (s0, s1, hw) in checks:
            n = max(1, int(math.ceil(math.dist(s0, s1) / 0.05)))
            for k in range(n + 1):
                t = k / n
                samples.append((s0[0] + (s1[0] - s0[0]) * t, s0[1] + (s1[1] - s0[1]) * t, hw))
        # the route leaving the escape cell: a track of the net's width in any direction
        samples.append((b[0], b[1], RULES["track"] / 2.0))
        reach = 2.5
        for q in self.board.pads:
            if q.ref == p.ref or q.net == net.name:
                continue
            if abs(q.x - b[0]) > reach + q.half_long or abs(q.y - b[1]) > reach + q.half_long:
                continue
            if L == F_CU and "F.Cu" not in q.layers:
                continue
            clr = max(RULES["clearance"], q.clearance)
            for poly in q.polys:
                for (x, y, hw) in samples:
                    if _point_poly_distance(x, y, poly) < hw + clr:
                        return False
        return True

    # -- obstacle maps ---------------------------------------------------------------
    def obstacle_maps(self, net, width, win, soft=False):
        """(obs_o, obs_d, soft_mask) per layer for the window, plus via_ok. Windows are (i0, j0, i1, j1) inclusive."""
        g = self.grid
        i0, j0, i1, j1 = win
        r_o = (RULES["clearance"] + width / 2.0 + SLOP) / RES
        r_d = r_o + 0.0707 / RES
        r_big = (self.big_clr_val + width / 2.0 + SLOP) / RES
        pad_R = int(math.ceil(max(r_d, r_big))) + 1
        # work on a padded window so the dilation sees copper just outside it
        I0, J0 = max(0, i0 - pad_R), max(0, j0 - pad_R)
        I1, J1 = min(self.W - 1, i1 + pad_R), min(self.H - 1, j1 + pad_R)
        obs_o, obs_d, softm = {}, {}, {}
        via_block = np.zeros((J1 - J0 + 1, I1 - I0 + 1), dtype=bool)
        for L in (F_CU, B_CU):
            praw = self.pad_raw[L][J0:J1 + 1, I0:I1 + 1]
            rraw = self.route_raw[L][J0:J1 + 1, I0:I1 + 1]
            other_pads = (praw != -1) & (praw != net.idx)
            other_routes = (rraw != -1) & (rraw != net.idx)
            big = self.big_clr[L][J0:J1 + 1, I0:I1 + 1] & other_pads
            hard = other_pads if soft else (other_pads | other_routes)
            o = g.dilate(hard, r_o) | g.dilate(big, r_big) | ~self.inside_for(width)[J0:J1 + 1, I0:I1 + 1]
            d = g.dilate(hard, r_d) | g.dilate(big, r_big + 0.0707 / RES)
            if L == F_CU and self.ic_nets:
                foreign = [idx for idx, nets in self.ic_nets.items() if net.idx not in nets]
                if foreign:
                    body = np.isin(self.body_owner[J0:J1 + 1, I0:I1 + 1], foreign)
                    o |= body
                    d |= body
            s = g.dilate(other_routes, r_d) if soft else None
            sl = (slice(j0 - J0, j1 - J0 + 1), slice(i0 - I0, i1 - I0 + 1))
            obs_o[L] = o[sl]
            obs_d[L] = d[sl]
            softm[L] = s[sl] if s is not None else None
            via_block |= g.dilate(other_pads | other_routes, (RULES["clearance"] + net.via / 2.0 + SLOP) / RES)
            via_block |= g.dilate(big, (self.big_clr_val + net.via / 2.0 + SLOP) / RES)
        own_smd = self.smd_pad_cells.get(net.idx)
        if own_smd is not None:
            via_block |= g.dilate(own_smd[J0:J1 + 1, I0:I1 + 1], (net.via / 2.0 + SLOP) / RES)
        via_block |= g.dilate(self.thru_cells[J0:J1 + 1, I0:I1 + 1], (net.via / 2.0 + SLOP) / RES)
        # other vias: annular ring + clearance for another net, hole to hole for this net
        groups = defaultdict(list)
        for (vi, vj, nid, dia, drill) in self.vias:
            if I0 <= vi <= I1 and J0 <= vj <= J1:
                groups[round(self.via_gap(net, nid, dia, drill), 4)].append((vj - J0, vi - I0))
        for gap, cells in groups.items():
            vm = np.zeros_like(via_block)
            for (a, b) in cells:
                vm[a, b] = True
            via_block |= g.dilate(vm, gap / RES - 1e-6)
        via_ok = ~via_block & self.inside_for(net.via)[J0:J1 + 1, I0:I1 + 1]
        sl = (slice(j0 - J0, j1 - J0 + 1), slice(i0 - I0, i1 - I0 + 1))
        return obs_o, obs_d, softm, via_ok[sl]

    # -- A* --------------------------------------------------------------------------
    def search(self, net, width, sources, targets, heur_pts, win, allow_via=True, soft=False, via_target=False, max_nodes=None, vip=()):
        """A* from sources to targets. sources: [(L,i,j,cost0)]; targets: {(L,i,j)} or None when via_target.
        Returns (cells, blockers) with cells [(L,i,j)] or None."""
        i0, j0, i1, j1 = win
        Ww, Hw = i1 - i0 + 1, j1 - j0 + 1
        NL = Ww * Hw
        obs_o, obs_d, softm, via_ok = self.obstacle_maps(net, width, win, soft)
        oo = {L: obs_o[L].ravel().tobytes() for L in (F_CU, B_CU)}
        od = {L: obs_d[L].ravel().tobytes() for L in (F_CU, B_CU)}
        sm = {L: (softm[L].ravel().tobytes() if softm[L] is not None else None) for L in (F_CU, B_CU)}
        vo = via_ok.ravel().tobytes()
        zone = self.ic_zone[j0:j1 + 1, i0:i1 + 1].ravel().tobytes()
        wallm = self.chan_count[j0:j1 + 1, i0:i1 + 1].astype(np.int32)
        for (nid, cidx, term), (cj, ci) in self.chan_lines.items():
            if nid == net.idx:
                sel = (cj >= j0) & (cj <= j1) & (ci >= i0) & (ci <= i1)
                wallm[cj[sel] - j0, ci[sel] - i0] -= 1
        wall = np.clip(wallm, 0, 60).astype(np.uint8).ravel().tobytes()
        hist = {L: np.clip(self.history[L][j0:j1 + 1, i0:i1 + 1], 0, 40).astype(np.uint8).ravel().tobytes() for L in (F_CU, B_CU)}
        tgt = bytearray(2 * NL)
        vipset = set()
        for (L, i, j) in vip:
            if i0 <= i <= i1 and j0 <= j <= j1:
                vipset.add((j - j0) * Ww + (i - i0))
        if via_target:
            for L in (F_CU,):
                base = L * NL
                for m in range(NL):
                    if vo[m] and not oo[L][m]:
                        tgt[base + m] = 1
        if targets:
            for (L, i, j) in targets:
                if i0 <= i <= i1 and j0 <= j <= j1:
                    tgt[L * NL + (j - j0) * Ww + (i - i0)] = 1
        if not any(tgt):
            return None, set()
        gcost = [INF] * (2 * NL)
        parent = [-1] * (2 * NL)
        pdir = [-1] * (2 * NL)
        closed = bytearray(2 * NL)
        heap = []
        hp = [(i - i0, j - j0) for (i, j) in heur_pts]

        def h(il, jl):
            best = INF
            for (hi, hj) in hp:
                dx, dy = abs(hi - il), abs(hj - jl)
                v = 10 * max(dx, dy) + 4 * min(dx, dy)
                if v < best:
                    best = v
            return best if hp else 0

        for (L, i, j, c0) in sources:
            if not (i0 <= i <= i1 and j0 <= j <= j1):
                continue
            m = (j - j0) * Ww + (i - i0)
            n = L * NL + m
            if oo[L][m]:
                continue
            if c0 < gcost[n]:
                gcost[n] = c0
                heapq.heappush(heap, (c0 + h(i - i0, j - j0), n))
        expanded = 0
        found = -1
        while heap:
            f, n = heapq.heappop(heap)
            if closed[n]:
                continue
            closed[n] = 1
            if tgt[n]:
                found = n
                break
            expanded += 1
            if max_nodes and expanded > max_nodes:
                break
            L = n // NL
            m = n - L * NL
            jl = m // Ww
            il = m - jl * Ww
            gn = gcost[n]
            pd = pdir[n]
            ooL, odL, smL, hiL = oo[L], od[L], sm[L], hist[L]
            mult = LAYER_MULT[L]
            for d in range(8):
                ni = il + DIRS[d][0]
                nj = jl + DIRS[d][1]
                if ni < 0 or nj < 0 or ni >= Ww or nj >= Hw:
                    continue
                nm = nj * Ww + ni
                if ooL[nm]:
                    continue
                if d >= 4 and odL[nm] and odL[m]:
                    continue
                nn = L * NL + nm
                if closed[nn]:
                    continue
                c = STEP[d] * mult
                if pd != -1 and pd != d:
                    c += COST_TURN
                if smL is not None and smL[nm]:
                    c += SOFT_EXTRA
                if L == F_CU and zone[nm]:
                    c += ZONE_COST
                if hiL[nm]:
                    c += HIST_COST * hiL[nm]
                ng = gn + c
                if ng < gcost[nn]:
                    gcost[nn] = ng
                    parent[nn] = n
                    pdir[nn] = d
                    heapq.heappush(heap, (ng + h(ni, nj), nn))
            if allow_via and (vo[m] or m in vipset):
                L2 = 1 - L
                if not oo[L2][m]:
                    nn = L2 * NL + m
                    if not closed[nn]:
                        ng = gn + COST_VIA + VIA_WALL * wall[m]
                        if ng < gcost[nn]:
                            gcost[nn] = ng
                            parent[nn] = n
                            pdir[nn] = -1
                            heapq.heappush(heap, (ng + h(il, jl), nn))
        self.stats["expanded"] += expanded
        if found < 0:
            return None, set()
        cells = []
        n = found
        while n != -1:
            L = n // NL
            m = n - L * NL
            jl = m // Ww
            il = m - jl * Ww
            cells.append((L, il + i0, jl + j0))
            n = parent[n]
        cells.reverse()
        blockers = set()
        if soft:
            r = int(math.ceil((RULES["clearance"] + width / 2.0 + SLOP) / RES)) + 1
            for (L, i, j) in cells:
                if sm[L] is not None and sm[L][(j - j0) * Ww + (i - i0)]:
                    sub = self.route_raw[L][max(0, j - r):j + r + 1, max(0, i - r):i + r + 1]
                    for v in np.unique(sub):
                        if v != -1 and v != net.idx:
                            blockers.add(int(v))
        return cells, blockers

    # -- per net -----------------------------------------------------------------------
    def window_for(self, pts, margin_mm):
        m = int(round(margin_mm / RES))
        xs = [p[0] for p in pts]
        ys = [p[1] for p in pts]
        return (max(0, min(xs) - m), max(0, min(ys) - m), min(self.W - 1, max(xs) + m), min(self.H - 1, max(ys) + m))

    def copper_targets(self, net):
        """Every cell of the net's connected copper: connected clusters' terminals and route centrelines."""
        t = set()
        for c in net.clusters:
            if c.connected:
                t.update(c.terminals)
        for r in net.routes:
            t.update(r.cells)
        return t

    def vip_cells(self, net, clusters):
        """Direct SMD pad terminals where a via may sit in the pad (clear of every other net)."""
        out = []
        for c in clusters:
            if c.primary.thru or c.escapes:
                continue
            for t in c.terminals:
                if t[0] == F_CU and self._via_clear_exact(net, *self.grid.to_xy(t[1], t[2])):
                    out.append(t)
        return out

    def connect(self, net, cluster, anchor_pts, soft=False, vip=False):
        """Route `cluster` to the net's existing copper. Returns (Route|None, blockers).

        vip=True is the last resort before rip-up: a via may sit in the pad of the cluster being
        routed or in the pad it lands on when every exit on F.Cu is walled in."""
        targets = self.copper_targets(net)
        sources = []
        for t in cluster.terminals:
            sources.append((t[0], t[1], t[2], 0))
        widths = [w for w in net.widths if w <= cluster.allow] or [min(net.widths)]
        src_pts = [(t[1], t[2]) for t in cluster.terminals]
        allpts = src_pts + list(anchor_pts)
        vip_src, vip_tgt = [], []
        if vip:
            vip_src = self.vip_cells(net, [cluster])
            vip_tgt = self.vip_cells(net, [c for c in net.clusters if c.connected])
            targets = set(targets) | {(B_CU, t[1], t[2]) for t in vip_tgt}
        if soft:
            stages = [(12.0, 200000)]
        elif vip:
            stages = [(12.0, 200000)]
        else:
            stages = [(5.0, None), (12.0, None), (80.0, 250000)]
        for width in widths:
            for margin, cap in stages:
                win = self.window_for(allpts, margin)
                cells, blockers = self.search(net, width, sources, targets, anchor_pts, win, soft=soft, max_nodes=cap, vip=vip_src)
                if cells:
                    start_term = cells[0]
                    end_cell = cells[-1]
                    start = ("escape", cluster, start_term) if start_term in cluster.escapes else ("pad", cluster, start_term)
                    end = ("copper",)
                    for c in net.clusters:
                        if c.connected and (end_cell in c.terminals or (end_cell[0] == B_CU and (F_CU, end_cell[1], end_cell[2]) in c.terminals and end_cell in targets)):
                            end = ("escape", c, end_cell) if end_cell in c.escapes else ("pad", c, end_cell)
                    route = Route(cells, width, start, end)
                    if end[0] == "pad" and end_cell[0] == B_CU and not end[1].primary.thru:
                        route.via_end = True
                        route.via_end_layer = "F.Cu"
                        self.stats["viaInPad"] += 1
                        net.via_in_pad.append(end[1].key)
                    if len(cells) > 1 and cells[0][1:] == cells[1][1:] and cells[0][0] != cells[1][0] and not cluster.primary.thru:
                        self.stats["viaInPad"] += 1
                        net.via_in_pad.append(cluster.key)
                    return route, blockers
        return None, set()

    def route_net(self, net):
        """Prim's order over clusters; each cluster to the existing copper. Returns list of blocker net ids on failure."""
        clusters = [c for c in net.clusters]
        for c in clusters:
            c.connected = False
        net.routes = []
        net.failed = []
        net.last_soft = []
        # start from the biggest pad (the trunk grows from the power pads)
        start = max(clusters, key=lambda c: (c.allow, c.primary.half_long * c.primary.half_short))
        start.connected = True
        connected = [start]
        remaining = [c for c in clusters if c is not start]
        blockers_all = set()
        while remaining:
            best = None
            for c in remaining:
                for k in connected:
                    d = math.dist(c.xy, k.xy)
                    if best is None or d < best[0]:
                        best = (d, c, k)
            d, c, k = best
            remaining.remove(c)
            anchor = [(t[1], t[2]) for t in k.terminals]
            route, _ = self.connect(net, c, anchor)
            if route is None:
                route, _ = self.connect(net, c, anchor, vip=True)
            if route is None:
                soft_route, blockers = self.connect(net, c, anchor, soft=True)
                blockers_all |= blockers
                if soft_route is not None:
                    net.last_soft.extend(soft_route.cells)
                net.failed.append((c.key, "no path" if not blockers else "blocked by %s" % sorted(self.name_of(b) for b in blockers)))
                c.connected = False
                continue
            self.commit(net, route)
            c.connected = True
            connected.append(c)
        return blockers_all

    def name_of(self, nid):
        for n in self.nets.values():
            if n.idx == nid:
                return n.name
        return "?"

    def commit(self, net, route):
        # junction: if the route ends inside another route of this net, split it there
        end = route.cells[-1]
        for r in net.routes:
            if end in r.cells:
                r.breaks.add(r.cells.index(end))
        for term in (route.start, route.end):
            if term[0] == "escape":
                net.used_escapes.add((term[1].idx, term[2]))
        net.routes.append(route)
        self.stamp_route(net, route, 1)
        # a routed cluster no longer needs its other escape: release that reservation
        for term in (route.start, route.end):
            if term[0] in ("escape", "pad"):
                self.release_escapes(net, term[1])
            if term[0] == "escape":
                self._stamp_channel(net, term[1], term[2], -1)

    def release_escapes(self, net, cluster):
        for t in list(cluster.escapes):
            if (cluster.idx, t) not in net.used_escapes and (cluster.idx, t) not in cluster.__dict__.setdefault("released", set()):
                self.stamp_stub(net, cluster, t, -1)
                cluster.released.add((cluster.idx, t))

    def reserve_escapes(self, net, cluster):
        for t in list(cluster.escapes):
            if (cluster.idx, t) in cluster.__dict__.get("released", set()):
                self.stamp_stub(net, cluster, t, 1)
                cluster.released.discard((cluster.idx, t))
            else:
                self._stamp_channel(net, cluster, t, 1)

    def rip_cluster(self, net, cluster):
        """Rip the stub of one plane-net cluster (its route to the plane) so a signal can pass; the
        cluster is re-queued as a plane retry."""
        keep = []
        for r in net.routes:
            if r.start[1] is cluster:
                self.stamp_route(net, r, -1)
                for (L, i, j) in r.cells:
                    self.history[L][max(0, j - 2):j + 3, max(0, i - 2):i + 3] += 1
            else:
                keep.append(r)
        net.routes = keep
        net.used_escapes = {(ci, t) for (ci, t) in net.used_escapes if ci != cluster.idx}
        cluster.connected = False
        self.reserve_escapes(net, cluster)
        if cluster.key not in {k for k, _ in net.failed}:
            net.failed.append((cluster.key, "ripped for a signal"))
        self.stats["rips"] += 1
        self.rip_total += 1

    def rip(self, net):
        g = self.grid
        for r in net.routes:
            self.stamp_route(net, r, -1)
            # remember where the contested copper was: a little dearer for every later search
            for (L, i, j) in r.cells:
                self.history[L][max(0, j - 2):j + 3, max(0, i - 2):i + 3] += 1
        net.routes = []
        net.used_escapes = set()
        for c in net.clusters:
            c.connected = False
            self.reserve_escapes(net, c)
        net.rips += 1
        self.rip_total += 1
        self.stats["rips"] += 1

    # -- planes --------------------------------------------------------------------------
    def route_plane_net(self, net, retry=False):
        g = self.grid
        if retry:
            failed = {k for k, _ in net.failed}
            net.failed = []
        for c in net.clusters:
            if c.primary.thru:
                c.connected = True
                continue
            if retry and (c.connected or c.key not in failed):
                continue
            sources = [(t[0], t[1], t[2], 0) for t in c.terminals]
            win = self.window_for([(t[1], t[2]) for t in c.terminals], RULES["via_search_mm"])
            # a via site, or the net's own copper already on its way to the plane (a neighbour's stub)
            own = {cell for cell in self.copper_targets(net) if cell[0] == F_CU}
            cells, _ = self.search(net, RULES["track"], sources, own, [], win, allow_via=False, via_target=True)
            if cells is None:
                # via in pad: the pad centre if a via there clears every other net
                i, j = g.to_cell(*c.xy)
                ok = self._via_clear_exact(net, c.primary.x, c.primary.y)
                if ok:
                    r = Route([(F_CU, i, j)], RULES["track"], ("pad", c, (F_CU, i, j)), ("via",))
                    r.via_end = True
                    self.commit(net, r)
                    c.connected = True
                    net.via_in_pad.append(c.key)
                    self.stats["viaInPad"] += 1
                else:
                    net.failed.append((c.key, "no via site within %.0f mm" % RULES["via_search_mm"]))
                continue
            start_term = cells[0]
            start = ("escape", c, start_term) if start_term in c.escapes else ("pad", c, start_term)
            joined = cells[-1] in own
            r = Route(cells, RULES["track"], start, ("copper",) if joined else ("via",))
            r.via_end = not joined
            self.commit(net, r)
            c.connected = True

    def _via_clear_exact(self, net, x, y):
        """Exact geometry: may a via of this net sit at (x, y)? Pads, routes and vias of other nets,
        every through pad, the outline and existing vias of any net are checked with real distances."""
        g = self.grid
        rv = net.via / 2.0
        i, j = g.to_cell(x, y)
        if not g.in_bounds(i, j) or not self.inside_for(net.via)[j, i]:
            return False
        reach = rv + self.big_clr_val + 1.5
        for p in self.board.pads:
            if abs(p.x - x) > reach + p.half_long or abs(p.y - y) > reach + p.half_long:
                continue
            if p.net == net.name and not p.thru:
                continue
            if p.thru and p.net == net.name:
                need = net.drill / 2.0 + RULES["hole_to_hole"] + (p.drill or 0) / 2.0 + SLOP   # same net: the holes must not meet
            else:
                need = rv + max(RULES["clearance"], p.clearance)
            if p.thru and p.net != net.name:
                need = max(need, net.drill / 2.0 + RULES["hole_to_hole"] + (p.drill or 0) / 2.0)
            for poly in p.polys:
                if _point_poly_distance(x, y, poly) < need:
                    return False
        for other in self.nets.values():
            if other.idx == net.idx:
                continue
            for r in other.routes:
                need = rv + RULES["clearance"] + r.width / 2.0
                for (ax, ay, bx, by) in _route_segments(g, r.cells):
                    if abs(ax - x) > 3 and abs(bx - x) > 3:
                        continue
                    if _seg_distance(x, y, ax, ay, bx, by) < need:
                        return False
        for (vi, vj, nid, dia, drill) in self.vias:
            vx, vy = g.to_xy(vi, vj)
            if math.hypot(vx - x, vy - y) < self.via_gap(net, nid, dia, drill):
                return False
        return True

    def _via_clear_other(self, net, i, j):
        g = self.grid
        r = (RULES["clearance"] + net.via / 2.0 + SLOP) / RES
        R = int(math.ceil(r)) + 1
        for L in (F_CU, B_CU):
            for raw in (self.pad_raw[L], self.route_raw[L]):
                sub = raw[max(0, j - R):j + R + 1, max(0, i - R):i + R + 1]
                jj, ii = np.nonzero((sub != -1) & (sub != net.idx))
                for a, b in zip(jj, ii):
                    if (a + max(0, j - R) - j) ** 2 + (b + max(0, i - R) - i) ** 2 <= r * r:
                        return False
        for (vi, vj, nid, dia, drill) in self.vias:
            if math.hypot(vi - i, vj - j) * RES < self.via_gap(net, nid, dia, drill):
                return False
        return bool(self.inside_for(net.via)[j, i])

    # -- driver --------------------------------------------------------------------------
    def mst_length(self, net):
        pts = [c.xy for c in net.clusters]
        if len(pts) < 2:
            return 0.0
        inn = [pts[0]]
        rest = pts[1:]
        total = 0.0
        while rest:
            best = min(((math.dist(a, b), b) for a in inn for b in rest), key=lambda x: x[0])
            total += best[0]
            inn.append(best[1])
            rest.remove(best[1])
        return total

    def run(self, only=None, planes=True, rip_per_net=8, rip_global=400, priority=None):
        t0 = time.time()
        self.rip_total = 0
        for n in self.nets.values():
            n.rips = 0
        if planes:
            # plane stubs first: the shortest connections on the board, and their vias then shape
            # the signal routing instead of hunting for holes in it afterwards
            for name in RULES["planes"]:
                net = self.nets.get(name)
                if net is None or (only is not None and name not in only):
                    continue
                t1 = time.time()
                self.route_plane_net(net)
                log("  %-28s plane %s: %d smd stubs, %d via-in-pad, %d failed, %.1fs" % (
                    net.name, net.plane, len(net.routes) - len(net.via_in_pad), len(net.via_in_pad), len(net.failed), time.time() - t1))
        signal = [n for n in self.nets.values() if not n.plane and len(n.clusters) >= 2 and (only is None or n.name in only)]
        for n in signal:
            n.mst_len = self.mst_length(n)
        first = [n for n in signal if n.name in (priority or ())]
        rest = [n for n in signal if n.name not in (priority or ())]
        queue = sorted(first, key=lambda n: n.mst_len) + sorted(rest, key=lambda n: n.mst_len)
        log("routing %d signal nets, shortest first (%.1f mm .. %.1f mm MST)%s" % (
            len(queue), queue[0].mst_len if queue else 0, queue[-1].mst_len if queue else 0,
            "" if not first else ", %d nets that failed last pass go first: %s" % (len(first), [n.name for n in first])))
        done = []
        order_no = 0
        best_state = None
        while queue:
            net = queue.pop(0)
            if net.routes:
                self.rip(net)
            t1 = time.time()
            blockers = self.route_net(net)
            order_no += 1
            net.routed_order = order_no
            log("  %-28s %2d clusters  %s  %d routes, %d failed, %.1fs%s" % (
                net.name, len(net.clusters), "/".join("%.2g" % w for w in net.widths), len(net.routes), len(net.failed), time.time() - t1,
                "" if not net.failed else "  FAILED %s" % net.failed))
            score = sum(len(n.failed) for n in self.nets.values() if n not in queue) + sum(max(0, len(n.clusters) - 1) for n in queue)
            if best_state is None or score < best_state[0]:
                best_state = (score, self.snapshot())
            if net.failed and blockers and net.rips < rip_per_net and self.rip_total < rip_global:
                cands = sorted((self.nets[self.name_of(b)] for b in blockers if self.nets[self.name_of(b)].routes and not self.nets[self.name_of(b)].plane),
                               key=lambda n: -(n.routed_order or 0))[:4]
                stubs = []
                soft = set()
                for (L, i, j) in net.last_soft:
                    for di in range(-6, 7):
                        for dj in range(-6, 7):
                            soft.add((i + di, j + dj))
                # plane stubs are ripped only when nothing else blocks: a stub moves easily, a
                # signal net that has to be re-routed around a moved stub does not
                for b in (blockers if not cands else ()):
                    pn = self.nets[self.name_of(b)]
                    if not pn.plane:
                        continue
                    for r in list(pn.routes):
                        if any((i, j) in soft for (_, i, j) in r.cells):
                            stubs.append((pn, r.start[1]))
                if cands or stubs:
                    log("    rip-up %s%s and retry %s" % ([c.name for c in cands], "" if not stubs else " + plane stubs %s" % [c.key for _, c in stubs], net.name))
                    for c in cands:
                        self.rip(c)
                        if c in queue:
                            queue.remove(c)
                    for pn, cl in stubs:
                        self.rip_cluster(pn, cl)
                    net.rips += 1
                    queue.insert(0, net)
                    for c in cands:
                        queue.insert(1, c)
                    continue
            # a signal landed: give any ripped plane stubs their spot back right away
            for name in RULES["planes"]:
                pn = self.nets.get(name)
                if pn is not None and pn.failed and planes:
                    self.route_plane_net(pn, retry=True)
            done.append(net)
        if planes:
            # second chance for plane stubs that were walled in by reservations the signal routing has since released
            for name in RULES["planes"]:
                net = self.nets.get(name)
                if net is None or not net.failed or (only is not None and name not in only):
                    continue
                before = len(net.failed)
                self.route_plane_net(net, retry=True)
                log("  %-28s plane retry: %d of %d stubs recovered" % (net.name, before - len(net.failed), before))
        final = sum(len(n.failed) for n in self.nets.values())
        if best_state is not None and best_state[0] < final:
            log("  restoring the best intermediate state (%d failed connections instead of %d)" % (best_state[0], final))
            self.restore(best_state[1])
            if planes:
                for name in RULES["planes"]:
                    pn = self.nets.get(name)
                    if pn is not None and pn.failed:
                        self.route_plane_net(pn, retry=True)
            final = sum(len(n.failed) for n in self.nets.values())
        log("routing done in %.1fs, %d node expansions, %d rip-ups, %d failed connections" % (time.time() - t0, self.stats["expanded"], self.stats["rips"], final))
        return final

    def reset(self):
        """Drop every route and reservation state so a fresh pass can start (history is kept)."""
        for net in self.nets.values():
            if net.routes:
                self.rip(net)
            net.failed = []
            net.via_in_pad = []
            net.routed_order = None
            net.used_escapes = set()
            for c in net.clusters:
                c.connected = False
        self.rip_total = 0

    def snapshot(self):
        return {name: (list(n.routes), set(n.used_escapes), list(n.failed), list(n.via_in_pad), n.routed_order) for name, n in self.nets.items()}

    def restore(self, snap):
        self.reset()
        for name, (routes, used, failed, vip, order) in snap.items():
            net = self.nets[name]
            net.used_escapes = set(used)
            net.failed = list(failed)
            net.via_in_pad = list(vip)
            net.routed_order = order
            for r in routes:
                net.routes.append(r)
                self.stamp_route(net, r, 1)
            for c in net.clusters:
                c.connected = any(r.start[1] is c or (r.end[0] in ("pad", "escape") and r.end[1] is c) for r in routes) or (net.plane and c.primary.thru)

    # -- plan emission -----------------------------------------------------------------------
    def _waypoints(self, net, route):
        g = self.grid
        cells = route.cells
        pts = []

        def xy(c):
            return list(g.to_xy(c[1], c[2]))

        # start
        kind, cl, term = route.start
        if kind == "pad":
            if term[0] == B_CU:
                pts.append({"pad": cl.primary.key, "layer": "B.Cu"})
            else:
                pts.append(cl.primary.key)
        else:
            pts.append(xy(cells[0]))
        # middle: collinear merge with forced breaks and layer changes
        k = 1
        n = len(cells)
        while k < n:
            L, i, j = cells[k]
            pL, pi, pj = cells[k - 1]
            if L != pL:
                # via at this cell
                pts.append({"x": xy(cells[k])[0], "y": xy(cells[k])[1], "layer": LAYER_NAMES[L]})
                k += 1
                continue
            di, dj = i - pi, j - pj
            m = k
            while m + 1 < n and cells[m + 1][0] == L and (cells[m + 1][1] - cells[m][1], cells[m + 1][2] - cells[m][2]) == (di, dj) and m not in route.breaks:
                m += 1
            if m == n - 1:
                break
            pts.append(xy(cells[m]))
            k = m + 1
        # end
        last = cells[-1]
        ek = route.end[0]
        if route.via_end:
            p = xy(last)
            if len(cells) == 1 and kind == "pad":
                p = [cl.primary.x, cl.primary.y]
            pts.append({"x": p[0], "y": p[1], "layer": route.via_end_layer})
            if ek == "pad":
                pts.append(route.end[1].primary.key)
        elif ek == "pad":
            cl = route.end[1]
            if pts and isinstance(pts[-1], dict) and pts[-1].get("layer") and len(cells) > 1 and cells[-1][1:] == cells[-2][1:]:
                pass
            pts.append(cl.primary.key)
        else:
            pts.append(xy(last))
        # a via exactly at the last cell followed by the pad name: keep both (the marker then the pad)
        return pts

    def plan(self):
        entries = []
        g = self.grid
        for net in sorted(self.nets.values(), key=lambda n: (n.routed_order or 10 ** 6, n.name)):
            if not net.routes:
                continue
            by_width = defaultdict(list)
            for r in net.routes:
                pts = self._waypoints(net, r)
                if len(pts) >= 2:
                    by_width[r.width].append(pts)
            stubs = []
            for (cidx, term) in sorted(net.used_escapes):
                cl = net.clusters[cidx]
                stubs.append([cl.primary.key, list(g.to_xy(term[1], term[2]))])
            if stubs:
                entries.append({"net": net.name, "width": RULES["stub"], "viaSize": net.via, "viaDrill": net.drill, "paths": stubs})
            for w in sorted(by_width, reverse=True):
                entries.append({"net": net.name, "width": w, "viaSize": net.via, "viaDrill": net.drill, "paths": by_width[w]})
        return entries

    def report(self):
        nets = {}
        for net in self.nets.values():
            if len(net.clusters) < 2 and not net.plane:
                continue
            nets[net.name] = {
                "clusters": len(net.clusters), "pads": len(net.pads), "routes": len(net.routes),
                "widths": sorted({r.width for r in net.routes}, reverse=True), "plane": net.plane,
                "failed": net.failed, "viaInPad": net.via_in_pad, "ripUps": net.rips, "order": net.routed_order,
                "mstMm": round(net.mst_len, 2),
            }
        return {"rules": RULES, "nets": nets, "stats": dict(self.stats),
                "unrouted": [(n, f) for n in nets for f in nets[n]["failed"]]}


def main(argv=None):
    ap = argparse.ArgumentParser(description=__doc__.split("\n\n")[0])
    ap.add_argument("board")
    ap.add_argument("--out", help="plan JSON (default: <board dir>/fable-esc-routing-plan.json)")
    ap.add_argument("--report", help="router report JSON")
    ap.add_argument("--nets", help="comma separated subset of nets")
    ap.add_argument("--no-planes", action="store_true")
    ap.add_argument("--passes", type=int, default=3, help="full passes; nets that failed a pass are routed first in the next")
    ap.add_argument("--verbose", action="store_true")
    a = ap.parse_args(argv)
    board = Board(a.board)
    r = Router(board, a.verbose)
    only = set(a.nets.split(",")) if a.nets else None
    best = None
    priority = None
    for k in range(1, a.passes + 1):
        if k > 1:
            r.reset()
        log("=== pass %d of %d ===" % (k, a.passes))
        failed = r.run(only=only, planes=not a.no_planes, priority=priority)
        names = sorted({n.name for n in r.nets.values() if n.failed})
        log("=== pass %d: %d failed connections in %s" % (k, failed, names))
        if best is None or failed < best[0]:
            best = (failed, r.snapshot(), k)
        if failed == 0:
            break
        priority = names
    if best is not None:
        r.restore(best[1])
        log("keeping pass %d (%d failed connections)" % (best[2], best[0]))
    entries = r.plan()
    rep = r.report()
    out = a.out or os.path.join(os.path.dirname(os.path.abspath(a.board)), "fable-esc-routing-plan.json")
    with open(out, "w", encoding="utf-8") as f:
        json.dump({"engine": "Claude Fable 5.1 grid maze router (ai_router.py)", "board": os.path.basename(a.board),
                   "rules": {k: v for k, v in RULES.items() if k in ("track", "clearance", "via", "drill", "via_small", "drill_small", "edge", "planes", "wide", "mid")},
                   "nets": entries}, f, indent=1)
    log("plan: %s (%d entries, %d nets)" % (out, len(entries), len({e["net"] for e in entries})))
    if rep["unrouted"]:
        log("UNROUTED: %s" % rep["unrouted"])
    if a.report:
        with open(a.report, "w", encoding="utf-8") as f:
            json.dump(rep, f, indent=1)
    return 0 if not rep["unrouted"] else 3


if __name__ == "__main__":
    sys.exit(main())