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.5 by root, Sun Dec 31 19:02:24 2006 UTC vs.
Revision 1.14 by root, Fri Nov 6 13:03:34 2009 UTC

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

Diff Legend

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