Fusion - the Fusion 360 Bridge

"""Explicit four-layer routing experiment. No reference copper or external router.
Candidate routes remain unvalidated until checked in native Fusion.
"""
import heapq,itertools,json,math,time,sys
from pathlib import Path
import sys
sys.path.insert(0,str(Path(__file__).resolve().parent.parent))
from geometry import Geometry as BaseGeometry,LAYERS
from shapely.geometry import box
from shapely.strtree import STRtree
ROOT=Path(__file__).resolve().parent
THERMAL=[('Q1','VAC1',(8.5,20.2,13.7,25.5)),('Q2_Q4','VBUS',(8.5,9.,13.8,17.5)),('Q3','VAC2',(8.5,.8,13.8,6.3)),('Q5','VBAT',(45.5,7.5,50.1,11.5)),('IC1','PGND',(33.7,12.,36.7,14.4))]
class Geometry(BaseGeometry):
 def __init__(self):
  super().__init__()
  for name,net,bounds in THERMAL:self.add_obstacle(box(*bounds),net,[16],'thermal-reservation')
  self.index=STRtree(self.obstacles)
def octilinear(a,b):
 dx=abs(b[0]-a[0]);dy=abs(b[1]-a[1]);return min(dx,dy,abs(dx-dy))<0.000002

POWER={'VBUS','VAC1','VAC2','VIN1','VIN2','VBAT','BAT','SYS','PGND','PMID','SW1','SW2','SRCTOSRC','SRCTOSRC1'}

def candidates(a,b):
 if octilinear(a,b):yield [a,b]
 dx,dy=b[0]-a[0],b[1]-a[1];d=min(abs(dx),abs(dy));sx=1 if dx>=0 else -1;sy=1 if dy>=0 else -1
 # Prefer chamfered Manhattan paths with a single 45-degree transition.
 for c in [(a[0]+sx*d,a[1]+sy*d),(b[0]-sx*d,b[1]-sy*d)]:
  yield [a,c,b]
 # Two 45-degree chamfers with a horizontal/vertical middle run.
 if abs(dx)>abs(dy):yield [a,(a[0]+sx*d/2,a[1]+sy*d/2),(b[0]-sx*d/2,b[1]-sy*d/2),b]
 else:yield [a,(a[0]+sx*d/2,a[1]+sy*d/2),(b[0]-sx*d/2,b[1]-sy*d/2),b]

def simple(m,a,b,net,layer,width):
 for p in candidates(a,b):
  if m.clear(p,net,layer,width):return p

def detour(m,a,b,net,layer,width,limit=12000,step=.2):
 direct=simple(m,a,b,net,layer,width)
 if direct:return direct
 # Endpoint-anchored eight-neighbor A*, with continuous geometry on every edge.
 def xy(k):return (round(a[0]+k[0]*step,6),round(a[1]+k[1]*step,6))
 q=[(math.dist(a,b),0.,(0,0))];cost={(0,0):0};parent={};edges={}
 for _ in range(limit):
  if not q:break
  _,g,k=heapq.heappop(q)
  if g>cost[k]+1e-8:continue
  p=xy(k)
  tail=simple(m,p,b,net,layer,width) if math.dist(p,b)<=step*2 else None
  if tail:
   points=list(reversed(tail))
   while k in parent:k=parent[k];points.append(xy(k))
   points.reverse();out=[points[0]];i=0
   while i<len(points)-1:
    j=len(points)-1
    while j>i+1 and simple(m,points[i],points[j],net,layer,width) is None:j-=1
    replacement=simple(m,points[i],points[j],net,layer,width)
    out.extend(replacement[1:]);i=j
   return out
  for dx,dy in itertools.product([-1,0,1],repeat=2):
   if dx==dy==0:continue
   z=(k[0]+dx,k[1]+dy);nz=g+step*math.hypot(dx,dy)
   if nz>=cost.get(z,float('inf')):continue
   edge=tuple(sorted((k,z)))
   if edge not in edges:edges[edge]=m.clear([p,xy(z)],net,layer,width)
   if not edges[edge]:continue
   cost[z]=nz;parent[z]=k;heapq.heappush(q,(nz+math.dist(xy(z),b),nz,z))
 return None

