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.2 by root, Tue Aug 29 08:01:36 2006 UTC vs.
Revision 1.14 by root, Fri Nov 6 13:03:34 2009 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; 25static int *wall_x_list = 0;
33int *wall_y_list=0; 26static int *wall_y_list = 0;
34int wall_free_size=0; 27static int 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; 32static int wall_chance;
33
34/* the free wall points are those outer points which aren't corners or
35 near corners, and don't have a maze wall growing out of them already. */
36static void
37make_wall_free_list (int xsize, int ysize)
38{
39 int i, j, count;
40
41 count = 0; /* entries already placed in the free list */
42 /*allocate it */
43 if (wall_free_size < 0)
44 return;
45
46 wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
47 wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
48
49 /* top and bottom wall */
50 for (i = 2; i < xsize - 2; i++)
51 {
52 wall_x_list[count] = i;
53 wall_y_list[count] = 0;
54 count++;
55 wall_x_list[count] = i;
56 wall_y_list[count] = ysize - 1;
57 count++;
58 }
59
60 /* left and right wall */
61 for (j = 2; j < ysize - 2; j++)
62 {
63 wall_x_list[count] = 0;
64 wall_y_list[count] = j;
65 count++;
66 wall_x_list[count] = xsize - 1;
67 wall_y_list[count] = j;
68 count++;
69 }
70}
71
72/* randomly returns one of the elements from the wall point list */
73static void
74pop_wall_point (int *x, int *y)
75{
76 int index = rmg_rndm (wall_free_size);
77
78 *x = wall_x_list[index];
79 *y = wall_y_list[index];
80 /* write the last array point here */
81 wall_x_list[index] = wall_x_list[wall_free_size - 1];
82 wall_y_list[index] = wall_y_list[wall_free_size - 1];
83 wall_free_size--;
84}
85
86/* find free point: randomly look for a square adjacent to this one where
87we can place a new block without closing a path. We may only look
88up, down, right, or left. */
89static int
90find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
91{
92 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
93 int dirlist[4];
94 int count = 0; /* # elements in dirlist */
95
96 /* look up */
97 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
98 {
99 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
100
101 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
102
103 if (cleartest == 0)
104 dirlist[count++] = 1;
105 }
106
107 /* look down */
108 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
109 {
110 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
111
112 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
113
114 if (cleartest == 0)
115 dirlist[count++] = 2;
116 }
117
118 /* look right */
119 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
120 {
121 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
122
123 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
124
125 if (cleartest == 0)
126 dirlist[count++] = 3;
127 }
128
129 /* look left */
130 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
131 {
132 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
133
134 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
135
136 if (cleartest == 0)
137 dirlist[count++] = 4;
138 }
139
140 if (count == 0)
141 return -1; /* failed to find any clear points */
142
143 /* choose a random direction */
144 switch (dirlist [rmg_rndm (count)])
145 {
146 case 1: /* up */
147 *y = yc + 1;
148 *x = xc;
149 break;
150
151 case 2: /* down */
152 *y = yc - 1;
153 *x = xc;
154 break;
155
156 case 3: /* right */
157 *y = yc;
158 *x = xc + 1;
159 break;
160
161 case 4: /* left */
162 *x = xc - 1;
163 *y = yc;
164 break;
165
166 default: /* ??? */
167 return -1;
168
169 }
170
171 return 1;
172}
173
174/* recursive routine which will fill every available space in the maze
175 with walls*/
176static void
177fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
178{
179 int xc, yc;
180
181 /* write a wall here */
182 maze[x][y] = '#';
183
184 /* decide if we're going to pick from the wall_free_list */
185 if (rmg_rndm (4) && wall_free_size > 0)
186 {
187 pop_wall_point (&xc, &yc);
188 fill_maze_full (maze, xc, yc, xsize, ysize);
189 }
190
191 /* change the if to a while for a complete maze. */
192 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
193 fill_maze_full (maze, xc, yc, xsize, ysize);
194}
195
196/* recursive routine which will fill much of the maze, but will leave
197 some free spots (possibly large) toward the center.*/
198static void
199fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
200{
201 int xc, yc;
202
203 /* write a wall here */
204 maze[x][y] = '#';
205
206 /* decide if we're going to pick from the wall_free_list */
207 if (rmg_rndm (4) && wall_free_size > 0)
208 {
209 pop_wall_point (&xc, &yc);
210 fill_maze_sparse (maze, xc, yc, xsize, ysize);
211 }
212
213 /* change the if to a while for a complete maze. */
214 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
215 fill_maze_sparse (maze, xc, yc, xsize, ysize);
216}
40 217
41/* the outsize interface routine: accepts sizes, returns a char 218/* the outsize interface routine: accepts sizes, returns a char
42** maze. option is a flag for either a sparse or a full maze. Sparse 219** maze. option is a flag for either a sparse or a full maze. Sparse
43mazes have sizable rooms. option = 1, full, 0, sparse.*/ 220mazes have sizable rooms. option = 1, full, 0, sparse.*/
221void
222maze_gen (Layout maze, int option)
223{
224 maze->clear ();
225 maze->border ();
44 226
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 */ 227 /* find how many free wall spots there are */
62 wall_free_size = 2 * (xsize-4) + 2*(ysize-4 ); 228 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
63 229
64 make_wall_free_list(xsize,ysize); 230 make_wall_free_list (maze->w, maze->h);
65 231
66 /* return the empty maze */ 232 /* return the empty maze */
67 if(wall_free_size <=0 ) return maze; 233 if (wall_free_size <= 0)
234 return;
68 235
69 /* recursively generate the walls of the maze */ 236 /* recursively generate the walls of the maze */
70 /* first pop a random starting point */ 237 /* first pop a random starting point */
71 while(wall_free_size > 0) { 238 while (wall_free_size > 0)
239 {
240 int i, j;
241
72 pop_wall_point(&i,&j); 242 pop_wall_point (&i, &j);
73 if(option) fill_maze_full(maze,i,j,xsize,ysize); 243
74 else fill_maze_sparse(maze,i,j,xsize,ysize); 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);
75 } 248 }
76 249
77 /* clean up our intermediate data structures. */ 250 /* clean up our intermediate data structures. */
78 251
79 free(wall_x_list); 252 free (wall_x_list);
80 free(wall_y_list); 253 free (wall_y_list);
81
82 return maze;
83} 254}
84 255
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
90void 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
125void 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
138we can place a new block without closing a path. We may only look
139up, down, right, or left. */
140
141int 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
247void 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
269void 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

Diff Legend

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