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.16 by root, Sat Nov 7 18:32:45 2009 UTC

1 1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 *
4 * Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) Crossfire Development Team (restored, original file without copyright notice)
6 *
7 * Deliantra is free software: you can redistribute it and/or modify it under
8 * the terms of the Affero GNU General Public License as published by the
9 * Free Software Foundation, either version 3 of the License, or (at your
10 * option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the Affero GNU General Public License
18 * and the GNU General Public License along with this program. If not, see
19 * <http://www.gnu.org/licenses/>.
20 *
21 * The authors can be reached via e-mail to <support@deliantra.net>
22 */
2 23
3/* peterm@langmuir.eecs.berkeley.edu: this function generates a random 24/* peterm@langmuir.eecs.berkeley.edu: this function generates a random
4blocked maze with the property that there is only one path from one spot 25blocked 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. 26to any other, and there is always a path from one spot to any other.
6 27
… …
14 35
15/* we need to maintain a list of wall points to generate 36/* we need to maintain a list of wall points to generate
16 reasonable mazes: a straightforward recursive random walk maze 37 reasonable mazes: a straightforward recursive random walk maze
17 generator would generate a map with a trivial circle-the-outer-wall solution */ 38 generator would generate a map with a trivial circle-the-outer-wall solution */
18 39
19#include <stdio.h>
20#include <global.h> 40#include <global.h>
41
21/*#include <random_map.h>*/ 42#include "random_map.h"
22#include <maze_gen.h> 43#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 44
30/* global variables that everyone needs: don't want to pass them in 45/* global variables that everyone needs: don't want to pass them in
31 as parameters every time. */ 46 as parameters every time. */
32int *wall_x_list=0; 47static int *wall_x_list = 0;
33int *wall_y_list=0; 48static int *wall_y_list = 0;
34int wall_free_size=0; 49static int wall_free_size = 0;
35 50
36/* heuristically, we need to change wall_chance based on the size of 51/* the free wall points are those outer points which aren't corners or
37 the maze. */ 52 near corners, and don't have a maze wall growing out of them already. */
53static void
54make_wall_free_list (int xsize, int ysize)
55{
56 int i, j, count;
38 57
39int wall_chance; 58 count = 0; /* entries already placed in the free list */
59 /*allocate it */
60 if (wall_free_size < 0)
61 return;
62
63 wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
64 wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
65
66 /* top and bottom wall */
67 for (i = 2; i < xsize - 2; i++)
68 {
69 wall_x_list[count] = i;
70 wall_y_list[count] = 0;
71 count++;
72 wall_x_list[count] = i;
73 wall_y_list[count] = ysize - 1;
74 count++;
75 }
76
77 /* left and right wall */
78 for (j = 2; j < ysize - 2; j++)
79 {
80 wall_x_list[count] = 0;
81 wall_y_list[count] = j;
82 count++;
83 wall_x_list[count] = xsize - 1;
84 wall_y_list[count] = j;
85 count++;
86 }
87}
88
89/* randomly returns one of the elements from the wall point list */
90static void
91pop_wall_point (int *x, int *y)
92{
93 int index = rmg_rndm (wall_free_size);
94
95 *x = wall_x_list[index];
96 *y = wall_y_list[index];
97 /* write the last array point here */
98 wall_x_list[index] = wall_x_list[wall_free_size - 1];
99 wall_y_list[index] = wall_y_list[wall_free_size - 1];
100 wall_free_size--;
101}
102
103/* find free point: randomly look for a square adjacent to this one where
104we can place a new block without closing a path. We may only look
105up, down, right, or left. */
106static int
107find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
108{
109 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
110 int dirlist[4];
111 int count = 0; /* # elements in dirlist */
112
113 /* look up */
114 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
115 {
116 int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
117
118 cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
119
120 if (cleartest == 0)
121 dirlist[count++] = 1;
122 }
123
124 /* look down */
125 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
126 {
127 int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
128
129 cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
130
131 if (cleartest == 0)
132 dirlist[count++] = 2;
133 }
134
135 /* look right */
136 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
137 {
138 int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
139
140 cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
141
142 if (cleartest == 0)
143 dirlist[count++] = 3;
144 }
145
146 /* look left */
147 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
148 {
149 int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
150
151 cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
152
153 if (cleartest == 0)
154 dirlist[count++] = 4;
155 }
156
157 if (count == 0)
158 return -1; /* failed to find any clear points */
159
160 /* choose a random direction */
161 switch (dirlist [rmg_rndm (count)])
162 {
163 case 1: /* up */
164 *y = yc + 1;
165 *x = xc;
166 break;
167
168 case 2: /* down */
169 *y = yc - 1;
170 *x = xc;
171 break;
172
173 case 3: /* right */
174 *y = yc;
175 *x = xc + 1;
176 break;
177
178 case 4: /* left */
179 *x = xc - 1;
180 *y = yc;
181 break;
182
183 default: /* ??? */
184 return -1;
185
186 }
187
188 return 1;
189}
190
191/* recursive routine which will fill every available space in the maze
192 with walls*/
193static void
194fill_maze_full (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_full (maze, xc, yc, xsize, ysize);
206 }
207
208 /* change the if to a while for a complete maze. */
209 while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
210 fill_maze_full (maze, xc, yc, xsize, ysize);
211}
212
213/* recursive routine which will fill much of the maze, but will leave
214 some free spots (possibly large) toward the center.*/
215static void
216fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
217{
218 int xc, yc;
219
220 /* write a wall here */
221 maze[x][y] = '#';
222
223 /* decide if we're going to pick from the wall_free_list */
224 if (rmg_rndm (4) && wall_free_size > 0)
225 {
226 pop_wall_point (&xc, &yc);
227 fill_maze_sparse (maze, xc, yc, xsize, ysize);
228 }
229
230 /* change the if to a while for a complete maze. */
231 if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
232 fill_maze_sparse (maze, xc, yc, xsize, ysize);
233}
40 234
41/* the outsize interface routine: accepts sizes, returns a char 235/* the outsize interface routine: accepts sizes, returns a char
42** maze. option is a flag for either a sparse or a full maze. Sparse 236** maze. option is a flag for either a sparse or a full maze. Sparse
43mazes have sizable rooms. option = 1, full, 0, sparse.*/ 237mazes have sizable rooms. option = 1, full, 0, sparse.*/
238void
239maze_gen (Layout maze, int option)
240{
241 maze->clear ();
242 maze->border ();
44 243
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 */ 244 /* find how many free wall spots there are */
62 wall_free_size = 2 * (xsize-4) + 2*(ysize-4 ); 245 wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
63 246
64 make_wall_free_list(xsize,ysize); 247 make_wall_free_list (maze->w, maze->h);
65 248
66 /* return the empty maze */ 249 /* return the empty maze */
67 if(wall_free_size <=0 ) return maze; 250 if (wall_free_size <= 0)
251 return;
68 252
69 /* recursively generate the walls of the maze */ 253 /* recursively generate the walls of the maze */
70 /* first pop a random starting point */ 254 /* first pop a random starting point */
71 while(wall_free_size > 0) { 255 while (wall_free_size > 0)
256 {
257 int i, j;
258
72 pop_wall_point(&i,&j); 259 pop_wall_point (&i, &j);
73 if(option) fill_maze_full(maze,i,j,xsize,ysize); 260
74 else fill_maze_sparse(maze,i,j,xsize,ysize); 261 if (option)
262 fill_maze_full (maze, i, j, maze->w, maze->h);
263 else
264 fill_maze_sparse (maze, i, j, maze->w, maze->h);
75 } 265 }
76 266
77 /* clean up our intermediate data structures. */ 267 /* clean up our intermediate data structures. */
78 268
79 free(wall_x_list); 269 free (wall_x_list);
80 free(wall_y_list); 270 free (wall_y_list);
81
82 return maze;
83} 271}
84 272
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