ShiboSoftwareDev/linux-gameboy-advance

scripts/route-backlight.mjs

import fs from "node:fs"

const soup = JSON.parse(fs.readFileSync("dist/index/circuit.json", "utf8"))
const step = 0.25
const layers = ["top", "inner1", "inner2", "bottom"]
const revisionTracePattern = /^(source_trace_36[1-9]|source_trace_37[0-1]|source_net_0_mst8[6-9]|source_net_6_mst4[3-9])_0$/
const oldTraces = soup.filter((e) => e.type === "pcb_trace" && !revisionTracePattern.test(e.pcb_trace_id ?? ""))
const pads = soup.filter((e) => e.type === "pcb_smtpad" || e.type === "pcb_plated_hole")
const vias = soup.filter((e) => e.type === "pcb_via" && !revisionTracePattern.test(e.pcb_trace_id ?? ""))
const holes = soup.filter((e) => e.type === "pcb_hole")
const ports = new Map(soup.filter((e) => e.type === "pcb_port").map((e) => [e.pcb_port_id, e]))

const plans = [
  { id: "source_trace_365_0", connection: "source_trace_365", from: "pcb_port_297", to: "pcb_port_554", width: 0.5, net: "OUT" },
  { id: "source_trace_366_0", connection: "source_trace_366", from: "pcb_port_550", to: "pcb_port_554", width: 0.12, net: "OUT" },
  { id: "source_trace_367_0", connection: "source_trace_367", from: "pcb_port_558", to: "pcb_port_554", width: 0.5, net: "OUT" },
  { id: "source_trace_369_0", connection: "source_trace_369", from: "pcb_port_298", to: "pcb_port_548", width: 0.12, net: "FB" },
  { id: "source_net_6_mst43_0", connection: "source_net_6", from: "pcb_port_528", to: "pcb_port_551", width: 0.5, net: "V3V3" },
  { id: "source_trace_361_0", connection: "source_trace_361", from: "pcb_port_556", to: "pcb_port_551", width: 0.5, net: "V3V3" },
  { id: "source_net_6_mst44_0", connection: "source_net_6", from: "pcb_port_551", to: "pcb_port_549", width: 0.5, net: "V3V3" },
  { id: "source_net_6_mst45_0", connection: "source_net_6", from: "pcb_port_551", to: "pcb_port_552", width: 0.5, net: "V3V3" },
  { id: "source_trace_363_0", connection: "source_trace_363", from: "pcb_port_553", to: "pcb_port_546", width: 0.5, net: "SW" },
  { id: "source_trace_364_0", connection: "source_trace_364", from: "pcb_port_555", to: "pcb_port_546", width: 0.5, net: "SW" },
  { id: "source_trace_370_0", connection: "source_trace_370", from: "pcb_port_548", to: "pcb_port_560", width: 0.12, net: "FB" },
  { id: "source_trace_371_0", connection: "source_trace_371", from: "pcb_port_561", to: "pcb_port_562", width: 0.12, net: "SET" },
  { id: "source_net_0_mst86_0", connection: "source_net_0", from: "pcb_port_399", to: "pcb_port_547", width: 0.5, net: "GND" },
  { id: "source_net_0_mst87_0", connection: "source_net_0", from: "pcb_port_533", to: "pcb_port_557", width: 0.5, net: "GND" },
  { id: "source_net_0_mst88_0", connection: "source_net_0", from: "pcb_port_379", to: "pcb_port_559", width: 0.5, net: "GND" },
  { id: "source_net_0_mst89_0", connection: "source_net_0", from: "pcb_port_557", to: "pcb_port_563", width: 0.5, net: "GND" },
]

const distToSegment = (p, a, b) => {
  const dx = b.x - a.x
  const dy = b.y - a.y
  const den = dx * dx + dy * dy
  const t = den === 0 ? 0 : Math.max(0, Math.min(1, ((p.x - a.x) * dx + (p.y - a.y) * dy) / den))
  return Math.hypot(p.x - (a.x + t * dx), p.y - (a.y + t * dy))
}

