1 /* 2 * Copyright (c) 1983-2003, Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * + Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * + Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * + Neither the name of the University of California, San Francisco nor 15 * the names of its contributors may be used to endorse or promote 16 * products derived from this software without specific prior written 17 * permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 20 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 22 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 * 31 * $OpenBSD: makemaze.c,v 1.6 2003/06/11 08:45:33 pjanzen Exp $ 32 * $NetBSD: makemaze.c,v 1.2 1997/10/10 16:33:43 lukem Exp $ 33 * $DragonFly: src/games/hunt/huntd/makemaze.c,v 1.2 2008/09/04 16:12:51 swildner Exp $ 34 */ 35 36 #include <string.h> 37 38 #include "hunt.h" 39 #include "server.h" 40 #include "conf.h" 41 42 # define ISCLEAR(y,x) (Maze[y][x] == SPACE) 43 # define ODD(n) ((n) & 01) 44 45 static int candig(int, int); 46 static void dig(int, int); 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 int dirs[NPERM][NDIR] = { 73 {0,1,2,3}, {3,0,1,2}, {0,2,3,1}, {0,3,2,1}, 74 {1,0,2,3}, {2,3,0,1}, {0,2,1,3}, {2,3,1,0}, 75 {1,0,3,2}, {1,2,0,3}, {3,1,2,0}, {2,0,3,1}, 76 {1,3,0,2}, {0,3,1,2}, {1,3,2,0}, {2,0,1,3}, 77 {0,1,3,2}, {3,1,0,2}, {2,1,0,3}, {1,2,3,0}, 78 {2,1,3,0}, {3,0,2,1}, {3,2,0,1}, {3,2,1,0} 79 }; 80 81 int incr[NDIR][2] = { 82 {0, 1}, {1, 0}, {0, -1}, {-1, 0} 83 }; 84 85 static void 86 dig(int y, int x) 87 { 88 int *dp; 89 int *ip; 90 int ny, nx; 91 int *endp; 92 93 Maze[y][x] = SPACE; /* Clear this spot */ 94 dp = dirs[rand_num(NPERM)]; 95 endp = &dp[NDIR]; 96 while (dp < endp) { 97 ip = &incr[*dp++][0]; 98 ny = y + *ip++; 99 nx = x + *ip; 100 if (candig(ny, nx)) 101 dig(ny, nx); 102 } 103 } 104 105 /* 106 * candig: 107 * Is it legal to clear this spot? 108 */ 109 static int 110 candig(int y, int 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 static void 140 dig_maze(int x, int y) 141 { 142 int tx, ty; 143 int i, j; 144 int order[4]; 145 #define MNORTH 0x1 146 #define MSOUTH 0x2 147 #define MEAST 0x4 148 #define MWEST 0x8 149 150 tx = ty = 0; 151 Maze[y][x] = SPACE; 152 order[0] = MNORTH; 153 for (i = 1; i < 4; i++) { 154 j = rand_num(i + 1); 155 order[i] = order[j]; 156 order[j] = 0x1 << i; 157 } 158 for (i = 0; i < 4; i++) { 159 switch (order[i]) { 160 case MNORTH: 161 tx = x; 162 ty = y - 2; 163 break; 164 case MSOUTH: 165 tx = x; 166 ty = y + 2; 167 break; 168 case MEAST: 169 tx = x + 2; 170 ty = y; 171 break; 172 case MWEST: 173 tx = x - 2; 174 ty = y; 175 break; 176 } 177 if (tx < 0 || ty < 0 || tx >= WIDTH || ty >= HEIGHT) 178 continue; 179 if (Maze[ty][tx] == SPACE) 180 continue; 181 Maze[(y + ty) / 2][(x + tx) / 2] = SPACE; 182 dig_maze(tx, ty); 183 } 184 } 185 186 static void 187 remap(void) 188 { 189 int y, x; 190 char *sp; 191 int stat; 192 193 for (y = 0; y < HEIGHT; y++) 194 for (x = 0; x < WIDTH; x++) { 195 sp = &Maze[y][x]; 196 if (*sp == SPACE) 197 continue; 198 /* Find occupied adjacent cells. */ 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 if (conf_random) 221 *sp = DOOR; 222 if (conf_reflect) 223 *sp = rand_num(2) ? WALL4 : WALL5; 224 break; 225 default: 226 *sp = WALL3; /* + */ 227 break; 228 } 229 } 230 memcpy(Orig_maze, Maze, sizeof Orig_maze); 231 } 232