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

Diff Legend

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