class Heap {
  data = []
  push(item) {
    this.data.push(item)
    for (let i = this.data.length - 1; i > 0;) {
      const p = (i - 1) >> 1
      if (this.data[p].f <= item.f) break
      this.data[i] = this.data[p]
      i = p
      this.data[i] = item
    }
  }
  pop() {
    const root = this.data[0]
    const last = this.data.pop()
    if (this.data.length && last) {
      this.data[0] = last
      for (let i = 0;;) {
        let c = i * 2 + 1
        if (c >= this.data.length) break
        if (c + 1 < this.data.length && this.data[c + 1].f < this.data[c].f) c++
        if (this.data[c].f >= this.data[i].f) break
        ;[this.data[c], this.data[i]] = [this.data[i], this.data[c]]
        i = c
      }
    }
    return root
  }
}

const routed = []
const key = (x, y, layer) => `${Math.round(x / step)},${Math.round(y / step)},${layer}`
const pointForKey = (k) => {
  const [ix, iy, layer] = k.split(",")
  return { x: Number(ix) * step, y: Number(iy) * step, layer }
}

function blocked(point, plan, forVia = false) {
  if (point.x < -64 || point.x > 64 || point.y < -32 || point.y > 32) return true
  const routeRadius = forVia ? 0.225 : plan.width / 2
  const clearance = 0.105
  const endpointIds = new Set([plan.from, plan.to])
  for (const pad of pads) {
    if (!forVia && endpointIds.has(pad.pcb_port_id)) continue
    const padLayers = pad.layer ? [pad.layer] : (pad.layers ?? layers)
    if (!forVia && !padLayers.includes(point.layer)) continue
    const w = pad.width ?? pad.outer_width ?? pad.outer_diameter ?? pad.diameter ?? 0
    const h = pad.height ?? pad.outer_height ?? pad.outer_diameter ?? pad.diameter ?? w
    if (Math.abs(point.x - pad.x) <= w / 2 + routeRadius + clearance && Math.abs(point.y - pad.y) <= h / 2 + routeRadius + clearance) return true
  }
  for (const hole of holes) {
    const radius = (hole.hole_diameter ?? hole.diameter ?? 0) / 2
    if (Math.hypot(point.x - hole.x, point.y - hole.y) <= radius + routeRadius + clearance) return true
  }
  for (const via of vias) {
    if (Math.hypot(point.x - via.x, point.y - via.y) <= (via.outer_diameter ?? 0.45) / 2 + routeRadius + clearance) return true
  }
  for (const trace of oldTraces) {
    if ((trace.connectsTo ?? []).some((id) => endpointIds.has(id))) continue
    if (plan.net === "V3V3" && (trace.pcb_trace_id ?? "").includes("source_net_6_mst")) continue
    const route = trace.route ?? []
    for (let i = 1; i < route.length; i++) {
      const a = route[i - 1]
      const b = route[i]
      if (a.route_type !== "wire" || b.route_type !== "wire") continue
      if (!forVia && a.layer !== point.layer) continue
      if (forVia || a.layer === point.layer) {
        const oldRadius = Math.max(a.width ?? 0.12, b.width ?? 0.12) / 2
        if (distToSegment(point, a, b) <= oldRadius + routeRadius + clearance) return true
      }
    }
  }
  for (const trace of routed) {
    if (trace.net === plan.net && !forVia) continue
    for (let i = 1; i < trace.points.length; i++) {
      const a = trace.points[i - 1]
      const b = trace.points[i]
      if (a.layer !== b.layer) {
        if (Math.hypot(point.x - a.x, point.y - a.y) <= 0.225 + routeRadius + clearance) return true
      } else if (trace.net !== plan.net && (forVia || a.layer === point.layer) && distToSegment(point, a, b) <= trace.width / 2 + routeRadius + clearance) return true
    }
  }
  return false
}

