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.18 by root, Sun Jun 27 09:54:36 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
… …
24 as parameters every time. */ 46 as parameters every time. */
25static int *wall_x_list = 0; 47static int *wall_x_list = 0;
26static int *wall_y_list = 0; 48static int *wall_y_list = 0;
27static int wall_free_size = 0; 49static int wall_free_size = 0;
28 50
29/* heuristically, we need to change wall_chance based on the size of
30 the maze. */
31
32static int wall_chance;
33
34/* the free wall points are those outer points which aren't corners or 51/* 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. */ 52 near corners, and don't have a maze wall growing out of them already. */
36static void 53static void
37make_wall_free_list (int xsize, int ysize) 54make_wall_free_list (int xsize, int ysize)
38{ 55{
… …
75{ 92{
76 int index = rmg_rndm (wall_free_size); 93 int index = rmg_rndm (wall_free_size);
77 94
78 *x = wall_x_list[index]; 95 *x = wall_x_list[index];
79 *y = wall_y_list[index]; 96 *y = wall_y_list[index];
97
80 /* write the last array point here */ 98 /* write the last array point here */
81 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 99 wall_x_list[index] = wall_x_list[wall_free_size - 1];
82 wall_y_list[index] = wall_y_list[wall_free_size - 1]; 100 wall_y_list[index] = wall_y_list[wall_free_size - 1];
83 wall_free_size--; 101 wall_free_size--;
84} 102}
… …
94 int count = 0; /* # elements in dirlist */ 112 int count = 0; /* # elements in dirlist */
95 113
96 /* look up */ 114 /* look up */
97 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */ 115 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
98 { 116 {
99 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1]; 117 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]; 118 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
102 119
103 if (cleartest == 0) 120 if (cleartest == 0)
104 dirlist[count++] = 1; 121 dirlist[count++] = 1;
105 } 122 }
106 123
107 /* look down */ 124 /* look down */
108 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */ 125 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
109 { 126 {
110 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1]; 127 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]; 128 + maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
113 129
114 if (cleartest == 0) 130 if (cleartest == 0)
115 dirlist[count++] = 2; 131 dirlist[count++] = 2;
116 } 132 }
117 133
118 /* look right */ 134 /* look right */
119 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */ 135 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
120 { 136 {
121 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1]; 137 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]; 138 + maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
124 139
125 if (cleartest == 0) 140 if (cleartest == 0)
126 dirlist[count++] = 3; 141 dirlist[count++] = 3;
127 } 142 }
128 143
129 /* look left */ 144 /* look left */
130 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */ 145 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
131 { 146 {
132 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1]; 147 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]; 148 + maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
135 149
136 if (cleartest == 0) 150 if (cleartest == 0)
137 dirlist[count++] = 4; 151 dirlist[count++] = 4;
138 } 152 }
139 153
… …
160 174
161 case 4: /* left */ 175 case 4: /* left */
162 *x = xc - 1; 176 *x = xc - 1;
163 *y = yc; 177 *y = yc;
164 break; 178 break;
165
166 default: /* ??? */
167 return -1;
168
169 } 179 }
170 180
171 return 1; 181 return 1;
172} 182}
173 183
… …
180 190
181 /* write a wall here */ 191 /* write a wall here */
182 maze[x][y] = '#'; 192 maze[x][y] = '#';
183 193
184 /* decide if we're going to pick from the wall_free_list */ 194 /* decide if we're going to pick from the wall_free_list */
185 if (rmg_rndm (4) && wall_free_size > 0) 195 if (rmg_rndm (2) && wall_free_size > 0)
186 { 196 {
187 pop_wall_point (&xc, &yc); 197 pop_wall_point (&xc, &yc);
188 fill_maze_full (maze, xc, yc, xsize, ysize); 198 fill_maze_full (maze, xc, yc, xsize, ysize);
189 } 199 }
190 200
191 /* change the if to a while for a complete maze. */ 201 /* change the while to an if for a sparse maze. */
192 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 202 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
193 fill_maze_full (maze, xc, yc, xsize, ysize); 203 fill_maze_full (maze, xc, yc, xsize, ysize);
194} 204}
195 205
196/* recursive routine which will fill much of the maze, but will leave 206/* recursive routine which will fill much of the maze, but will leave
… …
202 212
203 /* write a wall here */ 213 /* write a wall here */
204 maze[x][y] = '#'; 214 maze[x][y] = '#';
205 215
206 /* decide if we're going to pick from the wall_free_list */ 216 /* decide if we're going to pick from the wall_free_list */
207 if (rmg_rndm (4) && wall_free_size > 0) 217 if (rmg_rndm (2) && wall_free_size > 0)
208 { 218 {
209 pop_wall_point (&xc, &yc); 219 pop_wall_point (&xc, &yc);
210 fill_maze_sparse (maze, xc, yc, xsize, ysize); 220 fill_maze_sparse (maze, xc, yc, xsize, ysize);
211 } 221 }
212 222
213 /* change the if to a while for a complete maze. */ 223 /* change the if to a while for a complete maze. */
214 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 224 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
215 fill_maze_sparse (maze, xc, yc, xsize, ysize); 225 fill_maze_sparse (maze, xc, yc, xsize, ysize);
216} 226}
217 227
218/* the outsize interface routine: accepts sizes, returns a char 228/* the outsize interface routine: accepts sizes, returns a char
219** 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
220mazes have sizable rooms. option = 1, full, 0, sparse.*/ 230mazes have sizable rooms. option = 1, full, 0, sparse.*/
221void 231void
222maze_gen (Layout maze, int option) 232maze_gen (Layout maze, int full)
223{ 233{
224 maze->clear (); 234 maze->clear ();
225 maze->border (); 235 maze->border ();
226 236
227 /* find how many free wall spots there are */ 237 /* find how many free wall spots there are */
… …
239 { 249 {
240 int i, j; 250 int i, j;
241 251
242 pop_wall_point (&i, &j); 252 pop_wall_point (&i, &j);
243 253
244 if (option) 254 if (full)
245 fill_maze_full (maze, i, j, maze->w, maze->h); 255 fill_maze_full (maze, i, j, maze->w, maze->h);
246 else 256 else
247 fill_maze_sparse (maze, i, j, maze->w, maze->h); 257 fill_maze_sparse (maze, i, j, maze->w, maze->h);
248 } 258 }
249 259
… …
251 261
252 free (wall_x_list); 262 free (wall_x_list);
253 free (wall_y_list); 263 free (wall_y_list);
254} 264}
255 265
266#if 0
267static struct demo
268{
269 demo ()
270 {
271 Layout layout (30, 30);
272 rmg_rndm.seed (time (0));
273
274 for(int i=1;i<10;++i)
275 {
276 maze_gen (layout, 1);
277 layout.print ();
278 }
279 exit (1);
280 }
281} demo;
282#endif

Diff Legend

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