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

Diff Legend

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