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

Autorouter old and new

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.

10 thoughts on “A new autorouter

  1. Αποτι καταλαβαμε αφτα που εχω διβαση το Auto router πρεπη να ειναι πολι καλο

      1. Diskmedel funkar! Skura bort skiten från kedjan också så minskar slitaget på kransarna men glöm inte att smörja efteråt. Köp en bra allvädersolja som inte kladdar så mycket, lätt värt. Jag har nån vaxbaserad från Pedros, kolla hos din lokala cykelhandlare.

      2. make sure you take out time and…set up nice blog names. your blog name should have the keywords you are promoting. if you are promoting real estate, your blog name or domain name should have real estate incorporated in it, e.g realestatesecret.com.write 30 rich keyword articles per…

      3. Today, it is not take time returning to get payday loans uk multitude in your inspectionaccount. Mike John has become a well known as Financial Consultant.Borrowers could get the definition extended too also rollovers in legal proceeding of payment ailments.

  2. Στο ηλεκτρονικο σχεδιο που σχεδιαζω δεν μπορω να βρω τησ ροδελεσ κει τησ τελιεσ που ειναι κριμενεσ ?

  3. Στο ηλεκτρονικο σχεδιο που σχεδιαζω δεν μπορω να βρω τησ ροδελεσ και τησ τελιεσ που ειναι κρημενεσ ?

  4. The main objective of your web site could have vital implications for its construction, navigation structure and overall
    design, so it iss essential to be clear on this from the beginning.

Leave a Reply

Your email address will not be published. Required fields are marked *