def anchors(m,p,net,width):
 out=[(p['at'],[],[],p['layers'])]
 if len(p['layers'])==4:return out
 for radius in [.5,.75,1.,1.4,2.]:
  for i in range(16):
   t=math.pi*i/8;at=(round(p['at'][0]+radius*math.cos(t),6),round(p['at'][1]+radius*math.sin(t),6))
   if not m.via_clear(at,net):continue
   for l in p['layers']:
    path=simple(m,p['at'],at,net,l,width)
    if path:out.append((at,[(l,path,width)],[at],LAYERS));break
  if len(out)>12:break
 return out

def escape(m,p,net,width):
 # Search a fine grid for a legal through-via fanout when straight escapes fail.
 a=p['at'];step=.1;q=[(0.,(0,0))];cost={(0,0):0};parent={};found=[]
 def xy(k):return (round(a[0]+k[0]*step,6),round(a[1]+k[1]*step,6))
 for _ in range(6000):
  if not q or len(found)>=4:break
  g,k=heapq.heappop(q)
  if g>cost[k]+1e-8:continue
  at=xy(k)
  if g>.4 and m.via_clear(at,net) and all(math.dist(at,x[0])>.35 for x in found):
   path=[at];z=k
   while z in parent:z=parent[z];path.append(xy(z))
   path.reverse();found.append((at,[(p['layers'][0],path,width)],[at],LAYERS))
  if g>4:continue
  for dx,dy in itertools.product([-1,0,1],repeat=2):
   if not dx and not dy:continue
   z=(k[0]+dx,k[1]+dy);ng=g+step*math.hypot(dx,dy)
   if ng>=cost.get(z,float('inf')):continue
   if not m.clear([at,xy(z)],net,p['layers'][0],width):continue
   cost[z]=ng;parent[z]=k;heapq.heappush(q,(ng,z))
 return found

def connect(m,a,b,net,width,search=False):
 for l in set(a['layers'])&set(b['layers']):
  p=simple(m,a['at'],b['at'],net,l,width)
  if p:return [(l,p,width)],[]
 if not search:return None
 aa=anchors(m,a,net,width);bb=anchors(m,b,net,width)
 if len(aa)<3 and len(a['layers'])==1:aa+=escape(m,a,net,width)
 if len(bb)<3 and len(b['layers'])==1:bb+=escape(m,b,net,width)
 pairs=sorted(itertools.product(aa,bb),key=lambda x:math.dist(x[0][0],x[1][0])+2*(len(x[0][2])+len(x[1][2])))
 for x,y in pairs[:20]:
  if x[2] and y[2] and math.dist(x[0],y[0])<.405:continue
  for l in sorted(set(x[3])&set(y[3]),key=lambda v:[1,2,15,16].index(v)):
   path=simple(m,x[0],y[0],net,l,width)
   if path:return x[1]+[(l,path,width)]+y[1],x[2]+y[2]
 for x,y in sorted(pairs,key=lambda v:(not bool(set(v[0][3])&set(v[1][3])&{2,15}),math.dist(v[0][0],v[1][0])))[:12]:
  if x[2] and y[2] and math.dist(x[0],y[0])<.405:continue
  for l in sorted(set(x[3])&set(y[3]),key=lambda v:[15,2,1,16].index(v)):
   path=detour(m,x[0],y[0],net,l,width)
   if path:return x[1]+[(l,path,width)]+y[1],x[2]+y[2]
 for x,y in sorted(pairs,key=lambda v:math.dist(v[0][0],v[1][0]))[:6]:
  result=multilayer(m,x,y,net,width)
  if result:return result
 return None

