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.10 by root, Tue Apr 15 03:00:24 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 = 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)
129{
142 130
143/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 131/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
144 int dirlist[4]; 132 int dirlist[4];
145 int count = 0; /* # elements in dirlist */ 133 int count = 0; /* # elements in dirlist */
146 134
147 /* look up */ 135 /* look up */
148 if(yc < ysize-2 && xc > 2 && xc < xsize-2) /* it is valid to look up */ 136 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
149 { 137 {
150 int cleartest = (int) maze[xc][yc+1] + (int)maze[xc-1][yc+1] 138 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 139
140 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
141
155 if(cleartest == 0) { 142 if (cleartest == 0)
143 {
156 dirlist[count] = 1; 144 dirlist[count] = 1;
157 count++; 145 count++;
158 } 146 }
159 } 147 }
160
161 148
162 /* look down */ 149 /* look down */
163 if(yc > 2 && xc > 2 && xc < xsize-2) /* it is valid to look down */ 150 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
164 { 151 {
165 int cleartest = (int) maze[xc][yc-1] + (int)maze[xc-1][yc-1] 152 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 153
154 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
155
170 if(cleartest == 0) { 156 if (cleartest == 0)
157 {
171 dirlist[count] = 2; 158 dirlist[count] = 2;
172 count++; 159 count++;
173 } 160 }
174 } 161 }
175
176 162
177 /* look right */ 163 /* look right */
178 if(xc < xsize- 2 && yc > 2 && yc < ysize-2) /* it is valid to look left */ 164 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
179 { 165 {
180 int cleartest = (int) maze[xc+1][yc] + (int)maze[xc+1][yc-1] 166 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 167
168 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
169
185 if(cleartest == 0) { 170 if (cleartest == 0)
171 {
186 dirlist[count] = 3; 172 dirlist[count] = 3;
187 count++; 173 count++;
188 } 174 }
189 } 175 }
190
191 176
192 /* look left */ 177 /* look left */
193 if(xc > 2 && yc > 2 && yc < ysize-2) /* it is valid to look down */ 178 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
194 { 179 {
195 int cleartest = (int) maze[xc-1][yc] + (int)maze[xc-1][yc-1] 180 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 181
182 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
183
200 if(cleartest == 0) { 184 if (cleartest == 0)
185 {
201 dirlist[count] = 4; 186 dirlist[count] = 4;
202 count++; 187 count++;
203 } 188 }
204 } 189 }
205 190
191 if (count == 0)
206 if(count==0) return -1; /* failed to find any clear points */ 192 return -1; /* failed to find any clear points */
207 193
208 /* choose a random direction */ 194 /* choose a random direction */
209 if(count > 1) count = RANDOM() % count; 195 if (count > 1)
196 count = rndm (count);
197 else
210 else count=0; 198 count = 0;
199
211 switch(dirlist[count]) { 200 switch (dirlist[count])
212 case 1: /* up */
213 { 201 {
214 *y = yc +1; 202 case 1: /* up */
215 *x = xc; 203 {
216 break; 204 *y = yc + 1;
205 *x = xc;
206 break;
207 };
208 case 2: /* down */
209 {
210 *y = yc - 1;
211 *x = xc;
212 break;
213 };
214 case 3: /* right */
215 {
216 *y = yc;
217 *x = xc + 1;
218 break;
219 }
220 case 4: /* left */
221 {
222 *x = xc - 1;
223 *y = yc;
224 break;
225 }
226 default: /* ??? */
227 return -1;
228
217 }; 229 }
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; 230 return 1;
242} 231}
243 232
244/* recursive routine which will fill every available space in the maze 233/* recursive routine which will fill every available space in the maze
245 with walls*/ 234 with walls*/
246 235void
247void fill_maze_full(char **maze, int x, int y, int xsize, int ysize ) { 236fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
237{
248 int xc,yc; 238 int xc, yc;
249 239
250 /* write a wall here */ 240 /* write a wall here */
251 maze[x][y] = '#'; 241 maze[x][y] = '#';
252 242
253 /* decide if we're going to pick from the wall_free_list */ 243 /* decide if we're going to pick from the wall_free_list */
254 if(RANDOM()%4 && wall_free_size > 0) { 244 if (rndm (4) && wall_free_size > 0)
245 {
255 pop_wall_point(&xc,&yc); 246 pop_wall_point (&xc, &yc);
256 fill_maze_full(maze,xc,yc,xsize,ysize); 247 fill_maze_full (maze, xc, yc, xsize, ysize);
257 } 248 }
258 249
259 /* change the if to a while for a complete maze. */ 250 /* change the if to a while for a complete maze. */
260 while(find_free_point(maze,&xc,&yc,x,y,xsize,ysize)!=-1) { 251 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
252 {
261 fill_maze_full(maze,xc,yc,xsize,ysize); 253 fill_maze_full (maze, xc, yc, xsize, ysize);
262 } 254 }
263} 255}
264
265 256
266/* recursive routine which will fill much of the maze, but will leave 257/* recursive routine which will fill much of the maze, but will leave
267 some free spots (possibly large) toward the center.*/ 258 some free spots (possibly large) toward the center.*/
268 259void
269void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize ) { 260fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
261{
270 int xc,yc; 262 int xc, yc;
271 263
272 /* write a wall here */ 264 /* write a wall here */
273 maze[x][y] = '#'; 265 maze[x][y] = '#';
274 266
275 /* decide if we're going to pick from the wall_free_list */ 267 /* decide if we're going to pick from the wall_free_list */
276 if(RANDOM()%4 && wall_free_size > 0) { 268 if (rndm (4) && wall_free_size > 0)
269 {
277 pop_wall_point(&xc,&yc); 270 pop_wall_point (&xc, &yc);
278 fill_maze_sparse(maze,xc,yc,xsize,ysize); 271 fill_maze_sparse (maze, xc, yc, xsize, ysize);
279 } 272 }
280 273
281 /* change the if to a while for a complete maze. */ 274 /* change the if to a while for a complete maze. */
282 if(find_free_point(maze,&xc,&yc,x,y,xsize,ysize)!=-1) { 275 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
283 fill_maze_sparse(maze,xc,yc,xsize,ysize); 276 fill_maze_sparse (maze, xc, yc, xsize, ysize);
284 }
285} 277}
286
287
288
289
290
291
292
293

Diff Legend

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