https://github.com/StefanSalewski/RBR
That router project was the most important reason in 2014 for leaving Ruby and searching for another compiled and statically typed language. The router itself needs at least a delaunay triangulation and a reliable convexHullOfDisk implementation, and used initially also a fibonacci priority queue with decrese_key() function. And for an EDA tool to using that router a GUI is necessary of course.
Well now after nearly 7 years I finally managed to convert the core module with the rubberband routing from Ruby to Nim. Took me less than 200 hours for the 2k lines of Ruby code, which is faster than expected. The Nim code size is not much larger, and looks not worse than the Ruby code. Static typing makes all much cleaner. Speed with Nim is much larger of course.
Porting was really not that hard: I did all the conversions manually. First I converted very carefully to make it compile and partly work. Then I fixed a few bugs. Then I compared one more the Nim and Ruby code very carefully. And finally I had to find an ugly and difficult bug, which resulted from the fact that the Ruby code used the BOOST fibonacci queue for the dijstra routing, while we now use the heapqueue without decrese_key() operation and so have to record and check distances for each node carefully.
Well 200 hours for 2k Ruby code is fast for me, but it may sound slow to you: But note that we now use different libs with different API for delaunay, hull and priority queue. And after 7 years the own code looks partly strange as foreign code :-)
If someone really should be interested in the background of rubberband auto-routing of printed circuits boards, you can find more details in the PhD thesis of Tal Dayan from 1997:
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.8.6828&rep=rep1&type=pdf
Unfortunately the links to his thesis sometimes changes, but searching with
with search term "tal dayan router" or "tal dayan 1997" should find it.
Around 2010 we had discussed on the gEDA mailing lists concepts about autorouters for printed circuits boards. Beside the conventional grid based maze routers, which generates generally straight lines to connect electric terminals on a PCB board, we discussed topological routing with rubberbands. And I started an experimentation implementation in Ruby.
Unfortunately gEDA became less and less popular and was mostly replaced by the KiCad project then, so it made not that much sense to try to integrate a rubberband router into the gEDA schematics editor and PCB layout tool, as number of users went close to zero. And it became clear that Ruby is much better than C suited for such a router, but is still not the optimal language. So the project was stalled for a long time.
On the page http://ssalewski.de/Router.html.en there is a picture of a real PCB board with rubberband routed traces. The concept of routing copper traces on a PCB board is connecting terminal points with traces, while avoiding touching other terminals. Traces should be generally short, and of course are not allowed to cross. But most PCB boards have at least two layers for the traces, so traces can use vias to go from one layer to another layer. See https://en.wikipedia.org/wiki/Printed_circuit_board
And a commercial project with rubberband routing exists also: https://en.wikipedia.org/wiki/TopoR
Does he go into N layer PCBs, or is this constricted to just two layer?
The thesis describes routing of multi layer boards. Long traces are split into subparts, which than are designed to different layers by a greedy opimizeation algorithm, and the shorter traces are than rubberband routed and connected by vias.
For the colors in the pictures: The colored traces are the result of the dijkstra shortest path algorithm, which follows the edges of the delaunay triangulation. That dijkstra routing is then collapsed like rubberbands to the black curved traces, which are then finally the real copper traces on the PCB board.
Dijkstra routing and rubberband creation is by far the most daunting task, and unfortunately not described in much detail in his thesis. The layer assignment is described well and is easy to implement. The dijkstra routing is of course much more advanced as the plain pathfinding which one learns at university. One has to remember if the path makes left or right turns and other conditions. Rubberband collapsing is also not that easy. The terminals are described as disks in 2d, and concave traces relax on the convex hull on the disks. And finally the rubberbands, when they are relaxed and attached to the disks, have to be sorted, which took me some time to get it right. Another important point is the region split: Whenever one more trace is routed, that trace divides the whole set of terminals in two halves, as a routed trace can never be crossed by later routed traces.
Reading the thesis is indeed some fun.
Yes, it is all explained in the thesis, and the basic ideas are simple. The implementation not, they had a 14k lines of code C implementation they said, never released to the public, and full of bugs I guess due to C. Around 2010 someone of the gEDA project, I think it was Mr Anthony Blake, tried a C implementation, which was working partly, but no one was able to understand the few thousand lines of C code, and he gave up.
One point which is not that simple is rip up and retry. Tal Dayan was talking about that in his thesis, but I had no idea how it should work. Undoing region split seems to be impossible. But now I think that he did not really mean a ripup, but only saving some states. That should be easy, we may save the state maybe whenever 10 more traces are routed, and then when we notice during the routing process that some traces can not be routed as they are blocked, we can jump back to a saved state and reorder the remaining traces hoping that them they will not block each other.