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.9 by root, Mon Apr 14 22:41:17 2008 UTC vs.
Revision 1.20 by root, Sun Jun 27 20:40:54 2010 UTC

1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 *
4 * Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) 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
40#include <vector>
41
18#include <global.h> 42#include <global.h>
19 43
20#include "random_map.h" 44#include "random_map.h"
21#include "rproto.h" 45#include "rproto.h"
22 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
23/* 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
24 as parameters every time. */ 63 as parameters every time. */
25int *wall_x_list = 0; 64static point *seed_list;
26int *wall_y_list = 0; 65static int seed_size;
27int wall_free_size = 0; 66static int xsize, ysize;
67static char **maze;
28 68
29/* heuristically, we need to change wall_chance based on the size of 69/* the free wall points are those outer points which aren't corners or
30 the maze. */ 70 near corners, and don't have a maze wall growing out of them already. */
71static void
72make_wall_free_list ()
73{
74 // xsize * ysize is plenty too much, but it's temporary
75 seed_list = salloc<point> (xsize * ysize);
76 seed_size = 0;
31 77
32int wall_chance; 78 /* top and bottom wall */
79 for (int x = 2; x < xsize - 2; x++)
80 {
81 seed_list [seed_size++] = point (x, 0);
82 seed_list [seed_size++] = point (x, ysize - 1);
83 }
84
85 /* left and right wall */
86 for (int y = 2; y < ysize - 2; y++)
87 {
88 seed_list [seed_size++] = point (0, y);
89 seed_list [seed_size++] = point (xsize - 1, y);
90 }
91}
92
93/* randomly returns one of the elements from the wall point list */
94static point
95pop_point ()
96{
97 int index = rmg_rndm (seed_size);
98
99 point p = seed_list [index];
100
101 /* write the last array point here */
102 seed_list [index] = seed_list [--seed_size];
103
104 return p;
105}
106
107/* find free point: randomly look for a square adjacent to this one where
108we can place a new block without closing a path. We may only look
109up, down, right, or left. */
110static int
111find_free_point (point &p, point pc)
112{
113 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
114 int dirlist[4];
115 int count = 0; /* # elements in dirlist */
116
117 int xc = pc.x;
118 int yc = pc.y;
119
120 /* look up */
121 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
122 {
123 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
124 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
125
126 if (cleartest == 0)
127 dirlist[count++] = 1;
128 }
129
130 /* look down */
131 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
132 {
133 int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
134 + maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
135
136 if (cleartest == 0)
137 dirlist[count++] = 2;
138 }
139
140 /* look right */
141 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
142 {
143 int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
144 + maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
145
146 if (cleartest == 0)
147 dirlist[count++] = 3;
148 }
149
150 /* look left */
151 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
152 {
153 int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
154 + maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
155
156 if (cleartest == 0)
157 dirlist[count++] = 4;
158 }
159
160 if (count == 0)
161 return -1; /* failed to find any clear points */
162
163 /* choose a random direction */
164 switch (dirlist [rmg_rndm (count)])
165 {
166 case 1: /* up */
167 p.x = xc;
168 p.y = yc + 1;
169 break;
170
171 case 2: /* down */
172 p.x = xc;
173 p.y = yc - 1;
174 break;
175
176 case 3: /* right */
177 p.x = xc + 1;
178 p.y = yc;
179 break;
180
181 case 4: /* left */
182 p.x = xc - 1;
183 p.y = yc;
184 break;
185 }
186
187 return 1;
188}
189
190/* recursive routine which will fill every available space in the maze
191 with walls*/
192static void
193fill_maze_full (point p)
194{
195 point pc;
196
197 /* write a wall here */
198 maze[p.x][p.y] = '#';
199
200 /* decide if we're going to pick from the wall_free_list */
201 if (rmg_rndm (2) && seed_size)
202 fill_maze_full (pop_point ());
203
204 /* change the while to an if for a sparse maze. */
205 while (find_free_point (pc, p) != -1)
206 fill_maze_full (pc);
207}
208
209/* recursive routine which will fill much of the maze, but will leave
210 some free spots (possibly large) toward the center.*/
211static void
212fill_maze_sparse (point p)
213{
214 point pc;
215
216 /* write a wall here */
217 maze[p.x][p.y] = '#';
218
219 /* decide if we're going to pick from the wall_free_list */
220 if (rmg_rndm (2) && seed_size)
221 fill_maze_full (pop_point ());
222
223 /* change the if to a while for a complete maze. */
224 if (find_free_point (pc, p) != -1)
225 fill_maze_full (pc);
226}
33 227
34/* the outsize interface routine: accepts sizes, returns a char 228/* the outsize interface routine: accepts sizes, returns a char
35** maze. option is a flag for either a sparse or a full maze. Sparse 229** maze. option is a flag for either a sparse or a full maze. Sparse
36mazes have sizable rooms. option = 1, full, 0, sparse.*/ 230mazes have sizable rooms. option = 1, full, 0, sparse.*/
37void 231void
38maze_gen (Maze maze, int option) 232maze_gen (Layout maze, int full)
39{ 233{
234 xsize = maze->w;
235 ysize = maze->h;
236 ::maze = maze;
237
40 maze->clear (); 238 maze->clear ();
41 maze->border (); 239 maze->border ();
42 240
43 /* find how many free wall spots there are */ 241 if (xsize < 4 || ysize < 4)
44 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
45
46 make_wall_free_list (maze->w, maze->h);
47
48 /* return the empty maze */
49 if (wall_free_size <= 0)
50 return; 242 return;
243
244 make_wall_free_list ();
51 245
52 /* recursively generate the walls of the maze */ 246 /* recursively generate the walls of the maze */
53 /* first pop a random starting point */ 247 /* first pop a random starting point */
54 while (wall_free_size > 0) 248 while (seed_size)
55 { 249 if (full)
56 int i, j; 250 fill_maze_full (pop_point ());
57
58 pop_wall_point (&i, &j);
59
60 if (option)
61 fill_maze_full (maze, i, j, maze->w, maze->h);
62 else 251 else
63 fill_maze_sparse (maze, i, j, maze->w, maze->h); 252 fill_maze_sparse (pop_point ());
64 }
65 253
66 /* clean up our intermediate data structures. */ 254 /* clean up our intermediate data structures. */
67 255 sfree (seed_list, xsize * ysize);
68 free (wall_x_list);
69 free (wall_y_list);
70} 256}
71 257
72/* the free wall points are those outer points which aren't corners or 258#if 0
73 near corners, and don't have a maze wall growing out of them already. */ 259static struct demo
74void
75make_wall_free_list (int xsize, int ysize)
76{ 260{
77 int i, j, count; 261 demo ()
78
79 count = 0; /* entries already placed in the free list */
80 /*allocate it */
81 if (wall_free_size < 0)
82 return;
83
84 wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
85 wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
86
87 /* top and bottom wall */
88 for (i = 2; i < xsize - 2; i++)
89 { 262 {
90 wall_x_list[count] = i; 263 Layout layout (30, 30);
91 wall_y_list[count] = 0; 264 rmg_rndm.seed (time (0));
92 count++;
93 wall_x_list[count] = i;
94 wall_y_list[count] = ysize - 1;
95 count++;
96 }
97 265
98 /* left and right wall */ 266 for(int i=1;i<10;++i)
99 for (j = 2; j < ysize - 2; j++)
100 {
101 wall_x_list[count] = 0;
102 wall_y_list[count] = j;
103 count++;
104 wall_x_list[count] = xsize - 1;
105 wall_y_list[count] = j;
106 count++;
107 }
108}
109
110/* randomly returns one of the elements from the wall point list */
111void
112pop_wall_point (int *x, int *y)
113{
114 int index = rndm (wall_free_size);
115
116 *x = wall_x_list[index];
117 *y = wall_y_list[index];
118 /* write the last array point here */
119 wall_x_list[index] = wall_x_list[wall_free_size - 1];
120 wall_y_list[index] = wall_y_list[wall_free_size - 1];
121 wall_free_size--;
122}
123
124/* find free point: randomly look for a square adjacent to this one where
125we can place a new block without closing a path. We may only look
126up, down, right, or left. */
127int
128find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
129{
130
131/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
132 int dirlist[4];
133 int count = 0; /* # elements in dirlist */
134
135 /* look up */
136 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
137 {
138 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
139
140 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
141
142 if (cleartest == 0)
143 { 267 {
144 dirlist[count] = 1; 268 maze_gen (layout, 1);
145 count++; 269 layout.print ();
146 } 270 }
271 exit (1);
147 } 272 }
148 273} demo;
149 /* look down */ 274#endif
150 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
151 {
152 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
153
154 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
155
156 if (cleartest == 0)
157 {
158 dirlist[count] = 2;
159 count++;
160 }
161 }
162
163 /* look right */
164 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
165 {
166 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
167
168 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
169
170 if (cleartest == 0)
171 {
172 dirlist[count] = 3;
173 count++;
174 }
175 }
176
177 /* look left */
178 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
179 {
180 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
181
182 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
183
184 if (cleartest == 0)
185 {
186 dirlist[count] = 4;
187 count++;
188 }
189 }
190
191 if (count == 0)
192 return -1; /* failed to find any clear points */
193
194 /* choose a random direction */
195 if (count > 1)
196 count = rndm (count);
197 else
198 count = 0;
199
200 switch (dirlist[count])
201 {
202 case 1: /* up */
203 {
204 *y = yc + 1;
205 *x = xc;
206 break;
207 };
208 case 2: /* down */
209 {
210 *y = yc - 1;
211 *x = xc;
212 break;
213 };
214 case 3: /* right */
215 {
216 *y = yc;
217 *x = xc + 1;
218 break;
219 }
220 case 4: /* left */
221 {
222 *x = xc - 1;
223 *y = yc;
224 break;
225 }
226 default: /* ??? */
227 return -1;
228
229 }
230 return 1;
231}
232
233/* recursive routine which will fill every available space in the maze
234 with walls*/
235void
236fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
237{
238 int xc, yc;
239
240 /* write a wall here */
241 maze[x][y] = '#';
242
243 /* decide if we're going to pick from the wall_free_list */
244 if (rndm (4) && wall_free_size > 0)
245 {
246 pop_wall_point (&xc, &yc);
247 fill_maze_full (maze, xc, yc, xsize, ysize);
248 }
249
250 /* change the if to a while for a complete maze. */
251 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
252 {
253 fill_maze_full (maze, xc, yc, xsize, ysize);
254 }
255}
256
257/* recursive routine which will fill much of the maze, but will leave
258 some free spots (possibly large) toward the center.*/
259void
260fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
261{
262 int xc, yc;
263
264 /* write a wall here */
265 maze[x][y] = '#';
266
267 /* decide if we're going to pick from the wall_free_list */
268 if (rndm (4) && wall_free_size > 0)
269 {
270 pop_wall_point (&xc, &yc);
271 fill_maze_sparse (maze, xc, yc, xsize, ysize);
272 }
273
274 /* change the if to a while for a complete maze. */
275 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
276 fill_maze_sparse (maze, xc, yc, xsize, ysize);
277}

Diff Legend

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