Close
0%
0%

My Auto-Router

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

Similar projects worth following
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

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

Download

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

Preview
Download

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

Download

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

Download

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

Download

View all 11 files

  • Importing a KiCAD SPECCTRA File

    agp.cooper07/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.cooper07/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 2 project logs

Enjoy this project?

Share

Discussions

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

Does this project spark your interest?

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