ShiboSoftwareDev/linux-gameboy-advance

scripts/optimize-lcd-vias.mjs

import fs from "node:fs"
import { getFullConnectivityMapFromCircuitJson } from "circuit-json-to-connectivity-map"

const circuit = JSON.parse(fs.readFileSync("dist/index/circuit.json", "utf8"))
const cache = JSON.parse(fs.readFileSync("carrier-route-cache.json", "utf8"))
const traces = structuredClone(cache.traces)
const byId = new Map(traces.map((trace) => [trace.pcb_trace_id, trace]))
const finalTraceById = new Map(
  circuit.filter((e) => e.type === "pcb_trace").map((trace) => [trace.pcb_trace_id, trace]),
)
for (const trace of circuit.filter((e) => e.type === "pcb_trace")) {
  const cached = byId.get(trace.pcb_trace_id)
  if (cached) trace.route = cached.route
}
const connMap = getFullConnectivityMapFromCircuitJson(circuit)

const targets = [
  ["source_net_11_mst1_0", 58],
  ["source_trace_130_0", 52],
  ["source_trace_125_0", 15],
  ["source_trace_117_0", 7],
  ["source_trace_116_0", 18],
  ["source_trace_107_0", 12],
]

const segmentDistance = (a, b, c, d) => {
  const pointSegment = (p, u, v) => {
    const dx = v.x - u.x, dy = v.y - u.y
    const den = dx * dx + dy * dy
    const t = den ? Math.max(0, Math.min(1, ((p.x-u.x)*dx+(p.y-u.y)*dy)/den)) : 0
    return Math.hypot(p.x-(u.x+t*dx), p.y-(u.y+t*dy))
  }
  const orient = (p, q, r) => Math.sign((q.x-p.x)*(r.y-p.y)-(q.y-p.y)*(r.x-p.x))
  if (orient(a,b,c) !== orient(a,b,d) && orient(c,d,a) !== orient(c,d,b)) return 0
  return Math.min(pointSegment(a,c,d), pointSegment(b,c,d), pointSegment(c,a,b), pointSegment(d,a,b))
}
const pointSegmentDistance = (p, a, b) => {
  const dx=b.x-a.x, dy=b.y-a.y, den=dx*dx+dy*dy
  const t=den?Math.max(0,Math.min(1,((p.x-a.x)*dx+(p.y-a.y)*dy)/den)):0
  return Math.hypot(p.x-(a.x+t*dx),p.y-(a.y+t*dy))
}
const routeSegments = (trace) => {
  const out=[]
  for(let i=0;i<trace.route.length-1;i++){
    const a=trace.route[i], b=trace.route[i+1]
    const layer=a.route_type==="wire"?a.layer:b.route_type==="wire"?b.layer:null
    if(layer && (a.x!==b.x || a.y!==b.y)) out.push({a,b,layer,trace})
  }
  return out
}
const allTraceRecords = () => [
  ...circuit.filter((e) => e.type === "pcb_trace" && !byId.has(e.pcb_trace_id)),
  ...traces.map((route) => ({...finalTraceById.get(route.pcb_trace_id), ...route})),
]

const padElements = circuit.filter((e) => ["pcb_smtpad","pcb_plated_hole"].includes(e.type))
const padDistance = (point, pad) => {
  if(pad.type==="pcb_plated_hole") {
    const w=pad.outer_diameter??pad.outer_width, h=pad.outer_diameter??pad.outer_height
    return Math.hypot(Math.max(Math.abs(point.x-pad.x)-w/2,0),Math.max(Math.abs(point.y-pad.y)-h/2,0))
  }
  if(pad.shape==="circle") return Math.max(0,Math.hypot(point.x-pad.x,point.y-pad.y)-pad.radius)
  const angle=-(pad.ccw_rotation??0)*Math.PI/180, dx=point.x-pad.x, dy=point.y-pad.y
  const x=dx*Math.cos(angle)-dy*Math.sin(angle), y=dx*Math.sin(angle)+dy*Math.cos(angle)
  return Math.hypot(Math.max(Math.abs(x)-pad.width/2,0),Math.max(Math.abs(y)-pad.height/2,0))
}
const segmentPadDistance = (a,b,pad) => {
  const length=Math.hypot(b.x-a.x,b.y-a.y), steps=Math.max(1,Math.ceil(length/0.025))
  let best=Infinity
  for(let i=0;i<=steps;i++){
    const t=i/steps
    best=Math.min(best,padDistance({x:a.x+(b.x-a.x)*t,y:a.y+(b.y-a.y)*t},pad))
  }
  return best
}

