Close
0%
0%

My Auto-Router

I am not that impressed with auto-routers. Why are they so bad?

agpcooperagp.cooper
Following
Liked Like project

Just one more thing

To make the experience fit your profile, pick a username and tell us what interests you.

Pick an awesome username
hackaday.io/
Your profile's URL: hackaday.io/username. Max 25 alphanumeric characters.
Pick a few interests
Projects that share your interests
People that share your interests

We found and based on your interests.

Choose more interests.

OK, I'm done! Skip
Similar projects worth following
1.6k views
13 comments
9 followers
View Gallery
What is Wrong?
=============
If you have used a PCB auto-router they are rather "flashy". They show tracks on the screen in real time! Really! Is the algorithm so slow that this is practical. And even the simplest circuit need a two sided board.
I am not convinced so I am going to do it myself and find out why it is so hard (or not).

PCB Routing

When I first looked at this a few years ago, all I could really find was the "Channel" router algorithm. It was "as plain as day" that the "normal" auto-router was based on shortest path (or some variant), but not much was published.

The Channel Router

The Channel router is certainly an interesting problem. I looked at it for routing strip-board. Here is the concept, layout your components either side of a "channel" and the Channel router will link them up. Here is my proposed strip-board layout:

Note: the ICs can be replaced with individual components.

And here a typical "channel" wiring diagram:

Note: The Channel algorithm has been modified to suit the strip-board constraint of one wire join per location (or hole).

So it is possible to auto-route strip-board efficiently (from an algorithm point of view) but it is not that elegant (visually).

It might have a niche if the parts are also auto-placed. But at that point I did not feel as if this was going to be a "useful" project to continue.

Shortest Path

The shortest path algorithm is well known and I have used it n the past to determine truck haulage paths of open pit mines (yes I was a mining consultant in a past life). Here is an example (the white traces are the proposed truck haulage paths):

Note: the scale of this problem is quite large (i.e. about 10 km across).

So okay, I have used this algorithm before! So what is so hard about auto-routing?

AlanX

ImportDSN.c

x-csrc - 7.11 kB - 07/26/2019 at 03:13

Download

ezx_graphics.pdf

Adobe Portable Document Format - 92.72 kB - 07/23/2019 at 11:05

Preview

libezx.a

x-archive - 28.44 kB - 07/23/2019 at 11:05

Download

labels.txt

plain - 181.00 bytes - 07/23/2019 at 11:05

Download

links.txt

plain - 107.00 bytes - 07/23/2019 at 11:05

Download

View all 11 files

  • Exporting KiCad DSN to Text

    agp.cooper • 12/03/2019 at 08:37 • 0 comments

    Exporting KiCad DSN to Text

    I finally got round to exporting the DSN file to some intermediate files that are easier to work with:

    • pcb.txt
    • nets.txt
    • parts.txt

    The code is rather bloated so later I will try and remove the S-Expr linked list.

    The "pcb" file looks like this (units are um):

    pcb:
    130810 -95250
    130810 -120650
    175260 -120650
    175260 -95250
    130810 -95250
    130810 -95250

     I can write some code to consider an arbitrary shape but a rectangle is good enough for now.

    The "nets":

    nets:
    C1-1 D2-1 Q1-2 R2-1 
    C1-2 D1-2 D3-2 D4-2 D5-2 R3-1 
    D1-1 D2-2 
    D3-1 J1-3 
    D4-1 J1-4 
    D5-1 J1-5 
    J1-1 R1-2 R3-2 
    J1-2 Q1-3 R1-1 
    J1-6 Q1-1 R2-2

    The nets will need to be converted into number for the router.

    And finally the "pins" or parts:

    Component  Surface/Pin           X           Y  Rot
C1               front      154940     -105410  180
                     1           0           0    0
                     2        5000           0    0
D1               front      165100     -110490  180
                     1           0           0    0
                     2        7620           0    0
D2               front      157480     -107950    0
                     1           0           0    0
                     2        7620           0    0
D3               front      139700     -107950    0
                     1           0           0    0
                     2        7620           0    0
D4               front      139700     -110490    0
                     1           0           0    0
                     2        7620           0    0
D5               front      139700     -113030    0
                     1           0           0    0
                     2        7620           0    0
J1               front      135890     -102870    0
                     1           0           0    0
                     2           0       -2540    0
                     3           0       -5080    0
                     4           0       -7620    0
                     5           0      -10160    0
                     6           0      -12700    0
