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.12 by root, Thu May 8 14:20:19 2008 UTC vs.
Revision 1.14 by root, Fri Nov 6 13:03:34 2009 UTC

… …
20#include "random_map.h" 20#include "random_map.h"
21#include "rproto.h" 21#include "rproto.h"
22 22
23/* global variables that everyone needs: don't want to pass them in 23/* global variables that everyone needs: don't want to pass them in
24 as parameters every time. */ 24 as parameters every time. */
25int *wall_x_list = 0; 25static int *wall_x_list = 0;
26int *wall_y_list = 0; 26static int *wall_y_list = 0;
27int wall_free_size = 0; 27static int wall_free_size = 0;
28 28
29/* heuristically, we need to change wall_chance based on the size of 29/* heuristically, we need to change wall_chance based on the size of
30 the maze. */ 30 the maze. */
31 31
32int wall_chance; 32static int 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.*/
37void
38maze_gen (Layout maze, int option)
39{
40 maze->clear ();
41 maze->border ();
42
43 /* find how many free wall spots there are */
44 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
45
46 make_wall_free_list (maze->w, maze->h);
47
48 /* return the empty maze */
49 if (wall_free_size <= 0)
50 return;
51
52 /* recursively generate the walls of the maze */
53 /* first pop a random starting point */
54 while (wall_free_size > 0)
55 {
56 int i, j;
57
58 pop_wall_point (&i, &j);
59
60 if (option)
61 fill_maze_full (maze, i, j, maze->w, maze->h);
62 else
63 fill_maze_sparse (maze, i, j, maze->w, maze->h);
64 }
65
66 /* clean up our intermediate data structures. */
67
68 free (wall_x_list);
69 free (wall_y_list);
70}
71 33
72/* the free wall points are those outer points which aren't corners or 34/* the free wall points are those outer points which aren't corners or
73 near corners, and don't have a maze wall growing out of them already. */ 35 near corners, and don't have a maze wall growing out of them already. */
74void 36static void
75make_wall_free_list (int xsize, int ysize) 37make_wall_free_list (int xsize, int ysize)
76{ 38{
77 int i, j, count; 39 int i, j, count;
78 40
79 count = 0; /* entries already placed in the free list */ 41 count = 0; /* entries already placed in the free list */
… …
106 count++; 68 count++;
107 } 69 }
108} 70}
109 71
110/* randomly returns one of the elements from the wall point list */ 72/* randomly returns one of the elements from the wall point list */
111void 73static void
112pop_wall_point (int *x, int *y) 74pop_wall_point (int *x, int *y)
113{ 75{
114 int index = rmg_rndm (wall_free_size); 76 int index = rmg_rndm (wall_free_size);
115 77
116 *x = wall_x_list[index]; 78 *x = wall_x_list[index];
… …
122} 84}
123 85
124/* find free point: randomly look for a square adjacent to this one where 86/* find free point: randomly look for a square adjacent to this one where
125we can place a new block without closing a path. We may only look 87we can place a new block without closing a path. We may only look
126up, down, right, or left. */ 88up, down, right, or left. */
127int 89static int
128find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) 90find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
129{ 91{
130 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 92 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
131 int dirlist[4]; 93 int dirlist[4];
132 int count = 0; /* # elements in dirlist */ 94 int count = 0; /* # elements in dirlist */
… …
209 return 1; 171 return 1;
210} 172}
211 173
212/* recursive routine which will fill every available space in the maze 174/* recursive routine which will fill every available space in the maze
213 with walls*/ 175 with walls*/
214void 176static void
215fill_maze_full (char **maze, int x, int y, int xsize, int ysize) 177fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
216{ 178{
217 int xc, yc; 179 int xc, yc;
218 180
219 /* write a wall here */ 181 /* write a wall here */
… …
231 fill_maze_full (maze, xc, yc, xsize, ysize); 193 fill_maze_full (maze, xc, yc, xsize, ysize);
232} 194}
233 195
234/* recursive routine which will fill much of the maze, but will leave 196/* recursive routine which will fill much of the maze, but will leave
235 some free spots (possibly large) toward the center.*/ 197 some free spots (possibly large) toward the center.*/
236void 198static void
237fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize) 199fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
238{ 200{
239 int xc, yc; 201 int xc, yc;
240 202
241 /* write a wall here */ 203 /* write a wall here */
… …
251 /* change the if to a while for a complete maze. */ 213 /* change the if to a while for a complete maze. */
252 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 214 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
253 fill_maze_sparse (maze, xc, yc, xsize, ysize); 215 fill_maze_sparse (maze, xc, yc, xsize, ysize);
254} 216}
255 217
218/* the outsize interface routine: accepts sizes, returns a char
219** maze. option is a flag for either a sparse or a full maze. Sparse
220mazes have sizable rooms. option = 1, full, 0, sparse.*/
221void
222maze_gen (Layout maze, int option)
223{
224 maze->clear ();
225 maze->border ();
226
227 /* find how many free wall spots there are */
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;
235
236 /* recursively generate the walls of the maze */
237 /* first pop a random starting point */
238 while (wall_free_size > 0)
239 {
240 int i, j;
241
242 pop_wall_point (&i, &j);
243
244 if (option)
245 fill_maze_full (maze, i, j, maze->w, maze->h);
246 else
247 fill_maze_sparse (maze, i, j, maze->w, maze->h);
248 }
249
250 /* clean up our intermediate data structures. */
251
252 free (wall_x_list);
253 free (wall_y_list);
254}
255

Diff Legend

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