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

Diff Legend

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