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