hunt/huntd/makemaze.c

   1 /*      $NetBSD: makemaze.c,v 1.12 2021/05/02 12:50:45 rillig 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.12 2021/05/02 12:50:45 rillig 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 #if 0
  44
  45 #define NPERM   24
  46 #define NDIR    4
  47
  48 static const int dirs[NPERM][NDIR] = {
  49         {0,1,2,3},      {3,0,1,2},      {0,2,3,1},      {0,3,2,1},
  50         {1,0,2,3},      {2,3,0,1},      {0,2,1,3},      {2,3,1,0},
  51         {1,0,3,2},      {1,2,0,3},      {3,1,2,0},      {2,0,3,1},
  52         {1,3,0,2},      {0,3,1,2},      {1,3,2,0},      {2,0,1,3},
  53         {0,1,3,2},      {3,1,0,2},      {2,1,0,3},      {1,2,3,0},
  54         {2,1,3,0},      {3,0,2,1},      {3,2,0,1},      {3,2,1,0}
  55 };
  56
  57 static const int incr[NDIR][2] = {
  58         {0, 1}, {1, 0}, {0, -1}, {-1, 0}
  59 };
  60
  61
  62 /*
  63  * candig:
  64  *      Is it legal to clear this spot?
  65  */
  66 static bool
  67 candig(int y, int x)
  68 {
  69         int i;
  70
  71         if (ODD(x) && ODD(y))
  72                 return false;           /* can't touch ODD spots */
  73
  74         if (y < UBOUND || y >= DBOUND)
  75                 return false;           /* Beyond vertical bounds, NO */
  76         if (x < LBOUND || x >= RBOUND)
  77                 return false;           /* Beyond horizontal bounds, NO */
  78
  79         if (ISCLEAR(y, x))
  80                 return false;           /* Already clear, NO */
  81
  82         i = ISCLEAR(y, x + 1);
  83         i += ISCLEAR(y, x - 1);
  84         if (i > 1)
  85                 return false;           /* Introduces cycle, NO */
  86         i += ISCLEAR(y + 1, x);
  87         if (i > 1)
  88                 return false;           /* Introduces cycle, NO */
  89         i += ISCLEAR(y - 1, x);
  90         if (i > 1)
  91                 return false;           /* Introduces cycle, NO */
  92
  93         return true;                    /* OK */
  94 }
  95
  96 static void
  97 dig(int y, int x)
  98 {
  99         const int *dp;
 100         const int *ip;
 101         int ny, nx;
 102         const int *endp;
 103
 104         Maze[y][x] = SPACE;                     /* Clear this spot */
 105         dp = dirs[rand_num(NPERM)];
 106         endp = &dp[NDIR];
 107         while (dp < endp) {
 108                 ip = &incr[*dp++][0];
 109                 ny = y + *ip++;
 110                 nx = x + *ip;
 111                 if (candig(ny, nx))
 112                         dig(ny, nx);
 113         }
 114 }
 115 #endif
 116
 117 static void
 118 dig_maze(int x, int y)
 119 {
 120         int tx, ty;
 121         int i, j;
 122         int order[4];
 123 #define MNORTH  0x1
 124 #define MSOUTH  0x2
 125 #define MEAST   0x4
 126 #define MWEST   0x8
 127
 128         tx = ty = 0;
 129         Maze[y][x] = SPACE;
 130         order[0] = MNORTH;
 131         for (i = 1; i < 4; i++) {
 132                 j = rand_num(i + 1);
 133                 order[i] = order[j];
 134                 order[j] = 0x1 << i;
 135         }
 136         for (i = 0; i < 4; i++) {
 137                 switch (order[i]) {
 138                   case MNORTH:
 139                         tx = x;
 140                         ty = y - 2;
 141                         break;
 142                   case MSOUTH:
 143                         tx = x;
 144                         ty = y + 2;
 145                         break;
 146                   case MEAST:
 147                         tx = x + 2;
 148                         ty = y;
 149                         break;
 150                   case MWEST:
 151                         tx = x - 2;
 152                         ty = y;
 153                         break;
 154                 }
 155                 if (tx < 0 || ty < 0 || tx >= WIDTH || ty >= HEIGHT)
 156                         continue;
 157                 if (Maze[ty][tx] == SPACE)
 158                         continue;
 159                 Maze[(y + ty) / 2][(x + tx) / 2] = SPACE;
 160                 dig_maze(tx, ty);
 161         }
 162 }
 163
 164 static void
 165 remap(void)
 166 {
 167         int y, x;
 168         char *sp;
 169         int stat;
 170
 171         for (y = 0; y < HEIGHT; y++)
 172                 for (x = 0; x < WIDTH; x++) {
 173                         sp = &Maze[y][x];
 174                         if (*sp == SPACE)
 175                                 continue;
 176                         stat = 0;
 177                         if (y - 1 >= 0 && Maze[y - 1][x] != SPACE)
 178                                 stat |= NORTH;
 179                         if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE)
 180                                 stat |= SOUTH;
 181                         if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE)
 182                                 stat |= EAST;
 183                         if (x - 1 >= 0 && Maze[y][x - 1] != SPACE)
 184                                 stat |= WEST;
 185                         switch (stat) {
 186                           case WEST | EAST:
 187                           case EAST:
 188                           case WEST:
 189                                 *sp = WALL1;
 190                                 break;
 191                           case NORTH | SOUTH:
 192                           case NORTH:
 193                           case SOUTH:
 194                                 *sp = WALL2;
 195                                 break;
 196                           case 0:
 197 #ifdef RANDOM
 198                                 *sp = DOOR;
 199 #endif
 200 #ifdef REFLECT
 201                                 *sp = rand_num(2) ? WALL4 : WALL5;
 202 #endif
 203                                 break;
 204                           default:
 205                                 *sp = WALL3;
 206                                 break;
 207                         }
 208                 }
 209         memcpy(Orig_maze, Maze, sizeof Maze);
 210 }
 211
 212 void
 213 makemaze(void)
 214 {
 215         char *sp;
 216         int y, x;
 217
 218         /*
 219          * fill maze with walls
 220          */
 221         sp = &Maze[0][0];
 222         while (sp < &Maze[HEIGHT - 1][WIDTH])
 223                 *sp++ = DOOR;
 224
 225         x = rand_num(WIDTH / 2) * 2 + 1;
 226         y = rand_num(HEIGHT / 2) * 2 + 1;
 227         dig_maze(x, y);
 228         remap();
 229 }