Q1               front      163830     -101600   90
                     2        1270        1270   90
                     3        2540           0   90
                     1           0           0   90
R1               front      147320     -102870  180
                     1           0           0    0
                     2        7620           0    0
R2               front      157480     -105410    0
                     1           0           0    0
                     2        7620           0    0
R3               front      147320     -105410  180
                     1           0           0    0
                     2        7620           0    0

    All the pin locations need to be processed (translated and rotated).

    The next step is to build the "links" list:

    SRC    DST
  1	 7
  7	 8
  2	13
 13	22
  3	 9
  4	10
  5	11
  6	24
 24	25
 12	14
 14	19
 14	15
 15	16
 16	21
 17	18
 18	23
 18	20
 26	27

    The then build a "map":

    25 20
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  7  0  0  0  0  0 12  0 17  0  0  0  0  0 25  0  0  0  0
0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  2  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  8  0  0  0  0  0 13  0 18  0  0  0  0 22  0  0  0  0  0
0  0  0  0  3  0  0  0  0  0  0  0  0  0  0  0  0  0  0 23  0  0  0  0  0
0  0  0  0  0  0  9  0  0  0  0  0 14  0 19  0  0  0  0 24  0  0  0  0  0
0  0  0  0  4  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0 10  0  0  0  0  0 15  0 20  0  0  0  0  0 26  0  0  0  0
0  0  0  0  5  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0 11  0  0  0  0  0 16  0 21  0  0  0  0  0 27  0  0  0  0
0  0  0  0  6  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

    AlanX

  • Importing a KiCAD SPECCTRA File

    agp.cooper • 07/24/2019 at 10:25 • 0 comments

    The KiCAD SPECCTRA File

    KiCAD can export PCBs as "dsn" or SPECCTRA files. These file are ASCII and use Symbolic Expression format (often called  S-Expr format).  The SPECCTA specification is quite complex but for this application I only need the Board Area and the Pin locations.

    I have modified code by https://github.com/benthepoet/c-sexpr-parser to read "dsn" format and then write it out again. As the rewritten "dsn" file was readable I assume that the code is correct.

    Here is the modified "sexpr.h" and "sexpr.c" files:And finally my code to read/write the "dsn" file:

    enum SNodeType {
  LIST,
  STRING,
  SYMBOL,
  INTEGER,
  FLOAT
};

struct SNode {
  struct SNode *next;
  enum SNodeType type;
  union {
    struct SNode *list;
    char *value;
  };
};

struct SNode *snode_parse(FILE *fp);
void snode_free(struct SNode *node);
    #include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sexpr.h"
#define BUFFER_MAX 511

static char quoteChar='"';

int is_float(char *str) {
  char *ptr=NULL;
  strtod(str,&ptr);
  return !(*ptr);
}

int is_integer(char *str) {
  char *ptr=NULL;
  strtol(str,&ptr,10);
  return !(*ptr);
}

int is_lst_term(int c) {
  return ((c==EOF)||(isspace(c))||(c=='(')||(c ==')'));
}

int is_str_term(int c) {
  return ((c==EOF)||(c=='"'));
}

char *read_value(FILE *fp,int *c,int (*is_term)(int)) {
  int len=0;
  char buffer[BUFFER_MAX+1];

  while ((!is_term(*c=fgetc(fp)))&&(len<BUFFER_MAX)) {
    buffer[len]=(char)*c;
    len++;
  }
  buffer[len]='\0';
  char *str=malloc((unsigned int)(len+1)*sizeof(char));
  return strcpy(str,buffer);
}

// Recursively parse an s-expression from a file stream
struct SNode *snode_parse(FILE *fp) {
  // Using a linked list, nodes are appended to the list tail until we
  // reach a list terminator at which point we return the list head.
  struct SNode *tail=NULL,*head=NULL;
  int c;
  char lastSymbol[BUFFER_MAX+1]="";