for (const [traceId, viaIndex] of targets) {
  const trace=byId.get(traceId), route=trace.route, old=route[viaIndex]
  const wideSpans={
    source_trace_127_0:[24,37],
    source_trace_124_0:[25,36],
  }
  const [incomingIndex,outgoingIndex]=wideSpans[traceId]??[viaIndex-2,viaIndex+2]
  const incoming=route[incomingIndex], outgoing=route[outgoingIndex]
  if(!incoming||!outgoing) throw new Error(`Bad via index ${traceId}:${viaIndex}`)
  const otherSegments=allTraceRecords().filter((other)=>
    !connMap.areIdsConnected(traceId,other.pcb_trace_id)).flatMap(routeSegments)
  const otherVias=allTraceRecords().filter((other)=>
    !connMap.areIdsConnected(traceId,other.pcb_trace_id)).flatMap((other)=>
      other.route.filter((p)=>p.route_type==="via").map((p)=>({...p,trace:other})))
  const otherPads=padElements.filter((pad)=>
    !connMap.areIdsConnected(traceId,pad.pcb_smtpad_id??pad.pcb_plated_hole_id))
  let best=null
  const viaPointIsClear = (candidate) =>
    !otherSegments.some((s)=>pointSegmentDistance(candidate,s.a,s.b)<0.395) &&
    !otherVias.some((v)=>Math.hypot(candidate.x-v.x,candidate.y-v.y)<0.56) &&
    !otherPads.some((pad)=>padDistance(candidate,pad)<0.335)
  const segmentIsClear = (a,b,layer) =>
    !otherSegments.some((s)=>s.layer===layer&&segmentDistance(a,b,s.a,s.b)<0.23) &&
    !otherVias.some((v)=>pointSegmentDistance(v,a,b)<0.395) &&
    !otherPads.some((pad)=>(pad.layers??[pad.layer]).includes(layer)&&segmentPadDistance(a,b,pad)<0.17)
  const findPath = (start,end,layer) => {
    if(segmentIsClear(start,end,layer)) return [end]
    const minX=Math.min(start.x,end.x)-3,maxX=Math.max(start.x,end.x)+3
    const minY=Math.min(start.y,end.y)-3,maxY=Math.max(start.y,end.y)+3
    const candidates=[]
    for(let x=Math.ceil(minX*10)/10;x<=maxX;x+=0.1)
      for(let y=Math.ceil(minY*10)/10;y<=maxY;y+=0.1)
        candidates.push({x,y,cost:Math.hypot(x-start.x,y-start.y)+Math.hypot(end.x-x,end.y-y)})
    candidates.sort((a,b)=>a.cost-b.cost)
    for(const p of candidates)
      if(segmentIsClear(start,p,layer)&&segmentIsClear(p,end,layer)) return [p,end]
    // Fall back to an A* dogleg for the densest FPC channels.
    const step=0.1
    const gridMinX=Math.floor((minX-1)*10)/10,gridMaxX=Math.ceil((maxX+1)*10)/10
    const gridMinY=Math.floor((minY-1)*10)/10,gridMaxY=Math.ceil((maxY+1)*10)/10
    const key=(p)=>`${Math.round(p.x*10)},${Math.round(p.y*10)}`
    const point=(key)=>{const [x,y]=key.split(",").map(Number);return{x:x/10,y:y/10}}
    const startKey=key(start), open=[startKey], came=new Map(), g=new Map([[startKey,0]])
    const heuristic=(p)=>Math.hypot(p.x-end.x,p.y-end.y)
    const f=new Map([[startKey,heuristic(start)]])
    const openSet=new Set(open), closed=new Set()
    const dirs=[[-1,0],[1,0],[0,-1],[0,1],[-1,-1],[-1,1],[1,-1],[1,1]]
    let goalKey=null
    while(open.length&&closed.size<30000){
      let bestIndex=0
      for(let i=1;i<open.length;i++)if((f.get(open[i])??Infinity)<(f.get(open[bestIndex])??Infinity))bestIndex=i
      const currentKey=open.splice(bestIndex,1)[0];openSet.delete(currentKey)
      const current=currentKey===startKey?start:point(currentKey)
      if(segmentIsClear(current,end,layer)){goalKey=currentKey;break}
      closed.add(currentKey)
      for(const [dx,dy] of dirs){
        const next={x:Math.round((current.x+dx*step)*10)/10,y:Math.round((current.y+dy*step)*10)/10}
        if(next.x<gridMinX||next.x>gridMaxX||next.y<gridMinY||next.y>gridMaxY)continue
        const nextKey=key(next)
        if(closed.has(nextKey)||!segmentIsClear(current,next,layer))continue
        const tentative=(g.get(currentKey)??0)+Math.hypot(dx*step,dy*step)
        if(tentative>=(g.get(nextKey)??Infinity))continue
        came.set(nextKey,currentKey);g.set(nextKey,tentative);f.set(nextKey,tentative+heuristic(next))
        if(!openSet.has(nextKey)){open.push(nextKey);openSet.add(nextKey)}
      }
    }
    if(!goalKey)return null
    const path=[]
    let cursor=goalKey
    while(cursor!==startKey){path.unshift(point(cursor));cursor=came.get(cursor)}
    path.push(end)
    // Remove collinear grid points to keep the fixed route compact.
    for(let i=1;i<path.length-1;){
      if(segmentIsClear(path[i-1]??start,path[i+1],layer))path.splice(i,1)
      else i++
    }
    return path
  }
  for(let radius=0.05;radius<=3.0001&&!best;radius+=0.05){
    const candidates=[]
    const steps=Math.ceil(radius/0.05)
    for(let ix=-steps;ix<=steps;ix++) for(let iy=-steps;iy<=steps;iy++){
      const dx=ix*0.05,dy=iy*0.05
      if(Math.hypot(dx,dy)>radius+1e-6||Math.hypot(dx,dy)<radius-0.08)continue
      candidates.push({x:old.x+dx,y:old.y+dy,d:Math.hypot(dx,dy)})
    }
    candidates.sort((a,b)=>a.d-b.d)
    for(const candidate of candidates){
      if(!viaPointIsClear(candidate))continue
      if(!segmentIsClear(incoming,candidate,old.from_layer) ||
        !segmentIsClear(candidate,outgoing,old.to_layer)) continue
      best=candidate;break
    }
  }
  // In the two densest fanout channels, the unchanged adjacent segments can
  // make the conservative segment pre-check reject every point. Find the
  // nearest via-clear point anyway; the exact tscircuit routing checks below
  // are the authority for the two newly formed short segments.
  let usedFallback=false
  if(!best) outer: for(let radius=0.05;radius<=6.0001;radius+=0.05){
    const steps=Math.ceil(radius/0.05)
    for(let ix=-steps;ix<=steps;ix++) for(let iy=-steps;iy<=steps;iy++){
      const dx=ix*0.05,dy=iy*0.05,d=Math.hypot(dx,dy)
      if(d>radius+1e-6||d<radius-0.08)continue
      const candidate={x:old.x+dx,y:old.y+dy,d}
      if(viaPointIsClear(candidate)){best=candidate;usedFallback=true;break outer}
    }
  }
  if(best&&usedFallback){
    best.incomingPath=findPath(incoming,best,old.from_layer)
    best.outgoingPath=findPath(best,outgoing,old.to_layer)
    if(!best.incomingPath||!best.outgoingPath) best=null
  }
  if(!best){console.error(`No candidate for ${traceId}:${viaIndex}`);continue}
  console.log(`${traceId}:${viaIndex} (${old.x.toFixed(3)},${old.y.toFixed(3)}) -> (${best.x.toFixed(3)},${best.y.toFixed(3)}) d=${best.d.toFixed(3)}`)
  const incomingPath=best.incomingPath??[best]
  const outgoingPath=best.outgoingPath??[outgoing]
  route.splice(incomingIndex+1,outgoingIndex-incomingIndex-1,
    ...incomingPath.map((p)=>({route_type:"wire",x:p.x,y:p.y,width:0.12,layer:old.from_layer})),
    {route_type:"via",x:best.x,y:best.y,from_layer:old.from_layer,to_layer:old.to_layer,
      via_diameter:0.45,via_hole_diameter:0.3},
    {route_type:"wire",x:best.x,y:best.y,width:0.12,layer:old.to_layer},
    ...outgoingPath.slice(0,-1).map((p)=>({route_type:"wire",x:p.x,y:p.y,width:0.12,layer:old.to_layer})),
  )
}

// PE4's final inner1-to-top via sits between D7 (bottom), D10 (inner2), and the
// TWI0_SDA via. Route those two buried-layer bends around the southeast side of
// the via pair, then return to their already-routed northwest channels.
const localWire = (x, y, layer) => ({ route_type: "wire", x, y, width: 0.12, layer })
byId.get("source_trace_107_0").route.splice(15, 4,
  localWire(11.5, 27, "bottom"),
  localWire(11.5, 31, "bottom"),
)

fs.writeFileSync("work/optimized-carrier-traces.json",JSON.stringify(traces,null,2)+"\n")