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.3 by root, Sun Sep 10 16:06:37 2006 UTC vs.
Revision 1.14 by root, Fri Nov 6 13:03:34 2009 UTC

1
2 1
3/* peterm@langmuir.eecs.berkeley.edu: this function generates a random 2/* peterm@langmuir.eecs.berkeley.edu: this function generates a random
4blocked maze with the property that there is only one path from one spot 3blocked maze with the property that there is only one path from one spot
5to any other, and there is always a path from one spot to any other. 4to any other, and there is always a path from one spot to any other.
6 5
… …
14 13
15/* we need to maintain a list of wall points to generate 14/* we need to maintain a list of wall points to generate
16 reasonable mazes: a straightforward recursive random walk maze 15 reasonable mazes: a straightforward recursive random walk maze
17 generator would generate a map with a trivial circle-the-outer-wall solution */ 16 generator would generate a map with a trivial circle-the-outer-wall solution */
18 17
19#include <stdio.h>
20#include <global.h> 18#include <global.h>
21 19
22/*#include <random_map.h>*/ 20#include "random_map.h"
23#include <maze_gen.h> 21#include "rproto.h"
24#include <time.h>
25
26
27/* this include solely, and only, is needed for the definition of RANDOM */
28
29
30 22
31/* global variables that everyone needs: don't want to pass them in 23/* global variables that everyone needs: don't want to pass them in
32 as parameters every time. */ 24 as parameters every time. */
33int *wall_x_list = 0; 25static int *wall_x_list = 0;
34int *wall_y_list = 0; 26static int *wall_y_list = 0;
35int wall_free_size = 0; 27static int wall_free_size = 0;
36 28
37/* heuristically, we need to change wall_chance based on the size of 29/* heuristically, we need to change wall_chance based on the size of
38 the maze. */ 30 the maze. */
39 31
40int wall_chance; 32static int wall_chance;
41
42/* the outsize interface routine: accepts sizes, returns a char
43** maze. option is a flag for either a sparse or a full maze. Sparse
44mazes have sizable rooms. option = 1, full, 0, sparse.*/
45
46char **
47maze_gen (int xsize, int ysize, int option)
48{
49 int i, j;
50
51 /* allocate that array, set it up */
52 char **maze = (char **) calloc (sizeof (char *), xsize);
53
54 for (i = 0; i < xsize; i++)
55 {
56 maze[i] = (char *) calloc (sizeof (char), ysize);
57 }
58
59 /* write the outer walls */
60 for (i = 0; i < xsize; i++)
61 maze[i][0] = maze[i][ysize - 1] = '#';
62 for (j = 0; j < ysize; j++)
63 maze[0][j] = maze[xsize - 1][j] = '#';
64
65
66 /* find how many free wall spots there are */
67 wall_free_size = 2 * (xsize - 4) + 2 * (ysize - 4);
68
69 make_wall_free_list (xsize, ysize);
70
71 /* return the empty maze */
72 if (wall_free_size <= 0)
73 return maze;
74
75 /* recursively generate the walls of the maze */
76 /* first pop a random starting point */
77 while (wall_free_size > 0)
78 {
79 pop_wall_point (&i, &j);
80 if (option)
81 fill_maze_full (maze, i, j, xsize, ysize);
82 else
83 fill_maze_sparse (maze, i, j, xsize, ysize);
84 }
85
86 /* clean up our intermediate data structures. */
87
88 free (wall_x_list);
89 free (wall_y_list);
90
91 return maze;
92}
93
94
95 33
96/* the free wall points are those outer points which aren't corners or 34/* the free wall points are those outer points which aren't corners or
97 near corners, and don't have a maze wall growing out of them already. */ 35 near corners, and don't have a maze wall growing out of them already. */
98 36static void
99void
100make_wall_free_list (int xsize, int ysize) 37make_wall_free_list (int xsize, int ysize)
101{ 38{
102 int i, j, count; 39 int i, j, count;
103 40
104 count = 0; /* entries already placed in the free list */ 41 count = 0; /* entries already placed in the free list */
105 /*allocate it */ 42 /*allocate it */
106 if (wall_free_size < 0) 43 if (wall_free_size < 0)
107 return; 44 return;
45
108 wall_x_list = (int *) calloc (sizeof (int), wall_free_size); 46 wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
109 wall_y_list = (int *) calloc (sizeof (int), wall_free_size); 47 wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
110
111 48
112 /* top and bottom wall */ 49 /* top and bottom wall */
113 for (i = 2; i < xsize - 2; i++) 50 for (i = 2; i < xsize - 2; i++)
114 { 51 {
115 wall_x_list[count] = i; 52 wall_x_list[count] = i;
… …
130 wall_y_list[count] = j; 67 wall_y_list[count] = j;
131 count++; 68 count++;
132 } 69 }
133} 70}
134 71
135
136
137/* randomly returns one of the elements from the wall point list */ 72/* randomly returns one of the elements from the wall point list */
138 73static void
139void
140pop_wall_point (int *x, int *y) 74pop_wall_point (int *x, int *y)
141{ 75{
142 int index = RANDOM () % wall_free_size; 76 int index = rmg_rndm (wall_free_size);
143 77
144 *x = wall_x_list[index]; 78 *x = wall_x_list[index];
145 *y = wall_y_list[index]; 79 *y = wall_y_list[index];
146 /* write the last array point here */ 80 /* write the last array point here */
147 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 81 wall_x_list[index] = wall_x_list[wall_free_size - 1];
148 wall_y_list[index] = wall_y_list[wall_free_size - 1]; 82 wall_y_list[index] = wall_y_list[wall_free_size - 1];
149 wall_free_size--; 83 wall_free_size--;
150} 84}
151 85
152
153
154/* find free point: randomly look for a square adjacent to this one where 86/* find free point: randomly look for a square adjacent to this one where
155we can place a new block without closing a path. We may only look 87we can place a new block without closing a path. We may only look
156up, down, right, or left. */ 88up, down, right, or left. */
157 89static int
158int
159find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) 90find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
160{ 91{
161
162/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 92 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
163 int dirlist[4]; 93 int dirlist[4];
164 int count = 0; /* # elements in dirlist */ 94 int count = 0; /* # elements in dirlist */
165 95
166 /* look up */ 96 /* look up */
167 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */ 97 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
… …
169 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1]; 99 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
170 100
171 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2]; 101 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
172 102
173 if (cleartest == 0) 103 if (cleartest == 0)
174 {
175 dirlist[count] = 1; 104 dirlist[count++] = 1;
176 count++;
177 }
178 } 105 }
179
180 106
181 /* look down */ 107 /* look down */
182 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */ 108 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
183 { 109 {
184 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1]; 110 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
185 111
186 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2]; 112 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
187 113
188 if (cleartest == 0) 114 if (cleartest == 0)
189 {
190 dirlist[count] = 2; 115 dirlist[count++] = 2;
191 count++;
192 }
193 } 116 }
194
195 117
196 /* look right */ 118 /* look right */
197 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */ 119 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
198 { 120 {
199 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1]; 121 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
200 122
201 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1]; 123 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
202 124
203 if (cleartest == 0) 125 if (cleartest == 0)
204 {
205 dirlist[count] = 3; 126 dirlist[count++] = 3;
206 count++;
207 }
208 } 127 }
209
210 128
211 /* look left */ 129 /* look left */
212 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */ 130 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
213 { 131 {
214 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1]; 132 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
215 133
216 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1]; 134 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
217 135
218 if (cleartest == 0) 136 if (cleartest == 0)
219 {
220 dirlist[count] = 4; 137 dirlist[count++] = 4;
221 count++;
222 }
223 } 138 }
224 139
225 if (count == 0) 140 if (count == 0)
226 return -1; /* failed to find any clear points */ 141 return -1; /* failed to find any clear points */
227 142
228 /* choose a random direction */ 143 /* choose a random direction */
229 if (count > 1)
230 count = RANDOM () % count;
231 else
232 count = 0;
233 switch (dirlist[count]) 144 switch (dirlist [rmg_rndm (count)])
234 { 145 {
235 case 1: /* up */ 146 case 1: /* up */
236 {
237 *y = yc + 1; 147 *y = yc + 1;
238 *x = xc; 148 *x = xc;
239 break; 149 break;
240 }; 150
241 case 2: /* down */ 151 case 2: /* down */
242 {
243 *y = yc - 1; 152 *y = yc - 1;
244 *x = xc; 153 *x = xc;
245 break; 154 break;
246 }; 155
247 case 3: /* right */ 156 case 3: /* right */
248 {
249 *y = yc; 157 *y = yc;
250 *x = xc + 1; 158 *x = xc + 1;
251 break; 159 break;
252 } 160
253 case 4: /* left */ 161 case 4: /* left */
254 {
255 *x = xc - 1; 162 *x = xc - 1;
256 *y = yc; 163 *y = yc;
257 break; 164 break;
258 } 165
259 default: /* ??? */ 166 default: /* ??? */
260 {
261 return -1; 167 return -1;
262 } 168
263 } 169 }
170
264 return 1; 171 return 1;
265} 172}
266 173
267/* recursive routine which will fill every available space in the maze 174/* recursive routine which will fill every available space in the maze
268 with walls*/ 175 with walls*/
269 176static void
270void
271fill_maze_full (char **maze, int x, int y, int xsize, int ysize) 177fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
272{ 178{
273 int xc, yc; 179 int xc, yc;
274 180
275 /* write a wall here */ 181 /* write a wall here */
276 maze[x][y] = '#'; 182 maze[x][y] = '#';
277 183
278 /* decide if we're going to pick from the wall_free_list */ 184 /* decide if we're going to pick from the wall_free_list */
279 if (RANDOM () % 4 && wall_free_size > 0) 185 if (rmg_rndm (4) && wall_free_size > 0)
280 { 186 {
281 pop_wall_point (&xc, &yc); 187 pop_wall_point (&xc, &yc);
282 fill_maze_full (maze, xc, yc, xsize, ysize); 188 fill_maze_full (maze, xc, yc, xsize, ysize);
283 } 189 }
284 190
285 /* change the if to a while for a complete maze. */ 191 /* change the if to a while for a complete maze. */
286 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 192 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
287 {
288 fill_maze_full (maze, xc, yc, xsize, ysize); 193 fill_maze_full (maze, xc, yc, xsize, ysize);
289 }
290} 194}
291
292 195
293/* recursive routine which will fill much of the maze, but will leave 196/* recursive routine which will fill much of the maze, but will leave
294 some free spots (possibly large) toward the center.*/ 197 some free spots (possibly large) toward the center.*/
295 198static void
296void
297fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize) 199fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
298{ 200{
299 int xc, yc; 201 int xc, yc;
300 202
301 /* write a wall here */ 203 /* write a wall here */
302 maze[x][y] = '#'; 204 maze[x][y] = '#';
303 205
304 /* decide if we're going to pick from the wall_free_list */ 206 /* decide if we're going to pick from the wall_free_list */
305 if (RANDOM () % 4 && wall_free_size > 0) 207 if (rmg_rndm (4) && wall_free_size > 0)
306 { 208 {
307 pop_wall_point (&xc, &yc); 209 pop_wall_point (&xc, &yc);
308 fill_maze_sparse (maze, xc, yc, xsize, ysize); 210 fill_maze_sparse (maze, xc, yc, xsize, ysize);
309 } 211 }
310 212
311 /* change the if to a while for a complete maze. */ 213 /* change the if to a while for a complete maze. */
312 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 214 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
313 {
314 fill_maze_sparse (maze, xc, yc, xsize, ysize); 215 fill_maze_sparse (maze, xc, yc, xsize, ysize);
216}
217
218/* the outsize interface routine: accepts sizes, returns a char
219** maze. option is a flag for either a sparse or a full maze. Sparse
220mazes have sizable rooms. option = 1, full, 0, sparse.*/
221void
222maze_gen (Layout maze, int option)
223{
224 maze->clear ();
225 maze->border ();
226
227 /* find how many free wall spots there are */
228 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
229
230 make_wall_free_list (maze->w, maze->h);
231
232 /* return the empty maze */
233 if (wall_free_size <= 0)
234 return;
235
236 /* recursively generate the walls of the maze */
237 /* first pop a random starting point */
238 while (wall_free_size > 0)
315 } 239 {
240 int i, j;
241
242 pop_wall_point (&i, &j);
243
244 if (option)
245 fill_maze_full (maze, i, j, maze->w, maze->h);
246 else
247 fill_maze_sparse (maze, i, j, maze->w, maze->h);
248 }
249
250 /* clean up our intermediate data structures. */
251
252 free (wall_x_list);
253 free (wall_y_list);
316} 254}
255

Diff Legend

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