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