  while ((c=fgetc(fp))!=EOF) {
    struct SNode *node=NULL;

    if (c==')') {
      // Terminate list recursion
      break;
    } else if (c=='(') {
      // Begin list recursion
      node=malloc(sizeof(struct SNode));
      node->type=LIST;
      node->list=snode_parse(fp);
    } else if ((strcmp(lastSymbol,"string_quote")==0)&&(!isspace(c))) {
      // Read symbol
      ungetc(c,fp);
      node=malloc(sizeof(struct SNode));
      node->value=read_value(fp,&c,&is_lst_term);
      // Put the terminator back
      ungetc(c,fp);
      node->type=SYMBOL;
      strcpy(lastSymbol,node->value);
      quoteChar=lastSymbol[0];
    } else if (c=='"') {
      node=malloc(sizeof(struct SNode));
      node->type=STRING;
      node->value=read_value(fp,&c,&is_str_term);
    } else if (!isspace(c)) {
      // Read a float, integer, or symbol
      ungetc(c,fp);
      node=malloc(sizeof(struct SNode));
      node->value=read_value(fp,&c,&is_lst_term);
      // Put the terminator back
      ungetc(c,fp);
      if (is_integer(node->value)) {
        node->type=INTEGER;
      } else if (is_float(node->value)) {
        node->type=FLOAT;
      } else {
        node->type=SYMBOL;
        strcpy(lastSymbol,node->value);
      }
    }

    if (node!=NULL) {
      // Terminate the node
      node->next=NULL;
      if (head==NULL) {
        // Initialize the list head
        head=tail=node;
      } else {
        // Append the node to the list tail
        tail=tail->next=node;
      }
    }
  }

  return head;
}

// Recursively free memory allocated by a node
void snode_free(struct SNode *node) {
  while (node!=NULL) {
    struct SNode *tmp=node;

    if (node->type==LIST) {
      snode_free(node->list);
    } else {
      // Free current value
      free(node->value);
      node->value=NULL;
    }
    node=node->next;
    // Free current node
    free(tmp);
    tmp=NULL;
  }
}

    And my code to read the "dsn" file and then rewrite (export) it:

    #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "sexpr.h"

void run_tests(struct SNode *node);

int main(int argc, char *argv[]) {
  // Unused parameters
  (void)argc;
  (void)argv;

  FILE *fp=fopen("DTL.dsn","r");
  struct SNode *node=snode_parse(fp);
  fclose(fp);

  run_tests(node);

  snode_free(node);

  return 0;
}

