1: /*      $NetBSD: makemaze.c,v 1.4 2004/01/27 20:30:29 jsm Exp $      */
    2: /*
    3:  * Copyright (c) 1983-2003, Regents of the University of California.
    4:  * All rights reserved.
    5:  * 
    6:  * Redistribution and use in source and binary forms, with or without 
    7:  * modification, are permitted provided that the following conditions are 
    8:  * met:
    9:  * 
   10:  * + Redistributions of source code must retain the above copyright 
   11:  *   notice, this list of conditions and the following disclaimer.
   12:  * + Redistributions in binary form must reproduce the above copyright 
   13:  *   notice, this list of conditions and the following disclaimer in the 
   14:  *   documentation and/or other materials provided with the distribution.
   15:  * + Neither the name of the University of California, San Francisco nor 
   16:  *   the names of its contributors may be used to endorse or promote 
   17:  *   products derived from this software without specific prior written 
   18:  *   permission.
   19:  * 
   20:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 
   21:  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 
   22:  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 
   23:  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
   24:  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
   25:  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
   26:  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
   27:  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
   28:  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
   29:  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
   30:  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
   31:  */
   32: 
   33: #include <sys/cdefs.h>
   34: #ifndef lint
   35: __RCSID("$NetBSD: makemaze.c,v 1.4 2004/01/27 20:30:29 jsm Exp $");
   36: #endif /* not lint */
   37: 
   38: # include       "hunt.h"
   39: 
   40: # define        ISCLEAR(y,x)   (Maze[y][x] == SPACE)
   41: # define        ODD(n)         ((n) & 01)
   42: 
   43: static  int      candig(int, int);
   44: static  void     dig(int, int);
   45: static  void     dig_maze(int, int);
   46: static  void     remap(void);
   47: 
   48: void
   49: makemaze()
   50: {
   51:         char   *sp;
   52:         int    y, x;
   53: 
   54:         /*
   55:          * fill maze with walls
   56:          */
   57:         sp = &Maze[0][0];
   58:         while (sp < &Maze[HEIGHT - 1][WIDTH])
   59:                 *sp++ = DOOR;
   60: 
   61:         x = rand_num(WIDTH / 2) * 2 + 1;
   62:         y = rand_num(HEIGHT / 2) * 2 + 1;
   63:         dig_maze(x, y);
   64:         remap();
   65: }
   66: 
   67: # define        NPERM  24
   68: # define        NDIR   4
   69: 
   70: int     dirs[NPERM][NDIR] = {
   71:                 {0,1,2,3},    {3,0,1,2}, {0,2,3,1},      {0,3,2,1},
   72:                 {1,0,2,3},    {2,3,0,1}, {0,2,1,3},      {2,3,1,0},
   73:                 {1,0,3,2},    {1,2,0,3}, {3,1,2,0},      {2,0,3,1},
   74:                 {1,3,0,2},    {0,3,1,2}, {1,3,2,0},      {2,0,1,3},
   75:                 {0,1,3,2},    {3,1,0,2}, {2,1,0,3},      {1,2,3,0},
   76:                 {2,1,3,0},    {3,0,2,1}, {3,2,0,1},      {3,2,1,0}
   77:         };
   78: 
   79: int     incr[NDIR][2] = {
   80:                 {0, 1}, {1, 0}, {0, -1}, {-1, 0}
   81:         };
   82: 
   83: static void
   84: dig(y, x)
   85:         int    y, x;
   86: {
   87:         int    *dp;
   88:         int    *ip;
   89:         int    ny, nx;
   90:         int    *endp;
   91: 
   92:         Maze[y][x] = SPACE;                    /* Clear this spot */
   93:         dp = dirs[rand_num(NPERM)];
   94:         endp = &dp[NDIR];
   95:         while (dp < endp) {
   96:                 ip = &incr[*dp++][0];
   97:                 ny = y + *ip++;
   98:                 nx = x + *ip;
   99:                 if (candig(ny, nx))
  100:                         dig(ny, nx);
  101:         }
  102: }
  103: 
  104: /*
  105:  * candig:
  106:  *      Is it legal to clear this spot?
  107:  */
  108: static int
  109: candig(y, x)
  110:         int    y, x;
  111: {
  112:         int    i;
  113: 
  114:         if (ODD(x) && ODD(y))
  115:                 return FALSE;         /* can't touch ODD spots */
  116: 
  117:         if (y < UBOUND || y >= DBOUND)
  118:                 return FALSE;         /* Beyond vertical bounds, NO */
  119:         if (x < LBOUND || x >= RBOUND)
  120:                 return FALSE;         /* Beyond horizontal bounds, NO */
  121: 
  122:         if (ISCLEAR(y, x))
  123:                 return FALSE;         /* Already clear, NO */
  124: 
  125:         i = ISCLEAR(y, x + 1);
  126:         i += ISCLEAR(y, x - 1);
  127:         if (i > 1)
  128:                 return FALSE;         /* Introduces cycle, NO */
  129:         i += ISCLEAR(y + 1, x);
  130:         if (i > 1)
  131:                 return FALSE;         /* Introduces cycle, NO */
  132:         i += ISCLEAR(y - 1, x);
  133:         if (i > 1)
  134:                 return FALSE;         /* Introduces cycle, NO */
  135: 
  136:         return TRUE;                   /* OK */
  137: }
  138: 
  139: void
  140: dig_maze(x, y)
  141:         int    x, y;
  142: {
  143:         int    tx, ty;
  144:         int    i, j;
  145:         int    order[4];
  146: #define MNORTH  0x1
  147: #define MSOUTH  0x2
  148: #define MEAST   0x4
  149: #define MWEST   0x8
  150: 
  151:         tx = ty = 0;
  152:         Maze[y][x] = SPACE;
  153:         order[0] = MNORTH;
  154:         for (i = 1; i < 4; i++) {
  155:                 j = rand_num(i + 1);
  156:                 order[i] = order[j];
  157:                 order[j] = 0x1 << i;
  158:         }
  159:         for (i = 0; i < 4; i++) {
  160:                 switch (order[i]) {
  161:                   case MNORTH:
  162:                         tx = x;
  163:                         ty = y - 2;
  164:                         break;
  165:                   case MSOUTH:
  166:                         tx = x;
  167:                         ty = y + 2;
  168:                         break;
  169:                   case MEAST:
  170:                         tx = x + 2;
  171:                         ty = y;
  172:                         break;
  173:                   case MWEST:
  174:                         tx = x - 2;
  175:                         ty = y;
  176:                         break;
  177:                 }
  178:                 if (tx < 0 || ty < 0 || tx >= WIDTH || ty >= HEIGHT)
  179:                         continue;
  180:                 if (Maze[ty][tx] == SPACE)
  181:                         continue;
  182:                 Maze[(y + ty) / 2][(x + tx) / 2] = SPACE;
  183:                 dig_maze(tx, ty);
  184:         }
  185: }
  186: 
  187: void
  188: remap()
  189: {
  190:         int    y, x;
  191:         char   *sp;
  192:         int    stat;
  193: 
  194:         for (y = 0; y < HEIGHT; y++)
  195:                 for (x = 0; x < WIDTH; x++) {
  196:                         sp = &Maze[y][x];
  197:                         if (*sp == SPACE)
  198:                                 continue;
  199:                         stat = 0;
  200:                         if (y - 1 >= 0 && Maze[y - 1][x] != SPACE)
  201:                                 stat |= NORTH;
  202:                         if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE)
  203:                                 stat |= SOUTH;
  204:                         if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE)
  205:                                 stat |= EAST;
  206:                         if (x - 1 >= 0 && Maze[y][x - 1] != SPACE)
  207:                                 stat |= WEST;
  208:                         switch (stat) {
  209:                           case WEST | EAST:
  210:                           case EAST:
  211:                           case WEST:
  212:                                 *sp = WALL1;
  213:                                 break;
  214:                           case NORTH | SOUTH:
  215:                           case NORTH:
  216:                           case SOUTH:
  217:                                 *sp = WALL2;
  218:                                 break;
  219:                           case 0:
  220: # ifdef RANDOM
  221:                                 *sp = DOOR;
  222: # endif
  223: # ifdef REFLECT
  224:                                 *sp = rand_num(2) ? WALL4 : WALL5;
  225: # endif
  226:                                 break;
  227:                           default:
  228:                                 *sp = WALL3;
  229:                                 break;
  230:                         }
  231:                 }
  232:         memcpy(Orig_maze, Maze, sizeof Maze);
  233: }