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.27 by root, Sat Apr 23 04:56:52 2011 UTC

1 1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 *
4 * Copyright (©) 2005,2006,2007,2008,2009,2010,2011 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) 1994-2004 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> 40#include <vector>
41
20#include <global.h> 42#include <global.h>
21/*#include <random_map.h>*/ 43
22#include <maze_gen.h>
23#include <time.h> 44#include <rmg.h>
24 45#include "rproto.h"
25
26/* this include solely, and only, is needed for the definition of RANDOM */
27
28
29 46
30/* global variables that everyone needs: don't want to pass them in 47/* global variables that everyone needs: don't want to pass them in
31 as parameters every time. */ 48 as parameters every time. */
32int *wall_x_list=0; 49static fixed_stack<point> seeds;
33int *wall_y_list=0; 50static int xsize, ysize;
34int wall_free_size=0; 51static char **maze;
35 52
36/* heuristically, we need to change wall_chance based on the size of 53static void
37 the maze. */ 54push (point p)
38 55{
39int wall_chance; 56 seeds.push (p);
40 57 maze [p.x][p.y] = '#';
41/* the outsize interface routine: accepts sizes, returns a char
42** maze. option is a flag for either a sparse or a full maze. Sparse
43mazes have sizable rooms. option = 1, full, 0, sparse.*/
44
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 */
62 wall_free_size = 2 * (xsize-4) + 2*(ysize-4 );
63
64 make_wall_free_list(xsize,ysize);
65
66 /* return the empty maze */
67 if(wall_free_size <=0 ) return maze;
68
69 /* recursively generate the walls of the maze */
70 /* first pop a random starting point */
71 while(wall_free_size > 0) {
72 pop_wall_point(&i,&j);
73 if(option) fill_maze_full(maze,i,j,xsize,ysize);
74 else fill_maze_sparse(maze,i,j,xsize,ysize);
75 }
76
77 /* clean up our intermediate data structures. */
78
79 free(wall_x_list);
80 free(wall_y_list);
81
82 return maze;
83} 58}
84 59
85 60/* randomly returns one of the elements from the wall point list */
61static point
62pop_rand ()
63{
64 return seeds.remove (rmg_rndm (seeds.size));
65}
86 66
87/* the free wall points are those outer points which aren't corners or 67/* 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. */ 68 near corners, and don't have a maze wall growing out of them already. */
89 69static void
90void make_wall_free_list(int xsize, int ysize) { 70push_walls ()
91 int i,j,count; 71{
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 */ 72 /* top and bottom wall */
101 for(i = 2; i<xsize-2; i++) { 73 for (int x = 2; x < xsize - 2; x++)
102 wall_x_list[count] = i; 74 {
103 wall_y_list[count] = 0; 75 push (point (x, 0));
104 count++; 76 push (point (x, ysize - 1));
105 wall_x_list[count] = i;
106 wall_y_list[count] = ysize-1;
107 count++;
108 } 77 }
109 78
110 /* left and right wall */ 79 /* left and right wall */
111 for(j = 2; j<ysize-2; j++) { 80 for (int y = 2; y < ysize - 2; y++)
112 wall_x_list[count] = 0; 81 {
113 wall_y_list[count] = j; 82 push (point ( 0, y));
114 count++; 83 push (point (xsize - 1, y));
115 wall_x_list[count] = xsize-1;
116 wall_y_list[count] = j;
117 count++;
118 } 84 }
119} 85}
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 86
137/* find free point: randomly look for a square adjacent to this one where 87/* 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 88we can place a new block without closing a path. We may only look
139up, down, right, or left. */ 89up, down, right, or left. */
140 90static int
141int find_free_point(char **maze,int *x, int *y,int xc,int yc, int xsize, int ysize) { 91find_free_point (point &p, point pc)
142 92{
143/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */ 93 /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
144 int dirlist[4]; 94 int dirlist[4];
145 int count = 0; /* # elements in dirlist */ 95 int count = 0; /* # elements in dirlist */
96
97 int xc = pc.x;
98 int yc = pc.y;
146 99
147 /* look up */ 100 /* look up */
148 if(yc < ysize-2 && xc > 2 && xc < xsize-2) /* it is valid to look up */ 101 if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
149 { 102 {
150 int cleartest = (int) maze[xc][yc+1] + (int)maze[xc-1][yc+1] 103 int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
151 + (int) maze[xc+1][yc+1]; 104 + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
152 cleartest += (int) maze[xc][yc+2] + (int)maze[xc-1][yc+2]
153 + (int) maze[xc+1][yc+2];
154 105
155 if(cleartest == 0) { 106 if (cleartest == 0)
156 dirlist[count] = 1; 107 dirlist[count++] = 1;
157 count++;
158 }
159 } 108 }
160
161 109
162 /* look down */ 110 /* look down */
163 if(yc > 2 && xc > 2 && xc < xsize-2) /* it is valid to look down */ 111 if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
164 { 112 {
165 int cleartest = (int) maze[xc][yc-1] + (int)maze[xc-1][yc-1] 113 int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
166 + (int) maze[xc+1][yc-1]; 114 + maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
167 cleartest += (int) maze[xc][yc-2] + (int)maze[xc-1][yc-2]
168 + (int) maze[xc+1][yc-2];
169 115
170 if(cleartest == 0) { 116 if (cleartest == 0)
171 dirlist[count] = 2; 117 dirlist[count++] = 2;
172 count++;
173 }
174 } 118 }
175
176 119
177 /* look right */ 120 /* look right */
178 if(xc < xsize- 2 && yc > 2 && yc < ysize-2) /* it is valid to look left */ 121 if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
179 { 122 {
180 int cleartest = (int) maze[xc+1][yc] + (int)maze[xc+1][yc-1] 123 int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
181 + (int) maze[xc+1][yc+1]; 124 + maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
182 cleartest += (int) maze[xc+2][yc] + (int)maze[xc+2][yc-1]
183 + (int) maze[xc+2][yc+1];
184 125
185 if(cleartest == 0) { 126 if (cleartest == 0)
186 dirlist[count] = 3; 127 dirlist[count++] = 3;
187 count++;
188 }
189 } 128 }
190
191 129
192 /* look left */ 130 /* look left */
193 if(xc > 2 && yc > 2 && yc < ysize-2) /* it is valid to look down */ 131 if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
194 { 132 {
195 int cleartest = (int) maze[xc-1][yc] + (int)maze[xc-1][yc-1] 133 int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
196 + (int) maze[xc-1][yc+1]; 134 + maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
197 cleartest += (int) maze[xc-2][yc] + (int)maze[xc-2][yc-1]
198 + (int) maze[xc-2][yc+1];
199 135
200 if(cleartest == 0) { 136 if (cleartest == 0)
201 dirlist[count] = 4; 137 dirlist[count++] = 4;
202 count++;
203 }
204 } 138 }
205 139
140 if (count == 0)
206 if(count==0) return -1; /* failed to find any clear points */ 141 return -1; /* failed to find any clear points */
207 142
208 /* choose a random direction */ 143 /* choose a random direction */
209 if(count > 1) count = RANDOM() % count;
210 else count=0;
211 switch(dirlist[count]) { 144 switch (dirlist [rmg_rndm (count)])
212 case 1: /* up */
213 { 145 {
214 *y = yc +1; 146 case 1: /* up */
215 *x = xc; 147 p.x = xc;
216 break; 148 p.y = yc + 1;
149 break;
150
151 case 2: /* down */
152 p.x = xc;
153 p.y = yc - 1;
154 break;
155
156 case 3: /* right */
157 p.x = xc + 1;
158 p.y = yc;
159 break;
160
161 case 4: /* left */
162 p.x = xc - 1;
163 p.y = yc;
164 break;
217 }; 165 }
218 case 2: /* down */ 166
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; 167 return 1;
242} 168}
243 169
244/* recursive routine which will fill every available space in the maze 170/* the outsize interface routine: accepts sizes, returns a char
245 with walls*/ 171** maze. option is a flag for either a sparse or a full maze. Sparse
172mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
173void
174maze_gen (layout &maze, int subtype)
175{
176 xsize = maze.w;
177 ysize = maze.h;
178 ::maze = maze;
246 179
247void fill_maze_full(char **maze, int x, int y, int xsize, int ysize ) { 180 maze.clear ();
248 int xc,yc; 181 maze.border ();
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 182
183 if (xsize < 4 || ysize < 4)
184 return;
265 185
266/* recursive routine which will fill much of the maze, but will leave 186 seeds.reset (xsize * ysize);
267 some free spots (possibly large) toward the center.*/
268 187
269void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize ) { 188 if (subtype > 0)
270 int xc,yc; 189 push_walls ();
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 190
191 if (subtype == 0 || subtype == 2)
192 for (int i = (xsize + ysize) / 2; i; --i)
193 push (point (rmg_rndm (1, xsize - 2), rmg_rndm (1, ysize - 2)));
287 194
195 bool full = subtype == 3;
288 196
289 197 /* recursively generate the walls of the maze */
290 198 /* first pop a random starting point */
199 while (seeds.size)
291 200 {
201 point p = pop_rand ();
292 202
203 for (;;)
204 {
205 point pc;
206
207 maze [p.x][p.y] = '#';
208
209 if (find_free_point (pc, p) < 0)
210 break;
211
212 if (full)
213 push (p);
214
215 if (!rmg_rndm (8))
216 {
217 if (!full)
218 push (pc);
219
220 break;
221 }
222
223 p = pc;
224 }
293 225 }
226
227 seeds.free ();
228}
229

Diff Legend

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