seveibar/am3352-ram-dogbone-and-single-layer-route-test

routing/single-layer.ts

type Point={x:number,y:number}
type Route={name:string,points:Point[],targetLength?:number}
const STEP=0.1, TRACE_SPACING=0.202, VIA_SPACING=0.302
class Heap {
 a:{id:number,f:number,g:number}[]=[]
 push(e:{id:number,f:number,g:number}){let i=this.a.length;this.a.push(e);while(i){const p=(i-1)>>1;if(this.a[p].f<=e.f)break;this.a[i]=this.a[p];i=p}this.a[i]=e}
 pop(){const first=this.a[0],last=this.a.pop()!;if(this.a.length){let i=0;while(2*i+1<this.a.length){let j=2*i+1;if(j+1<this.a.length&&this.a[j+1].f<this.a[j].f)j++;if(this.a[j].f>=last.f)break;this.a[i]=this.a[j];i=j}this.a[i]=last}return first}
}
export const length=(p:Point[])=>p.slice(1).reduce((s,b,i)=>s+Math.hypot(b.x-p[i].x,b.y-p[i].y),0)
function simplify(p:Point[]){return p.filter((b,i)=>!i||i===p.length-1||Math.abs((b.x-p[i-1].x)*(p[i+1].y-b.y)-(b.y-p[i-1].y)*(p[i+1].x-b.x))>1e-8)}
export class Grid {
 nx:number;ny:number;blocked:Uint8Array
 occupancy?: Uint16Array | Uint8Array; history?: Float32Array; penalty=0
 constructor(public bounds:any){this.nx=Math.floor((bounds.maxX-bounds.minX)/STEP)+1;this.ny=Math.floor((bounds.maxY-bounds.minY)/STEP)+1;this.blocked=new Uint8Array(this.nx*this.ny)}
 point(i:number):Point{return{x:this.bounds.minX+(i%this.nx)*STEP,y:this.bounds.minY+Math.floor(i/this.nx)*STEP}}
 id(p:Point){return Math.round((p.x-this.bounds.minX)/STEP)+Math.round((p.y-this.bounds.minY)/STEP)*this.nx}
 disk(p:Point,r:number){const cx=Math.round((p.x-this.bounds.minX)/STEP),cy=Math.round((p.y-this.bounds.minY)/STEP),n=Math.ceil(r/STEP)+1;for(let y=Math.max(0,cy-n);y<=Math.min(this.ny-1,cy+n);y++)for(let x=Math.max(0,cx-n);x<=Math.min(this.nx-1,cx+n);x++){if(Math.hypot(this.bounds.minX+x*STEP-p.x,this.bounds.minY+y*STEP-p.y)<r)this.blocked[x+y*this.nx]=1}}
 segment(a:Point,b:Point,r:number){const n=Math.max(1,Math.ceil(Math.hypot(a.x-b.x,a.y-b.y)/0.045));for(let i=0;i<=n;i++)this.disk({x:a.x+(b.x-a.x)*i/n,y:a.y+(b.y-a.y)*i/n},r)}
 route(p:Point[],r:number){for(let i=1;i<p.length;i++)this.segment(p[i-1],p[i],r)}
 search(a:Point,b:Point){
  const start=this.id(a),end=this.id(b),n=this.blocked.length
  if(this.blocked[start]||this.blocked[end])return null
  const cost=new Float64Array(n);cost.fill(Infinity);cost[start]=0
  const parent=new Int32Array(n);parent.fill(-1)
  const heap=new Heap();const ex=end%this.nx,ey=Math.floor(end/this.nx)
  const h=(x:number,y:number)=>{const dx=Math.abs(x-ex),dy=Math.abs(y-ey);return Math.max(dx,dy)+(Math.SQRT2-1)*Math.min(dx,dy)}
  heap.push({id:start,g:0,f:h(start%this.nx,Math.floor(start/this.nx))})
  while(heap.a.length){const q=heap.pop();if(q.g!==cost[q.id])continue;if(q.id===end){const path:Point[]=[];let id=end;while(id!==-1){path.push(this.point(id));id=parent[id]}path.reverse();path[0]=a;path[path.length-1]=b;return simplify(path)}
   const x=q.id%this.nx,y=Math.floor(q.id/this.nx)
   for(let dy=-1;dy<=1;dy++)for(let dx=-1;dx<=1;dx++){
    if(!(dx||dy)||x+dx<2||x+dx>=this.nx-2||y+dy<2||y+dy>=this.ny-2)continue
    const id=q.id+dx+dy*this.nx;if(this.blocked[id])continue
    if(dx&&dy&&(this.blocked[q.id+dx]||this.blocked[q.id+dy*this.nx]))continue
    const occupancy=Math.max(this.occupancy?.[id]??0,dx&&dy?Math.max(this.occupancy?.[q.id+dx]??0,this.occupancy?.[q.id+dy*this.nx]??0):0)
    const g=q.g+(dx&&dy?Math.SQRT2:1)+occupancy*this.penalty+(this.history?.[id]??0)
    if(g+1e-8>=cost[id])continue
    cost[id]=g;parent[id]=q.id;heap.push({id,g,f:g+h(x+dx,y+dy)})
   }
  }return null
 }
}
export function routeLayer(connections:Route[],vias:any[],bounds:any,layer:string,options:{maxAttempts?:number,preferredOrder?:string[],quiet?:boolean}={}){
 let randomState=12345;const random=()=>{randomState=(Math.imul(randomState,1664525)+1013904223)>>>0;return randomState/4294967296}
 let order=[...connections].sort((a,b)=>length(a.points)-length(b.points));let best=0,bestRoutes:Route[]=[]
 if(options.preferredOrder)order.sort((a,b)=>options.preferredOrder!.indexOf(a.name)-options.preferredOrder!.indexOf(b.name))
 for(let attempt=0;attempt<(options.maxAttempts??500);attempt++){
  const routes:Route[]=[];let failed:Route|undefined
  for(const c of order){const grid=new Grid(bounds);for(const via of vias)if(via.net!==c.name)grid.disk(via,VIA_SPACING);for(const r of routes)grid.route(r.points,TRACE_SPACING)
   // Reserve the other terminals before routing any tracks.
   const points=grid.search(c.points[0],c.points[1]);if(!points){failed=c;break}const route={name:c.name,points}
   if(c.targetLength){
    if(length(points)>c.targetLength){failed=c;break}
    try {tuneLengths([...routes,route],vias,bounds,[{connectionNames:[c.name],targetLength:c.targetLength,maxLengthSkew:0.05}],[],layer,true)} catch{failed=c;break}
   }
   routes.push(route)
  }
  if(!failed){if(!options.quiet)console.log(`${layer}: routed ${routes.length} connections on attempt ${attempt+1}`);return routes}
  if(routes.length>best){best=routes.length;bestRoutes=structuredClone(routes);if(!options.quiet)console.log(`${layer}: best ${best}/${connections.length}, retrying ${failed.name}`)}
  const i=order.indexOf(failed);order.splice(i,1);order.splice(Math.max(0,i-1-Math.floor(attempt/10)%Math.max(1,i)),0,failed)
  if(attempt%20===19){order=[...connections];for(let j=order.length-1;j>0;j--){const k=Math.floor(random()*(j+1));[order[j],order[k]]=[order[k],order[j]]}}
  if(attempt%8===7){const k=attempt%order.length;[order[0],order[k]]=[order[k],order[0]]}
 }
 const error=new Error(`${layer}: no-via routing incomplete (${best}/${connections.length})`) as Error & {partialRoutes:Route[]};error.partialRoutes=bestRoutes;throw error
}
// Continuous segment checks for meander insertion; this is independent of the A* grid.
const dist=(a:Point,b:Point)=>Math.hypot(a.x-b.x,a.y-b.y)
function pointSegment(p:Point,a:Point,b:Point){const dx=b.x-a.x,dy=b.y-a.y,t=Math.max(0,Math.min(1,((p.x-a.x)*dx+(p.y-a.y)*dy)/(dx*dx+dy*dy||1)));return dist(p,{x:a.x+t*dx,y:a.y+t*dy})}
function cross(a:Point,b:Point,c:Point){return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)}
export function segmentDist(a:Point,b:Point,c:Point,d:Point){if(cross(a,b,c)*cross(a,b,d)<0&&cross(c,d,a)*cross(c,d,b)<0)return 0;return Math.min(pointSegment(a,c,d),pointSegment(b,c,d),pointSegment(c,a,b),pointSegment(d,a,b))}
export function tuneLengths(routes:Route[],vias:any[],bounds:any,buses:any[],pairs:any[],layer:string,quiet=false,orderSeed=0){
 const byName=new Map(routes.map(r=>[r.name,r]));
 const groups=[...buses.map(b=>({names:b.connectionNames,tol:b.maxLengthSkew??0.635,targetLength:b.targetLength})),...pairs.map(p=>({names:p.connectionNames,tol:p.lengthTolerance,targetLength:undefined}))]
 for(const group of groups){const members:Route[]=group.names.map((n:string)=>byName.get(n)).filter(Boolean);if(members.length<2&&!group.targetLength)continue
  const hash=(name:string)=>{let h=orderSeed+1;for(const ch of name)h=Math.imul(h^ch.charCodeAt(0),16777619);return h>>>0}
  members.sort((a,b)=>orderSeed===0?length(a.points)-length(b.points):orderSeed===1?length(b.points)-length(a.points):hash(a.name)-hash(b.name))
  const target=group.targetLength??Math.max(...members.map(r=>length(r.points)))
  for(const r of members){let need=target-length(r.points);if(need<=Math.min(group.tol*0.3,0.02))continue
   for(let pass=0;pass<1000&&need>0.01;pass++){
    let changed=false
    const others=routes.filter(t=>t!==r)
    for(let i=0;i<r.points.length-1&&!changed;i++){
     const a=r.points[i],b=r.points[i+1],d=dist(a,b);if(d<0.31)continue
     const ux=(b.x-a.x)/d,uy=(b.y-a.y)/d
     for(let offset=0.02;offset+0.25<d-0.02&&!changed;offset+=0.1){
     const p={x:a.x+ux*offset,y:a.y+uy*offset},q={x:a.x+ux*(offset+0.25),y:a.y+uy*(offset+0.25)}
     for(const sign of [1,-1]){
      const valid=(height:number)=>{
       const m={x:p.x-uy*height*sign,y:p.y+ux*height*sign},n={x:q.x-uy*height*sign,y:q.y+ux*height*sign}
       const candidate=[p,m,n,q]
       if(candidate.some(t=>t.x<bounds.minX+0.3||t.x>bounds.maxX-0.3||t.y<bounds.minY+0.3||t.y>bounds.maxY-0.3))return null
       for(let j=1;j<candidate.length;j++){
        for(const v of vias)if(v.net!==r.name&&pointSegment(v,candidate[j-1],candidate[j])<0.29999)return null
        for(const other of others)for(let k=1;k<other.points.length;k++)if(segmentDist(candidate[j-1],candidate[j],other.points[k-1],other.points[k])<0.19999)return null
        for(let k=1;k<r.points.length;k++)if(k<i||k>i+2)if(segmentDist(candidate[j-1],candidate[j],r.points[k-1],r.points[k])<0.19999)return null
       }return candidate
      }
      let hi=Math.min(need/2,6),lo=0;for(let t=0;t<16;t++){const mid=(lo+hi)/2;if(valid(mid))lo=mid;else hi=mid}
      if(lo<0.03)continue
      const points=valid(lo)!;r.points.splice(i+1,0,...points);need=target-length(r.points);changed=true;break
     }
    }
    }
    if(!changed)break
   }
   if(target-length(r.points)>group.tol)throw new Error(`${layer}: cannot length match ${r.name}: short by ${(target-length(r.points)).toFixed(3)}mm`)
  }
  if(!quiet)console.log(`${layer}: matched ${members.length} signals; skew ${(Math.max(...members.map(r=>length(r.points)))-Math.min(...members.map(r=>length(r.points)))).toFixed(4)}mm`)
 }
}

