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.16 by root, Sat Nov 7 18:32:45 2009 UTC vs.
Revision 1.19 by root, Sun Jun 27 16:36:12 2010 UTC

… …
45/* global variables that everyone needs: don't want to pass them in 45/* global variables that everyone needs: don't want to pass them in
46 as parameters every time. */ 46 as parameters every time. */
47static int *wall_x_list = 0; 47static int *wall_x_list = 0;
48static int *wall_y_list = 0; 48static int *wall_y_list = 0;
49static int wall_free_size = 0; 49static int wall_free_size = 0;
50static int xsize, ysize;
50 51
51/* the free wall points are those outer points which aren't corners or 52/* the free wall points are those outer points which aren't corners or
52 near corners, and don't have a maze wall growing out of them already. */ 53 near corners, and don't have a maze wall growing out of them already. */
53static void 54static void
54make_wall_free_list (int xsize, int ysize) 55make_wall_free_list (int xsize, int ysize)
… …
92{ 93{
93 int index = rmg_rndm (wall_free_size); 94 int index = rmg_rndm (wall_free_size);
94 95
95 *x = wall_x_list[index]; 96 *x = wall_x_list[index];
96 *y = wall_y_list[index]; 97 *y = wall_y_list[index];
98
97 /* write the last array point here */ 99 /* write the last array point here */
98 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 100 wall_x_list[index] = wall_x_list[wall_free_size - 1];
99 wall_y_list[index] = wall_y_list[wall_free_size - 1]; 101 wall_y_list[index] = wall_y_list[wall_free_size - 1];
100 wall_free_size--; 102 wall_free_size--;
101} 103}
102 104
103/* find free point: randomly look for a square adjacent to this one where 105/* find free point: randomly look for a square adjacent to this one where
104we can place a new block without closing a path. We may only look 106we can place a new block without closing a path. We may only look
105up, down, right, or left. */ 107up, down, right, or left. */
106static int 108static int
107find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) 109find_free_point (char **maze, int *x, int *y, int xc, int yc)
108{ 110{
109 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 111 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
110 int dirlist[4]; 112 int dirlist[4];
111 int count = 0; /* # elements in dirlist */ 113 int count = 0; /* # elements in dirlist */
112 114
113 /* look up */ 115 /* look up */
114 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */ 116 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
115 { 117 {
116 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1]; 118 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
117
118 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2]; 119 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
119 120
120 if (cleartest == 0) 121 if (cleartest == 0)
121 dirlist[count++] = 1; 122 dirlist[count++] = 1;
122 } 123 }
123 124
124 /* look down */ 125 /* look down */
125 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */ 126 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
126 { 127 {
127 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1]; 128 int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
128
129 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2]; 129 + maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
130 130
131 if (cleartest == 0) 131 if (cleartest == 0)
132 dirlist[count++] = 2; 132 dirlist[count++] = 2;
133 } 133 }
134 134
135 /* look right */ 135 /* look right */
136 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */ 136 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
137 { 137 {
138 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1]; 138 int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
139
140 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1]; 139 + maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
141 140
142 if (cleartest == 0) 141 if (cleartest == 0)
143 dirlist[count++] = 3; 142 dirlist[count++] = 3;
144 } 143 }
145 144
146 /* look left */ 145 /* look left */
147 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */ 146 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
148 { 147 {
149 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1]; 148 int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
150
151 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1]; 149 + maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
152 150
153 if (cleartest == 0) 151 if (cleartest == 0)
154 dirlist[count++] = 4; 152 dirlist[count++] = 4;
155 } 153 }
156 154
… …
177 175
178 case 4: /* left */ 176 case 4: /* left */
179 *x = xc - 1; 177 *x = xc - 1;
180 *y = yc; 178 *y = yc;
181 break; 179 break;
182
183 default: /* ??? */
184 return -1;
185
186 } 180 }
187 181
188 return 1; 182 return 1;
189} 183}
190 184
191/* recursive routine which will fill every available space in the maze 185/* recursive routine which will fill every available space in the maze
192 with walls*/ 186 with walls*/
193static void 187static void
194fill_maze_full (char **maze, int x, int y, int xsize, int ysize) 188fill_maze_full (char **maze, int x, int y)
195{ 189{
196 int xc, yc; 190 int xc, yc;
197 191
198 /* write a wall here */ 192 /* write a wall here */
199 maze[x][y] = '#'; 193 maze[x][y] = '#';
200 194
201 /* decide if we're going to pick from the wall_free_list */ 195 /* decide if we're going to pick from the wall_free_list */
202 if (rmg_rndm (4) && wall_free_size > 0) 196 if (rmg_rndm (2) && wall_free_size > 0)
203 { 197 {
204 pop_wall_point (&xc, &yc); 198 pop_wall_point (&xc, &yc);
205 fill_maze_full (maze, xc, yc, xsize, ysize); 199 fill_maze_full (maze, xc, yc);
206 } 200 }
207 201
208 /* change the if to a while for a complete maze. */ 202 /* change the while to an if for a sparse maze. */
209 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 203 while (find_free_point (maze, &xc, &yc, x, y) != -1)
210 fill_maze_full (maze, xc, yc, xsize, ysize); 204 fill_maze_full (maze, xc, yc);
211} 205}
212 206
213/* recursive routine which will fill much of the maze, but will leave 207/* recursive routine which will fill much of the maze, but will leave
214 some free spots (possibly large) toward the center.*/ 208 some free spots (possibly large) toward the center.*/
215static void 209static void
216fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize) 210fill_maze_sparse (char **maze, int x, int y)
217{ 211{
218 int xc, yc; 212 int xc, yc;
219 213
220 /* write a wall here */ 214 /* write a wall here */
221 maze[x][y] = '#'; 215 maze[x][y] = '#';
222 216
223 /* decide if we're going to pick from the wall_free_list */ 217 /* decide if we're going to pick from the wall_free_list */
224 if (rmg_rndm (4) && wall_free_size > 0) 218 if (rmg_rndm (2) && wall_free_size > 0)
225 { 219 {
226 pop_wall_point (&xc, &yc); 220 pop_wall_point (&xc, &yc);
227 fill_maze_sparse (maze, xc, yc, xsize, ysize); 221 fill_maze_sparse (maze, xc, yc);
228 } 222 }
229 223
230 /* change the if to a while for a complete maze. */ 224 /* change the if to a while for a complete maze. */
231 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 225 if (find_free_point (maze, &xc, &yc, x, y) != -1)
232 fill_maze_sparse (maze, xc, yc, xsize, ysize); 226 fill_maze_sparse (maze, xc, yc);
233} 227}
234 228
235/* the outsize interface routine: accepts sizes, returns a char 229/* the outsize interface routine: accepts sizes, returns a char
236** maze. option is a flag for either a sparse or a full maze. Sparse 230** maze. option is a flag for either a sparse or a full maze. Sparse
237mazes have sizable rooms. option = 1, full, 0, sparse.*/ 231mazes have sizable rooms. option = 1, full, 0, sparse.*/
238void 232void
239maze_gen (Layout maze, int option) 233maze_gen (Layout maze, int full)
240{ 234{
241 maze->clear (); 235 maze->clear ();
242 maze->border (); 236 maze->border ();
237
238 xsize = maze->w;
239 ysize = maze->h;
243 240
244 /* find how many free wall spots there are */ 241 /* find how many free wall spots there are */
245 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4); 242 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
246 243
247 make_wall_free_list (maze->w, maze->h); 244 make_wall_free_list (maze->w, maze->h);
… …
256 { 253 {
257 int i, j; 254 int i, j;
258 255
259 pop_wall_point (&i, &j); 256 pop_wall_point (&i, &j);
260 257
261 if (option) 258 if (full)
262 fill_maze_full (maze, i, j, maze->w, maze->h); 259 fill_maze_full (maze, i, j);
263 else 260 else
264 fill_maze_sparse (maze, i, j, maze->w, maze->h); 261 fill_maze_sparse (maze, i, j);
265 } 262 }
266 263
267 /* clean up our intermediate data structures. */ 264 /* clean up our intermediate data structures. */
268 265
269 free (wall_x_list); 266 free (wall_x_list);
270 free (wall_y_list); 267 free (wall_y_list);
271} 268}
272 269
270#if 1
271static struct demo
272{
273 demo ()
274 {
275 Layout layout (30, 30);
276 rmg_rndm.seed (time (0));
277
278 for(int i=1;i<10;++i)
279 {
280 maze_gen (layout, 1);
281 layout.print ();
282 }
283 exit (1);
284 }
285} demo;
286#endif

Diff Legend

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