1195331Simp/* $NetBSD: makemaze.c,v 1.7 2009/08/12 07:42:11 dholland Exp $ */ 2195331Simp/* 3195331Simp * Copyright (c) 1983-2003, Regents of the University of California. 4195331Simp * All rights reserved. 5195331Simp * 6195331Simp * Redistribution and use in source and binary forms, with or without 7195331Simp * modification, are permitted provided that the following conditions are 8195331Simp * met: 9195331Simp * 10195331Simp * + Redistributions of source code must retain the above copyright 11195331Simp * notice, this list of conditions and the following disclaimer. 12195331Simp * + Redistributions in binary form must reproduce the above copyright 13195331Simp * notice, this list of conditions and the following disclaimer in the 14195331Simp * documentation and/or other materials provided with the distribution. 15195331Simp * + Neither the name of the University of California, San Francisco nor 16195331Simp * the names of its contributors may be used to endorse or promote 17195331Simp * products derived from this software without specific prior written 18195331Simp * permission. 19195331Simp * 20195331Simp * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 21195331Simp * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22195331Simp * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 23195331Simp * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 24195331Simp * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 25195331Simp * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 26195331Simp * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27195331Simp * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28211158Sneel * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29195331Simp * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 30195331Simp * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31195331Simp */ 32195331Simp 33195331Simp#include <sys/cdefs.h> 34195331Simp#ifndef lint 35195331Simp__RCSID("$NetBSD: makemaze.c,v 1.7 2009/08/12 07:42:11 dholland Exp $"); 36195331Simp#endif /* not lint */ 37195331Simp 38195331Simp#include "hunt.h" 39195331Simp 40195331Simp#define ISCLEAR(y,x) (Maze[y][x] == SPACE) 41195331Simp#define ODD(n) ((n) & 01) 42195331Simp 43195331Simp#if 0 44195331Simpstatic int candig(int, int); 45211158Sneelstatic void dig(int, int); 46211158Sneel#endif 47195331Simpstatic void dig_maze(int, int); 48211158Sneelstatic void remap(void); 49195331Simp 50195331Simpvoid 51195331Simpmakemaze(void) 52195331Simp{ 53195331Simp char *sp; 54195331Simp int y, x; 55211158Sneel 56195331Simp /* 57195331Simp * fill maze with walls 58211158Sneel */ 59195331Simp sp = &Maze[0][0]; 60195331Simp while (sp < &Maze[HEIGHT - 1][WIDTH]) 61195331Simp *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 73static 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 82static int incr[NDIR][2] = { 83 {0, 1}, {1, 0}, {0, -1}, {-1, 0} 84}; 85 86 87static void 88dig(int y, int x) 89{ 90 int *dp; 91 int *ip; 92 int ny, nx; 93 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 */ 111static int 112candig(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 142void 143dig_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 189void 190remap(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