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.1 by elmex, Sun Aug 13 17:16:03 2006 UTC vs.
Revision 1.12 by root, Thu May 8 14:20:19 2008 UTC

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

Diff Legend

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