astra/f1c100s

scripts/grid-router.ts

import type { SimpleRouteJson, SimplifiedPcbTrace } from "tscircuit";
import { MODULE_SIZE, TERMINAL_EDGE } from "../src/profiles";

type P = { x: number; y: number; layer: string };
const LAYERS = ["top", "inner1", "inner2", "bottom"];
class Heap {
	ids: number[] = [];
	costs: number[] = [];
	push(id: number, cost: number) {
		let i = this.ids.length;
		this.ids.push(id);
		this.costs.push(cost);
		while (i) {
			const p = (i - 1) >> 1;
			if (this.costs[p]! <= cost) break;
			this.ids[i] = this.ids[p]!;
			this.costs[i] = this.costs[p]!;
			i = p;
		}
		this.ids[i] = id;
		this.costs[i] = cost;
	}
	pop() {
		const id = this.ids[0]!,
			v = this.ids.pop()!,
			c = this.costs.pop()!;
		if (this.ids.length) {
			let i = 0;
			while (i * 2 + 1 < this.ids.length) {
				let q = i * 2 + 1;
				if (q + 1 < this.ids.length && this.costs[q + 1]! < this.costs[q]!) q++;
				if (this.costs[q]! >= c) break;
				this.ids[i] = this.ids[q]!;
				this.costs[i] = this.costs[q]!;
				i = q;
			}
			this.ids[i] = v;
			this.costs[i] = c;
		}
		return id;
	}
}

/** Offline grid search. Through-via keepouts always span all four layers.
 * Rasterization includes a small additional clearance margin.
 * Every result is subsequently checked against exact Circuit JSON geometry.
 */
