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.11 by root, Sun May 4 14:12:37 2008 UTC vs.
Revision 1.22 by root, Tue Jun 29 18:27:02 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_max, 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 69static void
30 the maze. */ 70push (point p)
31
32int wall_chance;
33
34/* the outsize interface routine: accepts sizes, returns a char
35** maze. option is a flag for either a sparse or a full maze. Sparse
36mazes have sizable rooms. option = 1, full, 0, sparse.*/
37void
38maze_gen (Layout maze, int option)
39{ 71{
40 maze->clear (); 72 assert (seed_size < seed_max);
41 maze->border ();
42 73
43 /* find how many free wall spots there are */ 74 seed_list [seed_size++] = p;
44 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
45 75
46 make_wall_free_list (maze->w, maze->h); 76 maze [p.x][p.y] = '#';
47
48 /* return the empty maze */
49 if (wall_free_size <= 0)
50 return;
51
52 /* recursively generate the walls of the maze */
53 /* first pop a random starting point */
54 while (wall_free_size > 0)
55 {
56 int i, j;
57
58 pop_wall_point (&i, &j);
59
60 if (option)
61 fill_maze_full (maze, i, j, maze->w, maze->h);
62 else
63 fill_maze_sparse (maze, i, j, maze->w, maze->h);
64 }
65
66 /* clean up our intermediate data structures. */
67
68 free (wall_x_list);
69 free (wall_y_list);
70} 77}
71 78
72/* 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
73 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. */
74void 81static void
75make_wall_free_list (int xsize, int ysize) 82push_walls ()
76{ 83{
77 int i, j, count;
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 */ 84 /* top and bottom wall */
88 for (i = 2; i < xsize - 2; i++) 85 for (int x = 2; x < xsize - 2; x++)
89 { 86 {
90 wall_x_list[count] = i; 87 push (point (x, 0));
91 wall_y_list[count] = 0; 88 push (point (x, ysize - 1));
92 count++;
93 wall_x_list[count] = i;
94 wall_y_list[count] = ysize - 1;
95 count++;
96 } 89 }
97 90
98 /* left and right wall */ 91 /* left and right wall */
99 for (j = 2; j < ysize - 2; j++) 92 for (int y = 2; y < ysize - 2; y++)
100 { 93 {
101 wall_x_list[count] = 0; 94 push (point ( 0, y));
102 wall_y_list[count] = j; 95 push (point (xsize - 1, y));
103 count++;
104 wall_x_list[count] = xsize - 1;
105 wall_y_list[count] = j;
106 count++;
107 } 96 }
108} 97}
109 98
110/* randomly returns one of the elements from the wall point list */ 99/* randomly returns one of the elements from the wall point list */
111void 100static point
112pop_wall_point (int *x, int *y) 101pop_rand ()
113{ 102{
114 int index = rmg_rndm (wall_free_size); 103 int index = rmg_rndm (seed_size);
115 104
116 *x = wall_x_list[index]; 105 point p = seed_list [index];
117 *y = wall_y_list[index]; 106
118 /* write the last array point here */ 107 /* write the last array point here */
119 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 108 seed_list [index] = seed_list [--seed_size];
120 wall_y_list[index] = wall_y_list[wall_free_size - 1]; 109
121 wall_free_size--; 110 return p;
122} 111}
123 112
124/* 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
125we 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
126up, down, right, or left. */ 115up, down, right, or left. */
127int 116static int
128find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) 117find_free_point (point &p, point pc)
129{ 118{
130
131/* 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 */
132 int dirlist[4]; 120 int dirlist[4];
133 int count = 0; /* # elements in dirlist */ 121 int count = 0; /* # elements in dirlist */
134 122
123 int xc = pc.x;
124 int yc = pc.y;
125
135 /* look up */ 126 /* look up */
136 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 */
137 { 128 {
138 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1]; 129 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + 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]; 130 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
141 131
142 if (cleartest == 0) 132 if (cleartest == 0)
143 {
144 dirlist[count] = 1; 133 dirlist[count++] = 1;
145 count++;
146 }
147 } 134 }
148 135
149 /* look down */ 136 /* look down */
150 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */ 137 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
151 { 138 {
152 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1]; 139 int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + 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]; 140 + maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
155 141
156 if (cleartest == 0) 142 if (cleartest == 0)
157 {
158 dirlist[count] = 2; 143 dirlist[count++] = 2;
159 count++;
160 }
161 } 144 }
162 145
163 /* look right */ 146 /* look right */
164 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */ 147 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
165 { 148 {
166 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1]; 149 int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + 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]; 150 + maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
169 151
170 if (cleartest == 0) 152 if (cleartest == 0)
171 {
172 dirlist[count] = 3; 153 dirlist[count++] = 3;
173 count++;
174 }
175 } 154 }
176 155
177 /* look left */ 156 /* look left */
178 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */ 157 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
179 { 158 {
180 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1]; 159 int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + 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]; 160 + maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
183 161
184 if (cleartest == 0) 162 if (cleartest == 0)
185 {
186 dirlist[count] = 4; 163 dirlist[count++] = 4;
187 count++;
188 }
189 } 164 }
190 165
191 if (count == 0) 166 if (count == 0)
192 return -1; /* failed to find any clear points */ 167 return -1; /* failed to find any clear points */
193 168
194 /* choose a random direction */ 169 /* choose a random direction */
195 if (count > 1)
196 count = rmg_rndm (count);
197 else
198 count = 0;
199
200 switch (dirlist[count]) 170 switch (dirlist [rmg_rndm (count)])
201 { 171 {
202 case 1: /* up */ 172 case 1: /* up */
173 p.x = xc;
174 p.y = yc + 1;
175 break;
176
177 case 2: /* down */
178 p.x = xc;
179 p.y = yc - 1;
180 break;
181
182 case 3: /* right */
183 p.x = xc + 1;
184 p.y = yc;
185 break;
186
187 case 4: /* left */
188 p.x = xc - 1;
189 p.y = yc;
190 break;
191 }
192
193 return 1;
194}
195
196/* the outsize interface routine: accepts sizes, returns a char
197** maze. option is a flag for either a sparse or a full maze. Sparse
198mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
199void
200maze_gen (Layout maze, int subtype)
201{
202 xsize = maze->w;
203 ysize = maze->h;
204 ::maze = maze;
205
206 maze->clear ();
207 maze->border ();
208
209 if (xsize < 4 || ysize < 4)
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;
224
225 /* recursively generate the walls of the maze */
226 /* first pop a random starting point */
227 while (seed_size)
228 {
229 point p = pop_rand ();
230
231 for (;;)
203 { 232 {
204 *y = yc + 1; 233 point pc;
205 *x = xc; 234
235 maze [p.x][p.y] = '#';
236
237 if (find_free_point (pc, p) < 0)
206 break; 238 break;
207 }; 239
208 case 2: /* down */ 240 if (full)
241 push (p);
242
243 if (!rmg_rndm (8))
209 { 244 {
210 *y = yc - 1; 245 if (!full)
211 *x = xc; 246 push (pc);
247
212 break; 248 break;
213 }; 249 }
214 case 3: /* right */ 250
215 {
216 *y = yc; 251 p = pc;
217 *x = xc + 1;
218 break;
219 } 252 }
220 case 4: /* left */ 253 }
254
255 /* clean up our intermediate data structures. */
256 sfree (seed_list, seed_max);
257}
258
259#if 0
260static struct demo
261{
262 demo ()
263 {
264 Layout layout (40, 25);
265 rmg_rndm.seed (time (0));
266
267 for(int i=1;i<10;++i)
221 { 268 {
222 *x = xc - 1; 269 maze_gen (layout, 3);
223 *y = yc; 270 layout.print ();
224 break;
225 } 271 }
226 default: /* ??? */ 272 exit (1);
227 return -1;
228
229 } 273 }
230 return 1; 274} demo;
231} 275#endif
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 (rmg_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 (rmg_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