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.17 by root, Sat Jun 26 23:53:31 2010 UTC vs.
Revision 1.22 by root, Tue Jun 29 18:27:02 2010 UTC

… …
35 35
36/* we need to maintain a list of wall points to generate 36/* we need to maintain a list of wall points to generate
37 reasonable mazes: a straightforward recursive random walk maze 37 reasonable mazes: a straightforward recursive random walk maze
38 generator would generate a map with a trivial circle-the-outer-wall solution */ 38 generator would generate a map with a trivial circle-the-outer-wall solution */
39 39
40#include <vector>
41
40#include <global.h> 42#include <global.h>
41 43
42#include "random_map.h" 44#include "random_map.h"
43#include "rproto.h" 45#include "rproto.h"
44 46
47struct point
48{
49 short x;
50 short y;
51
52 point ()
53 {
54 }
55
56 point (int x, int y)
57 : x(x), y(y)
58 {
59 }
60};
61
45/* global variables that everyone needs: don't want to pass them in 62/* global variables that everyone needs: don't want to pass them in
46 as parameters every time. */ 63 as parameters every time. */
47static int *wall_x_list = 0; 64static point *seed_list;
48static int *wall_y_list = 0; 65static int seed_max, seed_size;
49static int wall_free_size = 0; 66static int xsize, ysize;
67static char **maze;
68
69static void
70push (point p)
71{
72 assert (seed_size < seed_max);
73
74 seed_list [seed_size++] = p;
75
76 maze [p.x][p.y] = '#';
77}
50 78
51/* the free wall points are those outer points which aren't corners or 79/* the free wall points are those outer points which aren't corners or
52 near corners, and don't have a maze wall growing out of them already. */ 80 near corners, and don't have a maze wall growing out of them already. */
53static void 81static void
54make_wall_free_list (int xsize, int ysize) 82push_walls ()
55{ 83{
56 int i, j, count;
57
58 count = 0; /* entries already placed in the free list */
59 /*allocate it */
60 if (wall_free_size < 0)
61 return;
62
63 wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
64 wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
65
66 /* top and bottom wall */ 84 /* top and bottom wall */
67 for (i = 2; i < xsize - 2; i++) 85 for (int x = 2; x < xsize - 2; x++)
68 { 86 {
69 wall_x_list[count] = i; 87 push (point (x, 0));
70 wall_y_list[count] = 0; 88 push (point (x, ysize - 1));
71 count++;
72 wall_x_list[count] = i;
73 wall_y_list[count] = ysize - 1;
74 count++;
75 } 89 }
76 90
77 /* left and right wall */ 91 /* left and right wall */
78 for (j = 2; j < ysize - 2; j++) 92 for (int y = 2; y < ysize - 2; y++)
79 { 93 {
80 wall_x_list[count] = 0; 94 push (point ( 0, y));
81 wall_y_list[count] = j; 95 push (point (xsize - 1, y));
82 count++;
83 wall_x_list[count] = xsize - 1;
84 wall_y_list[count] = j;
85 count++;
86 } 96 }
87} 97}
88 98
89/* randomly returns one of the elements from the wall point list */ 99/* randomly returns one of the elements from the wall point list */
90static void 100static point
91pop_wall_point (int *x, int *y) 101pop_rand ()
92{ 102{
93 int index = rmg_rndm (wall_free_size); 103 int index = rmg_rndm (seed_size);
94 104
95 *x = wall_x_list[index]; 105 point p = seed_list [index];
96 *y = wall_y_list[index];
97 106
98 /* write the last array point here */ 107 /* write the last array point here */
99 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 108 seed_list [index] = seed_list [--seed_size];
100 wall_y_list[index] = wall_y_list[wall_free_size - 1]; 109
101 wall_free_size--; 110 return p;
102} 111}
103 112
104/* find free point: randomly look for a square adjacent to this one where 113/* find free point: randomly look for a square adjacent to this one where
105we can place a new block without closing a path. We may only look 114we can place a new block without closing a path. We may only look
106up, down, right, or left. */ 115up, down, right, or left. */
107static int 116static int
108find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) 117find_free_point (point &p, point pc)
109{ 118{
110 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 119 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
111 int dirlist[4]; 120 int dirlist[4];
112 int count = 0; /* # elements in dirlist */ 121 int count = 0; /* # elements in dirlist */
113 122
123 int xc = pc.x;
124 int yc = pc.y;
125
114 /* look up */ 126 /* look up */
115 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */ 127 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
116 { 128 {
117 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1] 129 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
118 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2]; 130 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
… …
156 168
157 /* choose a random direction */ 169 /* choose a random direction */
158 switch (dirlist [rmg_rndm (count)]) 170 switch (dirlist [rmg_rndm (count)])
159 { 171 {
160 case 1: /* up */ 172 case 1: /* up */
173 p.x = xc;
161 *y = yc + 1; 174 p.y = yc + 1;
162 *x = xc;
163 break; 175 break;
164 176
165 case 2: /* down */ 177 case 2: /* down */
178 p.x = xc;
166 *y = yc - 1; 179 p.y = yc - 1;
167 *x = xc;
168 break; 180 break;
169 181
170 case 3: /* right */ 182 case 3: /* right */
171 *y = yc;
172 *x = xc + 1; 183 p.x = xc + 1;
184 p.y = yc;
173 break; 185 break;
174 186
175 case 4: /* left */ 187 case 4: /* left */
176 *x = xc - 1; 188 p.x = xc - 1;
177 *y = yc; 189 p.y = yc;
178 break; 190 break;
179 } 191 }
180 192
181 return 1; 193 return 1;
182}
183
184/* recursive routine which will fill every available space in the maze
185 with walls*/
186static void
187fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
188{
189 int xc, yc;
190
191 /* write a wall here */
192 maze[x][y] = '#';
193
194 /* decide if we're going to pick from the wall_free_list */
195 if (rmg_rndm (4) && wall_free_size > 0)
196 {
197 pop_wall_point (&xc, &yc);
198 fill_maze_full (maze, xc, yc, xsize, ysize);
199 }
200
201 /* change the while to an if for a sparse maze. */
202 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
203 fill_maze_full (maze, xc, yc, xsize, ysize);
204}
205
206/* recursive routine which will fill much of the maze, but will leave
207 some free spots (possibly large) toward the center.*/
208static void
209fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
210{
211 int xc, yc;
212
213 /* write a wall here */
214 maze[x][y] = '#';
215
216 /* decide if we're going to pick from the wall_free_list */
217 if (rmg_rndm (4) && wall_free_size > 0)
218 {
219 pop_wall_point (&xc, &yc);
220 fill_maze_sparse (maze, xc, yc, xsize, ysize);
221 }
222
223 /* change the if to a while for a complete maze. */
224 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
225 fill_maze_sparse (maze, xc, yc, xsize, ysize);
226} 194}
227 195
228/* the outsize interface routine: accepts sizes, returns a char 196/* the outsize interface routine: accepts sizes, returns a char
229** maze. option is a flag for either a sparse or a full maze. Sparse 197** maze. option is a flag for either a sparse or a full maze. Sparse
230mazes have sizable rooms. option = 1, full, 0, sparse.*/ 198mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
231void 199void
232maze_gen (Layout maze, int full) 200maze_gen (Layout maze, int subtype)
233{ 201{
202 xsize = maze->w;
203 ysize = maze->h;
204 ::maze = maze;
205
234 maze->clear (); 206 maze->clear ();
235 maze->border (); 207 maze->border ();
236 208
237 /* find how many free wall spots there are */ 209 if (xsize < 4 || ysize < 4)
238 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
239
240 make_wall_free_list (maze->w, maze->h);
241
242 /* return the empty maze */
243 if (wall_free_size <= 0)
244 return; 210 return;
211
212 seed_max = xsize * ysize;
213 seed_size = 0;
214 seed_list = salloc<point> (seed_max);
215
216 if (subtype > 0)
217 push_walls ();
218
219 if (subtype == 0 || subtype == 2)
220 for (int i = (xsize + ysize) / 2; i; --i)
221 push (point (rmg_rndm (1, xsize - 2), rmg_rndm (1, ysize - 2)));
222
223 bool full = subtype == 3;
245 224
246 /* recursively generate the walls of the maze */ 225 /* recursively generate the walls of the maze */
247 /* first pop a random starting point */ 226 /* first pop a random starting point */
248 while (wall_free_size > 0) 227 while (seed_size)
249 { 228 {
250 int i, j; 229 point p = pop_rand ();
251 230
252 pop_wall_point (&i, &j); 231 for (;;)
232 {
233 point pc;
253 234
235 maze [p.x][p.y] = '#';
236
237 if (find_free_point (pc, p) < 0)
238 break;
239
254 if (full) 240 if (full)
255 fill_maze_full (maze, i, j, maze->w, maze->h); 241 push (p);
256 else 242
257 fill_maze_sparse (maze, i, j, maze->w, maze->h); 243 if (!rmg_rndm (8))
244 {
245 if (!full)
246 push (pc);
247
248 break;
249 }
250
251 p = pc;
252 }
258 } 253 }
259 254
260 /* clean up our intermediate data structures. */ 255 /* clean up our intermediate data structures. */
261 256 sfree (seed_list, seed_max);
262 free (wall_x_list);
263 free (wall_y_list);
264} 257}
265 258
266#if 0 259#if 0
267static struct demo 260static struct demo
268{ 261{
269 demo () 262 demo ()
270 { 263 {
271 Layout layout (30, 30); 264 Layout layout (40, 25);
272 rmg_rndm.seed (time (0)); 265 rmg_rndm.seed (time (0));
273 266
274 for(int i=1;i<10;++i) 267 for(int i=1;i<10;++i)
275 { 268 {
276 maze_gen (layout, 1); 269 maze_gen (layout, 3);
277 layout.print (); 270 layout.print ();
278 } 271 }
279 exit (1); 272 exit (1);
280 } 273 }
281} demo; 274} demo;

Diff Legend

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