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.27 by root, Sat Apr 23 04:56:52 2011 UTC

1 1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 *
4 * Copyright (©) 2005,2006,2007,2008,2009,2010,2011 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) 1994-2004 Crossfire Development Team (restored, original file without copyright notice)
6 *
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
9 * Free Software Foundation, either version 3 of the License, or (at your
10 * option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
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
19 * <http://www.gnu.org/licenses/>.
20 *
21 * The authors can be reached via e-mail to <support@deliantra.net>
22 */
2 23
3/* peterm@langmuir.eecs.berkeley.edu: this function generates a random 24/* peterm@langmuir.eecs.berkeley.edu: this function generates a random
4blocked 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
5to any other, and there is always a path from one spot to any other. 26to any other, and there is always a path from one spot to any other.
6 27
… …
14 35
15/* we need to maintain a list of wall points to generate 36/* we need to maintain a list of wall points to generate
16 reasonable mazes: a straightforward recursive random walk maze 37 reasonable mazes: a straightforward recursive random walk maze
17 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 */
18 39
19#include <stdio.h> 40#include <vector>
41
20#include <global.h> 42#include <global.h>
21 43
22/*#include <random_map.h>*/
23#include <maze_gen.h>
24#include <time.h> 44#include <rmg.h>
25 45#include "rproto.h"
26
27/* this include solely, and only, is needed for the definition of RANDOM */
28
29
30 46
31/* 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
32 as parameters every time. */ 48 as parameters every time. */
33int *wall_x_list = 0; 49static fixed_stack<point> seeds;
34int *wall_y_list = 0; 50static int xsize, ysize;
35int wall_free_size = 0; 51static char **maze;
36 52
37/* heuristically, we need to change wall_chance based on the size of 53static void
38 the maze. */ 54push (point p)
39
40int 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{ 55{
49 int i, j; 56 seeds.push (p);
50 57 maze [p.x][p.y] = '#';
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} 58}
93 59
94 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}
95 66
96/* 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
97 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. */
98 69static void
99void 70push_walls ()
100make_wall_free_list (int xsize, int ysize)
101{ 71{
102 int i, j, count;
103
104 count = 0; /* entries already placed in the free list */
105 /*allocate it */
106 if (wall_free_size < 0)
107 return;
108 wall_x_list = (int *) calloc (sizeof (int), wall_free_size);
109 wall_y_list = (int *) calloc (sizeof (int), wall_free_size);
110
111
112 /* top and bottom wall */ 72 /* top and bottom wall */
113 for (i = 2; i < xsize - 2; i++) 73 for (int x = 2; x < xsize - 2; x++)
114 { 74 {
115 wall_x_list[count] = i; 75 push (point (x, 0));
116 wall_y_list[count] = 0; 76 push (point (x, ysize - 1));
117 count++;
118 wall_x_list[count] = i;
119 wall_y_list[count] = ysize - 1;
120 count++;
121 } 77 }
122 78
123 /* left and right wall */ 79 /* left and right wall */
124 for (j = 2; j < ysize - 2; j++) 80 for (int y = 2; y < ysize - 2; y++)
125 {
126 wall_x_list[count] = 0;
127 wall_y_list[count] = j;
128 count++;
129 wall_x_list[count] = xsize - 1;
130 wall_y_list[count] = j;
131 count++;
132 } 81 {
82 push (point ( 0, y));
83 push (point (xsize - 1, y));
84 }
133} 85}
134
135
136
137/* randomly returns one of the elements from the wall point list */
138
139void
140pop_wall_point (int *x, int *y)
141{
142 int index = RANDOM () % wall_free_size;
143
144 *x = wall_x_list[index];
145 *y = wall_y_list[index];
146 /* write the last array point here */
147 wall_x_list[index] = wall_x_list[wall_free_size - 1];
148 wall_y_list[index] = wall_y_list[wall_free_size - 1];
149 wall_free_size--;
150}
151
152
153 86
154/* 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
155we 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
156up, down, right, or left. */ 89up, down, right, or left. */
157 90static int
158int 91find_free_point (point &p, point pc)
159find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
160{ 92{
161
162/* 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 */
163 int dirlist[4]; 94 int dirlist[4];
164 int count = 0; /* # elements in dirlist */ 95 int count = 0; /* # elements in dirlist */
165 96
97 int xc = pc.x;
98 int yc = pc.y;
99
166 /* look up */ 100 /* look up */
167 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 */
168 { 102 {
169 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1]; 103 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
170
171 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2]; 104 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
172 105
173 if (cleartest == 0) 106 if (cleartest == 0)
174 {
175 dirlist[count] = 1; 107 dirlist[count++] = 1;
176 count++;
177 }
178 } 108 }
179
180 109
181 /* look down */ 110 /* look down */
182 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */ 111 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
183 { 112 {
184 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1]; 113 int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
185
186 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2]; 114 + maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
187 115
188 if (cleartest == 0) 116 if (cleartest == 0)
189 {
190 dirlist[count] = 2; 117 dirlist[count++] = 2;
191 count++;
192 }
193 } 118 }
194
195 119
196 /* look right */ 120 /* look right */
197 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */ 121 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
198 { 122 {
199 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1]; 123 int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
200
201 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1]; 124 + maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
202 125
203 if (cleartest == 0) 126 if (cleartest == 0)
204 {
205 dirlist[count] = 3; 127 dirlist[count++] = 3;
206 count++;
207 }
208 } 128 }
209
210 129
211 /* look left */ 130 /* look left */
212 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */ 131 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
213 { 132 {
214 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1]; 133 int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
215
216 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1]; 134 + maze[xc - 2][yc] + maze[xc - 2][yc - 1] + 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 */
147 p.x = xc;
148 p.y = yc + 1;
149 break;
150
151 case 2: /* down */
152 p.x = xc;
153 p.y = yc - 1;
154 break;
155
156 case 3: /* right */
157 p.x = xc + 1;
158 p.y = yc;
159 break;
160
161 case 4: /* left */
162 p.x = xc - 1;
163 p.y = yc;
164 break;
165 }
166
167 return 1;
168}
169
170/* the outsize interface routine: accepts sizes, returns a char
171** maze. option is a flag for either a sparse or a full maze. Sparse
172mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
173void
174maze_gen (layout &maze, int subtype)
175{
176 xsize = maze.w;
177 ysize = maze.h;
178 ::maze = maze;
179
180 maze.clear ();
181 maze.border ();
182
183 if (xsize < 4 || ysize < 4)
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;
196
197 /* recursively generate the walls of the maze */
198 /* first pop a random starting point */
199 while (seeds.size)
200 {
201 point p = pop_rand ();
202
203 for (;;)
236 { 204 {
237 *y = yc + 1; 205 point pc;
238 *x = xc; 206
207 maze [p.x][p.y] = '#';
208
209 if (find_free_point (pc, p) < 0)
239 break; 210 break;
240 }; 211
241 case 2: /* down */ 212 if (full)
213 push (p);
214
215 if (!rmg_rndm (8))
242 { 216 {
243 *y = yc - 1; 217 if (!full)
244 *x = xc; 218 push (pc);
219
245 break; 220 break;
246 };
247 case 3: /* right */
248 {
249 *y = yc;
250 *x = xc + 1;
251 break;
252 } 221 }
253 case 4: /* left */ 222
254 {
255 *x = xc - 1;
256 *y = yc; 223 p = pc;
257 break;
258 } 224 }
259 default: /* ??? */
260 {
261 return -1;
262 }
263 }
264 return 1;
265}
266
267/* recursive routine which will fill every available space in the maze
268 with walls*/
269
270void
271fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
272{
273 int xc, yc;
274
275 /* write a wall here */
276 maze[x][y] = '#';
277
278 /* decide if we're going to pick from the wall_free_list */
279 if (RANDOM () % 4 && wall_free_size > 0)
280 { 225 }
281 pop_wall_point (&xc, &yc);
282 fill_maze_full (maze, xc, yc, xsize, ysize);
283 }
284 226
285 /* change the if to a while for a complete maze. */ 227 seeds.free ();
286 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
287 {
288 fill_maze_full (maze, xc, yc, xsize, ysize);
289 }
290} 228}
291 229
292
293/* recursive routine which will fill much of the maze, but will leave
294 some free spots (possibly large) toward the center.*/
295
296void
297fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
298{
299 int xc, yc;
300
301 /* write a wall here */
302 maze[x][y] = '#';
303
304 /* decide if we're going to pick from the wall_free_list */
305 if (RANDOM () % 4 && wall_free_size > 0)
306 {
307 pop_wall_point (&xc, &yc);
308 fill_maze_sparse (maze, xc, yc, xsize, ysize);
309 }
310
311 /* change the if to a while for a complete maze. */
312 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
313 {
314 fill_maze_sparse (maze, xc, yc, xsize, ysize);
315 }
316}

Diff Legend

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