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