i use freerouting. I grabbed the source when it came up about the zuken takedown. built it to run locally (no webstart etc needed), the others I cant comment on.
the definition of the problem is very simple : you are trying to solve the 'travelling salesman problem' , except you are doing it for thousands of salesmen travelling at the same time and they can't use the same roads ... throw in rules for certain roads to be the same length and rules to keep certain roads specific distances away from others and how many bridges you can built between point a and b ... and you can imagine how the complexity simply explodes...
There is only one router that really works and that is SPECCTRA. And even that is a bitch to control and set up and get anything useful out of it.
Yo and a little detail - traveling salesman is most likely NP-hard too, so writing an autorouter that will actually do its job and finish in a reasonable time is pretty much black magic.
Then you have pesky domain-specific details that an experienced board designer will know but autorouters generally don't - like don't run weak ADC input traces next to the main Vcc rail. It is a much more complex problem than just routing few lines and making sure they don't cross.
Autorouter is not something that a hobbyist or someone working on an open source project in their free time is likely going to have resources and knowledge to tackle - that's why there are no decent ones around.
@Circuiteromalaguito, if you are looking for a "push a button for a ready to manufacture board" type of solution, better spend the time elsewhere - even the expensive commercial autorouters are not anywhere near to that sort of ability yet, unless you are doing very simple boards (but then why to use autorouter?).
I have used both freerouting and ELECTRA, freerouting produces superior results for small boards with zero effort.
ELECTRA scales to large boards well, but does need a lot of care and feeding to produce something meaningful.
Autorouting is not the travelling salesman problem at all, because the complexity in TSP is in finding the one and only optimal solution. Meanwhile, autorouters just have to find a solution that conforms to certain geometric constraints (tracks mustn't intersect), a problem which TSP isn't concerned with at all. TSP is really hard with 2000 points, right? I can write you an autorouter right now that can instantly connect 2000 points (all on the same net) on a PCB right now easily. TSP is one continuous, unbranching path. Autorouters are allowed to branch.
So no, there's basically nothing at all in common between TSP and autorouting. TSP doesn't even operate in a cartesian space, it's on a graph.
The misapprehension about TSP aside, autorouters need a lot of careful training before they can be useful -- "these are power rails, they should be short and thick". "This chip should have no signal lines running under it". "These are delicate analog signal traces that should be kept far away from the switching power supply". "The ground plane shouldn't be interrupted unnecessarily". It's very hard a) for the user to teach the autorouter all this, and b) for the autorouter to be able to take this all into account. Just the UI for the human-machine interaction there is a pain. It's one of those really ill-defined problems that benefits from man-years of hacky little adjustments and special cases and painstaking, expensive development. And even when an autorouter is done well, it requires a great deal of user configuration to actually work well. Which is why completely autorouting a board from scratch should never be done; you'll spend more time teaching the computer how to route certain parts than how long it'd take you to do yourself. Now if you have already routed your power lines and CPU and all that, and all you have left is 250 lines from shift registers than lead to 250 LEDs, then you're in autorouter territory. And even a fairly dumb autorouter will do well in thus circumstances. Routing CPUs to PCI express slots and memory slots is another example where autorouters shine, although those autorouters have 8 or more PCB layers to work with and undoubtedly that's not what you're planning to do.
Oh, and also, autorouting on even just a 4 layer board is much better than a 2 layer board. Once you have four layers, fairly trivial strategies like "Layer 1 is signals running horizontal, Layer 2 is ground, Layer 3 is power, Layer 4 is signals running vertical" work quite nicely.
the definition of the problem is very simple : you are trying to solve the 'travelling salesman problem' , ...
Minimal Steiner tree is a closer problem because you are allowed to introduce junction points. And then you have the obstacles, dependencies between nets (one blocking the other) and multi layers.
It was shown that the hard part of routing is finding the topology of the traces (how they go in relation to pads, obstacles and to each other). Once this is determined, assigning exact x/y locations to the traces can be done algorithmically fast in polynomial time. IIRC Altium is using a topological router.
This guy designed a topological router
http://www.ssalewski.de/Router.html.en . You can see how he cares only on the topological aspects of the routing, representing the wires as rubber bands.
Arduino Blinky is much more fun IMO.
Autorouting is not the travelling salesman problem at all, because the complexity in TSP is in finding the one and only optimal solution. Meanwhile, autorouters just have to find a solution that conforms to certain geometric constraints (tracks mustn't intersect), a problem which TSP isn't concerned with at all. TSP is really hard with 2000 points, right? I can write you an autorouter right now that can instantly connect 2000 points (all on the same net) on a PCB right now easily. TSP is one continuous, unbranching path. Autorouters are allowed to branch.
So no, there's basically nothing at all in common between TSP and autorouting. TSP doesn't even operate in a cartesian space, it's on a graph.
The misapprehension about TSP aside, autorouters need a lot of careful training before they can be useful -- "these are power rails, they should be short and thick". "This chip should have no signal lines running under it". "These are delicate analog signal traces that should be kept far away from the switching power supply". "The ground plane shouldn't be interrupted unnecessarily". It's very hard a) for the user to teach the autorouter all this, and b) for the autorouter to be able to take this all into account. Just the UI for the human-machine interaction there is a pain. It's one of those really ill-defined problems that benefits from man-years of hacky little adjustments and special cases and painstaking, expensive development. And even when an autorouter is done well, it requires a great deal of user configuration to actually work well. Which is why completely autorouting a board from scratch should never be done; you'll spend more time teaching the computer how to route certain parts than how long it'd take you to do yourself. Now if you have already routed your power lines and CPU and all that, and all you have left is 250 lines from shift registers than lead to 250 LEDs, then you're in autorouter territory. And even a fairly dumb autorouter will do well in thus circumstances. Routing CPUs to PCI express slots and memory slots is another example where autorouters shine, although those autorouters have 8 or more PCB layers to work with and undoubtedly that's not what you're planning to do.
Oh, and also, autorouting on even just a 4 layer board is much better than a 2 layer board. Once you have four layers, fairly trivial strategies like "Layer 1 is signals running horizontal, Layer 2 is ground, Layer 3 is power, Layer 4 is signals running vertical" work quite nicely.
Couldn't a PCB autorouter be collectively trained and learn in some way plus having a component library with useful metadata (this chip needs specific routing, take care of power lines, these RF stuff must be fine in certain way...), then submit that training data somewhere and improve it based on "big data"? And even make it learn from manual routing.
I know it's an insane idea and just thinked about OCR and speech recognition systems. Maybe some kind of weak AI could be applied here?
I'm a total layman, just speculating and very curious about why it's so difficult.
You should have a look at a PCB netlist file... it's just "there's a chip called U1, it has package TQFP-48, and pin 1 connects to the net called "Net-U1-1", pin 2 connects to the net "+5V", etc etc. Obviously in a machine-readable text-format, but that's the gist of it. An AI can't glean anything from that (aside from making assumptions based on the name of the nets, which is just a horrible idea), even a human would have to either make the name-based assumption, or reverse-engineer the original schematic to understand what net is actually doing (complete with reading component datasheets). You think an AI can handle this when 99.9% of humans aren't able to?
I'm not sure if you're saying that you're a layman with respect to software engineering, or PCB layout as well. But if you're a software layman, this doesn't need to be a mystery to you. I'd encourage you to imagine teaching another layman how to do PCB layout, since a computer is the ultimate extremely fast, pedantic, stupid layman. Try to imagine a list of written-out instructions that you could hand to a temp worker to do PCB layout. Because a computer program is just that, a written-out pile of instructions.
Regarding machine learning and AI, you perhaps appear (like many) to think that AI is some sort of magical panacea that just solves any problem. But the problems you mentioned (OCR, speech recognition) are recognition problems: take a large file (image of words, or speech audio) and output text (which has precisely one correct answer). In the case of image recognition, the successive layers in the neural net recognise progressively more complex/higher level concepts -- lines/bends, then junctions and loops, then digits. Similar for audio. PCB autorouting as a huge space of different-looking but essential equally acceptable outputs, so the solution is not unique; the output is a huge amount of data because it's a fully routed board, not some condensed text output; and it's really hard for me to imagine what the different layers of the neural net would be doing. What does the first layer of the neural net do?
One last thought: 4 year old humans can do OCR and speech recognition. They can't lay out PCBs better than autorouters. Just imagine trying to teach a 4 year old to route a PCB, and you should have a good sense of what trying to program a computer is like.
Couldn't a PCB autorouter be collectively trained and learn in some way plus having a component library with useful metadata (this chip needs specific routing, take care of power lines, these RF stuff must be fine in certain way...), then submit that training data somewhere and improve it based on "big data"? And even make it learn from manual routing.
The time you spend specifying all of the various layout constraints is better spent doing something else -- like, perhaps, doing the layout work manually.
Here's the problem I see with the whole notion of hobbyist autorouters: In order to get useful output from the autorouter, the designer needs to fully understand the design requirements and all of the specialist layout rules. This requires experience.
The hobbyist thinks that all he needs to do is just hand the netlist and the board size off to the autorouter and a high-quality board layout, better than the person can do manually, will pop out. But perhaps this hobbyist doesn't have the experience required to know what defines "high-quality board layout," so he can't properly constraint the autorouter, and the result is basically the same thing he'd get if he did it manually.
In other words, just expecting a high-quality result from the autorouter when you don't know what that means is a mistake.
I will offer the following comparison: lots of people complain about the lack of open-source FPGA synthesis and place-and-route tools. The problem domain for FPGA tools and PCB autorouters is highly similar. It's very complex work that requires disparate skills -- programming, obviously, but also a full understanding of the problem domain. The handful of people (compared to the number of skilled application programmers) who can do this work have a simple choice: a) do it as an open-source project, and maybe make a name for yourself, or b) work for Cadence or Mentor Graphics and get paid a nice salary and let someone else handle the marketing and support.
Couldn't a PCB autorouter be collectively trained and learn in some way plus having a component library with useful metadata (this chip needs specific routing, take care of power lines, these RF stuff must be fine in certain way...), then submit that training data somewhere and improve it based on "big data"? And even make it learn from manual routing.
The time you spend specifying all of the various layout constraints is better spent doing something else -- like, perhaps, doing the layout work manually.
That thought has kept me from attempting to use an autorouter with SMD boards. I think I autorouted one SMD board but I wasn't satisfied with the result. Back in the IC-in-DIP-package days I used the autorouter in Protel Autotrax a lot but it took a lot of tweaking to get useful results. And in many cases doing the last 3% of the traces and tidying up the power distribution took a lot of time as well.
The real question is will any router closed or open source ever actually prove useful. For digital stuff maybe they can do the bulk work of doing buses but still.
The real question is will any router closed or open source ever actually prove useful. For digital stuff maybe they can do the bulk work of doing buses but still.
At a previous job where some of the products were multiple-CPU processor boards, the layout gang would use specctra for the processor memory and PCI etc bus routing. Doing a couple hundred matched-length lines by hand is a royal pain in the ass. The autorouter could do it in minutes. The rest of the board was routed by hand.
Hi folks, I'm the author of
https://github.com/vygr/C-PCB.
I just wanted to do this as it was a technical challenge, I did the dsn import prog so I could test against a friends shower room controller board files
I can route his board at 2-Layers in 1 second on the default settings, although more complex settings push that time up a little. There are a lot of paramaters to control direction vectors, wire grouping, Z transition cost and so forth to play around with, as well as various distance metrics worth trying. Viewer output can be alpha'd coloured layers or a Gerber style PCB copper mask for each layer. You can view the route in realtime as it calculates or view an animation too.
It uses glfw3 lib for the viewer, but the rest is plain old c++11/14 so should be easy to build on most systems for anyone that wants to play with it.
Not had much exposure to bigger test files, and the dsn importer was done by reverse engineering the spec via just looking at the dsn files
Best regards to all.
Chris
ps. I might be slow to reply as I'm of on holiday for a while, so excuses my tardiness !
pps. Why not take a look at the prog and maybe give it a few Github stars
Thanks a lot for your reply!
I'm the guilty of making you post here, I confess it!
I think it's a good idea to make your project gain visibility, suggestions, testing and possible collaborators.
Maybe the perfect autorouter isn't possible to do, but maybe there could be an Open Source one in the future that could compete with the propietary ones.
I really hope your project becomes this one!
I'll try your project soon, as I need to learn KiCad and would like to do autorouter as a way of testing. They are easy designs, but I'll provide feedback.
Anyway....
Could anyone try C-PCB with deferent designs in terms of complexity and compare it with good quality manual routing? Maybe this could provide interesting feedback.
I'm not skilled to make a complex PCB, I'm to newbie at electronics
I use the eagle auto router on every project. I first route manually the critical nets and then let the auto router do the rest. I care about functionality, not traces aesthetics.
I use the eagle auto router on every project. I first route manually the critical nets and then let the auto router do the rest. I care about functionality, not traces aesthetics.
If you're doing, for example, an audio amp with a SMPS,
all your nets are "critical" to some extent.
I use the eagle auto router on every project. I first route manually the critical nets and then let the auto router do the rest. I care about functionality, not traces aesthetics.
If you're doing, for example, an audio amp with a SMPS, all your nets are "critical" to some extent.
I don't ;-)
Mostly MCU stuff. Roughly %25 of my nets are critical (power, crystal, USB lines, etc). I also use the auto router to evaluate component placement.
Hello.
Are there someone working on this?
Kind regards.
I don't know what it is doing, but C-PCB is unable to route my design, where freerouter has done it in a snap
(Hu? we can't direct attach DSN files? o_O)
The two images are the hand routed version in 3D view without the solder mask, I can do it better for sure, and remove the two via on the board, but I'm lazy...
Here are the results of freerouter, keeping the planes I've done manually for the routing I made by hand, the result without is better than when I don't keep them, but I'm not really fond of it. I will join the result of freerouter without the planes.
And for C-PCB, no results at all, I get nothing interesting I don't know why.
Edit: I've added the result without the planes, this one is really ugly
Hey folks, C-PCB hasn't had a huge test with various DSN files ! If fact it only had two board designs to test with and I reverse engineered the DSN format so can't say for certain that I got it correct !
However I would be interested to look at the DSN file and see why nothing happens at all if you could get a copy to me for testing ?
When you tried it did it run the test files OK before you ran your own DSN file ? Just as a sanity check.
Can you send me a copy via the Github project maybe ?
Best regards
Chris
