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.19 by root, Sun Jun 27 16:36:12 2010 UTC vs.
Revision 1.29 by root, Mon Oct 29 23:55:54 2012 UTC

1/* 1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG. 2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 * 3 *
4 * Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team 4 * Copyright (©) 2005,2006,2007,2008,2009,2010,2011,2012 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) Crossfire Development Team (restored, original file without copyright notice) 5 * Copyright (©) 1994-2004 Crossfire Development Team (restored, original file without copyright notice)
6 * 6 *
7 * Deliantra is free software: you can redistribute it and/or modify it under 7 * Deliantra is free software: you can redistribute it and/or modify it under
8 * the terms of the Affero GNU General Public License as published by the 8 * the terms of the Affero GNU General Public License as published by the
9 * Free Software Foundation, either version 3 of the License, or (at your 9 * Free Software Foundation, either version 3 of the License, or (at your
10 * option) any later version. 10 * option) any later version.
11 * 11 *
12 * This program is distributed in the hope that it will be useful, 12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details. 15 * GNU General Public License for more details.
16 * 16 *
17 * You should have received a copy of the Affero GNU General Public License 17 * You should have received a copy of the Affero GNU General Public License
18 * and the GNU General Public License along with this program. If not, see 18 * and the GNU General Public License along with this program. If not, see
19 * <http://www.gnu.org/licenses/>. 19 * <http://www.gnu.org/licenses/>.
20 * 20 *
21 * The authors can be reached via e-mail to <support@deliantra.net> 21 * The authors can be reached via e-mail to <support@deliantra.net>
22 */ 22 */
23 23
24/* peterm@langmuir.eecs.berkeley.edu: this function generates a random 24/* peterm@langmuir.eecs.berkeley.edu: this function generates a random
25blocked maze with the property that there is only one path from one spot 25blocked maze with the property that there is only one path from one spot
… …
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 <rmg.h>
43#include "rproto.h" 45#include "rproto.h"
44 46
45/* global variables that everyone needs: don't want to pass them in 47/* global variables that everyone needs: don't want to pass them in
46 as parameters every time. */ 48 as parameters every time. */
47static int *wall_x_list = 0; 49static fixed_stack<point> seeds;
48static int *wall_y_list = 0;
49static int wall_free_size = 0;
50static int xsize, ysize; 50static int xsize, ysize;
51static char **maze;
52
53static void
54push (point p)
55{
56 seeds.push (p);
57 maze [p.x][p.y] = '#';
58}
59
60/* randomly returns one of the elements from the wall point list */
61static point
62pop_rand ()
63{
64 return seeds.remove (rmg_rndm (seeds.size));
65}
51 66
52/* the free wall points are those outer points which aren't corners or 67/* the free wall points are those outer points which aren't corners or
53 near corners, and don't have a maze wall growing out of them already. */ 68 near corners, and don't have a maze wall growing out of them already. */
54static void 69static void
55make_wall_free_list (int xsize, int ysize) 70push_walls ()
56{ 71{
57 int i, j, count;
58
59 count = 0; /* entries already placed in the free list */
60 /*allocate it */
61 if (wall_free_size < 0)
62 return;
63
64 wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
65 wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
66
67 /* top and bottom wall */ 72 /* top and bottom wall */
68 for (i = 2; i < xsize - 2; i++) 73 for (int x = 2; x < xsize - 2; x++)
69 { 74 {
70 wall_x_list[count] = i; 75 push (point (x, 0));
71 wall_y_list[count] = 0; 76 push (point (x, ysize - 1));
72 count++;
73 wall_x_list[count] = i;
74 wall_y_list[count] = ysize - 1;
75 count++;
76 } 77 }
77 78
78 /* left and right wall */ 79 /* left and right wall */
79 for (j = 2; j < ysize - 2; j++) 80 for (int y = 2; y < ysize - 2; y++)
80 {
81 wall_x_list[count] = 0;
82 wall_y_list[count] = j;
83 count++;
84 wall_x_list[count] = xsize - 1;
85 wall_y_list[count] = j;
86 count++;
87 } 81 {
88} 82 push (point ( 0, y));
89 83 push (point (xsize - 1, y));
90/* randomly returns one of the elements from the wall point list */ 84 }
91static void
92pop_wall_point (int *x, int *y)
93{
94 int index = rmg_rndm (wall_free_size);
95
96 *x = wall_x_list[index];
97 *y = wall_y_list[index];
98
99 /* write the last array point here */
100 wall_x_list[index] = wall_x_list[wall_free_size - 1];
101 wall_y_list[index] = wall_y_list[wall_free_size - 1];
102 wall_free_size--;
103} 85}
104 86
105/* find free point: randomly look for a square adjacent to this one where 87/* find free point: randomly look for a square adjacent to this one where
106we can place a new block without closing a path. We may only look 88we can place a new block without closing a path. We may only look
107up, down, right, or left. */ 89up, down, right, or left. */
108static int 90static int
109find_free_point (char **maze, int *x, int *y, int xc, int yc) 91find_free_point (point &p, point pc)
110{ 92{
111 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 93 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
112 int dirlist[4]; 94 int dirlist[4];
113 int count = 0; /* # elements in dirlist */ 95 int count = 0; /* # elements in dirlist */
114 96
97 int xc = pc.x;
98 int yc = pc.y;
99
115 /* look up */ 100 /* look up */
116 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */ 101 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
117 { 102 {
118 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1] 103 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
119 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2]; 104 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
… …
157 142
158 /* choose a random direction */ 143 /* choose a random direction */
159 switch (dirlist [rmg_rndm (count)]) 144 switch (dirlist [rmg_rndm (count)])
160 { 145 {
161 case 1: /* up */ 146 case 1: /* up */
147 p.x = xc;
162 *y = yc + 1; 148 p.y = yc + 1;
163 *x = xc;
164 break; 149 break;
165 150
166 case 2: /* down */ 151 case 2: /* down */
152 p.x = xc;
167 *y = yc - 1; 153 p.y = yc - 1;
168 *x = xc;
169 break; 154 break;
170 155
171 case 3: /* right */ 156 case 3: /* right */
172 *y = yc;
173 *x = xc + 1; 157 p.x = xc + 1;
158 p.y = yc;
174 break; 159 break;
175 160
176 case 4: /* left */ 161 case 4: /* left */
177 *x = xc - 1; 162 p.x = xc - 1;
178 *y = yc; 163 p.y = yc;
179 break; 164 break;
180 } 165 }
181 166
182 return 1; 167 return 1;
183}
184
185/* recursive routine which will fill every available space in the maze
186 with walls*/
187static void
188fill_maze_full (char **maze, int x, int y)
189{
190 int xc, yc;
191
192 /* write a wall here */
193 maze[x][y] = '#';
194
195 /* decide if we're going to pick from the wall_free_list */
196 if (rmg_rndm (2) && wall_free_size > 0)
197 {
198 pop_wall_point (&xc, &yc);
199 fill_maze_full (maze, xc, yc);
200 }
201
202 /* change the while to an if for a sparse maze. */
203 while (find_free_point (maze, &xc, &yc, x, y) != -1)
204 fill_maze_full (maze, xc, yc);
205}
206
207/* recursive routine which will fill much of the maze, but will leave
208 some free spots (possibly large) toward the center.*/
209static void
210fill_maze_sparse (char **maze, int x, int y)
211{
212 int xc, yc;
213
214 /* write a wall here */
215 maze[x][y] = '#';
216
217 /* decide if we're going to pick from the wall_free_list */
218 if (rmg_rndm (2) && wall_free_size > 0)
219 {
220 pop_wall_point (&xc, &yc);
221 fill_maze_sparse (maze, xc, yc);
222 }
223
224 /* change the if to a while for a complete maze. */
225 if (find_free_point (maze, &xc, &yc, x, y) != -1)
226 fill_maze_sparse (maze, xc, yc);
227} 168}
228 169
229/* the outsize interface routine: accepts sizes, returns a char 170/* the outsize interface routine: accepts sizes, returns a char
230** maze. option is a flag for either a sparse or a full maze. Sparse 171** maze. option is a flag for either a sparse or a full maze. Sparse
231mazes have sizable rooms. option = 1, full, 0, sparse.*/ 172mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
232void 173void
233maze_gen (Layout maze, int full) 174maze_gen (layout &maze, int subtype)
234{ 175{
235 maze->clear ();
236 maze->border ();
237
238 xsize = maze->w; 176 xsize = maze.w;
239 ysize = maze->h; 177 ysize = maze.h;
178 ::maze = maze;
240 179
241 /* find how many free wall spots there are */ 180 maze.clear ();
242 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4); 181 maze.border ();
243 182
244 make_wall_free_list (maze->w, maze->h); 183 if (xsize < 4 || ysize < 4)
245
246 /* return the empty maze */
247 if (wall_free_size <= 0)
248 return; 184 return;
185
186 seeds.reset (xsize * ysize);
187
188 if (subtype > 0)
189 push_walls ();
190
191 if (subtype == 0 || subtype == 2)
192 for (int i = (xsize + ysize) / 2; i; --i)
193 push (point (rmg_rndm (1, xsize - 2), rmg_rndm (1, ysize - 2)));
194
195 bool full = subtype == 3;
249 196
250 /* recursively generate the walls of the maze */ 197 /* recursively generate the walls of the maze */
251 /* first pop a random starting point */ 198 /* first pop a random starting point */
252 while (wall_free_size > 0) 199 while (seeds.size)
253 { 200 {
254 int i, j; 201 point p = pop_rand ();
255 202
256 pop_wall_point (&i, &j); 203 for (;;)
204 {
205 point pc;
257 206
207 maze [p.x][p.y] = '#';
208
209 if (find_free_point (pc, p) < 0)
210 break;
211
258 if (full) 212 if (full)
259 fill_maze_full (maze, i, j); 213 push (p);
260 else
261 fill_maze_sparse (maze, i, j);
262 }
263 214
264 /* clean up our intermediate data structures. */ 215 if (!rmg_rndm (8))
216 {
217 if (!full)
218 push (pc);
265 219
266 free (wall_x_list); 220 break;
267 free (wall_y_list); 221 }
268}
269 222
270#if 1 223 p = pc;
271static struct demo
272{
273 demo ()
274 {
275 Layout layout (30, 30);
276 rmg_rndm.seed (time (0));
277
278 for(int i=1;i<10;++i)
279 {
280 maze_gen (layout, 1);
281 layout.print ();
282 } 224 }
283 exit (1);
284 } 225 }
285} demo; 226
286#endif 227 seeds.free ();
228}
229

Diff Legend

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