function findPath(plan) {
  const startPort = ports.get(plan.from)
  const endPort = ports.get(plan.to)
  if (!startPort || !endPort) throw new Error(`Missing endpoint for ${plan.id}`)
  const startLayer = startPort.layers?.[0] ?? startPort.layer ?? "top"
  const endLayer = endPort.layers?.[0] ?? endPort.layer ?? "top"
  const start = { x: Math.round(startPort.x / step) * step, y: Math.round(startPort.y / step) * step, layer: startLayer }
  const end = { x: Math.round(endPort.x / step) * step, y: Math.round(endPort.y / step) * step, layer: endLayer }
  const startKey = key(start.x, start.y, start.layer)
  const endKey = key(end.x, end.y, end.layer)
  const heap = new Heap()
  const scores = new Map([[startKey, 0]])
  const parents = new Map()
  heap.push({ key: startKey, f: 0 })
  let visits = 0
  while (heap.data.length) {
    const currentEntry = heap.pop()
    const current = pointForKey(currentEntry.key)
    const g = scores.get(currentEntry.key)
    if (currentEntry.key === endKey) {
      const path = []
      let cursor = endKey
      while (cursor) {
        path.push(pointForKey(cursor))
        cursor = parents.get(cursor)
      }
      path.reverse()
      path[0] = { x: startPort.x, y: startPort.y, layer: startLayer }
      path[path.length - 1] = { x: endPort.x, y: endPort.y, layer: endLayer }
      return path
    }
    if (++visits > 1_500_000) throw new Error(`Search limit for ${plan.id}`)
    const neighbors = [
      { x: current.x + step, y: current.y, layer: current.layer, cost: step },
      { x: current.x - step, y: current.y, layer: current.layer, cost: step },
      { x: current.x, y: current.y + step, layer: current.layer, cost: step },
      { x: current.x, y: current.y - step, layer: current.layer, cost: step },
      ...layers.filter((layer) => layer !== current.layer).map((layer) => ({ x: current.x, y: current.y, layer, cost: 2.5, via: true })),
    ]
    for (const neighbor of neighbors) {
      const neighborKey = key(neighbor.x, neighbor.y, neighbor.layer)
      if (neighborKey !== endKey && blocked(neighbor, plan, neighbor.via)) continue
      if (neighbor.via && blocked(current, plan, true)) continue
      const tentative = g + neighbor.cost
      if (tentative >= (scores.get(neighborKey) ?? Infinity)) continue
      scores.set(neighborKey, tentative)
      parents.set(neighborKey, currentEntry.key)
      const h = Math.abs(neighbor.x - end.x) + Math.abs(neighbor.y - end.y) + (neighbor.layer === end.layer ? 0 : 2)
      heap.push({ key: neighborKey, f: tentative + h })
    }
  }
  throw new Error(`No path for ${plan.id}`)
}

function simplify(points) {
  const out = []
  for (const point of points) {
    const a = out.at(-2)
    const b = out.at(-1)
    if (a && b && a.layer === b.layer && b.layer === point.layer && ((a.x === b.x && b.x === point.x) || (a.y === b.y && b.y === point.y))) out[out.length - 1] = point
    else out.push(point)
  }
  return out
}

const output = []
for (const plan of plans) {
  const points = simplify(findPath(plan))
  routed.push({ ...plan, points })
  const route = []
  for (let i = 0; i < points.length; i++) {
    const point = points[i]
    const prior = points[i - 1]
    if (prior && prior.layer !== point.layer) {
      route.push({ route_type: "via", x: point.x, y: point.y, from_layer: prior.layer, to_layer: point.layer, via_diameter: 0.45, via_hole_diameter: 0.3 })
    }
    route.push({ route_type: "wire", x: point.x, y: point.y, width: plan.width, layer: point.layer, ...(i === 0 ? { start_pcb_port_id: plan.from } : {}), ...(i === points.length - 1 ? { end_pcb_port_id: plan.to } : {}) })
  }
  output.push({ type: "pcb_trace", pcb_trace_id: plan.id, connection_name: plan.connection, connectsTo: [plan.from, plan.to], route })
  console.log(`${plan.id}: ${points.length} points`)
}
fs.writeFileSync("/tmp/backlight-routes.json", `${JSON.stringify(output, null, 2)}\n`)
console.log("Wrote /tmp/backlight-routes.json")