What happens if you have to make a lot of crossovers on a circuit board? For example, here is a printed circuit board that connects pins 1 to 10 in a randomly chosen order. In this layout, finished by a person after the autorouter gave up, you have to drill 14 holes, spend time and create dust.
Keeping in mind that our group is working on unconventional electronics, could a woven circuit do better? Woven items are made of crossovers between warp and weft threads. Looking at the problem of how you would bring 10 connectors from right to left on a circuit, crossovers are painless if the wires are insulated, but corners are harder because they involve soldering and cutting. Here is an autorouter in action that draws the same circuit as the PCB, attempts to minimize corners and doesn’t get stuck. (MATLAB code and 100-pin example after the jump).
Here is the code.
%weaveroute %CKH Aug 2015 %Use the "sliding puzzle" method to route N horizontal threads to their %randomly chosen destinations by creating a gap %Check if any lines are crooked %Move the first crooked line half off its destination to open a gap; the %penalty for doing this is an extra pair of corners. %Then use that gap to switch over each crooked line in turn. %Then plot all those lines, and finally draw in all the straight lines. %Then, fix any problems where two lines overlapped. Each fix adds an extra %pair of corners. clear; N=10;%How many threads? Source=1:N; %Here's the original thread positions Dest=randperm(N); %Here's where I have to route them Straightline=find(Source==Dest);%get indices of any straight line pairs Numstraight=length(Straightline); hold off Crookedline=find(Source~=Dest);%the rest are mixed up Numcrook=length(Crookedline); %ok works except for some overlaps am gonna have to detect each overlap & %add a corner pair if Numcrook >0 %if not all straight lines HalfpathY=[Source(Crookedline(1)), Source(Crookedline(1)), Dest(Crookedline(1))+0.5, Dest(Crookedline(1))+0.5, Dest(Crookedline(1)), Dest(Crookedline(1))];%Create a gap by moving the first crooked one to halfway off its destination HalfpathX=[0 1 1];%Begin drawing this crooked, gap-creating line. RestOPathsX=zeros(4,Numcrook-1); %space to hold all the rest of the paths which will have 4 points RestOPathsY=RestOPathsX; %Just initializing with zeros so Matlab won't warn about array size increasing Gapdex=find(Dest==Crookedline(1)); %Find gives the source position of the first crooked line Oldgap=[Source(Crookedline(1))]; %Now we've moved that trace off and can bring the correct trace down to Gapdex and its destination there. for i=2:Numcrook%all the rest of these paths will have 4 points Oldgap=[Oldgap Gapdex];%more about this below RestOPathsX(2:3,i-1)=i;%Set the x-coordinate where each crooked path makes its vertical transition RestOPathsY(1:2,i-1)=Gapdex; RestOPathsY(3:4,i-1)=Dest(Gapdex); Gapdex=find(Dest==Gapdex);%Gets stuck if there is a loop--so bust out if you've been there before if(ismember(Gapdex,Oldgap))%uh oh been here before unused=setdiff(Crookedline,Oldgap); if (unused)%check that we are not done...if we're done, there's nothing IN unused. Gapdex=unused(1);%If not done just go with the first unused value. end end end HalfpathX=[HalfpathX Numcrook+1 Numcrook+1 Numcrook+2]; %finish that first path RestOPathsX(4,:)=Numcrook+2; %add the final x-coord to all other crooked paths plot(HalfpathX,HalfpathY,'ko-'); %plot the first path in black hold on; plot(RestOPathsX,RestOPathsY,'o-'); %and the remaining crooked paths in various colors end StraightPathsX=; StraightPathsY=; if Numstraight>0 StraightPathsX=repmat([0;Numcrook+2],1,Numstraight); StraightPathsY=[Source(Straightline);Dest(Straightline)]; plot(StraightPathsX,StraightPathsY,'o--');%straight paths as various colored dashed lines end %Next detect & fix overlaps by moving the more lefterly point up 0.5, then %back down at the end of the row. It shouldn't hit the black line or the %straight lines because we don't route the crooked paths along their y-values. %Overlaps can be detected in the XY arrays. Look for same Y value and %out-of-order X values. %If there's an overlap I will create Figure 2 and show the repair. hold off RestOPathsYFixed=RestOPathsY; RestOPathsXFixed=RestOPathsX; badLocs=;%thing to hold any bad locations in the x-y coords for j=1:N crookedLocToCheck=find(RestOPathsY==j);%check if each row is on a crooked path if(crookedLocToCheck) crookedX=RestOPathsX(crookedLocToCheck); if (find(diff(crookedX)<0))%overlap if not monotonic. There are negative values in the diff. badLocs=[badLocs;crookedLocToCheck]; disp ('OVERLAP!!!') j %in what row? end end end %Now I'm going to add a couple points to the offending crooked lines using %badLocs. Add ([0.5 0.5 0 0]') to the existing y-values, do %something to bring it back down at the end. YFixIndex=badLocs([1:4:length(badLocs),2:4:length(badLocs)]) RestOPathsYFixed(YFixIndex)=RestOPathsY(YFixIndex)+0.5; XFixIndex=badLocs([2:4:length(badLocs)]); RestOPathsXFixed(XFixIndex)=RestOPathsX(XFixIndex)-1; %Now extend the end for everyone so we hit the target for all modified & unmodified traces, expanding the array RestOPathsXFixed=[RestOPathsXFixed;RestOPathsXFixed(4,:);RestOPathsXFixed(4,:)+1]; RestOPathsYFixed=[RestOPathsYFixed;floor(RestOPathsYFixed(4,:));floor(RestOPathsYFixed(4,:))]; PathsToRetract=find((RestOPathsYFixed(3,:)-RestOPathsYFixed(6,:))==0);%Gives which of the traces were not zig zagged at the end RestOPathsXFixed(5,PathsToRetract)=RestOPathsXFixed(4,PathsToRetract); RestOPathsXFixed(6,PathsToRetract)=RestOPathsXFixed(4,PathsToRetract);%pull back those path ends figure(2) hold off plot(HalfpathX,HalfpathY,'k+-', 'LineWidth',2);%The initial path hold on plot(RestOPathsXFixed,RestOPathsYFixed,'+-','LineWidth',2);%The crooked paths modified to avoid overlap plot(StraightPathsX,StraightPathsY,'+-','LineWidth',2);%The straight paths axis tight axis equal hold off