"""Shared 8-direction Dijkstra router for the LED nameplate generator. Used by both: - generate_nameplate.py (KiCad PCB generator) - route_visualizer.py (HTML/SVG visualiser served via Hydrogen webview) Anything that affects the routing decision lives HERE so the two tools stay byte-identical in algorithm and produce the same paths for a given letter bitmap. """ import heapq import math # --------------------------------------------------------------------------- # Grid + LED constants # --------------------------------------------------------------------------- GRID_COLS = 5 GRID_ROWS = 9 LED_PITCH = 4.0 GRID_ORIGIN_X = 40.0 GRID_ORIGIN_Y = 40.0 LETTER_WIDTH = (GRID_COLS - 1) * LED_PITCH # 16mm LETTER_HEIGHT = (GRID_ROWS - 1) * LED_PITCH # 32mm ROUTING_UNIT = 0.5 # mm — sub-grid spacing (8 sub-steps per 4mm LED pitch) SQRT2 = math.sqrt(2) # Snap-point offsets from LED center, in LED local frame (pre-rotation). # In KiCad Y-down coords these coincide with the actual pad centers: # DOUT pad at (-0.92, -0.55), DIN pad at (+0.92, +0.55). DIN_OFFSET = (1.0, 0.5) DOUT_OFFSET = (-1.0, -0.5) def grid_pos(row, col): """LED center (x, y) for grid cell (row, col), in template-local mm.""" return (GRID_ORIGIN_X + col * LED_PITCH, GRID_ORIGIN_Y + row * LED_PITCH) def get_led_rotation(row): """LED footprint rotation: even rows are rot=180, odd rows rot=0 (alternating serpentine orientation in the template).""" return 180 if row % 2 == 0 else 0 def chain_order(inverted=False): """Serpentine chain order across the 5x9 LED grid. Normal: starts at (row 0, col 0), row 0 L→R, row 1 R→L, ..., ending at (row 8, col 4). Inverted: starts at (row 8, col 0), row 8 L→R, row 7 R→L, ..., ending at (row 0, col 4). This is a vertical mirror of the normal serpentine — the chain begins at the bottom-LEFT and snakes UP the letter. Because the alternation L→R / R→L starts the same way (L→R on the first row of each variant), the existing template LED rotations already line up correctly: each LED's physical DOUT faces the next-LED-in-this-chain just as it does in normal mode. No extra per-letter rotation is required. """ rows = list(range(GRID_ROWS)) if inverted: rows.reverse() order = [] for ri, r in enumerate(rows): cols = range(GRID_COLS) if ri % 2 == 0 else range(GRID_COLS - 1, -1, -1) for c in cols: order.append((r, c)) return order def corner_for(row, col, pin): """Snap node (0.5mm grid) for an LED's DIN or DOUT pin, global coords.""" cx, cy = grid_pos(row, col) rot = get_led_rotation(row) lx, ly = DIN_OFFSET if pin == 'DIN' else DOUT_OFFSET if rot == 0: return (cx + lx, cy + ly) else: # rot == 180 return (cx - lx, cy - ly) def grid_bounds(): """Routing-graph bounding box in template-local mm coords.""" margin = 2.0 x0 = GRID_ORIGIN_X - margin x1 = GRID_ORIGIN_X + (GRID_COLS - 1) * LED_PITCH + margin y0 = GRID_ORIGIN_Y - margin y1 = GRID_ORIGIN_Y + (GRID_ROWS - 1) * LED_PITCH + margin return x0, x1, y0, y1 # --------------------------------------------------------------------------- # Dijkstra (8-direction, no-right-angle constraint) # --------------------------------------------------------------------------- def dijkstra(src, dst, blocked, bounds): """8-direction shortest path with no-right-angle constraint. State = (node, incoming_direction). A right angle happens whenever the dot product of the incoming and outgoing direction vectors is zero. That single rule covers BOTH: - orthogonal⊥orthogonal (e.g. E then N) - diagonal ⊥diagonal (e.g. NE then NW — a 45° edge meeting a 135° edge at the same node) Orthogonal-to-diagonal transitions can never be perpendicular in this 8-neighbour grid, so they're naturally allowed (these are the 45° turns). We also keep the original "orth backtrack" guard: an orthogonal edge cannot reverse onto its own direction in one step. Returns the path as a list of (x, y) nodes, or None if unreachable. """ x0, x1, y0, y1 = bounds start_state = (src, None) dist = {start_state: 0.0} prev = {} pq = [(0.0, start_state)] while pq: d, state = heapq.heappop(pq) u, in_dir = state if u == dst: path = [u] s = state while s in prev: s = prev[s] path.append(s[0]) return list(reversed(path)) if d > dist[state]: continue ux, uy = u for dx in (-ROUTING_UNIT, 0, ROUTING_UNIT): for dy in (-ROUTING_UNIT, 0, ROUTING_UNIT): if dx == 0 and dy == 0: continue if in_dir is not None: pdx, pdy = in_dir # Reject any transition whose two unit-direction vectors # are perpendicular (covers all right-angle cases). if abs(pdx * dx + pdy * dy) < 1e-9: continue # Reject orthogonal backtracks (E followed by W, etc.). prev_orth = (pdx == 0 or pdy == 0) this_orth = (dx == 0 or dy == 0) if prev_orth and this_orth and (pdx, pdy) != (dx, dy): continue vx, vy = ux + dx, uy + dy if not (x0 <= vx <= x1 and y0 <= vy <= y1): continue v = (vx, vy) if v in blocked and v != dst: continue cost = SQRT2 if (dx and dy) else 1.0 nd = d + cost new_state = (v, (dx, dy)) if new_state not in dist or nd < dist[new_state]: dist[new_state] = nd prev[new_state] = state heapq.heappush(pq, (nd, new_state)) return None def consolidate(path): """Merge consecutive co-linear nodes into endpoints of straight runs.""" if len(path) < 2: return list(path) out = [path[0]] cur_dir = (path[1][0] - path[0][0], path[1][1] - path[0][1]) for i in range(2, len(path)): nd = (path[i][0] - path[i - 1][0], path[i][1] - path[i - 1][1]) if nd != cur_dir: out.append(path[i - 1]) cur_dir = nd out.append(path[-1]) return out # --------------------------------------------------------------------------- # Blocked set construction # --------------------------------------------------------------------------- # # Keepouts are built from real copper RECTANGLES expanded by the routing # margin (pad-to-trace clearance + trace half-width), then sampled onto the # 0.5mm grid. A grid node is blocked if its centre falls inside the LED body # square or any expanded pad/cap rectangle. This guarantees every routed # trace keeps >= PAD_CLEARANCE from pad copper — the crude ±1mm square # keepout used before allowed traces at 1.5mm from centre, only 0.14mm from # the pads that stick out to 1.36mm. PAD_HALF_X = 0.4375 # 0.875mm pad / 2 (WS2812B-2020 corner pad) PAD_HALF_Y = 0.475 # 0.95mm pad / 2 PAD_CLEARANCE = 0.2 # required copper-to-copper clearance TRACE_HALF = 0.1 # half of 0.2mm trace width PAD_MARGIN = PAD_CLEARANCE + TRACE_HALF # 0.3mm: trace centre → pad edge LED_BODY_HALF = 1.0 # 2x2mm chip body # Pad centres in LED-local frame (pre-rotation). pad1=DOUT, 2=VSS, 3=DIN, 4=VDD. PAD_LOCAL = { 'DOUT': (-0.92, -0.55), 'VSS': (-0.92, 0.55), 'DIN': ( 0.92, 0.55), 'VDD': ( 0.92, -0.55), } # 0402 decoupling cap, placed at (cx, cy+1.5) in template coords (all rows). CAP_OFFSET = (0.0, 1.5) CAP_HALF_X = 0.78 # furthest cap copper from cap centre CAP_HALF_Y = 0.32 def _rotate_local(lx, ly, rot): return (-lx, -ly) if rot == 180 else (lx, ly) def _grid_nodes_in_rect(cx, cy, hx, hy): """Yield 0.5mm-grid nodes whose centre lies within the rect [cx-hx, cx+hx] x [cy-hy, cy+hy]. Grid is anchored at multiples of ROUTING_UNIT (LED centres are multiples of 4mm, so on-grid).""" eps = 1e-9 # snap rect bounds to the grid x_lo = math.ceil((cx - hx) / ROUTING_UNIT - eps) * ROUTING_UNIT x_hi = math.floor((cx + hx) / ROUTING_UNIT + eps) * ROUTING_UNIT y_lo = math.ceil((cy - hy) / ROUTING_UNIT - eps) * ROUTING_UNIT y_hi = math.floor((cy + hy) / ROUTING_UNIT + eps) * ROUTING_UNIT nx = x_lo while nx <= x_hi + eps: ny = y_lo while ny <= y_hi + eps: yield (round(nx, 3), round(ny, 3)) ny += ROUTING_UNIT nx += ROUTING_UNIT def initial_blocked_set(surviving_set): """Build the obstacle blocked set from a set of (row, col) surviving LEDs. Blocks the LED body, every pad (expanded by PAD_MARGIN), and the decoupling cap. Then reopens each LED's DIN/DOUT snap node plus one outward 'escape' node so Dijkstra can leave the pad cluster — those nodes sit beside the pin's OWN (same-net) pad, never a foreign pad. """ blocked = set() for (r, c) in surviving_set: cx, cy = grid_pos(r, c) rot = get_led_rotation(r) # LED body square for node in _grid_nodes_in_rect(cx, cy, LED_BODY_HALF, LED_BODY_HALF): blocked.add(node) # Each pad, expanded by the routing margin for (plx, ply) in PAD_LOCAL.values(): gx, gy = _rotate_local(plx, ply, rot) for node in _grid_nodes_in_rect(cx + gx, cy + gy, PAD_HALF_X + PAD_MARGIN, PAD_HALF_Y + PAD_MARGIN): blocked.add(node) # Decoupling cap (not rotated — template places it below every LED) for node in _grid_nodes_in_rect(cx + CAP_OFFSET[0], cy + CAP_OFFSET[1], CAP_HALF_X + PAD_MARGIN, CAP_HALF_Y + PAD_MARGIN): blocked.add(node) # Reopen DIN/DOUT snap nodes + one outward escape each. for pin in ('DIN', 'DOUT'): snap = corner_for(r, c, pin) blocked.discard(snap) out_x = snap[0] + (ROUTING_UNIT if snap[0] > cx else -ROUTING_UNIT) blocked.discard((round(out_x, 3), round(snap[1], 3))) # User request: free the top-row left 3 nodes of each LED keepout # (top edge, x = cx-1.5 / cx-1.0 / cx-0.5). top_y = cy - LED_BODY_HALF for dx in (-1.5, -1.0, -0.5): blocked.discard((round(cx + dx, 3), round(top_y, 3))) return blocked def _add_nodes_near(nodes, px, py, radius): """Add every 0.5mm-grid node within `radius` of (px, py) to `nodes`.""" lo_x = math.floor((px - radius) / ROUTING_UNIT) * ROUTING_UNIT hi_x = math.ceil((px + radius) / ROUTING_UNIT) * ROUTING_UNIT lo_y = math.floor((py - radius) / ROUTING_UNIT) * ROUTING_UNIT hi_y = math.ceil((py + radius) / ROUTING_UNIT) * ROUTING_UNIT nx = lo_x while nx <= hi_x + 1e-9: ny = lo_y while ny <= hi_y + 1e-9: if math.hypot(nx - px, ny - py) <= radius + 1e-9: nodes.add((round(nx, 3), round(ny, 3))) ny += ROUTING_UNIT nx += ROUTING_UNIT def gnd_keepout_nodes(via_centers, segments): """Routing-grid nodes a chain trace must avoid to clear the template's GND copper. A chain-trace centre must stay >= PAD_CLEARANCE (copper-to-copper) from a GND via (Ø0.6) or a GND trace (0.2mm wide): via : 0.3 (via r) + TRACE_HALF + PAD_CLEARANCE = 0.6 mm trace: 0.1 (gnd half) + TRACE_HALF + PAD_CLEARANCE = 0.4 mm `segments` is a list of (x1, y1, x2, y2) in template-local mm. """ R_VIA = 0.3 + TRACE_HALF + PAD_CLEARANCE R_SEG = 0.1 + TRACE_HALF + PAD_CLEARANCE nodes = set() for (vx, vy) in via_centers: _add_nodes_near(nodes, vx, vy, R_VIA) for (x1, y1, x2, y2) in segments: L = math.hypot(x2 - x1, y2 - y1) steps = max(1, int(L / (ROUTING_UNIT / 2)) + 1) for s in range(steps + 1): t = s / steps _add_nodes_near(nodes, x1 + (x2 - x1) * t, y1 + (y2 - y1) * t, R_SEG) return nodes # --------------------------------------------------------------------------- # Whole-chain router # --------------------------------------------------------------------------- def route_chain(surviving, inverted=False, extra_blocked=None): """Route every chain link between consecutive surviving LEDs. Args: surviving: iterable of (row, col) cells from the dot-font bitmap (the LEDs that survive after font-bitmap filtering). inverted: if True, traverse the LEDs in reverse serpentine order (start at bottom-left, end at top-right). LED placement is unchanged — only the chain visitation order differs, so the letter still reads upright but its data input is on the opposite corner. extra_blocked: optional iterable of (x, y) routing-grid nodes to treat as permanently blocked — e.g. keepout around the template's GND vias and GND traces so chain bridges don't short to them. Both the PCB generator and the visualiser pass the SAME set so their routes stay identical. Returns: (results, final_blocked) where: results: list of dicts, one per chain link, with keys: 'i' : link index in the surviving chain (0..N-2) 'r1','c1' : source LED grid cell 'r2','c2' : destination LED grid cell 'src' : source snap node (DOUT corner), (x, y) 'dst' : destination snap node (DIN corner), (x, y) 'same_row' : True iff r1 == r2 'path' : list of (x, y) nodes from src → dst, or None final_blocked: the full blocked set after all routes are placed (useful for visualising the obstacle field). Routes are produced in the same order as in generate_nameplate.py: same-row pairs first, then cross-row pairs (Manhattan-distance tiebreak). After each route, intermediate nodes + anti-diagonal corners of each diagonal edge are added to the blocked set so later routes can't cross. """ surviving_set = set(surviving) surv_chain = [(r, c) for (r, c) in chain_order(inverted=inverted) if (r, c) in surviving_set] bounds = grid_bounds() blocked = initial_blocked_set(surviving_set) if extra_blocked: # Don't let GND keepout swallow a surviving LED's own pin snap/escape # nodes (those must stay open as routing endpoints). keep_open = set() for (r, c) in surviving_set: cx, _ = grid_pos(r, c) for pin in ('DIN', 'DOUT'): snap = corner_for(r, c, pin) keep_open.add(snap) ox = snap[0] + (ROUTING_UNIT if snap[0] > cx else -ROUTING_UNIT) keep_open.add((round(ox, 3), round(snap[1], 3))) blocked |= (set(extra_blocked) - keep_open) pairs = [] for i in range(len(surv_chain) - 1): r1, c1 = surv_chain[i] r2, c2 = surv_chain[i + 1] pairs.append({ 'i': i, 'r1': r1, 'c1': c1, 'r2': r2, 'c2': c2, 'src': corner_for(r1, c1, 'DOUT'), 'dst': corner_for(r2, c2, 'DIN'), 'same_row': r1 == r2, }) pairs.sort(key=lambda p: (0 if p['same_row'] else 1, abs(p['src'][0] - p['dst'][0]) + abs(p['src'][1] - p['dst'][1]))) def _escapes(r, c, snap): """Outward exit nodes beside a pin: the horizontal escape plus the CORNER diagonal (pointing away from the LED centre, into open space). Both sit beyond the pin's own corner — clear of the LED's other-net pads (VSS/VDD/DIN) — so opening them per-link lets the router leave diagonally (a clean 45° chamfer) without risking a foreign-pad short. The two diagonals that point toward an ADJACENT pad are NOT opened. Opened only for THIS pair (never globally).""" cx, cy = grid_pos(r, c) ox = ROUTING_UNIT if snap[0] > cx else -ROUTING_UNIT oy = ROUTING_UNIT if snap[1] > cy else -ROUTING_UNIT return { (round(snap[0] + ox, 3), round(snap[1], 3)), # horizontal (round(snap[0] + ox, 3), round(snap[1] + oy, 3)), # corner diagonal } results = [] for p in pairs: src, dst = p['src'], p['dst'] open_nodes = {src, dst} open_nodes |= _escapes(p['r1'], p['c1'], src) open_nodes |= _escapes(p['r2'], p['c2'], dst) local_blocked = blocked - open_nodes path = dijkstra(src, dst, local_blocked, bounds) results.append({**p, 'path': path}) if path is None: continue for k in range(1, len(path) - 1): blocked.add(path[k]) for k in range(len(path) - 1): x1, y1 = path[k] x2, y2 = path[k + 1] dx = x2 - x1 dy = y2 - y1 if dx != 0 and dy != 0: blocked.add((x1 + dx, y1)) blocked.add((x1, y1 + dy)) # Sort results back into chain order for downstream emission. results.sort(key=lambda r: r['i']) return results, blocked