/** Remove closed centerline loops introduced by moving very short meander corners. */
export function removeLoops(points:Point[]) {
 let ps=points.filter((p,i)=>!i||Math.hypot(p.x-points[i-1].x,p.y-points[i-1].y)>1e-9)
 for(let pass=0;pass<points.length;pass++){
  let changed=false
  for(let i=0;i<ps.length-1&&!changed;i++)for(let j=i+2;j<ps.length-1;j++){
   const a=ps[i],b=ps[i+1],c=ps[j],d=ps[j+1],rx=b.x-a.x,ry=b.y-a.y,sx=d.x-c.x,sy=d.y-c.y,den=rx*sy-ry*sx
   if(Math.abs(den)<1e-16)continue
   const t=((c.x-a.x)*sy-(c.y-a.y)*sx)/den,u=((c.x-a.x)*ry-(c.y-a.y)*rx)/den
   if(t>=0&&t<=1&&u>=0&&u<=1){const p={x:a.x+t*rx,y:a.y+t*ry};ps=[...ps.slice(0,i+1),p,...ps.slice(j+1)];ps=ps.filter((p,k)=>!k||Math.hypot(p.x-ps[k-1].x,p.y-ps[k-1].y)>1e-9);changed=true;break}
  }
  if(!changed)return ps
 }
 throw new Error('Could not remove routing loops')
}