home *** CD-ROM | disk | FTP | other *** search
/ Power Programming / powerprogramming1994.iso / progtool / cad / pcb.arc / SOLVE.C < prev    next >
C/C++ Source or Header  |  1989-02-16  |  14KB  |  421 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <fcntl.h>
  4. #include <io.h>
  5. #include "cell.h"
  6.  
  7. /*
  8. ** visit neighboring cells like this (where [9] is on the other side):
  9. **
  10. **    +---+---+---+
  11. **    | 1 | 2 | 3 |
  12. **    +---+---+---+
  13. **    | 4 |[9]| 5 |
  14. **    +---+---+---+
  15. **    | 6 | 7 | 8 |
  16. **    +---+---+---+
  17. */
  18.  
  19. static int delta[8][2] = { /* for visiting neighbors on the same side */
  20.      {  1, -1 }, /* northwest    */
  21.      {  1,  0 }, /* north        */
  22.      {  1,  1 }, /* northeast    */
  23.      {  0, -1 }, /* west        */
  24.      {  0,  1 }, /* east        */
  25.      { -1, -1 }, /* southwest    */
  26.      { -1,  0 }, /* south        */
  27.      { -1,  1 }  /* southeast    */
  28.     };
  29.  
  30. static int ndir[8] = { /* for building paths back to source */
  31.      FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
  32.      FROM_EAST,                  FROM_WEST,
  33.      FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
  34.     };
  35.  
  36. /* blocking masks for neighboring cells */
  37. #define BLOCK_NORTHEAST        ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
  38.                 | ANGLE_NEtoSE | ANGLE_NWtoNE \
  39.                 | SHARP_NtoNE | SHARP_EtoNE )
  40. #define BLOCK_SOUTHEAST        ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  41.                 | ANGLE_NEtoSE | ANGLE_SEtoSW \
  42.                 | SHARP_EtoSE | SHARP_StoSE )
  43. #define BLOCK_SOUTHWEST        ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  44.                 | ANGLE_SEtoSW | ANGLE_SWtoNW \
  45.                 | SHARP_StoSW | SHARP_WtoSW )
  46. #define BLOCK_NORTHWEST        ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  47.                 | ANGLE_SWtoNW | ANGLE_NWtoNE \
  48.                 | SHARP_WtoNW | SHARP_NtoNW )
  49.  
  50. struct block {
  51.     int r1, c1;
  52.     long b1, h1;
  53.     int r2, c2;
  54.     long b2, h2;
  55.     };
  56.  
  57. static struct block blocking[8] = { /* blocking masks */
  58.      {  0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  59.         1,  0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
  60.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  61.      {  1,  0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  62.         0,  1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  63.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  64.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  65.      {  0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  66.        -1,  0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  67.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  68.      { -1,  0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  69.         0,  1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
  70.     };
  71.  
  72. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  73.      { 1, 1, 1, 1, 1, 1, 1, 1 },
  74.      { 0, 0, 0, 0, 1, 0, 1, 0 },
  75.      { 0, 0, 0, 1, 0, 0, 1, 0 },
  76.      { 0, 1, 0, 0, 1, 0, 0, 0 },
  77.      { 0, 1, 0, 1, 0, 0, 0, 0 }
  78.     };
  79.  
  80. static long newmask[5][8] = { /* patterns to mask out in neighbor cells */
  81.      { 0, 0, 0, 0, 0, 0, 0, 0 },
  82.      { 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
  83.         CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  84.      { 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
  85.         CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  86.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
  87.         CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
  88.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
  89.         CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
  90.     };
  91.  
  92. static char fmt[] =
  93.   "  open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";
  94.  
  95. /* board dimensions */
  96. extern int Nrows;
  97. extern int Ncols;
  98.  
  99. /* measures of progress */
  100. int Ntotal = 0;
  101. int Ncurrent = 0;
  102.  
  103. /* search statistics */
  104. extern long OpenNodes; /* total number of nodes opened */
  105. extern long ClosNodes; /* total number of nodes closed */
  106. extern long MoveNodes; /* total number of nodes moved */
  107. extern long MaxNodes; /* maximum number of nodes opened at one time */
  108.  
  109. extern void GetWork( int *, int *, char far * far *, int *, int *,
  110.     char far * far * );
  111. extern void InitQueue( void );
  112. extern void GetQueue( int *, int *, int *, int *, int * );
  113. extern void SetQueue( int, int, int, int, int, int, int );
  114. extern void ReSetQueue( int, int, int, int, int, int, int );
  115. extern long GetCell( int, int, int );
  116. extern void SetCell( int, int, int, long );
  117. extern void OrCell( int, int, int, long );
  118. extern int GetDir( int, int, int );
  119. extern void SetDir( int, int, int, int );
  120. extern int GetDist( int, int, int );
  121. extern void SetDist( int, int, int, int );
  122. extern int GetApxDist( int, int, int, int );
  123. extern int CalcDist( int, int, int );
  124.  
  125. void Solve( void );
  126. void Retrace( int, int, int, int, int );
  127.  
  128. void Solve () { /* route all traces */
  129.     int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
  130.     register int i;
  131.     char far *n1;
  132.     char far *n2;
  133.     long curcell, newcell, buddy, lastopen, lastclos, lastmove;
  134.     int newdist, olddir, success, self, echo;
  135.  
  136.     printf( "enter Solve()\n" );
  137.     echo = isatty( fileno(stdout) ) ? 1 : 0;
  138.     /* go until no more work to do */
  139.     for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
  140.             GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
  141.         Ncurrent++;
  142.         printf( "routing %Fs=%Fs, %d of %d\n", n1, n2, Ncurrent,
  143.             Ntotal );
  144.         if (r1 == r2 && c1 == c2) /* trivial case; already routed */
  145.             continue;
  146.         success = 0;
  147.         lastopen = lastclos = lastmove = 0;
  148.         InitQueue(); /* initialize the search queue */
  149.         a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
  150.         SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  151.         SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  152.         /* search until success or we exhaust all possibilities */
  153.         for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  154.             GetQueue( &r, &c, &s, &d, &a )) {
  155.             if (r == r2 && c == c2) { /* success! */
  156.                 Retrace( r1, c1, r2, c2, s ); /* lay traces */
  157.                 success++;
  158.                 break;
  159.                 }
  160.             /* report every 100 new nodes or so */
  161.             if (echo && (OpenNodes - lastopen > 100
  162.                 || ClosNodes - lastclos > 100
  163.                 || MoveNodes - lastmove > 100)) {
  164.                 lastopen = (OpenNodes/100)*100;
  165.                 lastclos = (ClosNodes/100)*100;
  166.                 lastmove = (MoveNodes/100)*100;
  167.                 printf( fmt, OpenNodes, ClosNodes,
  168.                     MoveNodes, MaxNodes,
  169.                     (ClosNodes*50)/(Nrows*Ncols) );
  170.                 putchar( '\r' );
  171.                 }
  172.             curcell = GetCell( r, c, s );
  173.             if (curcell & CORNER_NORTHWEST)
  174.                 self = 1;
  175.             else if (curcell & CORNER_NORTHEAST)
  176.                 self = 2;
  177.             else if (curcell & CORNER_SOUTHWEST)
  178.                 self = 3;
  179.             else if (curcell & CORNER_SOUTHEAST)
  180.                 self = 4;
  181.             else
  182.                 self = 0;
  183.             for (i = 0; i < 8; i++) { /* consider neighbors */
  184.                 if (!selfok[self][i]) /* check self-block */
  185.                     continue;
  186.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  187.                     || (nc = c+delta[i][1]) < 0
  188.                     || nc >= Ncols) /* off the edge? */
  189.                     continue;
  190.                 newcell = GetCell( nr, nc, s );
  191.                 /* check for non-target hole */
  192.                 if (newcell & HOLE) {
  193.                     if (nr != r2 || nc != c2)
  194.                         continue;
  195.                     }
  196.                 else {
  197.                     newcell &= ~(newmask[self][i]);
  198.                     if (newcell) /* check for traces */
  199.                         continue;
  200.                     }
  201.                 /* check blocking on corner neighbors */
  202.                 if (delta[i][0] && delta[i][1]) {
  203.                     /* check first buddy */
  204.                     buddy = GetCell( r+blocking[i].r1,
  205.                         c+blocking[i].c1, s );
  206.                     if (buddy & HOLE) {
  207.                         if (buddy & (blocking[i].h1))
  208.                             continue;
  209.                         }
  210.                     else if (buddy & (blocking[i].b1))
  211.                         continue;
  212.                     /* check second buddy */
  213.                     buddy = GetCell( r+blocking[i].r2,
  214.                         c+blocking[i].c2, s );
  215.                     if (buddy & HOLE) {
  216.                         if (buddy & (blocking[i].h2))
  217.                             continue;
  218.                         }
  219.                     else if (buddy & (blocking[i].b2))
  220.                         continue;
  221.                     }
  222.                 olddir = GetDir( r, c, s );
  223.                 newdist = d+CalcDist( ndir[i], olddir,
  224.                     (olddir == FROM_OTHERSIDE)
  225.                     ? GetDir( r, c, 1-s ) : 0 );
  226.                 /* if not visited yet, add it to queue */
  227.                 if (!GetDir( nr, nc, s )) {
  228.                     SetDir( nr, nc, s, ndir[i] );
  229.                     SetDist( nr, nc, s, newdist );
  230.                     SetQueue( nr, nc, s, newdist,
  231.                         GetApxDist( nr, nc, r2, c2 ),
  232.                         r2, c2 );
  233.                     }
  234.                 /* we might have found a better path */
  235.                 else if (newdist < GetDist( nr, nc, s )) {
  236.                     SetDir( nr, nc, s, ndir[i] );
  237.                     SetDist( nr, nc, s, newdist );
  238.                     ReSetQueue( nr, nc, s, newdist,
  239.                         GetApxDist( nr, nc, r2, c2 ),
  240.                         r2, c2 );
  241.                     }
  242.                 }
  243.             /* consider other side of board */
  244.             /* check for holes or traces on other side */
  245.             if (newcell = GetCell( r, c, 1-s ))
  246.                 continue;
  247.             skip = 0;
  248.             /* check for nearby holes */
  249.             for (i = 0; i < 8; i++) {
  250.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  251.                     || (nc = c+delta[i][1]) < 0
  252.                     || nc >= Ncols) /* off the edge? */
  253.                     continue;
  254.                 if (GetCell( nr, nc, s ) & HOLE) {
  255.                     skip = 1; /* neighboring hole */
  256.                     break;
  257.                     }
  258.                 }
  259.             if (skip) /* neighboring hole? */
  260.                 continue; /* yes, can't drill one here */
  261.             olddir = GetDir( r, c, s );
  262.             newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
  263.                 (olddir == FROM_OTHERSIDE)
  264.                 ? GetDir( r, c, 1-s ) : 0 );
  265.             /* if not visited yet, add it to queue */
  266.             if (!GetDir( r, c, 1-s )) {
  267.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  268.                 SetDist( r, c, 1-s, newdist );
  269.                 SetQueue( r, c, 1-s, newdist, a, r2, c2 );
  270.                 }
  271.             /* we might have found a better path */
  272.             else if (newdist < GetDist( r, c, 1-s )) {
  273.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  274.                 SetDist( r, c, 1-s, newdist );
  275.                 ReSetQueue( r, c, 1-s, newdist, a, r2, c2 );
  276.                 }
  277.             }
  278.         printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
  279.             (ClosNodes*50)/(Nrows*Ncols) );
  280.         putchar( '\n' );
  281.         if (!success)
  282.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  283.         /* clear direction flags */
  284.         for (r = 0; r < Nrows; r++) {
  285.             for (c = 0; c < Ncols; c++) {
  286.                 SetDir( r, c, TOP, EMPTY );
  287.                 SetDir( r, c, BOTTOM, EMPTY );
  288.                 }
  289.             }
  290.         }
  291.     printf( "leave Solve()\n" );
  292.     }
  293.  
  294. static long bit[8][9] = { /* OT=Otherside */
  295.      /* N, NE, E, SE, S, SW, W, NW, OT */
  296. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
  297.        SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
  298. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
  299.        0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
  300. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  301.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
  302. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
  303.        ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
  304. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
  305.        BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
  306. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
  307.        BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
  308. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
  309.        BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
  310. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  311.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
  312.     };
  313.  
  314. void Retrace ( rr1, cc1, rr2, cc2, s )
  315.     /* work from target back to source, actually laying the traces */
  316.     int rr1, cc1, rr2, cc2, s; /* start on side s */
  317.     {
  318.     int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  319.     register int x, y;
  320.     long b;
  321.  
  322.     r1 = rr2;
  323.     c1 = cc2;
  324.     s1 = s;
  325.     r0 = c0 = s0 = ILLEGAL;
  326.     do {
  327.         /* find where we came from to get here */
  328.         switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  329.         case FROM_NORTH:    r2++;        break;
  330.         case FROM_EAST:            c2++;    break;
  331.         case FROM_SOUTH:    r2--;        break;
  332.         case FROM_WEST:            c2--;    break;
  333.         case FROM_NORTHEAST:    r2++;    c2++;    break;
  334.         case FROM_SOUTHEAST:    r2--;    c2++;    break;
  335.         case FROM_SOUTHWEST:    r2--;    c2--;    break;
  336.         case FROM_NORTHWEST:    r2++;    c2--;    break;
  337.         case FROM_OTHERSIDE:    s2 = 1-s2;    break;
  338.         default:
  339.             printf( "internal error: no way back\n" );
  340.             exit( -1 );
  341.             break;
  342.             }
  343.         if (r0 != ILLEGAL)
  344.             y = GetDir( r0, c0, s0 );
  345.         /* see if target or hole */
  346.         if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  347.             switch (x) {
  348.             case FROM_NORTH:
  349.                 OrCell( r1, c1, s1, HOLE_NORTH );    break;
  350.             case FROM_EAST:
  351.                 OrCell( r1, c1, s1, HOLE_EAST );    break;
  352.             case FROM_SOUTH:
  353.                 OrCell( r1, c1, s1, HOLE_SOUTH );    break;
  354.             case FROM_WEST:
  355.                 OrCell( r1, c1, s1, HOLE_WEST );    break;
  356.             case FROM_NORTHEAST:
  357.                 OrCell( r1, c1, s1, HOLE_NORTHEAST );    break;
  358.             case FROM_SOUTHEAST:
  359.                 OrCell( r1, c1, s1, HOLE_SOUTHEAST );    break;
  360.             case FROM_SOUTHWEST:
  361.                 OrCell( r1, c1, s1, HOLE_SOUTHWEST );    break;
  362.             case FROM_NORTHWEST:
  363.                 OrCell( r1, c1, s1, HOLE_NORTHWEST );    break;
  364.             case FROM_OTHERSIDE:
  365.             default:
  366.                 printf( "internal error\n" );
  367.                 exit( -1 );
  368.                 break;
  369.                 }
  370.             }
  371.         else {
  372.             if ((y == FROM_NORTH || y == FROM_NORTHEAST
  373.                 || y == FROM_EAST || y == FROM_SOUTHEAST
  374.                 || y == FROM_SOUTH || y == FROM_SOUTHWEST
  375.                 || y == FROM_WEST || y == FROM_NORTHWEST)
  376.                 && (x == FROM_NORTH || x == FROM_NORTHEAST
  377.                 || x == FROM_EAST || x == FROM_SOUTHEAST
  378.                 || x == FROM_SOUTH || x == FROM_SOUTHWEST
  379.                 || x == FROM_WEST || x == FROM_NORTHWEST
  380.                 || x == FROM_OTHERSIDE)
  381.                 && (b = bit[y-1][x-1])) {
  382.                 OrCell( r1, c1, s1, b );
  383.                 if (b & HOLE)
  384.                     OrCell( r2, c2, s2, HOLE );
  385.                 }
  386.             else {
  387.                 printf( "internal error\n" );
  388.                 exit( -1 );
  389.                 }
  390.             }
  391.         if (r2 == rr1 && c2 == cc1) { /* see if source */
  392.             switch (x) {
  393.             case FROM_NORTH:
  394.                 OrCell( r2, c2, s2, HOLE_SOUTH );    break;
  395.             case FROM_EAST:
  396.                 OrCell( r2, c2, s2, HOLE_WEST );    break;
  397.             case FROM_SOUTH:
  398.                 OrCell( r2, c2, s2, HOLE_NORTH );    break;
  399.             case FROM_WEST:
  400.                 OrCell( r2, c2, s2, HOLE_EAST );    break;
  401.             case FROM_NORTHEAST:
  402.                 OrCell( r2, c2, s2, HOLE_SOUTHWEST );    break;
  403.             case FROM_SOUTHEAST:
  404.                 OrCell( r2, c2, s2, HOLE_NORTHWEST );    break;
  405.             case FROM_SOUTHWEST:
  406.                 OrCell( r2, c2, s2, HOLE_NORTHEAST );    break;
  407.             case FROM_NORTHWEST:
  408.                 OrCell( r2, c2, s2, HOLE_SOUTHEAST );    break;
  409.             case FROM_OTHERSIDE:
  410.             default:
  411.                 printf( "internal error\n" );
  412.                 exit( -1 );
  413.                 break;
  414.                 }
  415.             }
  416.         /* move to next cell */
  417.         r0 = r1; c0 = c1; s0 = s1;
  418.         r1 = r2; c1 = c2; s1 = s2;
  419.         } while (!(r2 == rr1 && c2 == cc1));
  420.     }
  421.