Open Source High Quality Autorouting: Is it possible?

[timofonic]

It's surprising a student effort may offer better features than high end EDA software such as Altium Designer.

Is so difficult to make a top quality advanced autorouter or just a "boring" topic?

What able sending patches to KiCad or other projects?

Those are the most active autorouters. Do to know about some more?

C-PCB. Last commit: Apr 13, 2016.

FreeRoutingNew. Last commit: May 27, 2016.

My interest lies in assisted learning, mostly. Good autorouters aren't perfect, but they inspire me to what paths to choose and such. Routing is somewhat a therapy for my spatial issues of ADHD too.

[Godzil]

Is so difficult to make a top quality advanced autorouter or just a "boring" topic?

First reason. You know about the P=NP problems? and the Travelling salesman problem?
Autorouting is some order of magnitude more complex than that.

[altaic]

First reason. You know about the P=NP problems? and the Travelling salesman problem?
Autorouting is some order of magnitude more complex than that.

I would be interested in seeing a proof of that.

TSP is NP-hard with a time complexity of O(n^2 * 2^n). Auto-routing is closer to the n-body problem, which has a time complexity of O(n^2). Furthermore, there are many approximation techniques which can reduce the time to O(n log n) if not O(n). Also, the algorithms for solving such problems are highly parallelizable and thus run nicely on GPUs. Finally, routing a PCB is unlikely to be a worst-case scenario, and algorithms exist that make solving common cases fast.

So, I respectfully disagree. Auto-routing is not so hard-- getting correct models from device manufacturers so can auto-routers can work is hard.

[Godzil]

There are also a lot of approximation on the TSP problem.

Auto routing is basically the TSP as we want the shortest path, but we have
- multiple path to look at the same time
- there are most of the time constrain on the path you have to choose because some sellers have to travel at the same time going to different borough of the same town (basically routing a bus)
- path MUST NOT cross in most conditions, where in the normal TSP it doesn't matter
- Highly parallelisable? Maybe by doing a lot of approximations, but there are some rules that would ultimately prevent parallelisations, like the fact that two track which does not belong to the same net must not ever cross, and that have a huge impact on parallelisation as each thread need to know what the other are doing, so basically they are not running asynchronously.
- Giving a solution "fast" does not mean that it's the best! It's also possible to give really fast a solution for the TSP, but it will never be the best solution.

There are way more constrain on routing than on the TSP, that's why it's more difficult.

Current approach of auto routing are approximations and not the "best results", as current TSP solvers.

[timofonic]

Why aren't brave souls improving projects like C-PCB or FreeRoutingNew? what about making a bounty for it?

- C-PCB is developed in C++14, it provides a better integration with EDA software and better performance.

- FreeRouting(New) provides better results, but it has a dubious legal situation and users the controversial and non-native Java programming language.

[zapta]

Auto routing is basically the TSP as we want the shortest path, but we have ...

Nets are typically not routed as a long trace going through a sequence of pads. For a single layer, single net, no obstacles, any angle routing and total length minimization, this is a closer problem https://en.wikipedia.org/wiki/Steiner_tree_problem which allows to insert additional points and to fork the trace.

[nctnico]

Why aren't brave souls improving projects like C-PCB or FreeRoutingNew? what about making a bounty for it?

IMHO fixing how Kicad handles components, symbols and footprints should have a much higher priority. As it is now you can't really use it in a (somewhat) professional environment. Once you get used to what Orcad Capture CIS offers (one click BOM generation from a database) you never want to go back to editing BOM files manually!

[Jeroen3]

Last routing sessing in Eagle I decided to record it using OBS. Inspired by Dave's Altium uSupply timelapse.
I must say that it is interesting to watch to see layout choices change on the way.
You can learn from yourself when playing back stuff like this.

It must be really hard for an AI to perform this, because even I cannot think of all the variables at play when I'm routing a board. It's an art.

[timofonic]

Extreme cases are extreme.

What are the best autorouters in the world? Specctre? Electra? TopoR?

Do they got analyzed and reverse engineered in Europe? Maybe clean room could help.

[Godzil]

Reverse engineering? Yeah probably, but I will wish you a really good luck at that, and clean room is not possible are you are not documenting API but how it is working, aka the algorithm which is likely to be patented.

It's would be easier to start from a blank paper than to try to clone something existing which is that complex.

[timofonic]

I see.

Why not get C-PCB and improve it?

What developers think about the code base? What about making it a library?

[timofonic]

No opinions? Any developer alive work some interest in it?

[janoc]

Extreme cases are extreme.

What are the best autorouters in the world? Specctre? Electra? TopoR?

Do they got analyzed and reverse engineered in Europe? Maybe clean room could help.

Considering that most people working on these things do so in their free time, I doubt that there is much interest in reverse engineering another program. The effort required in order to not put oneself in legal jeopardy (all the clean room stuff) is not something most will want to touch.

Even if the algorithms weren't patented (I doubt they are - there are many many publications on graph algorithms and specifically PCB routing, so at least the general ideas cannot really be patented), unless someone actually funds a project like that then nobody is going to do it just as a "hobby". Way too much legal risk (even if reverse engineering is legal, the costs of having to defend a baseless lawsuit are not free!) and there are much more pressing problems in the free EDA tools than the lack of an autorouter.

No opinions? Any developer alive work some interest in it?

