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.15 by root, Fri Nov 6 13:31:47 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
29/* heuristically, we need to change wall_chance based on the size of
30 the maze. */
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.*/
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 28
72/* the free wall points are those outer points which aren't corners or 29/* 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. */ 30 near corners, and don't have a maze wall growing out of them already. */
74void 31static void
75make_wall_free_list (int xsize, int ysize) 32make_wall_free_list (int xsize, int ysize)
76{ 33{
77 int i, j, count; 34 int i, j, count;
78 35
79 count = 0; /* entries already placed in the free list */ 36 count = 0; /* entries already placed in the free list */
… …
106 count++; 63 count++;
107 } 64 }
108} 65}
109 66
110/* randomly returns one of the elements from the wall point list */ 67/* randomly returns one of the elements from the wall point list */
111void 68static void
112pop_wall_point (int *x, int *y) 69pop_wall_point (int *x, int *y)
113{ 70{
114 int index = rmg_rndm (wall_free_size); 71 int index = rmg_rndm (wall_free_size);
115 72
116 *x = wall_x_list[index]; 73 *x = wall_x_list[index];
… …
122} 79}
123 80
124/* find free point: randomly look for a square adjacent to this one where 81/* 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 82we can place a new block without closing a path. We may only look
126up, down, right, or left. */ 83up, down, right, or left. */
127int 84static int
128find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize) 85find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
129{ 86{
130 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 87 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
131 int dirlist[4]; 88 int dirlist[4];
132 int count = 0; /* # elements in dirlist */ 89 int count = 0; /* # elements in dirlist */
… …
209 return 1; 166 return 1;
210} 167}
211 168
212/* recursive routine which will fill every available space in the maze 169/* recursive routine which will fill every available space in the maze
213 with walls*/ 170 with walls*/
214void 171static void
215fill_maze_full (char **maze, int x, int y, int xsize, int ysize) 172fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
216{ 173{
217 int xc, yc; 174 int xc, yc;
218 175
219 /* write a wall here */ 176 /* write a wall here */
… …
231 fill_maze_full (maze, xc, yc, xsize, ysize); 188 fill_maze_full (maze, xc, yc, xsize, ysize);
232} 189}
233 190
234/* recursive routine which will fill much of the maze, but will leave 191/* recursive routine which will fill much of the maze, but will leave
235 some free spots (possibly large) toward the center.*/ 192 some free spots (possibly large) toward the center.*/
236void 193static void
237fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize) 194fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
238{ 195{
239 int xc, yc; 196 int xc, yc;
240 197
241 /* write a wall here */ 198 /* write a wall here */
… …
251 /* change the if to a while for a complete maze. */ 208 /* change the if to a while for a complete maze. */
252 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 209 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
253 fill_maze_sparse (maze, xc, yc, xsize, ysize); 210 fill_maze_sparse (maze, xc, yc, xsize, ysize);
254} 211}
255 212
213/* the outsize interface routine: accepts sizes, returns a char
214** maze. option is a flag for either a sparse or a full maze. Sparse
215mazes have sizable rooms. option = 1, full, 0, sparse.*/
216void
217maze_gen (Layout maze, int option)
218{
219 maze->clear ();
220 maze->border ();
221
222 /* find how many free wall spots there are */
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;
230
231 /* recursively generate the walls of the maze */
232 /* first pop a random starting point */
233 while (wall_free_size > 0)
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 }
244
245 /* clean up our intermediate data structures. */
246
247 free (wall_x_list);
248 free (wall_y_list);
249}
250

Diff Legend

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