main
ae007 Project page: AFS_Adom rev A (Rice Eclipse AFS clean-room AI redesign): highlight reel and narrated process video with… cbe460e 7d ago
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546
"""Grid A* router for the AFS_Adom board (F.Cu / B.Cu signal layers, In1 GND plane, In2 3V3 plane + VBAT island).

Produces tracks/vias as KiCad s-expressions and a JSON plan for live replay through the KiCad bridge.
"""
import sys, json, math, heapq, time
sys.path.insert(0, '/tmp/claude-1001/-home-adom-project/8819fb5f-c2c6-4524-9528-99428cd6b88e/scratchpad/gen')
from kicad_gen import *
import pcb as B

G = 0.1                      # grid pitch mm
CLR = 0.15                   # copper clearance
EDGE = 0.4                   # keep copper this far from the board edge
VIA_D, VIA_DRILL = 0.6, 0.3
PVIA_D, PVIA_DRILL = 0.8, 0.4
LAYERS = ['F.Cu', 'B.Cu']
NX = int(round(B.BW / G)) + 1
NY = int(round(B.BH / G)) + 1


def gx(x): return int(round((x - B.BX0) / G))
def gy(y): return int(round((y - B.BY0) / G))
def wx(i): return B.BX0 + i * G
def wy(j): return B.BY0 + j * G


class Grid:
    def __init__(self):
        # blocked[layer] bytearray: bit0 = blocked for trace centre (dilated), stored per net-independent
        self.blk = {l: bytearray(NX * NY) for l in LAYERS}        # obstacles for traces (dilated by half-width + clearance)
        self.blk_via = {l: bytearray(NX * NY) for l in LAYERS}    # obstacles for via centres
        self.owner = {l: [None] * (NX * NY) for l in LAYERS}      # net that owns the copper at a cell (undilated)
        self.ring = {l: [None] * (NX * NY) for l in LAYERS}       # net whose clearance ring covers the cell ('__multi__' if several)

    def fill_rect(self, arr, x0, y0, x1, y1, val=1, owner=None, net=None, ring=None):
        if owner is not None:
            i0, i1 = max(0, gx(x0)), min(NX - 1, gx(x1))
            j0, j1 = max(0, gy(y0)), min(NY - 1, gy(y1))
        else:   # blocking areas only cover cells strictly inside the rectangle
            i0, i1 = max(0, int(math.ceil((x0 - B.BX0) / G - 1e-6))), min(NX - 1, int(math.floor((x1 - B.BX0) / G + 1e-6)))
            j0, j1 = max(0, int(math.ceil((y0 - B.BY0) / G - 1e-6))), min(NY - 1, int(math.floor((y1 - B.BY0) / G + 1e-6)))
        for j in range(j0, j1 + 1):
            base = j * NX
            if owner is not None:
                for i in range(i0, i1 + 1):
                    owner[base + i] = net
            elif ring is not None:
                for i in range(i0, i1 + 1):
                    c = base + i
                    ring[c] = net if ring[c] in (None, net) else '__multi__'
            else:
                arr[base + i0:base + i1 + 1] = b'\x01' * (i1 - i0 + 1)

    def fill_circle(self, arr, cx, cy, r, owner=None, net=None, ring=None):
        ci, cj = (cx - B.BX0) / G, (cy - B.BY0) / G
        rr = int(math.ceil(r / G)) + 1
        for dj in range(-rr, rr + 1):
            j = int(round(cj)) + dj
            if j < 0 or j >= NY:
                continue
            dj = j - cj
            half = math.sqrt(max(0.0, (r / G) ** 2 - dj * dj))
            if owner is not None:
                i0, i1 = max(0, int(round(ci - half))), min(NX - 1, int(round(ci + half)))
            else:
                i0, i1 = max(0, int(math.ceil(ci - half + 1e-6))), min(NX - 1, int(math.floor(ci + half - 1e-6)))
            if i1 < i0:
                continue
            base = j * NX
            if owner is not None:
                for i in range(i0, i1 + 1):
                    owner[base + i] = net
            elif ring is not None:
                for i in range(i0, i1 + 1):
                    c = base + i
                    ring[c] = net if ring[c] in (None, net) else '__multi__'
            else:
                arr[base + i0:base + i1 + 1] = b'\x01' * (i1 - i0 + 1)


