ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/random_maps/maze_gen.C
(Generate patch)

Comparing deliantra/server/random_maps/maze_gen.C (file contents):
Revision 1.8 by root, Fri Apr 11 21:09:53 2008 UTC vs.
Revision 1.12 by root, Thu May 8 14:20:19 2008 UTC

… …
32int wall_chance; 32int wall_chance;
33 33
34/* the outsize interface routine: accepts sizes, returns a char 34/* the outsize interface routine: accepts sizes, returns a char
35** maze. option is a flag for either a sparse or a full maze. Sparse 35** maze. option is a flag for either a sparse or a full maze. Sparse
36mazes have sizable rooms. option = 1, full, 0, sparse.*/ 36mazes have sizable rooms. option = 1, full, 0, sparse.*/
37 37void
38Maze 38maze_gen (Layout maze, int option)
39maze_gen (int xsize, int ysize, int option)
40{ 39{
41 int i, j; 40 maze->clear ();
42 41 maze->border ();
43 Maze maze (xsize, ysize);
44
45 /* write the outer walls */
46 for (i = 0; i < xsize; i++) maze[i][0] = maze[i][ysize - 1] = '#';
47 for (j = 0; j < ysize; j++) maze[0][j] = maze[xsize - 1][j] = '#';
48 42
49 /* find how many free wall spots there are */ 43 /* find how many free wall spots there are */
50 wall_free_size = 2 * (xsize - 4) + 2 * (ysize - 4); 44 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
51 45
52 make_wall_free_list (xsize, ysize); 46 make_wall_free_list (maze->w, maze->h);
53 47
54 /* return the empty maze */ 48 /* return the empty maze */
55 if (wall_free_size <= 0) 49 if (wall_free_size <= 0)
56 return maze; 50 return;
57 51
58 /* recursively generate the walls of the maze */ 52 /* recursively generate the walls of the maze */
59 /* first pop a random starting point */ 53 /* first pop a random starting point */
60 while (wall_free_size > 0) 54 while (wall_free_size > 0)
61 { 55 {
56 int i, j;
57
62 pop_wall_point (&i, &j); 58 pop_wall_point (&i, &j);
63 59
64 if (option) 60 if (option)
65 fill_maze_full (maze, i, j, xsize, ysize); 61 fill_maze_full (maze, i, j, maze->w, maze->h);
66 else 62 else
67 fill_maze_sparse (maze, i, j, xsize, ysize); 63 fill_maze_sparse (maze, i, j, maze->w, maze->h);
68 } 64 }
69 65
70 /* clean up our intermediate data structures. */ 66 /* clean up our intermediate data structures. */
71 67
72 free (wall_x_list); 68 free (wall_x_list);
73 free (wall_y_list); 69 free (wall_y_list);
74
75 return maze;
76} 70}
77 71
78/* the free wall points are those outer points which aren't corners or 72/* the free wall points are those outer points which aren't corners or
79 near corners, and don't have a maze wall growing out of them already. */ 73 near corners, and don't have a maze wall growing out of them already. */
80void 74void
… …
115 109
116/* randomly returns one of the elements from the wall point list */ 110/* randomly returns one of the elements from the wall point list */
117void 111void
118pop_wall_point (int *x, int *y) 112pop_wall_point (int *x, int *y)
119{ 113{
120 int index = rndm (wall_free_size); 114 int index = rmg_rndm (wall_free_size);
121 115
122 *x = wall_x_list[index]; 116 *x = wall_x_list[index];
123 *y = wall_y_list[index]; 117 *y = wall_y_list[index];
124 /* write the last array point here */ 118 /* write the last array point here */
125 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 119 wall_x_list[index] = wall_x_list[wall_free_size - 1];
… …
131we can place a new block without closing a path. We may only look 125we can place a new block without closing a path. We may only look
132up, down, right, or left. */ 126up, down, right, or left. */
133int 127int
134find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) 128find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
135{ 129{
136
137/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 130 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
138 int dirlist[4]; 131 int dirlist[4];
139 int count = 0; /* # elements in dirlist */ 132 int count = 0; /* # elements in dirlist */
140 133
141 /* look up */ 134 /* look up */
142 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */ 135 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
… …
144 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1]; 137 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
145 138
146 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2]; 139 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
147 140
148 if (cleartest == 0) 141 if (cleartest == 0)
149 {
150 dirlist[count] = 1; 142 dirlist[count++] = 1;
151 count++;
152 }
153 } 143 }
154
155 144
156 /* look down */ 145 /* look down */
157 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */ 146 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
158 { 147 {
159 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1]; 148 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
160 149
161 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2]; 150 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
162 151
163 if (cleartest == 0) 152 if (cleartest == 0)
164 {
165 dirlist[count] = 2; 153 dirlist[count++] = 2;
166 count++;
167 }
168 } 154 }
169
170 155
171 /* look right */ 156 /* look right */
172 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */ 157 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
173 { 158 {
174 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1]; 159 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
175 160
176 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1]; 161 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
177 162
178 if (cleartest == 0) 163 if (cleartest == 0)
179 {
180 dirlist[count] = 3; 164 dirlist[count++] = 3;
181 count++;
182 }
183 } 165 }
184
185 166
186 /* look left */ 167 /* look left */
187 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */ 168 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
188 { 169 {
189 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1]; 170 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
190 171
191 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1]; 172 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
192 173
193 if (cleartest == 0) 174 if (cleartest == 0)
194 {
195 dirlist[count] = 4; 175 dirlist[count++] = 4;
196 count++;
197 }
198 } 176 }
199 177
200 if (count == 0) 178 if (count == 0)
201 return -1; /* failed to find any clear points */ 179 return -1; /* failed to find any clear points */
202 180
203 /* choose a random direction */ 181 /* choose a random direction */
204 if (count > 1)
205 count = rndm (count);
206 else
207 count = 0;
208
209 switch (dirlist[count]) 182 switch (dirlist [rmg_rndm (count)])
210 { 183 {
211 case 1: /* up */ 184 case 1: /* up */
212 {
213 *y = yc + 1; 185 *y = yc + 1;
214 *x = xc; 186 *x = xc;
215 break; 187 break;
216 }; 188
217 case 2: /* down */ 189 case 2: /* down */
218 {
219 *y = yc - 1; 190 *y = yc - 1;
220 *x = xc; 191 *x = xc;
221 break; 192 break;
222 }; 193
223 case 3: /* right */ 194 case 3: /* right */
224 {
225 *y = yc; 195 *y = yc;
226 *x = xc + 1; 196 *x = xc + 1;
227 break; 197 break;
228 } 198
229 case 4: /* left */ 199 case 4: /* left */
230 {
231 *x = xc - 1; 200 *x = xc - 1;
232 *y = yc; 201 *y = yc;
233 break; 202 break;
234 } 203
235 default: /* ??? */ 204 default: /* ??? */
236 return -1; 205 return -1;
237 206
238 } 207 }
208
239 return 1; 209 return 1;
240} 210}
241 211
242/* recursive routine which will fill every available space in the maze 212/* recursive routine which will fill every available space in the maze
243 with walls*/ 213 with walls*/
244
245void 214void
246fill_maze_full (char **maze, int x, int y, int xsize, int ysize) 215fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
247{ 216{
248 int xc, yc; 217 int xc, yc;
249 218
250 /* write a wall here */ 219 /* write a wall here */
251 maze[x][y] = '#'; 220 maze[x][y] = '#';
252 221
253 /* decide if we're going to pick from the wall_free_list */ 222 /* decide if we're going to pick from the wall_free_list */
254 if (rndm (4) && wall_free_size > 0) 223 if (rmg_rndm (4) && wall_free_size > 0)
255 { 224 {
256 pop_wall_point (&xc, &yc); 225 pop_wall_point (&xc, &yc);
257 fill_maze_full (maze, xc, yc, xsize, ysize); 226 fill_maze_full (maze, xc, yc, xsize, ysize);
258 } 227 }
259 228
260 /* change the if to a while for a complete maze. */ 229 /* change the if to a while for a complete maze. */
261 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 230 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
262 {
263 fill_maze_full (maze, xc, yc, xsize, ysize); 231 fill_maze_full (maze, xc, yc, xsize, ysize);
264 }
265} 232}
266 233
267/* recursive routine which will fill much of the maze, but will leave 234/* recursive routine which will fill much of the maze, but will leave
268 some free spots (possibly large) toward the center.*/ 235 some free spots (possibly large) toward the center.*/
269void 236void
… …
273 240
274 /* write a wall here */ 241 /* write a wall here */
275 maze[x][y] = '#'; 242 maze[x][y] = '#';
276 243
277 /* decide if we're going to pick from the wall_free_list */ 244 /* decide if we're going to pick from the wall_free_list */
278 if (rndm (4) && wall_free_size > 0) 245 if (rmg_rndm (4) && wall_free_size > 0)
279 { 246 {
280 pop_wall_point (&xc, &yc); 247 pop_wall_point (&xc, &yc);
281 fill_maze_sparse (maze, xc, yc, xsize, ysize); 248 fill_maze_sparse (maze, xc, yc, xsize, ysize);
282 } 249 }
283 250
284 /* change the if to a while for a complete maze. */ 251 /* change the if to a while for a complete maze. */
285 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 252 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
286 fill_maze_sparse (maze, xc, yc, xsize, ysize); 253 fill_maze_sparse (maze, xc, yc, xsize, ysize);
287} 254}
255

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines