home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 1 / HamRadio.cdr / tech / pcbsrcs2 / astar.c < prev    next >
C/C++ Source or Header  |  1991-02-07  |  20KB  |  579 lines
  1. /*
  2. ** printed circuit board autorouter, Copyright (C) Randy Nevin 1989.
  3. **
  4. ** you may give this software to anyone, make as many copies as you
  5. ** like, and post it on public computer bulletin boards and file
  6. ** servers. you may not sell it or charge any fee for distribution
  7. ** (except for media and postage), remove this comment or the
  8. ** copyright notice from the code, or claim that you wrote this code
  9. ** or anything derived from it.
  10. **
  11. ** the author's address is: Randy Nevin, 1731 211th PL NE, Redmond,
  12. ** WA 98053. this code is available directly from the author; just
  13. ** send a floppy and a self-addressed floppy mailer with sufficient
  14. ** postage. however, you should first attempt to get a copy of this
  15. ** software package from the Dr. Dobb's Journal BBS.
  16. */
  17.  
  18. /* the low-order bit indicates a hole */
  19. #define HOLE         0x00000001L /* a conducting hole */
  20.  
  21. /* traces radiating outward from a hole to a side or corner */
  22. #define HOLE_NORTH     0x00000002L /* upward             */
  23. #define HOLE_NORTHEAST     0x00000004L /* upward and right   */
  24. #define HOLE_EAST     0x00000008L /* to the right       */
  25. #define HOLE_SOUTHEAST     0x00000010L /* downward and right */
  26. #define HOLE_SOUTH     0x00000020L /* downward           */
  27. #define HOLE_SOUTHWEST     0x00000040L /* downward and left  */
  28. #define HOLE_WEST     0x00000080L /* to the left        */
  29. #define HOLE_NORTHWEST     0x00000100L /* upward and left    */
  30.  
  31. /* straight lines through the center */
  32. #define LINE_HORIZONTAL     0x00000002L /* left-to-right line */
  33. #define LINE_VERTICAL     0x00000004L /* top-to-bottom line */
  34.  
  35. /* lines cutting across a corner, connecting adjacent sides */
  36. #define CORNER_NORTHEAST 0x00000008L /* upper right corner */
  37. #define CORNER_SOUTHEAST 0x00000010L /* lower right corner */
  38. #define CORNER_SOUTHWEST 0x00000020L /* lower left corner  */
  39. #define CORNER_NORTHWEST 0x00000040L /* upper left corner  */
  40.  
  41. /* diagonal lines through the center */
  42. #define DIAG_NEtoSW     0x00000080L /* northeast to southwest */
  43. #define DIAG_SEtoNW     0x00000100L /* southeast to northwest */
  44.  
  45. /* 135 degree angle side-to-far-corner lines */
  46. #define BENT_NtoSE     0x00000200L /* north to southeast */
  47. #define BENT_NtoSW     0x00000400L /* north to southwest */
  48. #define BENT_EtoSW     0x00000800L /* east to southwest  */
  49. #define BENT_EtoNW     0x00001000L /* east to northwest  */
  50. #define BENT_StoNW     0x00002000L /* south to northwest */
  51. #define BENT_StoNE     0x00004000L /* south to northeast */
  52. #define BENT_WtoNE     0x00008000L /* west to northeast  */
  53. #define BENT_WtoSE     0x00010000L /* west to southeast  */
  54.  
  55. /* 90 degree corner-to-adjacent-corner lines */
  56. #define ANGLE_NEtoSE     0x00020000L /* northeast to southeast */
  57. #define ANGLE_SEtoSW     0x00040000L /* southeast to southwest */
  58. #define ANGLE_SWtoNW     0x00080000L /* southwest to northwest */
  59. #define ANGLE_NWtoNE     0x00100000L /* northwest to northeast */
  60.  
  61. /* 45 degree angle side-to-near-corner lines */
  62. #define SHARP_NtoNE     0x00200000L /* north to northeast */
  63. #define SHARP_EtoNE     0x00400000L /* east to northeast  */
  64. #define SHARP_EtoSE     0x00800000L /* east to southeast  */
  65. #define SHARP_StoSE     0x01000000L /* south to southeast */
  66. #define SHARP_StoSW     0x02000000L /* south to southwest */
  67. #define SHARP_WtoSW     0x04000000L /* west to southwest  */
  68. #define SHARP_WtoNW     0x08000000L /* west to northwest  */
  69. #define SHARP_NtoNW     0x10000000L /* north to northwest */
  70.  
  71. /* directions the cell can be reached from (point to previous cell) */
  72. #define FROM_NORTH    1
  73. #define FROM_NORTHEAST    2
  74. #define FROM_EAST    3
  75. #define FROM_SOUTHEAST    4
  76. #define FROM_SOUTH    5
  77. #define FROM_SOUTHWEST    6
  78. #define FROM_WEST    7
  79. #define FROM_NORTHWEST    8
  80. #define FROM_OTHERSIDE    9
  81.  
  82. #define    TOP    0
  83. #define BOTTOM    1
  84. #define EMPTY    0
  85. #define ILLEGAL    -1
  86.  
  87. /* visit neighboring cells in this order
  88. ** (where [9] is on the other side):
  89. **
  90. **    +---+---+---+
  91. **    | 1 | 2 | 3 |
  92. **    +---+---+---+
  93. **    | 4 |[9]| 5 |
  94. **    +---+---+---+
  95. **    | 6 | 7 | 8 |
  96. **    +---+---+---+
  97. */
  98.  
  99. static int delta[8][2] = { /* for visiting neighbors on the same side */
  100.      {  1, -1 }, /* northwest    */
  101.      {  1,  0 }, /* north        */
  102.      {  1,  1 }, /* northeast    */
  103.      {  0, -1 }, /* west        */
  104.      {  0,  1 }, /* east        */
  105.      { -1, -1 }, /* southwest    */
  106.      { -1,  0 }, /* south        */
  107.      { -1,  1 }  /* southeast    */
  108.     };
  109.  
  110. static int ndir[8] = { /* for building paths back to source */
  111.      FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
  112.      FROM_EAST,                  FROM_WEST,
  113.      FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
  114.     };
  115.  
  116. /* blocking masks for neighboring cells */
  117. #define BLOCK_NORTHEAST    ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
  118.             | ANGLE_NEtoSE | ANGLE_NWtoNE \
  119.             | SHARP_NtoNE | SHARP_EtoNE )
  120. #define BLOCK_SOUTHEAST    ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  121.             | ANGLE_NEtoSE | ANGLE_SEtoSW \
  122.             | SHARP_EtoSE | SHARP_StoSE )
  123. #define BLOCK_SOUTHWEST    ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  124.             | ANGLE_SEtoSW | ANGLE_SWtoNW \
  125.             | SHARP_StoSW | SHARP_WtoSW )
  126. #define BLOCK_NORTHWEST    ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  127.             | ANGLE_SWtoNW | ANGLE_NWtoNE \
  128.             | SHARP_WtoNW | SHARP_NtoNW )
  129.  
  130. struct block {
  131.     int r1, c1;  long b1, h1;
  132.     int r2, c2;  long b2, h2;
  133.     };
  134.  
  135. static struct block blocking[8] = { /* blocking masks */
  136.      {  0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  137.         1,  0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
  138.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  139.      {  1,  0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  140.         0,  1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  141.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  142.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  143.      {  0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  144.        -1,  0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  145.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  146.      { -1,  0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  147.         0,  1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
  148.     };
  149.  
  150. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  151.      { 1, 1, 1, 1, 1, 1, 1, 1 },
  152.      { 0, 0, 0, 0, 1, 0, 1, 0 },
  153.      { 0, 0, 0, 1, 0, 0, 1, 0 },
  154.      { 0, 1, 0, 0, 1, 0, 0, 0 },
  155.      { 0, 1, 0, 1, 0, 0, 0, 0 }
  156.     };
  157.  
  158. static long newmask[5][8] = { /* patterns to mask in neighbor cells */
  159.      { 0, 0, 0, 0, 0, 0, 0, 0 },
  160.      { 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
  161.        CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  162.      { 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
  163.        CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  164.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
  165.        CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
  166.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
  167.        CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
  168.     };
  169.  
  170. /* board dimensions */
  171. extern int Nrows;
  172. extern int Ncols;
  173.  
  174. void Solve () { /* route all traces */
  175.     int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
  176.     register int i;
  177.     char far *n1;
  178.     char far *n2;
  179.     long curcell, newcell, buddy;
  180.     int newdist, olddir, success, self;
  181.  
  182.     /* go until no more work to do */
  183.     for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
  184.             GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
  185.         if (r1 == r2 && c1 == c2) /* already routed */
  186.             continue;
  187.         success = 0;
  188.         InitQueue(); /* initialize the search queue */
  189.         /* get rough estimate of trace distance */
  190.         a = GetApxDist( r1, c1, r2, c2 );
  191.         SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  192.         SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  193.         /* search until success or we exhaust all possibilities */
  194.         for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  195.             GetQueue( &r, &c, &s, &d, &a )) {
  196.             if (r == r2 && c == c2) { /* success! */
  197.                 /* lay traces */
  198.                 Retrace( r1, c1, r2, c2, s );
  199.                 success++;
  200.                 break;
  201.                 }
  202.             curcell = GetCell( r, c, s );
  203.             if (curcell & CORNER_NORTHWEST)
  204.                 self = 1;
  205.             else if (curcell & CORNER_NORTHEAST)
  206.                 self = 2;
  207.             else if (curcell & CORNER_SOUTHWEST)
  208.                 self = 3;
  209.             else if (curcell & CORNER_SOUTHEAST)
  210.                 self = 4;
  211.             else
  212.                 self = 0;
  213.             /* consider neighbors */
  214.             for (i = 0; i < 8; i++) {
  215.                 /* check self-block */
  216.                 if (!selfok[self][i])
  217.                     continue;
  218.                 if ((nr = r+delta[i][0]) < 0
  219.                     || nr >= Nrows
  220.                     || (nc = c+delta[i][1]) < 0
  221.                     || nc >= Ncols)
  222.                     /* off the edge */
  223.                     continue;
  224.                 newcell = GetCell( nr, nc, s );
  225.                 /* check for non-target hole */
  226.                 if (newcell & HOLE) {
  227.                     if (nr != r2 || nc != c2)
  228.                         continue;
  229.                     }
  230.                 else {
  231.                     newcell &= ~(newmask[self][i]);
  232.                     /* check for traces */
  233.                     if (newcell)
  234.                         continue;
  235.                     }
  236.                 /* check blocking on corner neighbors */
  237.                 if (delta[i][0] && delta[i][1]) {
  238.                     /* check first buddy */
  239.                     buddy = GetCell( r+blocking[i].r1,
  240.                         c+blocking[i].c1, s );
  241.                     if (buddy & HOLE) {
  242.                         if (buddy & (blocking[i].h1))
  243.                             continue;
  244.                         }
  245.                     else if (buddy & (blocking[i].b1))
  246.                         continue;
  247.                     /* check second buddy */
  248.                     buddy = GetCell( r+blocking[i].r2,
  249.                         c+blocking[i].c2, s );
  250.                     if (buddy & HOLE) {
  251.                         if (buddy & (blocking[i].h2))
  252.                             continue;
  253.                         }
  254.                     else if (buddy & (blocking[i].b2))
  255.                         continue;
  256.                     }
  257.                 olddir = GetDir( r, c, s );
  258.                 newdist = d+CalcDist( ndir[i], olddir,
  259.                     (olddir == FROM_OTHERSIDE)
  260.                     ? GetDir( r, c, 1-s ) : 0 );
  261.                 /* if not visited yet, add it to queue */
  262.                 if (!GetDir( nr, nc, s )) {
  263.                     SetDir( nr, nc, s, ndir[i] );
  264.                     SetDist( nr, nc, s, newdist );
  265.                     SetQueue( nr, nc, s, newdist,
  266.                         GetApxDist( nr, nc, r2, c2 ),
  267.                         r2, c2 );
  268.                     }
  269.                 /* we might have found a better path */
  270.                 else if (newdist < GetDist( nr, nc, s )) {
  271.                     SetDir( nr, nc, s, ndir[i] );
  272.                     SetDist( nr, nc, s, newdist );
  273.                     ReSetQueue( nr, nc, s, newdist,
  274.                         GetApxDist( nr, nc, r2, c2 ),
  275.                         r2, c2 );
  276.                     }
  277.                 }
  278.             /* consider other side of board */
  279.             /* check for holes or traces on other side */
  280.             if (newcell = GetCell( r, c, 1-s ))
  281.                 continue;
  282.             skip = 0;
  283.             /* check for nearby holes */
  284.             for (i = 0; i < 8; i++) {
  285.                 if ((nr = r+delta[i][0]) < 0
  286.                     || nr >= Nrows
  287.                     || (nc = c+delta[i][1]) < 0
  288.                     || nc >= Ncols)
  289.                     /* off the edge */
  290.                     continue;
  291.                 if (GetCell( nr, nc, s ) & HOLE) {
  292.                     /* neighboring hole */
  293.                     skip = 1;
  294.                     break;
  295.                     }
  296.                 }
  297.             if (skip) /* neighboring hole? */
  298.                 continue; /* yes, can't drill one here */
  299.             olddir = GetDir( r, c, s );
  300.             newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
  301.                 (olddir == FROM_OTHERSIDE)
  302.                 ? GetDir( r, c, 1-s ) : 0 );
  303.             /* if not visited yet, add it to queue */
  304.             if (!GetDir( r, c, 1-s )) {
  305.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  306.                 SetDist( r, c, 1-s, newdist );
  307.                 SetQueue( r, c, 1-s, newdist,
  308.                     a, r2, c2 );
  309.                 }
  310.             /* we might have found a better path */
  311.             else if (newdist < GetDist( r, c, 1-s )) {
  312.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  313.                 SetDist( r, c, 1-s, newdist );
  314.                 ReSetQueue( r, c, 1-s, newdist,
  315.                     a, r2, c2 );
  316.                 }
  317.             }
  318.         if (!success)
  319.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  320.         /* clear direction flags */
  321.         for (r = 0; r < Nrows; r++) {
  322.             for (c = 0; c < Ncols; c++) {
  323.                 SetDir( r, c, TOP, EMPTY );
  324.                 SetDir( r, c, BOTTOM, EMPTY );
  325.                 }
  326.             }
  327.         }
  328.     }
  329.  
  330. /* this table drives the retracing phase */
  331. static long bit[8][9] = { /* OT=Otherside */
  332.      /* N, NE, E, SE, S, SW, W, NW, OT */
  333. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE,
  334.        0, SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW,
  335.        (HOLE | HOLE_SOUTH) },
  336. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW,
  337.        SHARP_StoSW, 0, SHARP_WtoSW, ANGLE_SWtoNW,
  338.        (HOLE | HOLE_SOUTHWEST) },
  339. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  340.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW,
  341.        (HOLE | HOLE_WEST) },
  342. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW,
  343.        BENT_StoNW, ANGLE_SWtoNW, SHARP_WtoNW, 0,
  344.        (HOLE | HOLE_NORTHWEST) },
  345. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE,
  346.        LINE_VERTICAL, BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW,
  347.        (HOLE | HOLE_NORTH) },
  348. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE,
  349.        DIAG_NEtoSW, BENT_WtoNE, ANGLE_NWtoNE,
  350.        (HOLE | HOLE_NORTHEAST) },
  351. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE,
  352.        CORNER_SOUTHEAST, BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW,
  353.        (HOLE | HOLE_EAST) },
  354. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  355.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW,
  356.        (HOLE | HOLE_SOUTHEAST) }
  357.     };
  358.  
  359. void Retrace ( rr1, cc1, rr2, cc2, s )
  360.     /* work from target back to source, laying down the trace */
  361.     int rr1, cc1, rr2, cc2, s; /* start on side s */
  362.     {
  363.     int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  364.     register int x, y;
  365.     long b;
  366.  
  367.     r1 = rr2;
  368.     c1 = cc2;
  369.     s1 = s;
  370.     r0 = c0 = s0 = ILLEGAL;
  371.     do {
  372.         /* find where we came from to get here */
  373.         switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  374.         case FROM_NORTH:    r2++;        break;
  375.         case FROM_EAST:            c2++;    break;
  376.         case FROM_SOUTH:    r2--;        break;
  377.         case FROM_WEST:            c2--;    break;
  378.         case FROM_NORTHEAST:    r2++;    c2++;    break;
  379.         case FROM_SOUTHEAST:    r2--;    c2++;    break;
  380.         case FROM_SOUTHWEST:    r2--;    c2--;    break;
  381.         case FROM_NORTHWEST:    r2++;    c2--;    break;
  382.         case FROM_OTHERSIDE:    s2 = 1-s2;    break;
  383.         default:
  384.             fprintf( stderr, "internal error\n" );
  385.             exit( -1 );
  386.             break;
  387.             }
  388.         if (r0 != ILLEGAL)
  389.             y = GetDir( r0, c0, s0 );
  390.         /* see if target or hole */
  391.         if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  392.             switch (x) {
  393.             case FROM_NORTH:
  394.               OrCell( r1, c1, s1, HOLE_NORTH );  break;
  395.             case FROM_EAST:
  396.               OrCell( r1, c1, s1, HOLE_EAST );  break;
  397.             case FROM_SOUTH:
  398.               OrCell( r1, c1, s1, HOLE_SOUTH );  break;
  399.             case FROM_WEST:
  400.               OrCell( r1, c1, s1, HOLE_WEST );  break;
  401.             case FROM_NORTHEAST:
  402.               OrCell( r1, c1, s1, HOLE_NORTHEAST );  break;
  403.             case FROM_SOUTHEAST:
  404.               OrCell( r1, c1, s1, HOLE_SOUTHEAST );  break;
  405.             case FROM_SOUTHWEST:
  406.               OrCell( r1, c1, s1, HOLE_SOUTHWEST );  break;
  407.             case FROM_NORTHWEST:
  408.               OrCell( r1, c1, s1, HOLE_NORTHWEST );  break;
  409.             case FROM_OTHERSIDE:
  410.             default:
  411.                 fprintf( stderr, "internal error\n" );
  412.                 exit( -1 );
  413.                 break;
  414.                 }
  415.             }
  416.         else {
  417.             if ((y == FROM_NORTH
  418.                 || y == FROM_NORTHEAST
  419.                 || y == FROM_EAST
  420.                 || y == FROM_SOUTHEAST
  421.                 || y == FROM_SOUTH
  422.                 || y == FROM_SOUTHWEST
  423.                 || y == FROM_WEST
  424.                 || y == FROM_NORTHWEST)
  425.                 && (x == FROM_NORTH
  426.                 || x == FROM_NORTHEAST
  427.                 || x == FROM_EAST
  428.                 || x == FROM_SOUTHEAST
  429.                 || x == FROM_SOUTH
  430.                 || x == FROM_SOUTHWEST
  431.                 || x == FROM_WEST
  432.                 || x == FROM_NORTHWEST
  433.                 || x == FROM_OTHERSIDE)
  434.                 && (b = bit[y-1][x-1])) {
  435.                 OrCell( r1, c1, s1, b );
  436.                 if (b & HOLE)
  437.                     OrCell( r2, c2, s2, HOLE );
  438.                 }
  439.             else {
  440.                 fprintf( stderr, "internal error\n" );
  441.                 exit( -1 );
  442.                 }
  443.             }
  444.         if (r2 == rr1 && c2 == cc1) { /* see if source */
  445.             switch (x) {
  446.             case FROM_NORTH:
  447.               OrCell( r2, c2, s2, HOLE_SOUTH );  break;
  448.             case FROM_EAST:
  449.               OrCell( r2, c2, s2, HOLE_WEST );  break;
  450.             case FROM_SOUTH:
  451.               OrCell( r2, c2, s2, HOLE_NORTH );  break;
  452.             case FROM_WEST:
  453.               OrCell( r2, c2, s2, HOLE_EAST );  break;
  454.             case FROM_NORTHEAST:
  455.               OrCell( r2, c2, s2, HOLE_SOUTHWEST );  break;
  456.             case FROM_SOUTHEAST:
  457.               OrCell( r2, c2, s2, HOLE_NORTHWEST );  break;
  458.             case FROM_SOUTHWEST:
  459.               OrCell( r2, c2, s2, HOLE_NORTHEAST );  break;
  460.             case FROM_NORTHWEST:
  461.               OrCell( r2, c2, s2, HOLE_SOUTHEAST );  break;
  462.             case FROM_OTHERSIDE:
  463.             default:
  464.                 fprintf( stderr, "internal error\n" );
  465.                 exit( -1 );
  466.                 break;
  467.                 }
  468.             }
  469.         /* move to next cell */
  470.         r0 = r1; c0 = c1; s0 = s1;
  471.         r1 = r2; c1 = c2; s1 = s2;
  472.         } while (!(r2 == rr1 && c2 == cc1));
  473.     }
  474.  
  475. int GetApxDist ( r1, c1, r2, c2 ) /* calculate approximate distance */
  476.     int r1, c1, r2, c2;
  477.     {
  478.     register int d1, d2; /* row and column deltas */
  479.     int d0; /* temporary variable for swapping d1 and d2 */
  480.  
  481.     /* NOTE: the -25 used below is because we are not going */
  482.     /* from the center of (r1,c1) to the center of (r2,c2), */
  483.     /* we are going from the edge of a hole at (r1,c1) to   */
  484.     /* the edge of a hole at (r2,c2). holes are 25 mils in  */
  485.     /* diameter (12.5 mils in radius), so we back off by 2  */
  486.     /* radii.                                               */
  487.     if ((d1 = r1-r2) < 0) /* get absolute row delta */
  488.         d1 = -d1;
  489.     if ((d2 = c1-c2) < 0) /* get absolute column delta */
  490.         d2 = -d2;
  491.     if (!d1) /* in same row? */
  492.         return( (d2*50)-25 ); /* 50 mils per cell */
  493.     if (!d2) /* in same column? */
  494.         return( (d1*50)-25 ); /* 50 mils per cell */
  495.     if (d1 > d2) { /* get smaller into d1 */
  496.         d0 = d1;
  497.         d1 = d2;
  498.         d2 = d0;
  499.         }
  500.     d2 -= d1; /* get non-diagonal part of approximate route */
  501.     return( (d1*71)+(d2*50)-25 ); /* 71 mils diagonally per cell */
  502.     }
  503.  
  504. /* distance to go through a cell */
  505. static int dist[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  506.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  507. /* N  */ { 50, 60, 35, 60, 99, 60, 35, 60,   12, 12 },
  508. /* NE */ { 60, 71, 60, 71, 60, 99, 60, 71,   23, 23 },
  509. /* E  */ { 35, 60, 50, 60, 35, 60, 99, 60,   12, 12 },
  510. /* SE */ { 60, 71, 60, 71, 60, 71, 60, 99,   23, 23 },
  511. /* S  */ { 99, 60, 35, 60, 50, 60, 35, 60,   12, 12 },
  512. /* SW */ { 60, 99, 60, 71, 60, 71, 60, 71,   23, 23 },
  513. /* W  */ { 35, 60, 99, 60, 35, 60, 50, 60,   12, 12 },
  514. /* NW */ { 60, 71, 60, 99, 60, 71, 60, 71,   23, 23 },
  515.  
  516. /* OT */ { 12, 23, 12, 23, 12, 23, 12, 23,   99, 99 },
  517. /* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 99 }
  518.     };
  519.  
  520. /* distance around (circular) segment of hole */
  521. static int circ[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  522.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  523. /* N  */ { 39, 29, 20, 10,  0, 10, 20, 29,   99, 0 },
  524. /* NE */ { 29, 39, 29, 20, 10,  0, 10, 20,   99, 0 },
  525. /* E  */ { 20, 29, 39, 29, 20, 10,  0, 10,   99, 0 },
  526. /* SE */ { 10, 20, 29, 39, 29, 20, 10,  0,   99, 0 },
  527. /* S  */ {  0, 10, 20, 29, 39, 29, 20, 10,   99, 0 },
  528. /* SW */ { 10,  0, 10, 20, 29, 39, 29, 20,   99, 0 },
  529. /* W  */ { 20, 10,  0, 10, 20, 29, 39, 29,   99, 0 },
  530. /* NW */ { 29, 20, 10,  0, 10, 20, 29, 39,   99, 0 },
  531.  
  532. /* OT */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 0 },
  533. /* OR */ { 99, 99, 99, 99, 99, 99, 99, 99,   99, 0 }
  534.     };
  535.  
  536. /* penalty for routing holes and turns, scaled by sharpness of turn */
  537. static int penalty[10][10] = { /* OT=Otherside, OR=Origin (source) cell */
  538.      /* N, NE,  E, SE,  S, SW,  W, NW,   OT, OR */
  539. /* N  */ {  0,  5, 10, 15, 20, 15, 10,  5,   50, 0 },
  540. /* NE */ {  5,  0,  5, 10, 15, 20, 15, 10,   50, 0 },
  541. /* E  */ { 10,  5,  0,  5, 10, 15, 20, 15,   50, 0 },
  542. /* SE */ { 15, 10,  5,  0,  5, 10, 15, 20,   50, 0 },
  543. /* S  */ { 20, 15, 10,  5,  0,  5, 10, 15,   50, 0 },
  544. /* SW */ { 15, 20, 15, 10,  5,  0,  5, 10,   50, 0 },
  545. /* W  */ { 10, 15, 20, 15, 10,  5,  0,  5,   50, 0 },
  546. /* NW */ {  5, 10, 15, 20, 15, 10,  5,  0,   50, 0 },
  547.  
  548. /* OT */ { 50, 50, 50, 50, 50, 50, 50, 50,  100, 0 },
  549. /* OR */ {  0,  0,  0,  0,  0,  0,  0,  0,    0, 0 }
  550.     };
  551.  
  552. /*
  553. ** x is the direction to enter the cell of interest.
  554. ** y is the direction to exit the cell of interest.
  555. ** z is the direction to really exit the cell, if y=FROM_OTHERSIDE.
  556. **
  557. ** return the distance of the trace through the cell of interest.
  558. ** the calculation is driven by the tables above.
  559. */
  560.  
  561. int CalcDist ( x, y, z )
  562.     /* calculate distance of a trace through a cell */
  563.     int x, y, z;
  564.     {
  565.     int adjust;
  566.  
  567.     adjust = 0; /* set if hole is encountered */
  568.     if (x == EMPTY)
  569.         x = 10;
  570.     if (y == EMPTY)
  571.         y = 10;
  572.     else if (y == FROM_OTHERSIDE) {
  573.         if (z == EMPTY)
  574.             z = 10;
  575.         adjust = circ[x-1][z-1] + penalty[x-1][z-1];
  576.         }
  577.     return( dist[x-1][y-1] + penalty[x-1][y-1] + adjust );
  578.     }
  579.