class Pad:
    def __init__(self, ref, num, net, x, y, w, h, tht, drill=0.0, layers=None):
        self.ref, self.num, self.net, self.x, self.y, self.w, self.h, self.tht, self.drill = ref, num, net, x, y, w, h, tht, drill
        self.layers = layers


def load_pads():
    pads = []
    for ref, c in B.COMPS.items():
        name = c['footprint'].split(':')[1]
        x, y, r = B.PL[ref]
        t = B.fp_tree(name)
        for p in find(t, 'pad'):
            at = find1(p, 'at'); sz = find1(p, 'size')
            px, py = float(at[1]), float(at[2])
            pang = float(at[3]) if len(at) > 3 else 0.0
            w, h = float(sz[1]), float(sz[2])
            if abs(((pang + r) % 180) - 90) < 1:
                w, h = h, w
            dx, dy = B.rotpt(px, py, r)
            net = B.net_of(ref, uq(p[1]))
            kind = p[2]
            drill = 0.0
            d = find1(p, 'drill')
            if d:
                if d[1] == 'oval':
                    drill = max(float(d[2]), float(d[3]) if len(d) > 3 and not isinstance(d[3], list) else 0.0)
                else:
                    drill = float(d[1])
            layers = [uq(l) for l in find1(p, 'layers')[1:]]
            if kind == 'np_thru_hole':
                pads.append(Pad(ref, uq(p[1]), None, x + dx, y + dy, w, h, True, drill, layers))
            else:
                pads.append(Pad(ref, uq(p[1]), net, x + dx, y + dy, w, h, kind == 'thru_hole', drill, layers))
    return pads


