home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 1 / HamRadio.cdr / tech / pcbsrcs2 / solve3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-02-07  |  22.3 KB  |  491 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 | HOLE )
  40. #define BLOCK_SOUTHEAST            ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  41.                        | ANGLE_NEtoSE | ANGLE_SEtoSW \
  42.                        | SHARP_EtoSE | SHARP_StoSE | HOLE )
  43. #define BLOCK_SOUTHWEST            ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  44.                        | ANGLE_SEtoSW | ANGLE_SWtoNW \
  45.                        | SHARP_StoSW | SHARP_WtoSW | HOLE )
  46. #define BLOCK_NORTHWEST            ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  47.                        | ANGLE_SWtoNW | ANGLE_NWtoNE \
  48.                        | SHARP_WtoNW | SHARP_NtoNW | HOLE )
  49. #define BLOCK_NORTH            ( LINE_VERTICAL | BENT_NtoSE | BENT_NtoSW \
  50.                        | BENT_EtoNW | BENT_WtoNE \
  51.                        | BENT_StoNE | BENT_StoNW \
  52.                        | CORNER_NORTHEAST | CORNER_NORTHWEST \
  53.                        | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_NWtoNE \
  54.                        | DIAG_NEtoSW | DIAG_SEtoNW \
  55.                        | SHARP_NtoNE | SHARP_NtoNW \
  56.                        | SHARP_EtoNE | SHARP_WtoNW | HOLE )
  57. #define BLOCK_EAST             ( LINE_HORIZONTAL | BENT_EtoSW | BENT_EtoNW \
  58.                        | BENT_NtoSE | BENT_StoNE \
  59.                        | BENT_WtoNE | BENT_WtoSE \
  60.                        | CORNER_NORTHEAST | CORNER_SOUTHEAST \
  61.                        | ANGLE_NEtoSE | ANGLE_SEtoSW | ANGLE_NWtoNE \
  62.                        | DIAG_NEtoSW | DIAG_SEtoNW \
  63.                        | SHARP_EtoNE | SHARP_EtoSE \
  64.                        | SHARP_NtoNE | SHARP_StoSE | HOLE )
  65. #define BLOCK_SOUTH            ( LINE_VERTICAL | BENT_StoNE | BENT_StoNW \
  66.                        | BENT_EtoSW | BENT_WtoSE \
  67.                        | BENT_NtoSE | BENT_NtoSW \
  68.                        | CORNER_SOUTHEAST | CORNER_SOUTHWEST \
  69.                        | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_SEtoSW \
  70.                        | DIAG_NEtoSW | DIAG_SEtoNW \
  71.                        | SHARP_StoSE | SHARP_StoSW \
  72.                        | SHARP_EtoSE | SHARP_WtoSW | HOLE )
  73. #define BLOCK_WEST             ( LINE_HORIZONTAL | BENT_WtoNE | BENT_WtoSE \
  74.                        | BENT_NtoSW | BENT_StoNW \
  75.                        | BENT_EtoSW | BENT_EtoNW \
  76.                        | CORNER_SOUTHWEST | CORNER_NORTHWEST \
  77.                        | ANGLE_SWtoNW | ANGLE_SEtoSW | ANGLE_NWtoNE \
  78.                        | DIAG_NEtoSW | DIAG_SEtoNW \
  79.                        | SHARP_WtoSW | SHARP_WtoNW \
  80.                        | SHARP_NtoNW | SHARP_StoSW | HOLE )
  81.  
  82. struct block {
  83.            int r1, c1;
  84.            long b1;
  85.            int r2, c2;
  86.            long b2;
  87.            };
  88.  
  89. static struct block blocking[8] = { /* blocking masks for diagonal traces */
  90.             {  0, -1, BLOCK_NORTHEAST,  1, 0, BLOCK_SOUTHWEST },
  91.             {  0,  0, 0, 0, 0, 0 },
  92.             {  1,  0, BLOCK_SOUTHEAST,  0, 1, BLOCK_NORTHWEST },
  93.             {  0,  0, 0, 0, 0, 0 },
  94.             {  0,  0, 0, 0, 0, 0 },
  95.             {  0, -1, BLOCK_SOUTHEAST, -1, 0, BLOCK_NORTHWEST },
  96.             {  0,  0, 0, 0, 0, 0 },
  97.             { -1,  0, BLOCK_NORTHEAST,  0, 1, BLOCK_SOUTHWEST }
  98.            };
  99.  
  100. static long blocking2[8] = { /* blocking masks for drilling vias */
  101.             BLOCK_SOUTHEAST, BLOCK_SOUTH, BLOCK_SOUTHWEST,
  102.             BLOCK_EAST,                   BLOCK_WEST,
  103.             BLOCK_NORTHEAST, BLOCK_NORTH, BLOCK_NORTHWEST
  104.            };
  105.  
  106. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  107.             { 1, 1, 1, 1, 1, 1, 1, 1 },
  108.             { 0, 0, 0, 0, 1, 0, 1, 0 },
  109.             { 0, 0, 0, 1, 0, 0, 1, 0 },
  110.             { 0, 1, 0, 0, 1, 0, 0, 0 },
  111.             { 0, 1, 0, 1, 0, 0, 0, 0 }
  112.            };
  113.  
  114. /* mask for hole-related blocking effects */
  115. static struct {
  116.            long trace;
  117.            int present;
  118.            } selfok2[8] = {
  119.             { HOLE_NORTHWEST, 0 },
  120.             { HOLE_NORTH, 0 },
  121.             { HOLE_NORTHEAST, 0 },
  122.             { HOLE_WEST, 0 },
  123.             { HOLE_EAST, 0 },
  124.             { HOLE_SOUTHWEST, 0 },
  125.             { HOLE_SOUTH, 0 },
  126.             { HOLE_SOUTHEAST, 0 }
  127.            };
  128.  
  129. static long newmask[8] = { /* patterns to mask out in neighbor cells */
  130.            0, CORNER_NORTHWEST|CORNER_NORTHEAST, 0,
  131.            CORNER_NORTHWEST|CORNER_SOUTHWEST, CORNER_NORTHEAST|CORNER_SOUTHEAST,
  132.            0, CORNER_SOUTHWEST|CORNER_SOUTHEAST, 0
  133.            };
  134.  
  135. static char fmt[] =
  136.   "  open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";
  137.  
  138. extern int Nrows, Ncols; /* board dimensions */
  139.  
  140. /* measures of progress */
  141. extern int Ntotal;
  142. int Ncurrent = 0;
  143. int CompleteTrace = 0;
  144.  
  145. /* Do we want a double sided board?  Added by Stephen P. Smith */
  146. extern int DoubleSided;
  147. extern int NoDiag;
  148. extern int TopSide;
  149. extern long Percent; 
  150. extern int  RatsNest;
  151.  
  152. /* search statistics */
  153. extern long OpenNodes; /* total number of nodes opened */
  154. extern long ClosNodes; /* total number of nodes closed */
  155. extern long MoveNodes; /* total number of nodes moved */
  156. extern long MaxNodes; /* maximum number of nodes opened at one time */
  157.  
  158. extern void GetWork( int *, int *, char far * far *, int *, int *,
  159.            char far * far * );
  160. extern void InitQueue( void );
  161. extern void GetQueue( int *, int *, int *, int *, int * );
  162. extern void SetQueue( int, int, int, int, int, int, int );
  163. extern void ReSetQueue( int, int, int, int, int, int, int );
  164. extern long GetCell( int, int, int );
  165. extern void SetCell( int, int, int, long );
  166. extern void OrCell( int, int, int, long );
  167. extern int GetDir( int, int, int );
  168. extern void SetDir( int, int, int, int );
  169. extern int GetDist( int, int, int );
  170. extern void SetDist( int, int, int, int );
  171. extern int GetApxDist( int, int, int, int );
  172. extern int CalcDist( int, int, int, int );
  173.  
  174. void Solve( FILE * );
  175. void Retrace( int, int, int, int, int );
  176.  
  177. void Solve ( fp )
  178. FILE *fp;
  179.     { /* route all traces */
  180.            int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
  181.            register int i;
  182.            char far *n1;
  183.            char far *n2;
  184.            long curcell, newcell, buddy, lastopen, lastclos, lastmove;
  185.            int newdist, olddir, success, self, echo;
  186.  
  187.            printf( "enter Solve()\n" );
  188.            echo = isatty( fileno(stdout) ) ? 1 : 0;
  189.            /* go until no more work to do */
  190.            for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
  191.                    GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
  192.                Ncurrent++;
  193.                printf( "routing %Fs=%Fs, %d of %d\n", n1, n2, Ncurrent,
  194.                    Ntotal );
  195.                if (r1 == r2 && c1 == c2) /* trivial case; already routed */
  196.                    continue;
  197.                success = 0;
  198.                lastopen = lastclos = lastmove = 0;
  199.                InitQueue(); /* initialize the search queue */
  200.                a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
  201.                if ( DoubleSided ) {
  202.                       SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  203.                       SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  204.                    }
  205.                    else
  206.                    {
  207.                       if ( TopSide )  SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  208.                          if ( !TopSide ) SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  209.                    }
  210.                /* search until success or we exhaust all possibilities */
  211.                for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  212.                    GetQueue( &r, &c, &s, &d, &a )) {
  213.                    if (r == r2 && c == c2) { /* success! */
  214.                        Retrace( r1, c1, r2, c2, s ); /* lay traces */
  215.                        success++;
  216.                        break;
  217.                        }
  218.                    /* report every 100 new nodes or so */
  219.                    if (echo && (OpenNodes - lastopen > 100
  220.                        || ClosNodes - lastclos > 100
  221.                        || MoveNodes - lastmove > 100)) {
  222.                        lastopen = (OpenNodes/100)*100;
  223.                        lastclos = (ClosNodes/100)*100;
  224.                        lastmove = (MoveNodes/100)*100;
  225.                        printf( fmt, OpenNodes, ClosNodes,
  226.                            MoveNodes, MaxNodes,
  227.                            (ClosNodes*50)/(Nrows*Ncols) );
  228.                        putchar( '\r' );
  229.                        }
  230.                    curcell = GetCell( r, c, s );
  231.                    if (curcell&HOLE) {
  232.                        self = 5;
  233.                        /* set 'present' bits */
  234.                        for (i = 0; i < 8; i++)
  235.                            selfok2[i].present =
  236.                            ((curcell&selfok2[i].trace)?1:0);
  237.                        }
  238.                    else if (curcell & CORNER_NORTHWEST)
  239.                        self = 1;
  240.                    else if (curcell & CORNER_NORTHEAST)
  241.                        self = 2;
  242.                    else if (curcell & CORNER_SOUTHWEST)
  243.                        self = 3;
  244.                    else if (curcell & CORNER_SOUTHEAST)
  245.                        self = 4;
  246.                    else
  247.                        self = 0;
  248.                    for (i = 0; i < 8; i++) { /* consider neighbors */
  249.                        if ( (delta[i][0] != 0) && (delta[i][1] != 0 ) )
  250.                            if (  NoDiag )
  251.                               continue;
  252.                        /* Cause routing failure if a rats nest is desired */
  253.                        if ( RatsNest ) continue;
  254.                        /* check self-block */                       
  255.                        if (self < 5 && !selfok[self][i])
  256.                            continue;                                                       if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  257.                            || (nc = c+delta[i][1]) < 0
  258.                            || nc >= Ncols) /* off the edge? */
  259.                            continue;
  260.                        if (self == 5 && selfok2[i].present)
  261.                            continue;
  262.                        newcell = GetCell( nr, nc, s );
  263.                        /* check for non-target hole */
  264.                        if (newcell & HOLE) {
  265.                            if (nr != r2 || nc != c2)
  266.                                continue;
  267.                            }
  268.                        /* check for traces */
  269.                        else if (newcell & ~(newmask[i]))
  270.                            continue;
  271.                        /* check blocking on corner neighbors */
  272.                        if (delta[i][0] && delta[i][1]) {
  273.                            /* check first buddy */
  274.                            buddy = GetCell( r+blocking[i].r1,
  275.                                c+blocking[i].c1, s );
  276.                            if (buddy & (blocking[i].b1))
  277.                                continue;
  278.                            /* check second buddy */
  279.                            buddy = GetCell( r+blocking[i].r2,
  280.                                c+blocking[i].c2, s );
  281.                            if (buddy & (blocking[i].b2))
  282.                                continue;
  283.                            }
  284.                        olddir = GetDir( r, c, s );
  285.                        newdist = d+CalcDist( ndir[i], olddir,
  286.                            (olddir == FROM_OTHERSIDE, s)
  287.                            ? GetDir( r, c, 1-s ) : 0, s );
  288.                        /* if (a) not visited yet, or (b) we have */
  289.                        /* found a better path, add it to queue */
  290.                        if (!GetDir( nr, nc, s )
  291.                            || (newdist < GetDist( nr, nc, s ))) {
  292.                            SetDir( nr, nc, s, ndir[i] );
  293.                            SetDist( nr, nc, s, newdist );
  294.                            ReSetQueue( nr, nc, s, newdist,
  295.                                GetApxDist( nr, nc, r2, c2 ),
  296.                                r2, c2 );
  297.                            }
  298.                        }
  299.                        if ( DoubleSided ) {
  300.                            /* consider other side of board */
  301.                            olddir = GetDir( r, c, s );
  302.                            if (olddir == FROM_OTHERSIDE)
  303.                                continue; /* useless move, so don't bother */
  304.                            if (curcell) /* can't drill via if anything here */
  305.                                continue;
  306.                            /* check for holes or traces on other side */
  307.                            if (newcell = GetCell( r, c, 1-s ))
  308.                                continue;
  309.                            /* check for nearby holes or traces on both sides */
  310.                            for (skip = i = 0; i < 8; i++) {
  311.                                if ( (delta[i][0] != 0) && (delta[i][1] != 0 ) )
  312.                                    if (  NoDiag )
  313.                                       continue;
  314.                                if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  315.                                    || (nc = c+delta[i][1]) < 0
  316.                                    || nc >= Ncols) /* off the edge? */
  317.                                    continue;
  318.                                if (GetCell( nr, nc, s ) & blocking2[i]) {
  319.                                    skip = 1; /* can't drill via here */
  320.                                    break;
  321.                                    }
  322.                                if (GetCell( nr, nc, 1-s ) & blocking2[i]) {
  323.                                    skip = 1; /* can't drill via here */
  324.                                    break;
  325.                                    }
  326.                                }
  327.                            if (skip) /* neighboring hole or trace? */
  328.                                continue; /* yes, can't drill via here */
  329.                            newdist = d+CalcDist( FROM_OTHERSIDE, olddir, 0, s );
  330.                            /* if (a) not visited yet, or (b) we have found a
  331.                            /* better path, add it to queue */
  332.                            if (!GetDir( r, c, 1-s )
  333.                                || (newdist < GetDist( r, c, 1-s ))) {
  334.                                SetDir( r, c, 1-s, FROM_OTHERSIDE );
  335.                                SetDist( r, c, 1-s, newdist );
  336.                                ReSetQueue( r, c, 1-s, newdist, a, r2, c2 );
  337.                                }
  338.                            }
  339.                if( Percent <= ((ClosNodes*50)/(Nrows*Ncols)) ) break;
  340.             }
  341.         printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
  342.             (ClosNodes*50)/(Nrows*Ncols) );
  343.         putchar( '\n' );
  344.         if (!success){
  345.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  346.             if( fp != NULL )
  347.                 fprintf( fp, "LINE2( %d, %d, %d, %d)\n",
  348.                 r1*50+25, c1*50+25, r2*50+25, c2*50+25 );
  349.             }
  350.         else
  351.             CompleteTrace++;
  352.         /* clear direction flags */
  353.         for (r = 0; r < Nrows; r++) {
  354.             for (c = 0; c < Ncols; c++) {
  355.                 SetDir( r, c, TOP, FROM_NOWHERE );
  356.                 SetDir( r, c, BOTTOM, FROM_NOWHERE );
  357.                 }
  358.             }
  359.         }
  360.     printf( "\nCompleted Traces:  %d of %d\n\n", CompleteTrace, Ntotal );
  361.     printf( "leave Solve()\n" );
  362.     }
  363.  
  364. static long bit[8][9] = { /* OT=Otherside */
  365.      /* N, NE, E, SE, S, SW, W, NW, OT */
  366. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
  367.        SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
  368. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
  369.        0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
  370. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  371.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
  372. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
  373.        ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
  374. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
  375.        BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
  376. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
  377.        BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
  378. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
  379.        BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
  380. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  381.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
  382.            };
  383.  
  384. void Retrace ( rr1, cc1, rr2, cc2, s )
  385.            /* work from target back to source, actually laying the traces */
  386.            int rr1, cc1, rr2, cc2, s; /* start on side s */
  387.            {
  388.            int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  389.            register int x, y;
  390.            long b;
  391.  
  392.            r1 = rr2;
  393.            c1 = cc2;
  394.            s1 = s;
  395.            r0 = c0 = s0 = ILLEGAL;
  396.            do {
  397.                /* find where we came from to get here */
  398.                switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  399.                case FROM_NORTH:    r2++;       break;
  400.                case FROM_EAST:         c2++;   break;
  401.                case FROM_SOUTH:    r2--;       break;
  402.                case FROM_WEST:         c2--;   break;
  403.                case FROM_NORTHEAST:    r2++;   c2++;   break;
  404.                case FROM_SOUTHEAST:    r2--;   c2++;   break;
  405.                case FROM_SOUTHWEST:    r2--;   c2--;   break;
  406.                case FROM_NORTHWEST:    r2++;   c2--;   break;
  407.                case FROM_OTHERSIDE:    s2 = 1-s2;  break;
  408.                default:
  409.                    fprintf( stderr, "internal error: no way back\n" );
  410.                    exit( -1 );
  411.                    break;
  412.                    }
  413.                if (r0 != ILLEGAL)
  414.                    y = GetDir( r0, c0, s0 );
  415.                /* see if target or hole */
  416.                if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  417.                    switch (x) {
  418.                    case FROM_NORTH:
  419.                        OrCell( r1, c1, s1, HOLE_NORTH );   break;
  420.                    case FROM_EAST:
  421.                        OrCell( r1, c1, s1, HOLE_EAST );    break;
  422.                    case FROM_SOUTH:
  423.                        OrCell( r1, c1, s1, HOLE_SOUTH );   break;
  424.                    case FROM_WEST:
  425.                        OrCell( r1, c1, s1, HOLE_WEST );    break;
  426.                    case FROM_NORTHEAST:
  427.                        OrCell( r1, c1, s1, HOLE_NORTHEAST );   break;
  428.                    case FROM_SOUTHEAST:
  429.                        OrCell( r1, c1, s1, HOLE_SOUTHEAST );   break;
  430.                    case FROM_SOUTHWEST:
  431.                        OrCell( r1, c1, s1, HOLE_SOUTHWEST );   break;
  432.                    case FROM_NORTHWEST:
  433.                        OrCell( r1, c1, s1, HOLE_NORTHWEST );   break;
  434.                    case FROM_OTHERSIDE:
  435.                    default:
  436.                        fprintf( stderr, "internal error\n" );
  437.                        exit( -1 );
  438.                        break;
  439.                        }
  440.                    }
  441.                else {
  442.                    if ((y == FROM_NORTH || y == FROM_NORTHEAST
  443.                        || y == FROM_EAST || y == FROM_SOUTHEAST
  444.                        || y == FROM_SOUTH || y == FROM_SOUTHWEST
  445.                        || y == FROM_WEST || y == FROM_NORTHWEST)
  446.                        && (x == FROM_NORTH || x == FROM_NORTHEAST
  447.                        || x == FROM_EAST || x == FROM_SOUTHEAST
  448.                        || x == FROM_SOUTH || x == FROM_SOUTHWEST
  449.                        || x == FROM_WEST || x == FROM_NORTHWEST
  450.                        || x == FROM_OTHERSIDE)
  451.                        && (b = bit[y-1][x-1])) {
  452.                        OrCell( r1, c1, s1, b );
  453.                        if (b & HOLE)
  454.                            OrCell( r2, c2, s2, HOLE );
  455.                        }
  456.                    else {
  457.                        fprintf( stderr, "internal error\n" );
  458.                        exit( -1 );
  459.                        }
  460.                    }
  461.                if (r2 == rr1 && c2 == cc1) { /* see if source */
  462.                    switch (x) {
  463.                    case FROM_NORTH:
  464.                        OrCell( r2, c2, s2, HOLE_SOUTH );   break;
  465.                    case FROM_EAST:
  466.                        OrCell( r2, c2, s2, HOLE_WEST );    break;
  467.                    case FROM_SOUTH:
  468.                        OrCell( r2, c2, s2, HOLE_NORTH );   break;
  469.                    case FROM_WEST:
  470.                        OrCell( r2, c2, s2, HOLE_EAST );    break;
  471.                    case FROM_NORTHEAST:
  472.                        OrCell( r2, c2, s2, HOLE_SOUTHWEST );   break;
  473.                    case FROM_SOUTHEAST:
  474.                        OrCell( r2, c2, s2, HOLE_NORTHWEST );   break;
  475.                    case FROM_SOUTHWEST:
  476.                        OrCell( r2, c2, s2, HOLE_NORTHEAST );   break;
  477.                    case FROM_NORTHWEST:
  478.                        OrCell( r2, c2, s2, HOLE_SOUTHEAST );   break;
  479.                    case FROM_OTHERSIDE:
  480.                    default:
  481.                        fprintf( stderr, "internal error\n" );
  482.                        exit( -1 );
  483.                        break;
  484.                        }
  485.                    }
  486.                /* move to next cell */
  487.                r0 = r1; c0 = c1; s0 = s1;
  488.                r1 = r2; c1 = c2; s1 = s2;
  489.                } while (!(r2 == rr1 && c2 == cc1));
  490.            }
  491.