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

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

Diff Legend

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