class Router:
    def __init__(self):
        self.pads = load_pads()
        self.grid = Grid()
        self.tracks = []    # (net, layer, width, x0, y0, x1, y1)
        self.vias = []      # (net, x, y, size, drill)
        self.plan = []      # per-net replay plan
        self.netpads = {}
        for p in self.pads:
            if p.net:
                self.netpads.setdefault(p.net, []).append(p)
        self.width = {}
        self.via_size = {}
        self.unrouted = []
        self.done_pads = set()
        self.NECK_R = 1.2
        self.NECK_W = 0.2
        # board edge
        for l in LAYERS:
            for arr, m in ((self.grid.blk[l], EDGE), (self.grid.blk_via[l], EDGE + VIA_D / 2)):
                self.grid.fill_rect(arr, B.BX0, B.BY0, B.BX0 + m, B.BY1)
                self.grid.fill_rect(arr, B.BX1 - m, B.BY0, B.BX1, B.BY1)
                self.grid.fill_rect(arr, B.BX0, B.BY0, B.BX1, B.BY0 + m)
                self.grid.fill_rect(arr, B.BX0, B.BY1 - m, B.BX1, B.BY1)
        # pads as obstacles (dilated); owner map undilated
        for p in self.pads:
            self.add_pad_obstacle(p)
        # keep traces/vias off the LX cutout on inner layers is automatic; keep vias away from the LX node area on top? no.

    def net_width(self, net):
        if net in self.width:
            return self.width[net]
        if net in ('VBAT_IN',):
            return 1.5
        if net in ('VBAT', 'VSYS', 'SW_5V', 'SW_3V3', '+5V'):
            return 0.6
        if net in ('DVDD', 'VREG_LX', 'BST_5V', 'BST_3V3', '+3V3', 'GND', 'VREG_AVDD', 'MAG_CAP'):
            return 0.35
        if net.startswith('USB_D'):
            return 0.2
        return 0.2

    def net_via(self, net):
        if net in ('VBAT', 'VBAT_IN', 'VSYS', '+5V', 'SW_5V', 'SW_3V3'):
            return PVIA_D, PVIA_DRILL
        return VIA_D, VIA_DRILL

    def add_pad_obstacle(self, p):
        half_w = 0.2 / 2   # dilate by the widest signal trace half width later per net (we use a fixed max for safety)
        lays = LAYERS if p.tht else ['F.Cu']
        for l in lays:
            d = CLR                   # clearance ring; the trace half-width is enforced by the neighbourhood check in astar()
            self.grid.fill_rect(self.grid.blk[l], p.x - p.w / 2 - d, p.y - p.h / 2 - d, p.x + p.w / 2 + d, p.y + p.h / 2 + d)
            self.grid.fill_rect(None, p.x - p.w / 2 - d, p.y - p.h / 2 - d, p.x + p.w / 2 + d, p.y + p.h / 2 + d, ring=self.grid.ring[l], net=p.net or '__npth__')
            dv = CLR + VIA_D / 2
            self.grid.fill_rect(self.grid.blk_via[l], p.x - p.w / 2 - dv, p.y - p.h / 2 - dv, p.x + p.w / 2 + dv, p.y + p.h / 2 + dv)
            self.grid.fill_rect(None, p.x - p.w / 2, p.y - p.h / 2, p.x + p.w / 2, p.y + p.h / 2, owner=self.grid.owner[l], net=p.net or '__npth__')
        if p.tht:
            # THT barrel blocks vias on both layers already; also block the other layer's traces (done) and keep clear of hole on all
            pass

    def add_track_obstacle(self, net, layer, w, x0, y0, x1, y1):
        d = CLR + w / 2
        dv = CLR + VIA_D / 2 + w / 2
        n = max(1, int(math.hypot(x1 - x0, y1 - y0) / (G * 2)))
        for k in range(n + 1):
            t = k / n
            x, y = x0 + (x1 - x0) * t, y0 + (y1 - y0) * t
            self.grid.fill_circle(self.grid.blk[layer], x, y, d)
            self.grid.fill_circle(None, x, y, d, ring=self.grid.ring[layer], net=net)
            self.grid.fill_circle(self.grid.blk_via[layer], x, y, dv)
            self.grid.fill_circle(None, x, y, w / 2, owner=self.grid.owner[layer], net=net)

    def add_via_obstacle(self, net, x, y, size):
        for l in LAYERS:
            self.grid.fill_circle(self.grid.blk[l], x, y, size / 2 + CLR)
            self.grid.fill_circle(None, x, y, size / 2 + CLR, ring=self.grid.ring[l], net=net)
            self.grid.fill_circle(self.grid.blk_via[l], x, y, size / 2 + CLR + VIA_D / 2)
            self.grid.fill_circle(None, x, y, size / 2, owner=self.grid.owner[l], net=net)

    # ------------------------------------------------------------ A*
    def neck_cells(self, net):
        """Cells within NECK_R of a fine-pitch pad of `net` (traces are necked to NECK_W there)."""
        out = set()
        for p in self.netpads.get(net, []):
            if min(p.w, p.h) < 0.5:
                rr = int(self.NECK_R / G)
                ci, cj = gx(p.x), gy(p.y)
                for dj in range(-rr, rr + 1):
                    for di in range(-rr, rr + 1):
                        if di * di + dj * dj <= rr * rr:
                            i, j = ci + di, cj + dj
                            if 0 <= i < NX and 0 <= j < NY:
                                out.add(j * NX + i)
        return out

    def astar(self, net, sources, goals, width, via_cost=25.0, max_nodes=900000, extra_block=None):
        """sources/goals: sets of (layer_idx, cell). Returns list of (layer_idx, cell) path or None."""
        neck = self.neck_cells(net) if width > self.NECK_W else set()
        blk = [self.grid.blk[l] for l in LAYERS]
        blkv = [self.grid.blk_via[l] for l in LAYERS]
        own = [self.grid.owner[l] for l in LAYERS]
        rng = [self.grid.ring[l] for l in LAYERS]
        # extra dilation for wide nets: require neighbours free too
        ext = max(1, int(math.ceil((width / 2) / G)))
        goalset = goals
        gx_ = [c % NX for c in goals]; gy_ = [c // NX for c in goals]
        if not goals:
            return None
        # heuristic: octile distance to nearest goal (sampled)
        gsample = list(goals)[:: max(1, len(goals) // 40)]
        gsx = [c % NX for c in gsample]; gsy = [c // NX for c in gsample]

        def h(c):
            x, y = c % NX, c // NX
            best = 1e9
            for sx, sy in zip(gsx, gsy):
                dx, dy = abs(x - sx), abs(y - sy)
                v = (dx + dy) + (1.41421 - 2) * min(dx, dy)
                if v < best:
                    best = v
            return best * 0.98

        openh = []
        gcost = {}
        parent = {}
        for s in sources:
            gcost[s] = 0.0
            heapq.heappush(openh, (h(s[1]), 0.0, s))
        nbrs = [(1, 0, 1.0), (-1, 0, 1.0), (0, 1, 1.0), (0, -1, 1.0), (1, 1, 1.41421), (1, -1, 1.41421), (-1, 1, 1.41421), (-1, -1, 1.41421)]
        expanded = 0

        def free(li, c):
            # cell is routable for this net if not blocked, or blocked only by own-net copper
            if blk[li][c]:
                if own[li][c] != net and rng[li][c] != net:
                    return False
            e = 1 if c in neck else ext
            if e:
                x, y = c % NX, c // NX
                for ddx in range(-e, e + 1):
                    for ddy in range(-e, e + 1):
                        xx, yy = x + ddx, y + ddy
                        if xx < 0 or yy < 0 or xx >= NX or yy >= NY:
                            return False
                        cc = yy * NX + xx
                        if blk[li][cc] and own[li][cc] != net and rng[li][cc] != net:
                            return False
            if extra_block and c in extra_block:
                return False
            return True

        while openh:
            f, gc, cur = heapq.heappop(openh)
            if gcost.get(cur, 1e18) < gc - 1e-9:
                continue
            li, c = cur
            if c in goalset and li == 0 or (c in goalset and li == 1 and self.goal_layer_ok):
                # reconstruct
                path = [cur]
                while cur in parent:
                    cur = parent[cur]
                    path.append(cur)
                return path[::-1]
            expanded += 1
            if expanded > max_nodes:
                return None
            x, y = c % NX, c // NX
            for dx, dy, cost in nbrs:
                xx, yy = x + dx, y + dy
                if xx < 0 or yy < 0 or xx >= NX or yy >= NY:
                    continue
                cc = yy * NX + xx
                if not free(li, cc):
                    continue
                # no corner cutting through blocked orthogonal cells
                if dx and dy:
                    if not free(li, y * NX + xx) or not free(li, yy * NX + x):
                        continue
                nc = gc + cost
                key = (li, cc)
                if nc < gcost.get(key, 1e18):
                    gcost[key] = nc
                    parent[key] = cur
                    heapq.heappush(openh, (nc + h(cc), nc, key))
            # via
            if not blkv[0][c] and not blkv[1][c] or (own[0][c] == net and own[1][c] == net):
                ol = 1 - li
                if free(ol, c):
                    nc = gc + via_cost
                    key = (ol, c)
                    if nc < gcost.get(key, 1e18):
                        gcost[key] = nc
                        parent[key] = cur
                        heapq.heappush(openh, (nc + h(c), nc, key))
        return None

    # ------------------------------------------------------------ helpers
    def pad_cells(self, p, layer_idx):
        cells = set()
        i0, i1 = gx(p.x - p.w / 2 + 0.05), gx(p.x + p.w / 2 - 0.05)
        j0, j1 = gy(p.y - p.h / 2 + 0.05), gy(p.y + p.h / 2 - 0.05)
        for j in range(max(0, j0), min(NY - 1, j1) + 1):
            for i in range(max(0, i0), min(NX - 1, i1) + 1):
                cells.add(j * NX + i)
        if not cells:
            cells.add(gy(p.y) * NX + gx(p.x))
        return cells

    def net_copper_cells(self, net):
        """All cells owned by `net` (pads + tracks + vias) per layer."""
        out = set()
        for li, l in enumerate(LAYERS):
            own = self.grid.owner[l]
            for c in range(NX * NY):
                if own[c] == net:
                    out.add((li, c))
        return out

    def commit_path(self, net, path, width, via):
        """Turn a cell path into segments and vias; register obstacles. Segments inside neck zones are NECK_W wide."""
        neck = self.neck_cells(net) if width > self.NECK_W else set()
        segs = []
        vias = []
        # split by layer
        cur_layer = path[0][0]
        pts = [path[0]]
        for node in path[1:]:
            if node[0] != cur_layer:
                vias.append(node[1])
                segs.append((cur_layer, pts))
                cur_layer = node[0]
                pts = [node]
            else:
                pts.append(node)
        segs.append((cur_layer, pts))
        out_segs = []
        for li, pl in segs:
            # simplify collinear runs
            cells = [p[1] for p in pl]
            if len(cells) < 2:
                continue
            xy = [(c % NX, c // NX) for c in cells]
            simp = [xy[0]]
            for k in range(1, len(xy) - 1):
                d1 = (xy[k][0] - xy[k - 1][0], xy[k][1] - xy[k - 1][1])
                d2 = (xy[k + 1][0] - xy[k][0], xy[k + 1][1] - xy[k][1])
                if d1 != d2:
                    simp.append(xy[k])
            simp.append(xy[-1])
            for a, b in zip(simp, simp[1:]):
                x0, y0, x1, y1 = wx(a[0]), wy(a[1]), wx(b[0]), wy(b[1])
                wseg = self.NECK_W if (a[1] * NX + a[0] in neck or b[1] * NX + b[0] in neck) else width
                out_segs.append((LAYERS[li], x0, y0, x1, y1, wseg))
                self.tracks.append((net, LAYERS[li], wseg, x0, y0, x1, y1))
                self.add_track_obstacle(net, LAYERS[li], wseg, x0, y0, x1, y1)
        out_vias = []
        for c in vias:
            x, y = wx(c % NX), wy(c // NX)
            self.vias.append((net, x, y, via[0], via[1]))
            self.add_via_obstacle(net, x, y, via[0])
            out_vias.append((x, y))
        return out_segs, out_vias

    # ------------------------------------------------------------ plane stubs
    def in_poly(self, x, y, poly):
        inside = False
        n = len(poly)
        for i in range(n):
            x0, y0 = poly[i]; x1, y1 = poly[(i + 1) % n]
            if (y0 > y) != (y1 > y):
                xi = x0 + (y - y0) * (x1 - x0) / (y1 - y0)
                if x < xi:
                    inside = not inside
        return inside

    def plane_stub_fn(self, p, fn, via=(VIA_D, VIA_DRILL), maxr=3.0):
        return self.plane_stub(p, fn, via, maxr)

    def plane_stub(self, p, region, via=(VIA_D, VIA_DRILL), maxr=3.0):
        """Connect SMD pad p to a plane: find a via spot inside `region` (polygon or None) and route a short track."""
        net = p.net
        # candidate via centres in rings around the pad
        best = None
        cand = []
        ci, cj = gx(p.x), gy(p.y)
        rmax = int(maxr / G)
        for r in range(int(0.6 / G), rmax):
            for a in range(0, 360, 10):
                i = ci + int(round(r * math.cos(math.radians(a))))
                j = cj + int(round(r * math.sin(math.radians(a))))
                if i < 0 or j < 0 or i >= NX or j >= NY:
                    continue
                c = j * NX + i
                if self.grid.blk_via['F.Cu'][c] or self.grid.blk_via['B.Cu'][c]:
                    continue
                if region is not None and not (region(wx(i), wy(j)) if callable(region) else self.in_poly(wx(i), wy(j), region)):
                    continue
                cand.append((r, c))
            if len(cand) >= 12:
                break
        if not cand:
            return False
        # prefer via spots on the far side of the pad from its component body
        cx, cy, _ = B.PL[p.ref]
        ox, oy = p.x - cx, p.y - cy
        on = math.hypot(ox, oy) or 1.0
        def rank(rc):
            r, c = rc
            vx, vy = wx(c % NX) - p.x, wy(c // NX) - p.y
            dot = (vx * ox + vy * oy) / on / (math.hypot(vx, vy) or 1.0)
            return (r - 6 * dot, c)
        src = set((0, c) for c in self.pad_cells(p, 0))
        w = self.net_width(net)
        for r, c in sorted(cand, key=rank)[:12]:
            goal = {c}
            self.goal_layer_ok = False
            path = self.astar(net, src, goal, w, via_cost=1e9, max_nodes=20000)
            if path:
                segs, vs = self.commit_path(net, path, w, via)
                x, y = wx(c % NX), wy(c // NX)
                self.vias.append((net, x, y, via[0], via[1]))
                self.add_via_obstacle(net, x, y, via[0])
                self.plan.append(dict(net=net, kind='stub', ref=p.ref, pad=p.num, segs=segs, vias=vs + [(x, y)], width=w, via=via))
                self.done_pads.add((net, p.ref, p.num))
                return True
        return False

    # ------------------------------------------------------------ net routing
    def net_sources(self, net, connected):
        src = set()
        for q in connected:
            for li in ([0, 1] if q.tht else [0]):
                for c in self.pad_cells(q, li):
                    src.add((li, c))
        for (n, l, ww, x0, y0, x1, y1) in self.tracks:
            if n != net:
                continue
            li = LAYERS.index(l)
            nn = max(1, int(math.hypot(x1 - x0, y1 - y0) / G))
            for k in range(nn + 1):
                t = k / nn
                src.add((li, gy(y0 + (y1 - y0) * t) * NX + gx(x0 + (x1 - x0) * t)))
        for (n, x, y, s, d) in self.vias:
            if n == net:
                for li in (0, 1):
                    src.add((li, gy(y) * NX + gx(x)))
        return src

    def connected_pads(self, net):
        """Pads of `net` that already touch copper of the net (tracks or vias)."""
        out = []
        for p in self.netpads.get(net, []):
            if p.tht:
                continue
            cells = self.pad_cells(p, 0)
            hit = False
            for (n, l, ww, x0, y0, x1, y1) in self.tracks:
                if n == net and l == 'F.Cu':
                    for (xx, yy) in ((x0, y0), (x1, y1)):
                        if gy(yy) * NX + gx(xx) in cells:
                            hit = True; break
                if hit:
                    break
            if hit:
                out.append(p)
        return out

    def connect_pad(self, ref, num, via_cost=25.0, max_nodes=900000):
        """Connect one pad to the existing copper of its net (planes reached through vias)."""
        p = [q for q in self.pads if q.ref == ref and q.num == num][0]
        net = p.net
        w = self.net_width(net)
        via = self.net_via(net)
        others = [q for q in self.netpads[net] if q is not p and (q.tht or q in self.connected_pads(net))]
        src = self.net_sources(net, others)
        if net in ('GND', '+3V3', 'VBAT'):
            # a plane net: any via-able spot inside the plane region is also a valid target
            pass
        goals = self.pad_cells(p, 0)
        self.goal_layer_ok = False
        path = self.astar(net, src, goals, w, via_cost=via_cost, max_nodes=max_nodes)
        if path is None:
            self.unrouted.append((net, ref, num))
            return False
        segs, vs = self.commit_path(net, path, w, via)
        self.plan.append(dict(net=net, kind='net', segs=segs, vias=vs, width=w, via=via))
        self.done_pads.add((net, ref, num))
        return True

    def route_net(self, net, via_cost=25.0, max_nodes=900000):
        pads = self.netpads.get(net, [])
        if len(pads) < 2:
            return True
        w = self.net_width(net)
        via = self.net_via(net)
        # connectivity groups by current copper: start from the first pad, connect the rest by nearest-first
        remaining = [q for q in pads[1:] if (net, q.ref, q.num) not in self.done_pads]
        connected = [pads[0]] + [q for q in pads[1:] if (net, q.ref, q.num) in self.done_pads]
        plan_segs, plan_vias = [], []
        ok = True
        while remaining:
            # pick the remaining pad nearest to any connected pad
            best = min(remaining, key=lambda p: min(math.hypot(p.x - q.x, p.y - q.y) for q in connected))
            remaining.remove(best)
            src = self.net_sources(net, connected)
            goals = set()
            for li in ([0, 1] if best.tht else [0]):
                goals |= self.pad_cells(best, li)
            self.goal_layer_ok = best.tht
            path = self.astar(net, src, goals, w, via_cost=via_cost, max_nodes=max_nodes)
            if path is None:
                self.unrouted.append((net, best.ref, best.num))
                ok = False
                continue
            segs, vs = self.commit_path(net, path, w, via)
            plan_segs += segs; plan_vias += vs
            connected.append(best)
        self.plan.append(dict(net=net, kind='net', segs=plan_segs, vias=plan_vias, width=w, via=via))
        return ok

    # ------------------------------------------------------------ output
    def emit(self):
        tr = []
        for (net, l, w, x0, y0, x1, y1) in self.tracks:
            tr.append(['segment', ['start', fmt(x0), fmt(y0)], ['end', fmt(x1), fmt(y1)], ['width', fmt(w)], ['layer', q(l)], ['net', str(B.NET[net])], ['uuid', q(nuid())]])
        vi = []
        for (net, x, y, s, d) in self.vias:
            vi.append(['via', ['at', fmt(x), fmt(y)], ['size', fmt(s)], ['drill', fmt(d)], ['layers', q('F.Cu'), q('B.Cu')], ['net', str(B.NET[net])], ['uuid', q(nuid())]])
        return tr, vi