sandTable/pcb/tools/router.py

"""A small two-layer grid router (A* with turn penalties, vias, per-net widths).

Obstacle model: for every distinct "inflation radius" R (track half-width +
clearance + discretisation margin) we keep, per layer, an owner map:
  -1 = free, k >= 0 = only copper of net k is within R, -2 = blocked for everyone.
A cell is usable by net k iff its owner is -1 or k.
"""
import heapq
import math
from array import array

G = 0.1            # grid pitch, mm
CLEAR = 0.2        # copper-copper clearance used by the router (DRC default is 0.15)
EDGE = 0.35        # copper-to-board-edge clearance
MARGIN = 0.08      # discretisation safety margin
VIA_D = 0.6
COST_STEP = 10
COST_DIAG = 14
COST_VIA = 90
COST_TURN = 4
COST_BCU = 1       # tiny extra per step on the bottom layer (keeps B.Cu freer for GND)

DIRS = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


def seg_dist(px, py, x1, y1, x2, y2):
    dx, dy = x2 - x1, y2 - y1
    L2 = dx * dx + dy * dy
    if L2 == 0:
        return math.hypot(px - x1, py - y1)
    t = max(0.0, min(1.0, ((px - x1) * dx + (py - y1) * dy) / L2))
    return math.hypot(px - (x1 + t * dx), py - (y1 + t * dy))


