1 /* $OpenBSD: makemaze.c,v 1.4 2001/02/13 11:55:11 pjanzen Exp $ */ 2 /* $NetBSD: makemaze.c,v 1.2 1997/10/10 16:33:43 lukem Exp $ */ 3 /* 4 * Hunt 5 * Copyright (c) 1985 Conrad C. Huang, Gregory S. Couch, Kenneth C.R.C. Arnold 6 * San Francisco, California 7 */ 8 9 #include <string.h> 10 11 #include "hunt.h" 12 #include "server.h" 13 #include "conf.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 static 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 static 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 /* Find occupied adjacent cells. */ 175 stat = 0; 176 if (y - 1 >= 0 && Maze[y - 1][x] != SPACE) 177 stat |= NORTH; 178 if (y + 1 < HEIGHT && Maze[y + 1][x] != SPACE) 179 stat |= SOUTH; 180 if (x + 1 < WIDTH && Maze[y][x + 1] != SPACE) 181 stat |= EAST; 182 if (x - 1 >= 0 && Maze[y][x - 1] != SPACE) 183 stat |= WEST; 184 switch (stat) { 185 case WEST | EAST: 186 case EAST: 187 case WEST: 188 *sp = WALL1; /* - */ 189 break; 190 case NORTH | SOUTH: 191 case NORTH: 192 case SOUTH: 193 *sp = WALL2; /* | */ 194 break; 195 case 0: 196 if (conf_random) 197 *sp = DOOR; 198 if (conf_reflect) 199 *sp = rand_num(2) ? WALL4 : WALL5; 200 break; 201 default: 202 *sp = WALL3; /* + */ 203 break; 204 } 205 } 206 memcpy(Orig_maze, Maze, sizeof Orig_maze); 207 } 208