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

Diff Legend

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