C-PCB is pretty much a toy at the moment and not a serious/usable router. It takes a netlist and routes everything, without any constraints or rules, such as "don't route this high current trace around my ADC!". I don't think that anyone would want to spend the non-trivial time that it would take to integrate on something that is ultimately not usable yet. Also the development doesn't seem to be very active - one developer and the last significant changes were 6 and 11 months ago.

[vygr]

Hi folks, got a little time to experiment with my PCB solver. I'm going to do a JavaScript version. With a view to eventually having a website where you drop your .dsn file and set a few options and it gives you back the Gerbers etc.

Just got the viewer going so far this weekend. Learning JavaScript while I go, and D3/SVG for the output. Nice thing about this version will be that any modern browser gives you all you need to route your boards, no software to install etc. The client does the solving, not the server.

I'm hoping that modern JavaScript jits are as good as they say 60% C++ speed. We will see..... If it is, then hobby boards should solve in a few seconds. Well that's the plan.

https://github.com/vygr/JS-PCB

Regards to all as usual.

Chris

[vygr]

BTW I completely agree with Janoc's comments that for a comercial router you need more rules about how to route tracks. But you've got to start somewhere so I did.

Thanks Timofonic for your enthusiastic push of C-PCB, but there does need to be more done than I can possibly do alone. I put it out there to see if it was useful to people. As I said before, I was interested in the problem but don't have full time I can spend on it. Certainly not if I can't make money for living from it !

I'll keep adding bits as I find time, and the JavaScript web version is the next idea I'm going to tackle.

Chris

[vygr]

Progress being made on the JS version.

Live view is now enabled at https://vygr.github.io/JS-PCB/. No need to download or clone anything, just give it a try on a DSN file, you might find a few issues ATM, enjoy.

Just got the DSN import going and the viewer. No solver ported yet, but working on it.

Regards

Chris

[janoc]

Um, I don't want to pour cold water on your effort, but you do realize that a JavaScript based autorouter has very little chance to be actually integrated into anything? (unless you are planning to run it as a web service hosted somewhere, of course).

I simply don't see Kicad/Geda/whatever developers to include Node.js or a Chrome/Webkit runtime (or whatever you are using) only to run your autorouter. You would stand a lot better chance to have it integrated if it had a C/C++ or Python interfaces, because that is what these projects are using already.

[BloodyCactus]

I simply don't see Kicad/Geda/whatever developers to include Node.js or a Chrome/Webkit runtime (or whatever you are using) only to run your autorouter. You would stand a lot better chance to have it integrated if it had a C/C++ or Python interfaces, because that is what these projects are using already.

kicad is built with wxwidgets, wx already has a wxWebView which lets you run javascript...

[janoc]

kicad is built with wxwidgets, wx already has a wxWebView which lets you run javascript...

wxWebView actually has to be enabled at compile time first, it is an optional component in Wx. It is also meant to display HTML using Webkit (Linux & Mac) or Microsoft's IE engine (in Windows), but that is not a full blown browser by itself. So while you can run Javascript, I would be mightily surprised if some complex "weby" framework stuff relying on the presence of certain browser features was running in it out of the box, without hooking up a ton of extra plumbing to it first.

Anyhow, even if it did - have you actually tried interacting with HTML/Javascript code running inside of a webpage from outside of the HTML widget using C++ APIs? I can tell you, you don't want to go there - it is a huge and complex mess, because most of the Javascript apis are simply not accessible from outside. It is an encapsulated black box (by design) and all you get is an API to load a HTML page, navigate history, copy & paste and similar, but nothing to actually interact with the objects within the page (e.g. DOM access). So the "integration" would have to be done using temporary files, injecting bits of Javascript to the page and similar kludges. Gee, thank you ..

[BloodyCactus]

kicad is built with wxwidgets, wx already has a wxWebView which lets you run javascript...

wxWebView actually has to be enabled at compile time first, it is an optional component in Wx. It is also meant to display HTML using Webkit (Linux & Mac) or Microsoft's IE engine (in Windows), but that is not a full blown browser by itself. So while you can run Javascript, I would be mightily surprised if some complex "weby" framework stuff relying on the presence of certain browser features was running in it out of the box, without hooking up a ton of extra plumbing to it first.

Anyhow, even if it did - have you actually tried interacting with HTML/Javascript code running inside of a webpage from outside of the HTML widget using C++ APIs? I can tell you, you don't want to go there - it is a huge and complex mess, because most of the Javascript apis are simply not accessible from outside. It is an encapsulated black box (by design) and all you get is an API to load a HTML page, navigate history, copy & paste and similar, but nothing to actually interact with the objects within the page (e.g. DOM access). So the "integration" would have to be done using temporary files, injecting bits of Javascript to the page and similar kludges. Gee, thank you ..

huh thats interesting. I use javascript scripts in java all the time for scripting. as long as you dont do DOM manipulation, you can do all kinds of javascript stuff. I thought it would have been similar in wx.

[janoc]

huh thats interesting. I use javascript scripts in java all the time for scripting. as long as you dont do DOM manipulation, you can do all kinds of javascript stuff. I thought it would have been similar in wx.

Well, look at the API of that class for yourself: http://docs.wxwidgets.org/trunk/classwx_web_view.html

That's all you get. There is not even direct access to the Webkit backend.