class Router:
    def __init__(self, width, height, radii):
        self.W, self.H = width, height
        self.nx = int(round(width / G)) + 1
        self.ny = int(round(height / G)) + 1
        self.radii = sorted(set(round(r, 3) for r in radii))
        n = self.nx * self.ny
        self.maps = {r: [array('h', [-1]) * n, array('h', [-1]) * n] for r in self.radii}
        self.net_index = {}
        self.objects = []          # (kind, data, net) for re-rasterising
        self.tracks = []           # (x1,y1,x2,y2,w,layer,net)
        self.vias = []             # (x,y,net)
        self.net_cells = {}        # net -> set of (layer, ix, iy) owned copper cells (tree)
        self.no_via = bytearray(n) # 1 = a via centred here would touch or crowd a pad (any net)

    # ------------------------------------------------------------ helpers
    def nid(self, net):
        if net is None:
            return -2
        if net not in self.net_index:
            self.net_index[net] = len(self.net_index)
        return self.net_index[net]

    def cell(self, x, y):
        return int(round(x / G)), int(round(y / G))

    def xy(self, ix, iy):
        return ix * G, iy * G

    def _mark(self, layer_ids, net, x0, y0, x1, y1, inside):
        """inside(px,py,R) -> True if cell centre is within R of the object."""
        k = self.nid(net)
        for r in self.radii:
            ix0 = max(0, int((x0 - r) / G) - 1)
            iy0 = max(0, int((y0 - r) / G) - 1)
            ix1 = min(self.nx - 1, int((x1 + r) / G) + 1)
            iy1 = min(self.ny - 1, int((y1 + r) / G) + 1)
            for L in layer_ids:
                m = self.maps[r][L]
                for iy in range(iy0, iy1 + 1):
                    py = iy * G
                    base = iy * self.nx
                    for ix in range(ix0, ix1 + 1):
                        idx = base + ix
                        v = m[idx]
                        if v == -2 or v == k:
                            continue
                        if inside(ix * G, py, r):
                            m[idx] = k if v == -1 else -2

    def add_pad(self, pad):
        layers = [0 if l == 'F.Cu' else 1 for l in pad.layers]
        if pad.kind == 'np_thru_hole':
            layers = [0, 1]
            hole = pad.drill[0] / 2 if pad.drill else pad.hx
            cx, cy = pad.x, pad.y
            self._mark(layers, None, cx - hole, cy - hole, cx + hole, cy + hole,
                       lambda px, py, r: math.hypot(px - cx, py - cy) < hole + r)
            return
        net = pad.net
        self._mark(layers, net, pad.x - pad.hx, pad.y - pad.hy, pad.x + pad.hx, pad.y + pad.hy,
                   lambda px, py, r: pad.dist(px, py) < r)
        # drilled THT pads also block the other layer for different nets via the copper ring (both layers)

    def keep_vias_off_pad(self, pad, gap):
        """Forbid via centres within (via radius + gap) of this pad's copper, whatever its net.
        A via in or touching a pad lets solder drain into the hole during assembly."""
        if pad.kind == 'np_thru_hole' or not pad.layers:
            return
        r = VIA_D / 2 + gap
        ix0, iy0 = max(0, int((pad.x - pad.hx - r) / G) - 1), max(0, int((pad.y - pad.hy - r) / G) - 1)
        ix1, iy1 = min(self.nx - 1, int((pad.x + pad.hx + r) / G) + 1), min(self.ny - 1, int((pad.y + pad.hy + r) / G) + 1)
        for iy in range(iy0, iy1 + 1):
            for ix in range(ix0, ix1 + 1):
                if pad.dist(ix * G, iy * G) < r:
                    self.no_via[iy * self.nx + ix] = 1

    def add_track(self, x1, y1, x2, y2, w, layer, net):
        hw = w / 2
        self._mark([layer], net, min(x1, x2) - hw, min(y1, y2) - hw, max(x1, x2) + hw, max(y1, y2) + hw,
                   lambda px, py, r: seg_dist(px, py, x1, y1, x2, y2) < hw + r)
        self.tracks.append((x1, y1, x2, y2, w, 'F.Cu' if layer == 0 else 'B.Cu', net))

    def add_via(self, x, y, net):
        rv = VIA_D / 2
        self._mark([0, 1], net, x - rv, y - rv, x + rv, y + rv,
                   lambda px, py, r: math.hypot(px - x, py - y) < rv + r)
        self.vias.append((x, y, net))

    def block_edges(self):
        for r in self.radii:
            lim = EDGE + r - CLEAR   # r already includes clearance; edge rule replaces it
            n = int(math.ceil(lim / G))          # cells with index < n (or > max-n) are too close
            for L in (0, 1):
                m = self.maps[r][L]
                for iy in range(self.ny):
                    base = iy * self.nx
                    if iy < n or iy > self.ny - 1 - n:
                        for ix in range(self.nx):
                            m[base + ix] = -2
                    else:
                        for ix in list(range(n)) + list(range(self.nx - n, self.nx)):
                            m[base + ix] = -2

    def block_rect(self, x0, y0, x1, y1):
        """Keep-out: nothing may enter (tracks are inflated by their radius)."""
        for r in self.radii:
            for L in (0, 1):
                m = self.maps[r][L]
                hw = r - CLEAR - MARGIN   # track half width
                for iy in range(max(0, int((y0 - hw) / G)), min(self.ny, int((y1 + hw) / G) + 2)):
                    for ix in range(max(0, int((x0 - hw) / G)), min(self.nx, int((x1 + hw) / G) + 2)):
                        px, py = ix * G, iy * G
                        if x0 - hw - CLEAR <= px <= x1 + hw + CLEAR and y0 - hw - CLEAR <= py <= y1 + hw + CLEAR:
                            m[iy * self.nx + ix] = -2

    # ------------------------------------------------------------ search
    def pad_cells(self, pad):
        layers = [0 if l == 'F.Cu' else 1 for l in pad.layers]
        cells = set()
        ix0, iy0 = int((pad.x - pad.hx) / G), int((pad.y - pad.hy) / G)
        ix1, iy1 = int((pad.x + pad.hx) / G) + 1, int((pad.y + pad.hy) / G) + 1
        for iy in range(iy0, iy1 + 1):
            for ix in range(ix0, ix1 + 1):
                if pad.dist(ix * G, iy * G) <= 1e-9:
                    for L in layers:
                        cells.add((L, ix, iy))
        if not cells:
            ix, iy = self.cell(pad.x, pad.y)
            for L in layers:
                cells.add((L, ix, iy))
        return cells

    def search(self, net, r_track, r_via, sources, targets, tx, ty, max_expand=1500000):
        k = self.nid(net)
        nx = self.nx
        mt = self.maps[r_track]
        mv = self.maps[r_via]
        own = self.net_cells.setdefault(net, set())
        tset = targets
        txi, tyi = tx / G, ty / G

        def free(L, ix, iy):
            if ix < 0 or iy < 0 or ix >= nx or iy >= self.ny:
                return False
            if (L, ix, iy) in tset:
                return True
            v = mt[L][iy * nx + ix]
            return v == -1 or v == k

        def via_ok(ix, iy):
            if self.no_via[iy * nx + ix]:
                return False
            for L in (0, 1):
                v = mv[L][iy * nx + ix]
                if not (v == -1 or v == k):
                    return False
            return True

        def h(ix, iy):
            dx, dy = abs(ix - txi), abs(iy - tyi)
            return int(COST_STEP * (max(dx, dy) - min(dx, dy)) + COST_DIAG * min(dx, dy))

        openh = []
        g = {}
        came = {}
        for (L, ix, iy) in sources:
            s = (L, ix, iy, 8)
            g[s] = 0
            heapq.heappush(openh, (h(ix, iy), 0, s))
        expanded = 0
        while openh:
            f, gc, s = heapq.heappop(openh)
            if g.get(s, 1 << 60) < gc:
                continue
            L, ix, iy, d = s
            if (L, ix, iy) in tset:
                path = [(L, ix, iy)]
                while s in came:
                    s = came[s]
                    path.append(s[:3])
                path.reverse()
                return path
            expanded += 1
            if expanded > max_expand:
                return None
            for nd, (dx, dy) in enumerate(DIRS):
                jx, jy = ix + dx, iy + dy
                if not free(L, jx, jy):
                    continue
                if dx and dy:
                    # don't cut corners between two blocked orthogonal neighbours
                    if not (free(L, ix + dx, iy) or free(L, ix, iy + dy)):
                        continue
                    step = COST_DIAG
                else:
                    step = COST_STEP
                if d != 8 and nd != d:
                    step += COST_TURN * (1 if (nd - d) % 8 in (1, 7) else 3)
                if L == 1:
                    step += COST_BCU
                ns = (L, jx, jy, nd)
                ng = gc + step
                if ng < g.get(ns, 1 << 60):
                    g[ns] = ng
                    came[ns] = s
                    heapq.heappush(openh, (ng + h(jx, jy), ng, ns))
            # via
            if via_ok(ix, iy):
                ns = (1 - L, ix, iy, 8)
                ng = gc + COST_VIA
                if ng < g.get(ns, 1 << 60) and free(1 - L, ix, iy):
                    g[ns] = ng
                    came[ns] = s
                    heapq.heappush(openh, (ng + h(ix, iy), ng, ns))
        return None

    def commit_path(self, net, path, w, start_xy=None, end_xy=None):
        """Turn a cell path into merged segments + vias, add them as obstacles."""
        own = self.net_cells.setdefault(net, set())
        pts = []   # (layer, x, y)
        for (L, ix, iy) in path:
            pts.append((L, ix * G, iy * G))
            own.add((L, ix, iy))
        segs = []
        vias = []
        run = [pts[0]]
        for p in pts[1:]:
            if p[0] != run[-1][0]:
                vias.append((p[1], p[2]))
                if len(run) > 1:
                    segs.append(run)
                run = [p]
            else:
                run.append(p)
        if len(run) > 1:
            segs.append(run)
        out = []
        for run in segs:
            # merge collinear points
            simp = [run[0]]
            for i in range(1, len(run) - 1):
                a, b, c = simp[-1], run[i], run[i + 1]
                d1 = (round((b[1] - a[1]) / G), round((b[2] - a[2]) / G))
                d2 = (round((c[1] - b[1]) / G), round((c[2] - b[2]) / G))
                if d1[0] * d2[1] - d1[1] * d2[0] != 0 or d1[0] * d2[0] + d1[1] * d2[1] < 0:
                    simp.append(b)
            simp.append(run[-1])
            for a, b in zip(simp, simp[1:]):
                out.append((a[1], a[2], b[1], b[2], w, a[0], net))
        for (x, y) in vias:
            self.add_via(x, y, net)
        for (x1, y1, x2, y2, ww, L, n) in out:
            self.add_track(x1, y1, x2, y2, ww, L, n)
        return len(out), len(vias)