1 |
|
2 |
|
3 |
/* peterm@langmuir.eecs.berkeley.edu: this function generates a random |
4 |
blocked maze with the property that there is only one path from one spot |
5 |
to any other, and there is always a path from one spot to any other. |
6 |
|
7 |
input: xsize, ysize; |
8 |
output: a char** array with # and . for closed and open respectively. |
9 |
|
10 |
a char value of 0 represents a blank space: a '#' is |
11 |
a wall. |
12 |
|
13 |
*/ |
14 |
|
15 |
/* we need to maintain a list of wall points to generate |
16 |
reasonable mazes: a straightforward recursive random walk maze |
17 |
generator would generate a map with a trivial circle-the-outer-wall solution */ |
18 |
|
19 |
#include <stdio.h> |
20 |
#include <global.h> |
21 |
/*#include <random_map.h>*/ |
22 |
#include <maze_gen.h> |
23 |
#include <time.h> |
24 |
|
25 |
|
26 |
/* this include solely, and only, is needed for the definition of RANDOM */ |
27 |
|
28 |
|
29 |
|
30 |
/* global variables that everyone needs: don't want to pass them in |
31 |
as parameters every time. */ |
32 |
int *wall_x_list=0; |
33 |
int *wall_y_list=0; |
34 |
int wall_free_size=0; |
35 |
|
36 |
/* heuristically, we need to change wall_chance based on the size of |
37 |
the maze. */ |
38 |
|
39 |
int wall_chance; |
40 |
|
41 |
/* the outsize interface routine: accepts sizes, returns a char |
42 |
** maze. option is a flag for either a sparse or a full maze. Sparse |
43 |
mazes have sizable rooms. option = 1, full, 0, sparse.*/ |
44 |
|
45 |
char **maze_gen(int xsize, int ysize,int option) { |
46 |
int i,j; |
47 |
|
48 |
/* allocate that array, set it up */ |
49 |
char **maze = (char **)calloc(sizeof(char*),xsize); |
50 |
for(i=0;i<xsize;i++) { |
51 |
maze[i] = (char *) calloc(sizeof(char),ysize); |
52 |
} |
53 |
|
54 |
/* write the outer walls */ |
55 |
for(i=0;i<xsize;i++) |
56 |
maze[i][0] = maze[i][ysize-1] = '#'; |
57 |
for(j=0;j<ysize;j++) |
58 |
maze[0][j] = maze[xsize-1][j] = '#'; |
59 |
|
60 |
|
61 |
/* find how many free wall spots there are */ |
62 |
wall_free_size = 2 * (xsize-4) + 2*(ysize-4 ); |
63 |
|
64 |
make_wall_free_list(xsize,ysize); |
65 |
|
66 |
/* return the empty maze */ |
67 |
if(wall_free_size <=0 ) return maze; |
68 |
|
69 |
/* recursively generate the walls of the maze */ |
70 |
/* first pop a random starting point */ |
71 |
while(wall_free_size > 0) { |
72 |
pop_wall_point(&i,&j); |
73 |
if(option) fill_maze_full(maze,i,j,xsize,ysize); |
74 |
else fill_maze_sparse(maze,i,j,xsize,ysize); |
75 |
} |
76 |
|
77 |
/* clean up our intermediate data structures. */ |
78 |
|
79 |
free(wall_x_list); |
80 |
free(wall_y_list); |
81 |
|
82 |
return maze; |
83 |
} |
84 |
|
85 |
|
86 |
|
87 |
/* the free wall points are those outer points which aren't corners or |
88 |
near corners, and don't have a maze wall growing out of them already. */ |
89 |
|
90 |
void make_wall_free_list(int xsize, int ysize) { |
91 |
int i,j,count; |
92 |
|
93 |
count = 0; /* entries already placed in the free list */ |
94 |
/*allocate it*/ |
95 |
if(wall_free_size < 0) return; |
96 |
wall_x_list = (int *) calloc(sizeof(int),wall_free_size); |
97 |
wall_y_list = (int *) calloc(sizeof(int),wall_free_size); |
98 |
|
99 |
|
100 |
/* top and bottom wall */ |
101 |
for(i = 2; i<xsize-2; i++) { |
102 |
wall_x_list[count] = i; |
103 |
wall_y_list[count] = 0; |
104 |
count++; |
105 |
wall_x_list[count] = i; |
106 |
wall_y_list[count] = ysize-1; |
107 |
count++; |
108 |
} |
109 |
|
110 |
/* left and right wall */ |
111 |
for(j = 2; j<ysize-2; j++) { |
112 |
wall_x_list[count] = 0; |
113 |
wall_y_list[count] = j; |
114 |
count++; |
115 |
wall_x_list[count] = xsize-1; |
116 |
wall_y_list[count] = j; |
117 |
count++; |
118 |
} |
119 |
} |
120 |
|
121 |
|
122 |
|
123 |
/* randomly returns one of the elements from the wall point list */ |
124 |
|
125 |
void pop_wall_point(int *x,int *y) { |
126 |
int index = RANDOM() % wall_free_size; |
127 |
*x = wall_x_list[index]; |
128 |
*y = wall_y_list[index]; |
129 |
/* write the last array point here */ |
130 |
wall_x_list[index]=wall_x_list[wall_free_size-1]; |
131 |
wall_y_list[index]=wall_y_list[wall_free_size-1]; |
132 |
wall_free_size--; |
133 |
} |
134 |
|
135 |
|
136 |
|
137 |
/* find free point: randomly look for a square adjacent to this one where |
138 |
we can place a new block without closing a path. We may only look |
139 |
up, down, right, or left. */ |
140 |
|
141 |
int find_free_point(char **maze,int *x, int *y,int xc,int yc, int xsize, int ysize) { |
142 |
|
143 |
/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ |
144 |
int dirlist[4]; |
145 |
int count = 0; /* # elements in dirlist */ |
146 |
|
147 |
/* look up */ |
148 |
if(yc < ysize-2 && xc > 2 && xc < xsize-2) /* it is valid to look up */ |
149 |
{ |
150 |
int cleartest = (int) maze[xc][yc+1] + (int)maze[xc-1][yc+1] |
151 |
+ (int) maze[xc+1][yc+1]; |
152 |
cleartest += (int) maze[xc][yc+2] + (int)maze[xc-1][yc+2] |
153 |
+ (int) maze[xc+1][yc+2]; |
154 |
|
155 |
if(cleartest == 0) { |
156 |
dirlist[count] = 1; |
157 |
count++; |
158 |
} |
159 |
} |
160 |
|
161 |
|
162 |
/* look down */ |
163 |
if(yc > 2 && xc > 2 && xc < xsize-2) /* it is valid to look down */ |
164 |
{ |
165 |
int cleartest = (int) maze[xc][yc-1] + (int)maze[xc-1][yc-1] |
166 |
+ (int) maze[xc+1][yc-1]; |
167 |
cleartest += (int) maze[xc][yc-2] + (int)maze[xc-1][yc-2] |
168 |
+ (int) maze[xc+1][yc-2]; |
169 |
|
170 |
if(cleartest == 0) { |
171 |
dirlist[count] = 2; |
172 |
count++; |
173 |
} |
174 |
} |
175 |
|
176 |
|
177 |
/* look right */ |
178 |
if(xc < xsize- 2 && yc > 2 && yc < ysize-2) /* it is valid to look left */ |
179 |
{ |
180 |
int cleartest = (int) maze[xc+1][yc] + (int)maze[xc+1][yc-1] |
181 |
+ (int) maze[xc+1][yc+1]; |
182 |
cleartest += (int) maze[xc+2][yc] + (int)maze[xc+2][yc-1] |
183 |
+ (int) maze[xc+2][yc+1]; |
184 |
|
185 |
if(cleartest == 0) { |
186 |
dirlist[count] = 3; |
187 |
count++; |
188 |
} |
189 |
} |
190 |
|
191 |
|
192 |
/* look left */ |
193 |
if(xc > 2 && yc > 2 && yc < ysize-2) /* it is valid to look down */ |
194 |
{ |
195 |
int cleartest = (int) maze[xc-1][yc] + (int)maze[xc-1][yc-1] |
196 |
+ (int) maze[xc-1][yc+1]; |
197 |
cleartest += (int) maze[xc-2][yc] + (int)maze[xc-2][yc-1] |
198 |
+ (int) maze[xc-2][yc+1]; |
199 |
|
200 |
if(cleartest == 0) { |
201 |
dirlist[count] = 4; |
202 |
count++; |
203 |
} |
204 |
} |
205 |
|
206 |
if(count==0) return -1; /* failed to find any clear points */ |
207 |
|
208 |
/* choose a random direction */ |
209 |
if(count > 1) count = RANDOM() % count; |
210 |
else count=0; |
211 |
switch(dirlist[count]) { |
212 |
case 1: /* up */ |
213 |
{ |
214 |
*y = yc +1; |
215 |
*x = xc; |
216 |
break; |
217 |
}; |
218 |
case 2: /* down */ |
219 |
{ |
220 |
*y = yc-1; |
221 |
*x = xc; |
222 |
break; |
223 |
}; |
224 |
case 3: /* right */ |
225 |
{ |
226 |
*y = yc; |
227 |
*x = xc+1; |
228 |
break; |
229 |
} |
230 |
case 4: /* left */ |
231 |
{ |
232 |
*x = xc-1; |
233 |
*y = yc; |
234 |
break; |
235 |
} |
236 |
default: /* ??? */ |
237 |
{ |
238 |
return -1; |
239 |
} |
240 |
} |
241 |
return 1; |
242 |
} |
243 |
|
244 |
/* recursive routine which will fill every available space in the maze |
245 |
with walls*/ |
246 |
|
247 |
void fill_maze_full(char **maze, int x, int y, int xsize, int ysize ) { |
248 |
int xc,yc; |
249 |
|
250 |
/* write a wall here */ |
251 |
maze[x][y] = '#'; |
252 |
|
253 |
/* decide if we're going to pick from the wall_free_list */ |
254 |
if(RANDOM()%4 && wall_free_size > 0) { |
255 |
pop_wall_point(&xc,&yc); |
256 |
fill_maze_full(maze,xc,yc,xsize,ysize); |
257 |
} |
258 |
|
259 |
/* change the if to a while for a complete maze. */ |
260 |
while(find_free_point(maze,&xc,&yc,x,y,xsize,ysize)!=-1) { |
261 |
fill_maze_full(maze,xc,yc,xsize,ysize); |
262 |
} |
263 |
} |
264 |
|
265 |
|
266 |
/* recursive routine which will fill much of the maze, but will leave |
267 |
some free spots (possibly large) toward the center.*/ |
268 |
|
269 |
void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize ) { |
270 |
int xc,yc; |
271 |
|
272 |
/* write a wall here */ |
273 |
maze[x][y] = '#'; |
274 |
|
275 |
/* decide if we're going to pick from the wall_free_list */ |
276 |
if(RANDOM()%4 && wall_free_size > 0) { |
277 |
pop_wall_point(&xc,&yc); |
278 |
fill_maze_sparse(maze,xc,yc,xsize,ysize); |
279 |
} |
280 |
|
281 |
/* change the if to a while for a complete maze. */ |
282 |
if(find_free_point(maze,&xc,&yc,x,y,xsize,ysize)!=-1) { |
283 |
fill_maze_sparse(maze,xc,yc,xsize,ysize); |
284 |
} |
285 |
} |
286 |
|
287 |
|
288 |
|
289 |
|
290 |
|
291 |
|
292 |
|
293 |
|