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.21 by root, Tue Jun 29 16:52:53 2010 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. 2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 * 3 *
4 * Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team 4 * Copyright (©) 2005,2006,2007,2008,2009,2010,2011 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) Crossfire Development Team (restored, original file without copyright notice) 5 * Copyright (©) 1994-2004 Crossfire Development Team (restored, original file without copyright notice)
6 * 6 *
7 * Deliantra is free software: you can redistribute it and/or modify it under 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 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 9 * Free Software Foundation, either version 3 of the License, or (at your
10 * option) any later version. 10 * option) any later version.
… …
39 39
40#include <vector> 40#include <vector>
41 41
42#include <global.h> 42#include <global.h>
43 43
44#include "random_map.h" 44#include <rmg.h>
45#include "rproto.h" 45#include "rproto.h"
46
47struct point
48{
49 short x;
50 short y;
51
52 point ()
53 {
54 }
55
56 point (int x, int y)
57 : x(x), y(y)
58 {
59 }
60};
61 46
62/* 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
63 as parameters every time. */ 48 as parameters every time. */
64static point *seed_list; 49static fixed_stack<point> seeds;
65static int seed_max, seed_size;
66static int xsize, ysize; 50static int xsize, ysize;
67static char **maze; 51static char **maze;
68 52
69static void 53static void
70push (point p) 54push (point p)
71{ 55{
72 assert (seed_size < seed_max); 56 seeds.push (p);
73
74 seed_list [seed_size++] = p;
75
76 maze [p.x][p.y] = '#'; 57 maze [p.x][p.y] = '#';
58}
59
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));
77} 65}
78 66
79/* 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
80 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. */
81static void 69static void
… …
92 for (int y = 2; y < ysize - 2; y++) 80 for (int y = 2; y < ysize - 2; y++)
93 { 81 {
94 push (point ( 0, y)); 82 push (point ( 0, y));
95 push (point (xsize - 1, y)); 83 push (point (xsize - 1, y));
96 } 84 }
97}
98
99/* randomly returns one of the elements from the wall point list */
100static point
101pop_rand ()
102{
103 int index = rmg_rndm (seed_size);
104
105 point p = seed_list [index];
106
107 /* write the last array point here */
108 seed_list [index] = seed_list [--seed_size];
109
110 return p;
111} 85}
112 86
113/* 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
114we 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
115up, down, right, or left. */ 89up, down, right, or left. */
… …
195 169
196/* the outsize interface routine: accepts sizes, returns a char 170/* the outsize interface routine: accepts sizes, returns a char
197** maze. option is a flag for either a sparse or a full maze. Sparse 171** maze. option is a flag for either a sparse or a full maze. Sparse
198mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/ 172mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
199void 173void
200maze_gen (Layout maze, int subtype) 174maze_gen (layout &maze, int subtype)
201{ 175{
202 xsize = maze->w; 176 xsize = maze.w;
203 ysize = maze->h; 177 ysize = maze.h;
204 ::maze = maze; 178 ::maze = maze;
205 179
206 maze->clear (); 180 maze.clear ();
207 maze->border (); 181 maze.border ();
208 182
209 if (xsize < 4 || ysize < 4) 183 if (xsize < 4 || ysize < 4)
210 return; 184 return;
211 185
212 seed_max = xsize * ysize; 186 seeds.reset (xsize * ysize);
213 seed_size = 0;
214 seed_list = salloc<point> (seed_max);
215 187
216 if (subtype > 0) 188 if (subtype > 0)
217 push_walls (); 189 push_walls ();
218 190
219 if (subtype == 0 || subtype == 2) 191 if (subtype == 0 || subtype == 2)
… …
222 194
223 bool full = subtype == 3; 195 bool full = subtype == 3;
224 196
225 /* recursively generate the walls of the maze */ 197 /* recursively generate the walls of the maze */
226 /* first pop a random starting point */ 198 /* first pop a random starting point */
227 while (seed_size) 199 while (seeds.size)
228 { 200 {
229 point p = pop_rand (); 201 point p = pop_rand ();
230 202
231 for (;;) 203 for (;;)
232 { 204 {
… …
250 222
251 p = pc; 223 p = pc;
252 } 224 }
253 } 225 }
254 226
255 /* clean up our intermediate data structures. */ 227 seeds.free ();
256 sfree (seed_list, seed_max);
257} 228}
258 229
259#if 0
260static struct demo
261{
262 demo ()
263 {
264 Layout layout (30, 30);
265 rmg_rndm.seed (time (0));
266
267 for(int i=1;i<10;++i)
268 {
269 maze_gen (layout, 3);
270 layout.print ();
271 }
272 exit (1);
273 }
274} demo;
275#endif

Diff Legend

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