ShiboSoftwareDev/linux-gameboy-advance

scripts/route-d10-local.mjs

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

const routeFile = process.argv[2] ?? "work/optimized-carrier-traces.json"
const circuit = JSON.parse(fs.readFileSync("dist/index/circuit.json", "utf8"))
const traces = JSON.parse(fs.readFileSync(routeFile, "utf8"))
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 fixed = byId.get(trace.pcb_trace_id)
  if (fixed) trace.route = fixed.route
}
const connMap = getFullConnectivityMapFromCircuitJson(circuit)
const targetId = "source_trace_108_0"
const target = byId.get(targetId)
const startIndex = 12
const endIndex = 16
const start = target.route[startIndex]
const end = target.route[endIndex]
const layer = "inner2"
const bounds = { minX: -10, maxX: 30, minY: 15, maxY: 40.5 }

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 segmentDistance = (a,b,c,d) => {
  const cross = (p,q,r)=>(q.x-p.x)*(r.y-p.y)-(q.y-p.y)*(r.x-p.x)
  const o1=cross(a,b,c),o2=cross(a,b,d),o3=cross(c,d,a),o4=cross(c,d,b)
  if (((o1>0&&o2<0)||(o1<0&&o2>0))&&((o3>0&&o4<0)||(o3<0&&o4>0))) return 0
  return Math.min(pointSegmentDistance(a,c,d),pointSegmentDistance(b,c,d),
    pointSegmentDistance(c,a,b),pointSegmentDistance(d,a,b))
}
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 otherSegments=[]
const otherVias=[]
for(const trace of allTraceRecords){
  if(connMap.areIdsConnected(targetId,trace.pcb_trace_id))continue
  for(let i=0;i<trace.route.length-1;i++){
    const a=trace.route[i],b=trace.route[i+1]
    if(a.route_type==="wire"&&b.route_type==="wire"&&a.layer===layer&&
      Math.max(a.x,b.x)>=bounds.minX&&Math.min(a.x,b.x)<=bounds.maxX&&
      Math.max(a.y,b.y)>=bounds.minY&&Math.min(a.y,b.y)<=bounds.maxY)
      otherSegments.push({a,b,id:trace.pcb_trace_id})
  }
  for(const point of trace.route)if(point.route_type==="via"&&
    point.x>=bounds.minX&&point.x<=bounds.maxX&&point.y>=bounds.minY&&point.y<=bounds.maxY)otherVias.push({...point,id:trace.pcb_trace_id})
}
const pads=circuit.filter((pad)=>["pcb_smtpad","pcb_plated_hole"].includes(pad.type)&&
  (pad.layers??[pad.layer]).includes(layer)&&pad.x>=bounds.minX&&pad.x<=bounds.maxX&&
  pad.y>=bounds.minY&&pad.y<=bounds.maxY)
  .filter((pad)=>!connMap.areIdsConnected(targetId,pad.pcb_smtpad_id??pad.pcb_plated_hole_id))
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 count=Math.max(1,Math.ceil(Math.hypot(b.x-a.x,b.y-a.y)/0.04));let best=Infinity
  for(let i=0;i<=count;i++){const t=i/count;best=Math.min(best,padDistance({x:a.x+(b.x-a.x)*t,y:a.y+(b.y-a.y)*t},pad))}
  return best
}
const edgeClear=(a,b)=>
  !otherSegments.some((s)=>segmentDistance(a,b,s.a,s.b)<0.221)&&
  !otherVias.some((v)=>pointSegmentDistance(v,a,b)<0.386)&&
  !pads.some((pad)=>segmentPadDistance(a,b,pad)<0.161)

const nearest = (point) => ({
  segment: otherSegments.map((s)=>({d:pointSegmentDistance(point,s.a,s.b),id:s.id}))
    .sort((a,b)=>a.d-b.d)[0],
  via: otherVias.map((v)=>({d:Math.hypot(point.x-v.x,point.y-v.y),id:v.id,x:v.x,y:v.y}))
    .sort((a,b)=>a.d-b.d)[0],
  pad: pads.map((pad)=>({d:padDistance(point,pad),id:pad.pcb_smtpad_id??pad.pcb_plated_hole_id}))
    .sort((a,b)=>a.d-b.d)[0],
})
console.log(JSON.stringify({obstacles:{segments:otherSegments.length,vias:otherVias.length,pads:pads.length},start:nearest(start),end:nearest(end)},null,2))

const step=.1,key=(p)=>`${Math.round(p.x/step)},${Math.round(p.y/step)}`
const point=(k)=>{const [x,y]=k.split(",").map(Number);return{x:x*step,y:y*step}}
const startKey=key(start),open=[startKey],openSet=new Set(open),closed=new Set()
const came=new Map(),g=new Map([[startKey,0]]),score=new Map([[startKey,Math.hypot(start.x-end.x,start.y-end.y)]])
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<50000){
  let bi=0;for(let i=1;i<open.length;i++)if((score.get(open[i])??Infinity)<(score.get(open[bi])??Infinity))bi=i
  const ck=open.splice(bi,1)[0];openSet.delete(ck)
  const current=ck===startKey?start:point(ck)
  if(edgeClear(current,end)){goalKey=ck;break}
  closed.add(ck)
  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<bounds.minX||next.x>bounds.maxX||next.y<bounds.minY||next.y>bounds.maxY)continue
    const nk=key(next);if(closed.has(nk)||!edgeClear(current,next))continue
    const ng=(g.get(ck)??0)+Math.hypot(dx*step,dy*step)
    if(ng>=(g.get(nk)??Infinity))continue
    came.set(nk,ck);g.set(nk,ng);score.set(nk,ng+Math.hypot(next.x-end.x,next.y-end.y))
    if(!openSet.has(nk)){open.push(nk);openSet.add(nk)}
  }
}
if(!goalKey)throw new Error(`No inner2 path after ${closed.size} nodes`)
const path=[];let cursor=goalKey
while(cursor!==startKey){path.unshift(point(cursor));cursor=came.get(cursor)}
path.push(end)
for(let i=0;i<path.length-1;) {
  const previous=i===0?start:path[i-1]
  if(edgeClear(previous,path[i+1]))path.splice(i,1);else i++
}
const wires=path.slice(0,-1).map((p)=>({route_type:"wire",x:p.x,y:p.y,width:.12,layer}))
target.route.splice(startIndex+1,endIndex-startIndex-1,...wires)
fs.writeFileSync(routeFile,JSON.stringify(traces,null,2)+"\n")
console.log(JSON.stringify({nodes:closed.size,segments:wires.length+1,path:[start,...path]},null,2))