A new autorouter

At last, a new release of Fritzing.  Sorry it’s been such a long time since the last one–partly this is because there is no full time Fritzing staff (we all have to work for a living), and partly because I had the mistaken notion that I knew a fast way to implement an autorouter.  But let’s go straight to the before-and-after:

autorouter compared

The spiders-on-drugs image on the left is from Fritzing 0.4.3; the image on the right is from Fritzing 0.5.0, and they are each the result of autorouting the barebones arduino example.  The one on the left took 30 seconds on a 2.80 GHz dual-core laptop, the one on the right took 3  seconds (yes, on the same machine). This video might make the difference clearer:

Why should I care?

If you are still gamely reading at this point, and don’t know what an autorouter is, I commend your courage, and will now attempt a definition.  Once you’ve placed your parts and wired them up in breadboard view or schematic view, and you’re ready to make a pcb, you’re faced with a new task.  This task is to draw out or route the electrical circuit–the connections between parts–in copper on your pcb.  The orange-colored lines in the above images represent copper routes (also known as traces) on a pcb (green), where the white shapes represent the outlines of parts. Routing can be done by hand, but it can be tedious and tricky (though some people find it enjoyable, like doing a puzzle).  An autorouter is a piece of software than can do the routing task for you, and some routers are very sophisticated–able to handle millions of connections.  Fritzing’s new router is not the brightest star in the galaxy, but as you can see from the two images, the new router is not so dim a bulb as the old one.

Some background

Here are the details on the new router:

  • It's a "manhattan" router--all new traces will be drawn at 90 degree angles.  If you draw your own non-manhattan traces, the router will respect them, but you will probably make the routing job more difficult.
  • It only takes a finite (and usually short) time for the router to determine whether it can trace a path between two points (no more waiting for endless futile line-probes).
  • DRC (overlap checking) comes for free, giving clear feedback about what's overlapping, so the old crazy DRC code has been replaced.
  • There is a rudimentary rip-up-and-reroute feature, meaning that if the router can't successfully route the whole board, it will automatically try routing again with a different ordering of connector pairs.  This is usually quite speedy, and you can limit the number of retries: the router will keep the best result.
  • As before, when drawing a trace fails, the router will attempt to place a jumper.  The new router's jumper placement code is much improved over the 0.4.3 code.
  • The router does not guarantee a shortest path when routing between two points.

The new router–like the rest of Fritzing–is a work in progress. You will probably have to do some tidying up after it runs.  However, it’s already such an improvement over the previous that we decided not to wait any longer to release it. Here’s what’s still on the to-do list:

  • Placing vias in double-sided routing.
  • More intelligent rip-up-and-reroute strategy.
  • More intelligent overall routing strategy.
  • It misses some routes that it should find.
  • Some traces violate DRC.
  • Running the same autoroute twice in a row won't necessarily give the same result.

Despite the to-do list, we think you’ll be pleased.

Cheers,

  • j

PS.  For those of you interested in the technical details, the new router uses a “tiled” data-structure.  The technique was invented by John Ousterhout, and in fact Fritzing uses a modified version of the basic corner-stitching code from Ousterhout’s Magic VLSI Layout Tool. I’ve also incorporated ideas for improvements from a paper describing the Contour router and from another paper describing an ECO router.

In general, tile-routers are more complex than maze-routers, but I felt that a tile-based approach was suited to Fritzing because we don’t enforce a grid.  It was also much easier to get my head around tiles than steiner-tree approaches (see a random sample of the latter).  In theory, tile-based routers scale up better than maze routers because the number of tiles doesn’t expand so quickly as the working area increases (on the other hand, maze routers do guarantee a shortest path between connections).  You also get some freebies with tile routers: the DRC and jumper and via placement are all variations on the same underlying code.