void run_tests(struct SNode *node) {
  int depth=...
    Read more »

  • First Steps

    agp.cooper • 07/20/2019 at 02:23 • 0 comments

    First Steps

    There is a lot of work setting up the interface between the schematic capture and PCB layout applications and the auto-routing applications. So I will just read in a simple text files to begin.

    The Schematic

    One of my first PCB schematics was a DTL (Diode Transistor Logic) three input NAND gate. Here is a KiCAD version.

    First the KiCAD schematic:

    And the KiCAD PCB:

    Now I have tried to get a single sided PCB version of this design (in Eagle and EasyEDA) but it is surprisingly difficult to do. KiCAD does not even offer the option. In the end I had to hand route a design (okay it has nine copies):

    With a bit of imagination you should see the KiCAD PCB here (map.txt):

    And the links list:

    SRC DST
 1    7
 7    8
 2   13
13   22
 3    9
 4   10
 5   11
 6   24
24   25
12   14
14   19
14   15
15   16
16   21
17   18
18   23
18   20
26   27

    After a Day of Coding

    Here is a series of images as I debugged and got the penalty function working.

    Well its just about getting something on screen to look at!

    I want to penalise paths that get too close to the pins (thus the small red dots):

    Note: The red tracks failed to find a legal path. A diagonal path between tracks was consider illegal.

    Here is a working case:

    Note: The links are exactly honoured and thus the ugly links.

    Finally with a pseudo-Steiner Tree modification gives a pretty reasonable result:

    So for a single side PCB I have a result that works (for the small example).

    So how is that, all of the above in less than 600 lines of code!

    A lot more to do, add multi-able layers and back-tracking when the algorithm fails.

    Update

    Added some code to randomly swap around the links to see if I can improve the result.

    I gave the router 1 second, it looked as 2083 options and reduced the penalty from 682 to 582:


    I have been looking at the passes that failed to determine if there is an easy heuristic I could apply. Even in the above image the I can see faults that could be fixed that would improve the success rate.

    A couple of papers suggested:

    • Sorting the nest by complexity (i.e. number of bounding square interactions) or at least net length.
    • And if that fails, then route the conflicted net on the next layer.

    Currently I completely randomise the links for a run and run a many as I can in one second.

    Here is an example where I use the above approach (i.e. a single run) but include a congestion penalty:

    You can see that the congestion penalty has moved the tracks away from the pins (and other tracks) leaving space for later tracks. This in my mind is a pretty good result (for a single run). Without the congestion penalty you get:



    Code

    I have posted the code for the above.

    Paper by Eric Rosenberg on Iterative Routers

    I found a paper by Eric Rosenberg that describes an iterative method for improving the router performance. Here is a simplified version of his algorithm:

    • There is no prioritisation of the nets (or links).
    • Initially with the supply/demand router, all nets are routed without regard to conflicts and can share the grid node (or cell). After each iteration, the conflicted cells are given a penalty with the "hope" that it will resolve the conflict.
    • With each iteration the penalties of the remaining conflicted cell are increased.
    • Eric Rosenberg proposes that if a solution cannot be found after a number of iterations, then the conflicting nets are ripped up and rerouted....
    Read more »

View all 3 project logs

Enjoy this project?

Share

Discussions

agp.cooper wrote 11/28/2019 at 03:00 • point

Hi Ken,

Added support for image rotation. So I have something useful now. Next would be to export the nets and the board outline.

Looking at my code, it is not great but it is functional. I read the S-Expr name and depth and what ever list item number I need. I join the fragments with associative arrays. Final I export the associative arrays for further processing. It is hard coded so I just need to know all the possible cases.

A LISP or Prolog programmer would probable only need a few 10s of lines of code to do the same job.

I have other things to do today, so I will have another look tomorrow.

---

I have designed a new version of my CP/M machine. This time with external timers and a UART. I have upgraded the flash drives from 32k to 256k. The only problem is I have only been able to auto-route a 4 layer board. 

AlanX

  Are you sure? yes | no

agp.cooper wrote 11/27/2019 at 13:41 • point

Hi Ken,

You are right I have to think about the data structures I am using.
I was looking at the DSN file and I noticed that the rotation operation is done two different ways. One is position inside a list like this:
  (place R1 147320 -102870 front 180 (PN 750))
but the other is an optional "insert" like this:
  (pin Round[A]Pad_1000_um (rotate 90) 2 1270 1270)

I had another look at the code and it does appear that all I need to do is add the image rotation to the pin line and I am done (assuming no more rotations are inserted elsewhere). Then I can reparse the output to make the rotations.
After that its just parsing the nets and the board outline (I think). Its a crappy process but it should work in practice.

I will have a go tomorrow.

AlanX

  Are you sure? yes | no

agp.cooper wrote 11/27/2019 at 12:31 • point

Yes there are libraries that can read S-Exprs, but the issue is the "query" engine.
Or at least that is what I think the problem is? Perhaps it is in my head!

I think I have to write a program/script (for the S-Expr library) to interpret the S-Exprs. The S-Exprs are just a way of storing data, I need to get it into a flat table so my auto-router can read it.

LISP can do it but the LISP language set is too big for me to learn for just one application.

I have had partial success with my C code but the code is not very elegant.
I am using associative array to join the S-Expressions but S-Expr structure is not fixed. I have stopped working on it as I don't no how best to proceed.

For example, rotation information can be found at different depths of the S-Expr tree and on different "branches" of the tree. To date I have assumed the same information will be found at the same depth and on the same branch of the tree. Thus I have been cheated so far in assuming the structure is fixed!

Really I need to scan the tree (bottom up) and execute the operations as I encounter them but this requires a recursive parser. Even then I need some data structure that ends up being a table.

Really I am just lazy to go there!

AlanX

  Are you sure? yes | no

Ken Yap wrote 11/27/2019 at 12:57 • point

Perhaps you need to step back and work out the most suitable data structure(s) inside your program for objects being described and the operations desired, which may or may not be a table. S-exprs are just a serialisation format.

  Are you sure? yes | no

Ken Yap wrote 11/26/2019 at 08:10 • point

Just saw from a comment in the Kicad forum that VeeCAD was made open source a few months back. It accepts a netlist, presumably that from Kicad/eeschema will do. But it's written in Delphi Object Pascal for Windows. https://veecad.com/

  Are you sure? yes | no

agp.cooper wrote 11/27/2019 at 07:07 • point

I can read in the the net-list and decode it (i.e. joining the various tables together). It is just a headache decoding it. S-Exps are just too fluid (no fun at all). For example you can rotate a part in a number of different places (almost anywhere!).

If I could code in LISP I think it would be much easier.

I will get back to it when the motivation returns!

AlanX

  Are you sure? yes | no

Ken Yap wrote 11/27/2019 at 08:24 • point

Surely there are libraries to read S-exprs?

  Are you sure? yes | no

Ken Yap wrote 08/22/2019 at 23:39 • point

Came across this actively developed tool browsing the Kicad forums. Appears to be interactive rather than batch but claims to handle perfboard amongst others. Haven't taken a closer look since I'm not enamored of perfboard.

https://sourceforge.net/projects/veroroute/

  Are you sure? yes | no

agp.cooper wrote 08/24/2019 at 00:09 • point

Now that looks interesting. I feel like a druggie that has gone "cold-turkey" looking at his next hit. I swore off vero-board a while back.

  Are you sure? yes | no

Ken Yap wrote 07/21/2019 at 15:35 • point

Incidentally to do 1 layer boards in Kicad just make one of the layers totally keep-out area. But fabs charge the same for 1 as for 2. Only people who do them at home work with 1 layer. 2 layer is possible at home with good registration of the photomask. In my youth I worked for an engineering firm that did double sided boards with photoresist with a two registered negatives in a perspex frame.

Also you don't have to let freeRouting run until it can't optimise any more. You can stop it anytime you think the results are good enough. The initial routing is actually quite fast, it's the backtracking to try new routes to shorten the total path length that takes time. I think it's only showing you the improvements accepted at each stage, there are many tries that are rejected and not displayed. So the interactive display may not be eating as much time as it looks.

  Are you sure? yes | no

agp.cooper wrote 07/22/2019 at 02:17 • point

Okay, that nice to know with regard to single layer boards. Single sided boards were somewhat a historical interest when I did PCB etching. A while back I was doing PCB isolation from PCB images. This works best with single sided boards as you don't want feed through holes for components (too hard to solder both sides of the component lead). The problem with PCB isolation is that the isolation gap is very small and with failing eye-sight, bridges are a pain. Having said that these guys have worked it out:

https://www.youtube.com/watch?v=9DhPwtCZ9u4


I think much of my frustration was with auto-routing was with the current EasyEDA and the past Eagle routers. They really struggled to find any solution.

Anyway, I have been reading a paper by "Eric Rosenberg" that describes the "supply/demand" iterative router that rather appeals to me. He lets the tracks go (initially) anywhere they want. For any cell/grid with a conflict the penalty is increased for the cell/grid and routing repeated.

AlanX

  Are you sure? yes | no

agp.cooper wrote 07/21/2019 at 15:12 • point

Yes agree.

I would have said the same with regard to 2 layer boards but after looking at failed routing attempts, the problem is "congestion", the "pin" is a small target and gets cut off or blocked.

This is the reason for the pin area penalty. It makes the track "go around" the pins leaving access.

I think the next step is look at rip-up and re-route.

The code in not very long, about 600 lines, so I will put it up before I start the Specctra interpreter.

AlanX

  Are you sure? yes | no

Ken Yap wrote 07/20/2019 at 03:22 • point

I suspect it's a variant of the traveling salesman problem so NP-complete in the worst case. Might get decent results with heuristics.

The other hunch I have is that it's always possible to find a solution in 2 layers provided there is enough space for vias.

  Are you sure? yes | no

Similar Projects

An ST-Link clone has a powerful MCU, nice enclosure and useful connectors to repurpose it for quite some projects.
Project Owner Contributor

ST-Link clone repurposing

gertuxgertux

Managing resistors is a chore. Well, with the Resistorganizer, you can just jam your loose resistors into a breadboard and be done with it.
Project Owner Contributor

The Resistorganizer

mikeMike

Building a smart underfloor heater controller
Project Owner Contributor

Smart Underfloor Heater Retrofit

floFlo

Electronic “paper crane”
Project Owner Contributor

Orizuru

tauno-erikTauno Erik

Does this project spark your interest?

Become a member to follow this project and never miss any updates

Going up?

About Us Contact Hackaday.io Give Feedback Terms of Use Privacy Policy Hackaday API

© 2025 Hackaday

Yes, delete it Cancel

Report project as inappropriate

You are about to report the project "My Auto-Router", please tell us the reason.

Send message

Your application has been submitted.

Remove Member

Are you sure you want to remove yourself as a member for this project?

Project owner will be notified upon removal.