hunt/huntd/makemaze.c

   1 /*      $NetBSD: makemaze.c,v 1.2 1997/10/10 16:33:43 lukem Exp $       */
   2 /*
   3  *  Hunt
   4  *  Copyright (c) 1985 Conrad C. Huang, Gregory S. Couch, Kenneth C.R.C. Arnold
   5  *  San Francisco, California
   6  */
   7
   8 #include <sys/cdefs.h>
   9 #ifndef lint
  10 __RCSID("$NetBSD: makemaze.c,v 1.2 1997/10/10 16:33:43 lukem Exp $");
  11 #endif /* not lint */
  12
  13 # include       "hunt.h"
  14
  15 # define        ISCLEAR(y,x)    (Maze[y][x] == SPACE)
  16 # define        ODD(n)          ((n) & 01)
  17
  18 static  int     candig __P((int, int));
  19 static  void    dig __P((int, int));
  20 static  void    dig_maze __P((int, int));
  21 static  void    remap __P((void));
  22
  23 void
  24 makemaze()
  25 {
  26         char    *sp;
  27         int     y, x;
  28
  29         /*
  30          * fill maze with walls
  31          */
  32         sp = &Maze[0][0];
  33         while (sp < &Maze[HEIGHT - 1][WIDTH])
  34                 *sp++ = DOOR;
  35
  36         x = rand_num(WIDTH / 2) * 2 + 1;
  37         y = rand_num(HEIGHT / 2) * 2 + 1;
  38         dig_maze(x, y);
  39         remap();
  40 }
  41
  42 # define        NPERM   24
  43 # define        NDIR    4
  44
  45 int     dirs[NPERM][NDIR] = {
  46                 {0,1,2,3},      {3,0,1,2},      {0,2,3,1},      {0,3,2,1},
  47                 {1,0,2,3},      {2,3,0,1},      {0,2,1,3},      {2,3,1,0},
  48                 {1,0,3,2},      {1,2,0,3},      {3,1,2,0},      {2,0,3,1},
  49                 {1,3,0,2},      {0,3,1,2},      {1,3,2,0},      {2,0,1,3},
  50                 {0,1,3,2},      {3,1,0,2},      {2,1,0,3},      {1,2,3,0},
  51                 {2,1,3,0},      {3,0,2,1},      {3,2,0,1},      {3,2,1,0}
  52         };
  53
  54 int     incr[NDIR][2] = {
  55                 {0, 1}, {1, 0}, {0, -1}, {-1, 0}
  56         };
  57
  58 static void
  59 dig(y, x)
  60         int     y, x;
  61 {
  62         int     *dp;
  63         int     *ip;
  64         int     ny, nx;
  65         int     *endp;
  66
  67         Maze[y][x] = SPACE;                     /* Clear this spot */
  68         dp = dirs[rand_num(NPERM)];
  69         endp = &dp[NDIR];
  70         while (dp < endp) {
  71                 ip = &incr[*dp++][0];
  72                 ny = y + *ip++;
  73                 nx = x + *ip;
  74                 if (candig(ny, nx))
  75                         dig(ny, nx);
  76         }
  77 }
  78
  79 /*
  80  * candig:
  81  *      Is it legal to clear this spot?
  82  */
  83 static int
  84 candig(y, x)
  85         int     y, x;
  86 {
  87         int     i;
  88
  89         if (ODD(x) && ODD(y))
  90                 return FALSE;           /* can't touch ODD spots */
  91
  92         if (y < UBOUND || y >= DBOUND)
  93                 return FALSE;           /* Beyond vertical bounds, NO */
  94         if (x < LBOUND || x >= RBOUND)
  95                 return FALSE;           /* Beyond horizontal bounds, NO */
  96
  97         if (ISCLEAR(y, x))
  98                 return FALSE;           /* Already clear, NO */
  99
 100         i = ISCLEAR(y, x + 1);
 101         i += ISCLEAR(y, x - 1);
 102         if (i > 1)
 103                 return FALSE;           /* Introduces cycle, NO */
 104         i += ISCLEAR(y + 1, x);
 105         if (i > 1)
 106                 return FALSE;           /* Introduces cycle, NO */
 107         i += ISCLEAR(y - 1, x);
 108         if (i > 1)
 109                 return FALSE;           /* Introduces cycle, NO */
 110
 111         return TRUE;                    /* OK */
 112 }
 113
 114 void
 115 dig_maze(x, y)
 116         int     x, y;
 117 {
 118         int     tx, ty;
 119         int     i, j;
 120         int     order[4];
 121 #define MNORTH  0x1
 122 #define MSOUTH  0x2
 123 #define MEAST   0x4
 124 #define MWEST   0x8
 125
 126         tx = ty = 0;
 127         Maze[y][x] = SPACE;
 128         order[0] = MNORTH;
 129         for (i = 1; i < 4; i++) {
 130                 j = rand_num(i + 1);
 131                 order[i] = order[j];
 132                 order[j] = 0x1 << i;
 133         }
 134         for (i = 0; i < 4; i++) {
 135                 switch (order[i]) {
 136                   case MNORTH:
 137                         tx = x;
 138                         ty = y - 2;
 139                         break;
 140                   case MSOUTH:
 141                         tx = x;
 142                         ty = y + 2;
 143                         break;
 144                   case MEAST:
 145                         tx = x + 2;
 146                         ty = y;
 147                         break;
 148                   case MWEST:
 149                         tx = x - 2;
 150                         ty = y;
 151                         break;
 152                 }
 153                 if (tx < 0 || ty < 0 || tx >= WIDTH || ty >= HEIGHT)
 154                         continue;
 155                 if (Maze[ty][tx] == SPACE)
 156                         continue;
 157                 Maze[(y + ty) / 2][(x + tx) / 2] = SPACE;
 158                 dig_maze(tx, ty);
 159         }
 160 }
 161
 162 void
 163 remap()
 164 {
 165         int     y, x;
 166         char    *sp;
 167         int     stat;
 168
 169         for (y = 0; y < HEIGHT; y++)
 170                 for (x = 0; x < WIDTH; x++) {
 171                         sp = &Maze[y][x];
 172                         if (*sp == SPACE)
 173                                 continue;
 174                         stat = 0;
 175                         if (y - 1 >= 0 && Maze[y - 1][x] != SPACE)
 176                                 stat |= NORTH;
 177                         if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE)
 178                                 stat |= SOUTH;
 179                         if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE)
 180                                 stat |= EAST;
 181                         if (x - 1 >= 0 && Maze[y][x - 1] != SPACE)
 182                                 stat |= WEST;
 183                         switch (stat) {
 184                           case WEST | EAST:
 185                           case EAST:
 186                           case WEST:
 187                                 *sp = WALL1;
 188                                 break;
 189                           case NORTH | SOUTH:
 190                           case NORTH:
 191                           case SOUTH:
 192                                 *sp = WALL2;
 193                                 break;
 194                           case 0:
 195 # ifdef RANDOM
 196                                 *sp = DOOR;
 197 # endif
 198 # ifdef REFLECT
 199                                 *sp = rand_num(2) ? WALL4 : WALL5;
 200 # endif
 201                                 break;
 202                           default:
 203                                 *sp = WALL3;
 204                                 break;
 205                         }
 206                 }
 207         memcpy(Orig_maze, Maze, sizeof Maze);
 208 }