1 /* $NetBSD: makemaze.c,v 1.2 1997/10/10 16:33:43 lukem Exp $ */ 2 /* 3 * Hunt 4 * Copyright (c) 1985 Conrad C. Huang, Gregory S. Couch, Kenneth C.R.C. Arnold 5 * San Francisco, California 6 */ 7 8 #include <sys/cdefs.h> 9 #ifndef lint 10 __RCSID("$NetBSD: makemaze.c,v 1.2 1997/10/10 16:33:43 lukem Exp $"); 11 #endif /* not lint */ 12 13 # include "hunt.h" 14 15 # define ISCLEAR(y,x) (Maze[y][x] == SPACE) 16 # define ODD(n) ((n) & 01) 17 18 static int candig __P((int, int)); 19 static void dig __P((int, int)); 20 static void dig_maze __P((int, int)); 21 static void remap __P((void)); 22 23 void 24 makemaze() 25 { 26 char *sp; 27 int y, x; 28 29 /* 30 * fill maze with walls 31 */ 32 sp = &Maze[0][0]; 33 while (sp < &Maze[HEIGHT - 1][WIDTH]) 34 *sp++ = DOOR; 35 36 x = rand_num(WIDTH / 2) * 2 + 1; 37 y = rand_num(HEIGHT / 2) * 2 + 1; 38 dig_maze(x, y); 39 remap(); 40 } 41 42 # define NPERM 24 43 # define NDIR 4 44 45 int dirs[NPERM][NDIR] = { 46 {0,1,2,3}, {3,0,1,2}, {0,2,3,1}, {0,3,2,1}, 47 {1,0,2,3}, {2,3,0,1}, {0,2,1,3}, {2,3,1,0}, 48 {1,0,3,2}, {1,2,0,3}, {3,1,2,0}, {2,0,3,1}, 49 {1,3,0,2}, {0,3,1,2}, {1,3,2,0}, {2,0,1,3}, 50 {0,1,3,2}, {3,1,0,2}, {2,1,0,3}, {1,2,3,0}, 51 {2,1,3,0}, {3,0,2,1}, {3,2,0,1}, {3,2,1,0} 52 }; 53 54 int incr[NDIR][2] = { 55 {0, 1}, {1, 0}, {0, -1}, {-1, 0} 56 }; 57 58 static void 59 dig(y, x) 60 int y, x; 61 { 62 int *dp; 63 int *ip; 64 int ny, nx; 65 int *endp; 66 67 Maze[y][x] = SPACE; /* Clear this spot */ 68 dp = dirs[rand_num(NPERM)]; 69 endp = &dp[NDIR]; 70 while (dp < endp) { 71 ip = &incr[*dp++][0]; 72 ny = y + *ip++; 73 nx = x + *ip; 74 if (candig(ny, nx)) 75 dig(ny, nx); 76 } 77 } 78 79 /* 80 * candig: 81 * Is it legal to clear this spot? 82 */ 83 static int 84 candig(y, x) 85 int y, x; 86 { 87 int i; 88 89 if (ODD(x) && ODD(y)) 90 return FALSE; /* can't touch ODD spots */ 91 92 if (y < UBOUND || y >= DBOUND) 93 return FALSE; /* Beyond vertical bounds, NO */ 94 if (x < LBOUND || x >= RBOUND) 95 return FALSE; /* Beyond horizontal bounds, NO */ 96 97 if (ISCLEAR(y, x)) 98 return FALSE; /* Already clear, NO */ 99 100 i = ISCLEAR(y, x + 1); 101 i += ISCLEAR(y, x - 1); 102 if (i > 1) 103 return FALSE; /* Introduces cycle, NO */ 104 i += ISCLEAR(y + 1, x); 105 if (i > 1) 106 return FALSE; /* Introduces cycle, NO */ 107 i += ISCLEAR(y - 1, x); 108 if (i > 1) 109 return FALSE; /* Introduces cycle, NO */ 110 111 return TRUE; /* OK */ 112 } 113 114 void 115 dig_maze(x, y) 116 int x, y; 117 { 118 int tx, ty; 119 int i, j; 120 int order[4]; 121 #define MNORTH 0x1 122 #define MSOUTH 0x2 123 #define MEAST 0x4 124 #define MWEST 0x8 125 126 tx = ty = 0; 127 Maze[y][x] = SPACE; 128 order[0] = MNORTH; 129 for (i = 1; i < 4; i++) { 130 j = rand_num(i + 1); 131 order[i] = order[j]; 132 order[j] = 0x1 << i; 133 } 134 for (i = 0; i < 4; i++) { 135 switch (order[i]) { 136 case MNORTH: 137 tx = x; 138 ty = y - 2; 139 break; 140 case MSOUTH: 141 tx = x; 142 ty = y + 2; 143 break; 144 case MEAST: 145 tx = x + 2; 146 ty = y; 147 break; 148 case MWEST: 149 tx = x - 2; 150 ty = y; 151 break; 152 } 153 if (tx < 0 || ty < 0 || tx >= WIDTH || ty >= HEIGHT) 154 continue; 155 if (Maze[ty][tx] == SPACE) 156 continue; 157 Maze[(y + ty) / 2][(x + tx) / 2] = SPACE; 158 dig_maze(tx, ty); 159 } 160 } 161 162 void 163 remap() 164 { 165 int y, x; 166 char *sp; 167 int stat; 168 169 for (y = 0; y < HEIGHT; y++) 170 for (x = 0; x < WIDTH; x++) { 171 sp = &Maze[y][x]; 172 if (*sp == SPACE) 173 continue; 174 stat = 0; 175 if (y - 1 >= 0 && Maze[y - 1][x] != SPACE) 176 stat |= NORTH; 177 if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE) 178 stat |= SOUTH; 179 if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE) 180 stat |= EAST; 181 if (x - 1 >= 0 && Maze[y][x - 1] != SPACE) 182 stat |= WEST; 183 switch (stat) { 184 case WEST | EAST: 185 case EAST: 186 case WEST: 187 *sp = WALL1; 188 break; 189 case NORTH | SOUTH: 190 case NORTH: 191 case SOUTH: 192 *sp = WALL2; 193 break; 194 case 0: 195 # ifdef RANDOM 196 *sp = DOOR; 197 # endif 198 # ifdef REFLECT 199 *sp = rand_num(2) ? WALL4 : WALL5; 200 # endif 201 break; 202 default: 203 *sp = WALL3; 204 break; 205 } 206 } 207 memcpy(Orig_maze, Maze, sizeof Maze); 208 } 209