export function routeGrid(
	input: SimpleRouteJson,
	options: {
		first?: string[];
		onProgress?: (s: string) => void;
		requiredPairs?: [string, string][];
	} = {},
) {
	const step = 0.05,
		half = MODULE_SIZE / 2 - 0.45,
		W = Math.round((half * 2) / step) + 1,
		N = W * W,
		total = N * 4;
	const width = 0.12,
		clearance = 0.1,
		viaRadius = 0.225,
		extra = 0.008;
	const wire = new Int16Array(total),
		via = new Int16Array(total);
	const holeBlocked = new Int16Array(N),
		viaCenters = new Int16Array(N);
	const toGrid = (x: number) => Math.round((x + half) / step);
	const pos = (i: number) => ({
		x: (i % W) * step - half,
		y: Math.floor((i % N) / W) * step - half,
		layer: LAYERS[Math.floor(i / N)]!,
	});
	const index = (p: P) =>
		LAYERS.indexOf(p.layer) * N + toGrid(p.y) * W + toGrid(p.x);
	const stamp = (
		map: Int16Array,
		layer: number,
		x: number,
		y: number,
		hx: number,
		hy: number,
		r: number,
		owner: number,
	) => {
		const x0 = Math.max(0, Math.floor((x - hx - r + half) / step)),
			x1 = Math.min(W - 1, Math.ceil((x + hx + r + half) / step));
		const y0 = Math.max(0, Math.floor((y - hy - r + half) / step)),
			y1 = Math.min(W - 1, Math.ceil((y + hy + r + half) / step));
		for (let iy = y0; iy <= y1; iy++)
			for (let ix = x0; ix <= x1; ix++) {
				const dx = Math.max(0, Math.abs(ix * step - half - x) - hx),
					dy = Math.max(0, Math.abs(iy * step - half - y) - hy);
				if (dx * dx + dy * dy > r * r) continue;
				const id = layer * N + iy * W + ix,
					old = map[id]!;
				map[id] = old === 0 || old === owner ? owner : -1;
			}
	};
	const owners = new Map<string, number>();
	input.connections.forEach((c, i) => {
		for (const key of [
			c.name,
			c.source_trace_id,
			...c.pointsToConnect.flatMap((p) => [p.pcb_port_id, p.pointId]),
		])
			if (key) owners.set(key, i + 1);
	});
	for (const o of input.obstacles) {
		const owner =
			o.connectedTo.map((k) => owners.get(k)).find((x) => x !== undefined) ??
			-1;
		// Current package consists only of axis-aligned pad rectangles.
		const rot = (o as any).ccwRotationDegrees ?? 0;
		if (Math.abs(rot % 90) > 1e-6)
			throw new Error("Grid generator requires axis-aligned pads");
		const swap = Math.abs(Math.round(rot / 90)) % 2 === 1;
		const hx = (swap ? o.height : o.width) / 2,
			hy = (swap ? o.width : o.height) / 2;
		for (const l of o.layers) {
			const z = LAYERS.indexOf(l);
			if (z < 0) throw new Error(`Unexpected layer ${l}`);
			stamp(
				wire,
				z,
				o.center.x,
				o.center.y,
				hx,
				hy,
				width / 2 + clearance + extra,
				owner,
			);
			// Even same-net pads forbid via-in-pad for ordinary fabrication.
			stamp(
				via,
				z,
				o.center.x,
				o.center.y,
				hx,
				hy,
				viaRadius + clearance + extra,
				-1,
			);
		}
	}
	// Every exposed top-side terminal needs an unobstructed outward connection
	// to the carrier. Reserve its exit corridor before routing internal nets.
	for (const [ci, c] of input.connections.entries()) {
		for (const p of c.pointsToConnect) {
			if (
				p.layer !== "top" ||
				Math.max(Math.abs(p.x), Math.abs(p.y)) < TERMINAL_EDGE - 1e-4
			)
				continue;
			const vertical = Math.abs(p.y) > Math.abs(p.x);
			const outward = vertical
				? { x: p.x, y: Math.sign(p.y) * half }
				: { x: Math.sign(p.x) * half, y: p.y };
			const inward = vertical
				? { x: p.x, y: p.y - Math.sign(p.y) * 0.25 }
				: { x: p.x - Math.sign(p.x) * 0.25, y: p.y };
			const x = (inward.x + outward.x) / 2,
				y = (inward.y + outward.y) / 2;
			const hx = Math.abs(inward.x - outward.x) / 2,
				hy = Math.abs(inward.y - outward.y) / 2;
			stamp(wire, 0, x, y, hx, hy, width + clearance + extra, ci + 1);
			stamp(
				via,
				0,
				x,
				y,
				hx,
				hy,
				width / 2 + viaRadius + clearance + extra,
				ci + 1,
			);
		}
	}
	// Do not let an earlier signal's access via occupy another lead's escape.
	for (const [ci, c] of input.connections.entries())
		for (const p of c.pointsToConnect) {
			if (
				!p.port_selector?.startsWith("U1.") ||
				Math.max(Math.abs(p.x), Math.abs(p.y)) < 4.5
			)
				continue;
			const vertical = Math.abs(p.y) > Math.abs(p.x);
			const q = {
				x: vertical ? p.x : Math.sign(p.x) * 6.15,
				y: vertical ? Math.sign(p.y) * 6.15 : p.y,
			};
			stamp(
				via,
				0,
				(p.x + q.x) / 2,
				(p.y + q.y) / 2,
				Math.abs(p.x - q.x) / 2,
				Math.abs(p.y - q.y) / 2,
				width / 2 + viaRadius + clearance + extra,
				ci + 1,
			);
		}
	const scores = new Float32Array(total),
		parents = new Int32Array(total),
		seen = new Int32Array(total),
		closed = new Int32Array(total);
	let serial = 0;
	const traces: SimplifiedPcbTrace[] = [];
	const free = (map: Int16Array, id: number, owner: number) =>
		map[id] === 0 || map[id] === owner;
	const canVia = (q: number, owner: number) =>
		(holeBlocked[q] === 0 || viaCenters[q] === owner) &&
		[0, 1, 2, 3].every((l) => free(via, l * N + q, owner));
	function solve(a: P, b: P, owner: number, allowVias = true) {
		const start = index(a),
			end = index(b),
			endZ = Math.floor(end / N),
			endXY = end % N,
			ex = endXY % W,
			ey = Math.floor(endXY / W);
		if (!free(wire, start, owner) || !free(wire, end, owner))
			throw new Error(
				`Blocked terminal for net ${owner}: ${JSON.stringify({ a, b, aw: wire[start], bw: wire[end] })}`,
			);
		const h = (id: number) => {
			const q = id % N;
			return (
				Math.abs((q % W) - ex) +
				Math.abs(Math.floor(q / W) - ey) +
				(Math.floor(id / N) === endZ ? 0 : 45)
			);
		};
		const heap = new Heap();
		serial++;
		seen[start] = serial;
		scores[start] = 0;
		parents[start] = -1;
		heap.push(start, h(start));
		let expanded = 0;
		while (heap.ids.length) {
			const id = heap.pop();
			if (closed[id] === serial) continue;
			closed[id] = serial;
			if (id === end) {
				const result: number[] = [];
				let p = id;
				while (p !== -1) {
					result.push(p);
					p = parents[p]!;
				}
				return result.reverse();
			}
			if (++expanded > total) throw new Error("Search exhausted");
			const z = Math.floor(id / N),
				q = id % N,
				x = q % W,
				y = Math.floor(q / W),
				g = scores[id]!;
			const add = (next: number, cost: number) => {
				if (closed[next] === serial || !free(wire, next, owner)) return;
				const ng = g + cost;
				if (seen[next] === serial && scores[next]! <= ng) return;
				seen[next] = serial;
				scores[next] = ng;
				parents[next] = id;
				heap.push(next, ng + h(next));
			};
			if (x > 0) add(id - 1, 1);
			if (x + 1 < W) add(id + 1, 1);
			if (y > 0) add(id - W, 1);
			if (y + 1 < W) add(id + W, 1);
			if (allowVias && canVia(q, owner)) {
				let prev = id,
					nearVia = false;
				for (let k = 0; k < 15; k++) {
					const parent = parents[prev]!;
					if (parent < 0) break;
					if (Math.floor(parent / N) !== Math.floor(prev / N)) {
						const v = prev % N,
							dx = ((v % W) - x) * step,
							dy = (Math.floor(v / W) - y) * step;
						if (dx * dx + dy * dy < 0.31 ** 2 && v !== q) nearVia = true;
					}
					prev = parent;
				}
				if (!nearVia)
					for (let l = 0; l < 4; l++) if (l !== z) add(l * N + q, 45);
			}
		}
		throw new Error(`No route ${JSON.stringify({ a, b, owner, expanded })}`);
	}
	// Pull same-layer paths taut using clear straight/45-degree shortcuts.
	// Via positions and endpoints are fixed. Check all cells touched by a
	// shortcut against the clearance-inflated occupancy before committing it.
	function simplify(ids: number[], owner: number): number[] {
		const clearLine = (a: number, b: number) => {
			const z = Math.floor(a / N);
			if (Math.floor(b / N) !== z) return false;
			const ax = a % W,
				ay = Math.floor((a % N) / W);
			const dx = (b % W) - ax,
				dy = Math.floor((b % N) / W) - ay;
			if (dx && dy && Math.abs(dx) !== Math.abs(dy)) return false;
			const samples = Math.max(Math.abs(dx), Math.abs(dy)) * 2;
			for (let k = 0; k <= samples; k++) {
				const x = ax + (dx * k) / (samples || 1),
					y = ay + (dy * k) / (samples || 1);
				for (const gx of [Math.floor(x), Math.ceil(x)])
					for (const gy of [Math.floor(y), Math.ceil(y)])
						if (!free(wire, z * N + gy * W + gx, owner)) return false;
			}
			return true;
		};
		const result: number[] = [];
		let i = 0;
		while (i < ids.length) {
			result.push(ids[i]!);
			let end = i;
			while (
				end + 1 < ids.length &&
				Math.floor(ids[end + 1]! / N) === Math.floor(ids[i]! / N)
			)
				end++;
			let next = i + 1;
			for (let j = end; j > i + 1; j--) {
				if (clearLine(ids[i]!, ids[j]!)) {
					next = j;
					break;
				}
			}
			i = next;
		}
		return result;
	}
	function record(
		ids: number[],
		a: P,
		b: P,
		owner: number,
		connection: SimpleRouteJson["connections"][number],
		branch: number,
		waypoints?: P[],
	) {
		const points: P[] = [a, ...(waypoints ?? simplify(ids, owner).map(pos)), b];
		const compact: P[] = [];
		for (const p of points) {
			const last = compact.at(-1);
			if (
				last &&
				Math.hypot(p.x - last.x, p.y - last.y) < 1e-9 &&
				last.layer === p.layer
			)
				continue;
			const prev = compact.at(-2);
			if (
				last &&
				prev &&
				prev.layer === last.layer &&
				last.layer === p.layer &&
				Math.abs(
					(last.x - prev.x) * (p.y - last.y) -
						(last.y - prev.y) * (p.x - last.x),
				) < 1e-10
			)
				compact.pop();
			compact.push(p);
		}
		const route: SimplifiedPcbTrace["route"] = [];
		for (let i = 0; i < compact.length; i++) {
			const p = compact[i]!,
				prev = compact[i - 1];
			if (prev && prev.layer !== p.layer) {
				route.push({
					route_type: "via",
					x: p.x,
					y: p.y,
					from_layer: prev.layer,
					to_layer: p.layer,
					layers: LAYERS,
					via_diameter: viaRadius * 2,
					via_hole_diameter: 0.2,
				});
				for (let l = 0; l < 4; l++) {
					stamp(
						wire,
						l,
						p.x,
						p.y,
						0,
						0,
						viaRadius + width / 2 + clearance + extra,
						owner,
					);
					stamp(
						via,
						l,
						p.x,
						p.y,
						0,
						0,
						2 * viaRadius + clearance + extra,
						owner,
					);
				}
				stamp(holeBlocked, 0, p.x, p.y, 0, 0, 0.31, -1);
				viaCenters[index(p) % N] = owner;
			}
			route.push({ route_type: "wire", ...p, width });
			if (prev && prev.layer === p.layer) {
				const length = Math.hypot(p.x - prev.x, p.y - prev.y),
					samples = Math.max(1, Math.ceil(length / (step / 2)));
				for (let j = 0; j <= samples; j++) {
					const x = prev.x + ((p.x - prev.x) * j) / samples,
						y = prev.y + ((p.y - prev.y) * j) / samples,
						l = LAYERS.indexOf(p.layer);
					stamp(wire, l, x, y, 0, 0, width + clearance + extra, owner);
					stamp(
						via,
						l,
						x,
						y,
						0,
						0,
						width / 2 + viaRadius + clearance + extra,
						owner,
					);
				}
			}
		}
		traces.push({
			type: "pcb_trace",
			pcb_trace_id: `${connection.name}_grid${branch}`,
			connection_name: connection.name,
			source_trace_id: connection.source_trace_id,
			route,
		} as SimplifiedPcbTrace);
	}
	// Reserve package-normal dogbones and staggered through-vias before routing
	// any bus. Without this, an early bus can cut off its neighbor's pad escape.
	const escaped = new Map<string, P>();
	const accessRoutes = new Map<P, SimplifiedPcbTrace["route"]>();
	const directNets = new Set<string>();
	for (const [ci, c] of input.connections.entries()) {
		if (
			!c.pointsToConnect.some(
				(p) =>
					p.port_selector === "U1.USB_DP" || p.port_selector === "U1.USB_DM",
			)
		)
			continue;
		if (c.pointsToConnect.length !== 2)
			throw new Error("USB must remain point-to-point");
		const pair = [...c.pointsToConnect].sort(
			(a, b) =>
				Number(!a.port_selector?.startsWith("U1.")) -
				Number(!b.port_selector?.startsWith("U1.")),
		);
		const [a, b] = pair as [P, P];
		const vertical = Math.abs(b.y) > Math.abs(b.x);
		const tangent = vertical ? "x" : "y",
			normal = vertical ? "y" : "x";
		const bend = { ...a };
		bend[normal] =
			b[normal] -
			Math.sign(b[normal] - a[normal]) * Math.abs(b[tangent] - a[tangent]);
		// Keep the pair parallel on the top copper, without a layer transition.
		// Exact terminal geometry and pair skew are checked after rendering.
		record([], a, b, ci + 1, c, 0, [bend]);
		directNets.add(c.name);
	}
	const capSupplyPorts = new Set(
		(options.requiredPairs ?? []).map(([cap]) => cap),
	);
	for (const [capId, pinId] of options.requiredPairs ?? []) {
		const ci = input.connections.findIndex((c) =>
			c.pointsToConnect.some((p) => p.pcb_port_id === capId),
		);
		const c = input.connections[ci]!;
		const a = c.pointsToConnect.find((p) => p.pcb_port_id === capId)!;
		const b = c.pointsToConnect.find((p) => p.pcb_port_id === pinId)!;
		const early = /^C_D\d+\./.test(a.port_selector ?? "");
		if (!early) continue;
		const vertical = Math.abs(b.y) > Math.abs(b.x);
		const tangent = vertical ? "x" : "y",
			normal = vertical ? "y" : "x";
		const bend = { ...b };
		bend[normal] =
			a[normal] -
			Math.sign(a[normal] - b[normal]) * Math.abs(a[tangent] - b[tangent]);
		record([], b, a, ci + 1, c, 1000 + Number(capId.replace(/\D/g, "")), [
			bend,
		]);
	}
	// Reserve each local decoupler return before other nets can occupy the
	// nearby via sites. Underside reservoirs must not force a long return.
	for (const [ci, c] of input.connections.entries())
		for (const [pi, p] of c.pointsToConnect.entries()) {
			if (!/^C_D\d+\.pin2$/.test(p.port_selector ?? "")) continue;
			let found = false;
			for (const radius of [0.7, 1, 1.25]) {
				for (let angle = 0; angle < 360; angle += 45) {
					const ep = pos(
						index({
							...p,
							x: p.x + radius * Math.cos((angle * Math.PI) / 180),
							y: p.y + radius * Math.sin((angle * Math.PI) / 180),
						}),
					);
					if (
						Math.hypot(ep.x - p.x, ep.y - p.y) > 1.3 ||
						!canVia(index(ep) % N, ci + 1)
					)
						continue;
					try {
						const ids = solve(p, ep, ci + 1, false);
						if (ids.length > 60) continue;
						const dest = { ...ep, layer: "inner1" };
						ids.push(index(dest));
						record(ids, p, dest, ci + 1, c, -pi - 1);
						escaped.set(`${ci}:${pi}`, dest);
						accessRoutes.set(dest, traces.at(-1)!.route);
						found = true;
						break;
					} catch {}
				}
				if (found) break;
			}
			if (!found)
				throw Error(
					`Cannot reserve local decoupler ground via: ${p.port_selector}`,
				);
		}
	// Crystal signal nets are short, completely top-side trees. Route them
	// after neighboring QFN escapes and before general support/bus routing.
	for (const [ci, c] of input.connections.entries()) {
		if (
			!c.pointsToConnect.some(
				(p) =>
					p.port_selector?.startsWith("Y1.") &&
					!p.port_selector?.match(/pin[24]|gnd/),
			)
		)
			continue;
		const remaining = [...c.pointsToConnect];
		const connected = [remaining.shift()!];
		let branch = 0;
		while (remaining.length) {
			let best = Infinity,
				ai = 0,
				bi = 0;
			for (let i = 0; i < connected.length; i++)
				for (let j = 0; j < remaining.length; j++) {
					const a = connected[i]!,
						b = remaining[j]!,
						d = Math.hypot(a.x - b.x, a.y - b.y);
					if (d < best) {
						best = d;
						ai = i;
						bi = j;
					}
				}
			const a = connected[ai]!,
				b = remaining[bi]!;
			record(solve(a, b, ci + 1, false), a, b, ci + 1, c, branch++);
			connected.push(b);
			remaining.splice(bi, 1);
		}
		directNets.add(c.name);
	}
	for (const [ci, c] of input.connections.entries())
		for (const [pi, p] of c.pointsToConnect.entries()) {
			if (
				directNets.has(c.name) ||
				(options.requiredPairs ?? []).some(
					([, pin]) => pin === p.pcb_port_id,
				) ||
				c.pointsToConnect.some(
					(p) =>
						p.port_selector?.startsWith("Y1.") &&
						!p.port_selector?.match(/pin[24]|gnd/),
				)
			)
				continue;
			if (
				!p.port_selector?.startsWith("U1.") ||
				Math.max(Math.abs(p.x), Math.abs(p.y)) < 4.5
			)
				continue;
			const vertical = Math.abs(p.y) > Math.abs(p.x),
				tangent = vertical ? p.x : p.y;
			const parity = Math.round((tangent + 4.2) / 0.4) % 2;
			let found = false;
			escapeSearch: for (const normal of [
				6.15 + parity * 0.65,
				5.85,
				6.15,
				6.8,
				7.5,
				3.75,
				4.15,
				8.1,
				9.2,
			])
				for (const shift of [0, 0.4, -0.4, 0.8, -0.8]) {
					const e: P = {
						x: vertical ? p.x + shift : Math.sign(p.x) * normal,
						y: vertical ? Math.sign(p.y) * normal : p.y + shift,
						layer: "top",
					};
					const ep = pos(index(e));
					ep.layer = "top";
					if (!canVia(index(ep) % N, ci + 1)) continue;
					try {
						const ids = solve(p, ep, ci + 1, false);
						if (ids.length > 160) continue;
						const dest = { ...ep, layer: LAYERS[1 + ((pi + ci) % 3)]! };
						ids.push(index(dest));
						record(ids, p, dest, ci + 1, c, -pi - 1);
						escaped.set(`${ci}:${pi}`, dest);
						accessRoutes.set(dest, traces.at(-1)!.route);
						found = true;
						break escapeSearch;
					} catch {}
				}
			if (!found) throw Error(`Cannot escape processor pin ${p.port_selector}`);
		}
	for (const [capId, pinId] of options.requiredPairs ?? []) {
		const ci = input.connections.findIndex((c) =>
			c.pointsToConnect.some((p) => p.pcb_port_id === capId),
		);
		const c = input.connections[ci]!;
		const a = c.pointsToConnect.find((p) => p.pcb_port_id === capId)!;
		const b = c.pointsToConnect.find((p) => p.pcb_port_id === pinId)!;
		const early = /^C_D\d+\./.test(a.port_selector ?? "");
		if (early) continue;
		record(
			solve(a, b, ci + 1, false),
			a,
			b,
			ci + 1,
			c,
			1000 + Number(capId.replace(/\D/g, "")),
		);
	}
	// Reserve an access via for each support-component pad and boundary terminal
	// as well: no later route is allowed to isolate an as-yet unrouted terminal.
	const padAccessOrder = input.connections
		.flatMap((c, ci) => c.pointsToConnect.map((p, pi) => ({ c, ci, p, pi })))
		.sort((a, b) => {
			const ai = options.first?.indexOf(a.c.name) ?? -1,
				bi = options.first?.indexOf(b.c.name) ?? -1;
			if (ai >= 0 || bi >= 0) return (ai < 0 ? 999 : ai) - (bi < 0 ? 999 : bi);
			const boundary = (p: P) =>
				Math.max(Math.abs(p.x), Math.abs(p.y)) >= TERMINAL_EDGE - 1e-4;
			return Number(boundary(b.p)) - Number(boundary(a.p));
		});
	for (const { c, ci, p, pi } of padAccessOrder) {
		if (escaped.has(`${ci}:${pi}`)) continue;
		if (directNets.has(c.name)) continue;
		if (
			p.port_selector?.startsWith("U1.") ||
			capSupplyPorts.has(p.pcb_port_id!)
		)
			continue;
		if (
			input.obstacles.some(
				(o) =>
					o.circuitJsonMetadata?.pcb_plated_hole_id &&
					o.circuitJsonMetadata.pcb_port_id === p.pcb_port_id &&
					o.layers.length === 4,
			)
		) {
			const preferred = 1 + ((ci + pi) % 3);
			const choices = [
				LAYERS[preferred]!,
				...LAYERS.filter((l) => l !== LAYERS[preferred]),
			];
			const vertical = Math.abs(p.y) > Math.abs(p.x);
			let reserved = false;
			for (const layer of choices) {
				for (const depth of [0.75, 1.25, 1.8]) {
					const contact = { ...p, layer };
					const target = pos(
						index({
							...contact,
							x: vertical ? p.x : p.x - Math.sign(p.x) * depth,
							y: vertical ? p.y - Math.sign(p.y) * depth : p.y,
						}),
					);
					try {
						const ids = solve(contact, target, ci + 1, false);
						if (ids.length > 100) continue;
						record(ids, contact, target, ci + 1, c, -pi - 1);
						escaped.set(`${ci}:${pi}`, target);
						accessRoutes.set(target, traces.at(-1)!.route);
						reserved = true;
						break;
					} catch {}
				}
				if (reserved) break;
			}
			if (!reserved)
				throw Object.assign(
					new Error(`Cannot reserve plated exit: ${p.port_selector}`),
					{ connection: c.name },
				);
			continue;
		}
		const candidates: P[] = [];
		if (Math.max(Math.abs(p.x), Math.abs(p.y)) >= TERMINAL_EDGE - 1e-4) {
			const vertical = Math.abs(p.y) > Math.abs(p.x);
			for (const depth of [0.75, 1.25, 1.8, 2.4])
				for (const offset of [0, 0.3, -0.3, 0.65, -0.65, 1.3, -1.3])
					candidates.push({
						...p,
						x: vertical ? p.x + offset : p.x - Math.sign(p.x) * depth,
						y: vertical ? p.y - Math.sign(p.y) * depth : p.y + offset,
					});
		} else {
			const componentName = p.port_selector?.split(".")[0];
			const otherPad =
				/^[CR]_/.test(componentName ?? "") &&
				input.connections
					.flatMap((c) => c.pointsToConnect)
					.find(
						(q) =>
							q.pcb_port_id !== p.pcb_port_id &&
							q.port_selector?.split(".")[0] === componentName,
					);
			const separation = otherPad
				? Math.hypot(p.x - otherPad.x, p.y - otherPad.y)
				: 1;
			const normal = otherPad
				? {
						x: (p.x - otherPad.x) / separation,
						y: (p.y - otherPad.y) / separation,
					}
				: { x: p.port_selector?.endsWith("pin1") ? -1 : 1, y: 0 };
			const sign = 1;
			for (const dx of [
				sign * 0.7,
				sign * 1.0,
				0,
				sign * 1.4,
				sign * 1.8,
				-sign * 0.7,
				-sign * 1.0,
				-sign * 1.4,
				-sign * 1.8,
			])
				for (const dy of [
					0, 0.7, -0.7, 1.05, -1.05, 1.4, -1.4, 1.8, -1.8, 2.2, -2.2,
				]) {
					if (dx === 0 && dy === 0) continue;
					candidates.push({
						x: p.x + dx * normal.x - dy * normal.y,
						y: p.y + dx * normal.y + dy * normal.x,
						layer: p.layer,
					});
				}
		}
		let found = false;
		for (const e of candidates) {
			if (Math.max(Math.abs(e.x), Math.abs(e.y)) > half - 0.15) continue;
			const ep = pos(index(e)),
				q = index(ep) % N;
			if (!canVia(q, ci + 1)) continue;
			const dest = {
				...ep,
				layer: LAYERS.filter((l) => l !== p.layer)[(ci + pi) % 3]!,
			};
			try {
				const ids = solve(p, ep, ci + 1);
				// A local access stub must stay short and on its pad's layer.
				if (
					ids.length > 120 ||
					ids.some((id) => Math.floor(id / N) !== LAYERS.indexOf(p.layer))
				)
					continue;
				ids.push(index(dest));
				record(ids, p, dest, ci + 1, c, -pi - 1);
				escaped.set(`${ci}:${pi}`, dest);
				found = true;
				break;
			} catch {}
		}
		if (!found)
			throw Object.assign(
				new Error(`Cannot reserve pad access: ${p.port_selector}`),
				{ connection: c.name },
			);
		accessRoutes.set(escaped.get(`${ci}:${pi}`)!, traces.at(-1)!.route);
	}
	const branchCounts = new Map<string, number>();
	const routePair = (
		c: SimpleRouteJson["connections"][number],
		owner: number,
		a: P,
		b: P,
	) => {
		const branch = branchCounts.get(c.name) ?? 0;
		branchCounts.set(c.name, branch + 1);
		try {
			record(solve(a, b, owner), a, b, owner, c, branch);
			const reverse = (r: SimplifiedPcbTrace["route"]) =>
				r
					.toReversed()
					.map((p) =>
						p.route_type === "via"
							? { ...p, from_layer: p.to_layer, to_layer: p.from_layer }
							: { ...p },
					);
			const trace = traces.at(-1)!;
			trace.route = [
				...(accessRoutes.get(a) ?? []),
				...trace.route,
				...reverse(accessRoutes.get(b) ?? []),
			].filter((p, i, all) => {
				const prev = all[i - 1];
				return !(
					prev?.route_type === "wire" &&
					p.route_type === "wire" &&
					prev.layer === p.layer &&
					Math.hypot(prev.x - p.x, prev.y - p.y) < 1e-8
				);
			});
		} catch (e) {
			throw Object.assign(new Error(`${c.name}: ${(e as Error).message}`), {
				connection: c.name,
				partialTraces: traces,
			});
		}
	};
	const endpointLists = input.connections.map((c, ci) =>
		c.pointsToConnect.map((p, pi) => escaped.get(`${ci}:${pi}`) ?? p),
	);
	const parent = new Map<P, P>();
	const root = (p: P): P => {
		const q = parent.get(p);
		return q && q !== p ? root(q) : p;
	};
	// Route each assigned capacitor-to-pin branch before constructing rail trees.
	// Union these pairs so the general tree cannot replace them with nearest-net edges.
	for (const [capId, pinId] of options.requiredPairs ?? []) {
		const ci = input.connections.findIndex(
			(c) =>
				c.pointsToConnect.some((p) => p.pcb_port_id === capId) &&
				c.pointsToConnect.some((p) => p.pcb_port_id === pinId),
		);
		if (ci < 0)
			throw Error(`Dedicated decoupler and target must share a rail: ${capId}`);
		const c = input.connections[ci]!,
			endpoints = endpointLists[ci]!;
		const a =
			endpoints[c.pointsToConnect.findIndex((p) => p.pcb_port_id === capId)]!;
		const b =
			endpoints[c.pointsToConnect.findIndex((p) => p.pcb_port_id === pinId)]!;
		// The top-only capacitor branch was reserved before support routing.
		parent.set(root(a), root(b));
	}
	const ordered = input.connections
		.map((c, i) => ({ c, owner: i + 1 }))
		.sort((a, b) => {
			const ai = options.first?.indexOf(a.c.name) ?? -1,
				bi = options.first?.indexOf(b.c.name) ?? -1;
			if (ai >= 0 || bi >= 0) return (ai < 0 ? 999 : ai) - (bi < 0 ? 999 : bi);
			return a.c.pointsToConnect.length - b.c.pointsToConnect.length;
		});
	for (const [i, { c, owner }] of ordered.entries()) {
		if (directNets.has(c.name)) continue;
		options.onProgress?.(
			`${i + 1}/${ordered.length} ${c.name} (${c.pointsToConnect.length} terminals)`,
		);
		const endpoints = endpointLists[owner - 1]!;
		const connected = endpoints.filter((p) => root(p) === root(endpoints[0]!));
		let remaining = endpoints.filter((p) => !connected.includes(p));
		while (remaining.length) {
			let best = Infinity,
				a = connected[0]!,
				b = remaining[0]!;
			for (const p of connected)
				for (const q of remaining) {
					const d = Math.abs(p.x - q.x) + Math.abs(p.y - q.y);
					if (d < best) {
						best = d;
						a = p;
						b = q;
					}
				}
			routePair(c, owner, a, b);
			const group = remaining.filter((p) => root(p) === root(b));
			connected.push(...group);
			remaining = remaining.filter((p) => !group.includes(p));
		}
	}

	return traces.filter((t) => !t.pcb_trace_id.includes("_grid-"));
}