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.9 by root, Mon Apr 14 22:41:17 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 (Maze 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 = 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];
117 *y = wall_y_list[index]; 79 *y = wall_y_list[index];
118 /* write the last array point here */ 80 /* write the last array point here */
119 wall_x_list[index] = wall_x_list[wall_free_size - 1]; 81 wall_x_list[index] = wall_x_list[wall_free_size - 1];
… …
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
131/* 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 */
132 int dirlist[4]; 93 int dirlist[4];
133 int count = 0; /* # elements in dirlist */ 94 int count = 0; /* # elements in dirlist */
134 95
135 /* look up */ 96 /* look up */
136 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */ 97 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
… …
138 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1]; 99 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
139 100
140 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2]; 101 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
141 102
142 if (cleartest == 0) 103 if (cleartest == 0)
143 {
144 dirlist[count] = 1; 104 dirlist[count++] = 1;
145 count++;
146 }
147 } 105 }
148 106
149 /* look down */ 107 /* look down */
150 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */ 108 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
151 { 109 {
152 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1]; 110 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
153 111
154 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2]; 112 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
155 113
156 if (cleartest == 0) 114 if (cleartest == 0)
157 {
158 dirlist[count] = 2; 115 dirlist[count++] = 2;
159 count++;
160 }
161 } 116 }
162 117
163 /* look right */ 118 /* look right */
164 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */ 119 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
165 { 120 {
166 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1]; 121 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
167 122
168 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1]; 123 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
169 124
170 if (cleartest == 0) 125 if (cleartest == 0)
171 {
172 dirlist[count] = 3; 126 dirlist[count++] = 3;
173 count++;
174 }
175 } 127 }
176 128
177 /* look left */ 129 /* look left */
178 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */ 130 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
179 { 131 {
180 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1]; 132 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
181 133
182 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1]; 134 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
183 135
184 if (cleartest == 0) 136 if (cleartest == 0)
185 {
186 dirlist[count] = 4; 137 dirlist[count++] = 4;
187 count++;
188 }
189 } 138 }
190 139
191 if (count == 0) 140 if (count == 0)
192 return -1; /* failed to find any clear points */ 141 return -1; /* failed to find any clear points */
193 142
194 /* choose a random direction */ 143 /* choose a random direction */
195 if (count > 1)
196 count = rndm (count);
197 else
198 count = 0;
199
200 switch (dirlist[count]) 144 switch (dirlist [rmg_rndm (count)])
201 { 145 {
202 case 1: /* up */ 146 case 1: /* up */
203 {
204 *y = yc + 1; 147 *y = yc + 1;
205 *x = xc; 148 *x = xc;
206 break; 149 break;
207 }; 150
208 case 2: /* down */ 151 case 2: /* down */
209 {
210 *y = yc - 1; 152 *y = yc - 1;
211 *x = xc; 153 *x = xc;
212 break; 154 break;
213 }; 155
214 case 3: /* right */ 156 case 3: /* right */
215 {
216 *y = yc; 157 *y = yc;
217 *x = xc + 1; 158 *x = xc + 1;
218 break; 159 break;
219 } 160
220 case 4: /* left */ 161 case 4: /* left */
221 {
222 *x = xc - 1; 162 *x = xc - 1;
223 *y = yc; 163 *y = yc;
224 break; 164 break;
225 } 165
226 default: /* ??? */ 166 default: /* ??? */
227 return -1; 167 return -1;
228 168
229 } 169 }
170
230 return 1; 171 return 1;
231} 172}
232 173
233/* recursive routine which will fill every available space in the maze 174/* recursive routine which will fill every available space in the maze
234 with walls*/ 175 with walls*/
235void 176static void
236fill_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)
237{ 178{
238 int xc, yc; 179 int xc, yc;
239 180
240 /* write a wall here */ 181 /* write a wall here */
241 maze[x][y] = '#'; 182 maze[x][y] = '#';
242 183
243 /* decide if we're going to pick from the wall_free_list */ 184 /* decide if we're going to pick from the wall_free_list */
244 if (rndm (4) && wall_free_size > 0) 185 if (rmg_rndm (4) && wall_free_size > 0)
245 { 186 {
246 pop_wall_point (&xc, &yc); 187 pop_wall_point (&xc, &yc);
247 fill_maze_full (maze, xc, yc, xsize, ysize); 188 fill_maze_full (maze, xc, yc, xsize, ysize);
248 } 189 }
249 190
250 /* change the if to a while for a complete maze. */ 191 /* change the if to a while for a complete maze. */
251 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1) 192 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
252 {
253 fill_maze_full (maze, xc, yc, xsize, ysize); 193 fill_maze_full (maze, xc, yc, xsize, ysize);
254 }
255} 194}
256 195
257/* 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
258 some free spots (possibly large) toward the center.*/ 197 some free spots (possibly large) toward the center.*/
259void 198static void
260fill_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)
261{ 200{
262 int xc, yc; 201 int xc, yc;
263 202
264 /* write a wall here */ 203 /* write a wall here */
265 maze[x][y] = '#'; 204 maze[x][y] = '#';
266 205
267 /* decide if we're going to pick from the wall_free_list */ 206 /* decide if we're going to pick from the wall_free_list */
268 if (rndm (4) && wall_free_size > 0) 207 if (rmg_rndm (4) && wall_free_size > 0)
269 { 208 {
270 pop_wall_point (&xc, &yc); 209 pop_wall_point (&xc, &yc);
271 fill_maze_sparse (maze, xc, yc, xsize, ysize); 210 fill_maze_sparse (maze, xc, yc, xsize, ysize);
272 } 211 }
273 212
274 /* change the if to a while for a complete maze. */ 213 /* change the if to a while for a complete maze. */
275 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)
276 fill_maze_sparse (maze, xc, yc, xsize, ysize); 215 fill_maze_sparse (maze, xc, yc, xsize, ysize);
277} 216}
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