def multilayer(m,x,y,net,width):
 a,b=x[0],y[0];step=.2;cost={};parent={};q=[];edgecache={};vcache={}
 def xy(k):return (round(a[0]+k[0]*step,6),round(a[1]+k[1]*step,6))
 for l in x[3]:
  k=(0,0,l);cost[k]=0.;heapq.heappush(q,(math.dist(a,b),0.,k))
 for _ in range(70000):
  if not q:break
  _,g,k=heapq.heappop(q)
  if g>cost[k]+1e-8:continue
  at=xy(k)
  tail=simple(m,at,b,net,k[2],width) if k[2] in y[3] and math.dist(at,b)<.4 else None
  if tail:
   states=[k]
   while k in parent:k=parent[k];states.append(k)
   states.reverse();parts=[];vias=[];points=[a];layer=states[0][2]
   for z in states[1:]:
    p=xy(z)
    if z[2]!=layer:
     parts.append((layer,points,width));vias.append(p);points=[p];layer=z[2]
    else:points.append(p)
   points.extend(tail[1:]);parts.append((layer,points,width));allvias=x[2]+vias+y[2]
   if any(math.dist(v,w)<.405 for i,v in enumerate(allvias) for w in allvias[:i]):continue
   return x[1]+parts+y[1],allvias
  neighbors=[]
  for dx,dy in itertools.product([-1,0,1],repeat=2):
   if not dx and not dy:continue
   z=(k[0]+dx,k[1]+dy,k[2]);ng=g+step*math.hypot(dx,dy)
   if ng>=cost.get(z,float('inf')):continue
   edge=tuple(sorted((k,z)))
   if edge not in edgecache:edgecache[edge]=m.clear([at,xy(z)],net,k[2],width)
   if edgecache[edge]:neighbors.append((z,ng))
  loc=k[:2]
  if loc not in vcache:vcache[loc]=all(math.dist(at,v)>.405 for v in x[2]+y[2]) and m.via_clear(at,net)
  if vcache[loc]:neighbors.extend(((k[0],k[1],l),g+3.) for l in LAYERS if l!=k[2])
  for z,ng in neighbors:
   if ng>=cost.get(z,float('inf')):continue
   cost[z]=ng;parent[z]=k;heapq.heappush(q,(ng+math.dist(xy(z),b),ng,z))
 return None

def run():
 outdir=ROOT/(sys.argv[1] if len(sys.argv)>1 else 'pass-02');outdir.mkdir(exist_ok=False)
 m=Geometry();parents={p:p for p in m.pads}
 def find(x):
  while parents[x]!=x:parents[x]=parents[parents[x]];x=parents[x]
  return x
 def join(a,b):parents[find(a)]=find(b)
 edges=[]
 for net,pads in m.groups.items():
  for a,b in itertools.combinations(pads,2):
   if set(a['layers'])&set(b['layers']) and a['shape'].intersection(b['shape']).area>1e-7:join(a['name'],b['name'])
   edges.append((math.dist(a['at'],b['at']),net,a,b))
 edges.sort(key=lambda e:e[0]);started=time.time();failures=[]
 def save():
  groups={n:len({find(p['name']) for p in ps}) for n,ps in m.groups.items()}
  report={'status':'experimental - native DRC pending','source':'bq25792-astra-unrouted.brd','externalRouter':False,'elapsed':time.time()-started,'componentsPerNet':groups,'remainingConnections':sum(n-1 for n in groups.values()),'routes':m.routes,'failures':failures}
  (outdir/'candidate-plan.json').write_text(json.dumps(report,indent=2));m.export(outdir/'bq25792-astra-candidate.brd')
 escaped=set()
 for stage in ['ic','direct','search']:
  search=stage!='direct'
  for _,net,a,b in edges:
   if stage=='ic':
    pins=[p['name'] for p in (a,b) if p['name'].startswith('IC1.')]
    if not pins or all(p in escaped for p in pins):continue
   if find(a['name'])==find(b['name']):continue
   width=.4 if net in POWER else .15
   # Fine-pitch power escapes will need wider trunks/pours before electrical qualification.
   if min(a['shape'].bounds[2]-a['shape'].bounds[0],a['shape'].bounds[3]-a['shape'].bounds[1],b['shape'].bounds[2]-b['shape'].bounds[0],b['shape'].bounds[3]-b['shape'].bounds[1])<.4:width=.2 if net in POWER else .15
   r=connect(m,a,b,net,width,search)
   if r:
    m.add_route(net,*r);join(a['name'],b['name']);escaped.update(p['name'] for p in (a,b) if p['name'].startswith('IC1.'));print(net,a['name'],b['name'],'routes',len(m.routes),flush=True);save()
   elif search:failures.append({'net':net,'from':a['name'],'to':b['name']});save()
 save()
if __name__=='__main__':run()