server/random_maps/maze_gen.C

/*
 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
 * 
 * Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
 * Copyright (©) Crossfire Development Team (restored, original file without copyright notice)
 * 
 * Deliantra is free software: you can redistribute it and/or modify it under
 * the terms of the Affero GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or (at your
 * option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the Affero GNU General Public License
 * and the GNU General Public License along with this program. If not, see
 * <http://www.gnu.org/licenses/>.
 * 
 * The authors can be reached via e-mail to <support@deliantra.net>
 */

/* peterm@langmuir.eecs.berkeley.edu:  this function generates a random
blocked maze with the property that there is only one path from one spot
to any other, and there is always a path from one spot to any other.

input:  xsize, ysize;
output:  a char** array with # and . for closed and open respectively.

a char value of 0 represents a blank space:  a '#' is
a wall.

*/

/* we need to maintain a list of wall points to generate
   reasonable mazes:  a straightforward recursive random walk maze
   generator would generate a map with a trivial circle-the-outer-wall solution */

#include <vector>

#include <global.h>

#include "random_map.h"
#include "rproto.h"

struct point
{
  short x;
  short y;

  point ()
  {
  }

  point (int x, int y)
  : x(x), y(y)
  {
  }
};

/* global variables that everyone needs:  don't want to pass them in
   as parameters every time. */
static point *seed_list;
static int seed_max, seed_size;
static int xsize, ysize;
static char **maze;

static void
push (point p)
{
  assert (seed_size < seed_max);

  seed_list [seed_size++] = p;

  maze [p.x][p.y] = '#';
}

/*  the free wall points are those outer points which aren't corners or
    near corners, and don't have a maze wall growing out of them already. */
static void
push_walls ()
{
  /* top and bottom wall */
  for (int x = 2; x < xsize - 2; x++)
    {
      push (point (x,         0));
      push (point (x, ysize - 1));
    }

  /* left and right wall */
  for (int y = 2; y < ysize - 2; y++)
    {
      push (point (        0, y));
      push (point (xsize - 1, y));
    }
}

/* randomly returns one of the elements from the wall point list */
static point
pop_rand ()
{
  int index = rmg_rndm (seed_size);

  point p = seed_list [index];

  /* write the last array point here */
  seed_list [index] = seed_list [--seed_size];

  return p;
}

/* find free point:  randomly look for a square adjacent to this one where
we can place a new block without closing a path.  We may only look
up, down, right, or left. */
static int
find_free_point (point &p, point pc)
{
  /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
  int dirlist[4];
  int count = 0;                /* # elements in dirlist */

  int xc = pc.x;
  int yc = pc.y;

  /* look up */
  if (yc < ysize - 2 && xc > 2 && xc < xsize - 2)       /* it is valid to look up */
    {
      int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
                    + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];

      if (cleartest == 0)
        dirlist[count++] = 1;
    }

  /* look down */
  if (yc > 2 && xc > 2 && xc < xsize - 2)       /* it is valid to look down */
    {
      int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
                    + maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];

      if (cleartest == 0)
        dirlist[count++] = 2;
    }

  /* look right */
  if (xc < xsize - 2 && yc > 2 && yc < ysize - 2)       /* it is valid to look left */
    {
      int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
                    + maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];

      if (cleartest == 0)
        dirlist[count++] = 3;
    }

  /* look left */
  if (xc > 2 && yc > 2 && yc < ysize - 2)       /* it is valid to look down */
    {
      int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
                    + maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];

      if (cleartest == 0)
        dirlist[count++] = 4;
    }

  if (count == 0)
    return -1;                  /* failed to find any clear points */

  /* choose a random direction */
  switch (dirlist [rmg_rndm (count)])
    {
      case 1:                  /* up */
        p.x = xc;
        p.y = yc + 1;
        break;

      case 2:                  /* down */
        p.x = xc;
        p.y = yc - 1;
        break;

      case 3:                  /* right */
        p.x = xc + 1;
        p.y = yc;
        break;
        
      case 4:                  /* left */
        p.x = xc - 1;
        p.y = yc;
        break;
    }

  return 1;
}

/* the outsize interface routine:  accepts sizes, returns a char
** maze.  option is a flag for either a sparse or a full maze. Sparse
mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
void
maze_gen (Layout maze, int subtype)
{
  xsize = maze->w;
  ysize = maze->h;
  ::maze = maze;

  maze->clear ();
  maze->border ();

  if (xsize < 4 || ysize < 4)
    return;

  seed_max = xsize * ysize;
  seed_size = 0;
  seed_list = salloc<point> (seed_max);

  if (subtype > 0)
    push_walls ();

  if (subtype == 0 || subtype == 2)
    for (int i = (xsize + ysize) / 2; i; --i)
      push (point (rmg_rndm (1, xsize - 2), rmg_rndm (1, ysize - 2)));

  bool full = subtype == 3;

  /* recursively generate the walls of the maze */
  /* first pop a random starting point */
  while (seed_size)
    {
      point p = pop_rand ();

      for (;;)
        {
          point pc;

          maze [p.x][p.y] = '#';

          if (find_free_point (pc, p) < 0)
            break;

          if (full)
            push (p);

          if (!rmg_rndm (8))
            {
              if (!full)
                push (pc);

              break;
            }

          p = pc;
        }
    }

  /* clean up our intermediate data structures. */
  sfree (seed_list, seed_max);
}

#if 0
static struct demo
{
  demo ()
  {
    Layout layout (40, 25);
    rmg_rndm.seed (time (0));

    for(int i=1;i<10;++i)
      {
        maze_gen (layout, 3);
        layout.print ();
      }
    exit (1);
  }
} demo;
#endif
Revision:	1.22
Committed:	Tue Jun 29 18:27:02 2010 UTC (14 years ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.21:	+1 -1 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.16	/*
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			*/
23	root	1.5
24	elmex	1.1	/* peterm@langmuir.eecs.berkeley.edu: this function generates a random
25			blocked maze with the property that there is only one path from one spot
26			to any other, and there is always a path from one spot to any other.
27
28			input: xsize, ysize;
29			output: a char** array with # and . for closed and open respectively.
30
31			a char value of 0 represents a blank space: a '#' is
32			a wall.
33
34			*/
35
36			/* we need to maintain a list of wall points to generate
37			reasonable mazes: a straightforward recursive random walk maze
38			generator would generate a map with a trivial circle-the-outer-wall solution */
39
40	root	1.20	#include <vector>
41
42	elmex	1.1	#include <global.h>
43	root	1.3
44	root	1.8	#include "random_map.h"
45			#include "rproto.h"
46	elmex	1.1
47	root	1.20	struct 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
62	elmex	1.1	/* global variables that everyone needs: don't want to pass them in
63			as parameters every time. */
64	root	1.20	static point *seed_list;
65	root	1.21	static int seed_max, seed_size;
66	root	1.19	static int xsize, ysize;
67	root	1.20	static char **maze;
68	elmex	1.1
69	root	1.21	static void
70			push (point p)
71			{
72			assert (seed_size < seed_max);
73
74			seed_list [seed_size++] = p;
75
76			maze [p.x][p.y] = '#';
77			}
78
79	elmex	1.1	/* 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. */
81	root	1.14	static void
82	root	1.21	push_walls ()
83	root	1.3	{
84	elmex	1.1	/* top and bottom wall */
85	root	1.20	for (int x = 2; x < xsize - 2; x++)
86	root	1.3	{
87	root	1.21	push (point (x, 0));
88			push (point (x, ysize - 1));
89	root	1.3	}
90	elmex	1.1
91			/* left and right wall */
92	root	1.20	for (int y = 2; y < ysize - 2; y++)
93	root	1.3	{
94	root	1.21	push (point ( 0, y));
95			push (point (xsize - 1, y));
96	root	1.3	}
97	elmex	1.1	}
98
99			/* randomly returns one of the elements from the wall point list */
100	root	1.20	static point
101	root	1.21	pop_rand ()
102	root	1.3	{
103	root	1.20	int index = rmg_rndm (seed_size);
104	root	1.3
105	root	1.20	point p = seed_list [index];
106	root	1.17
107	elmex	1.1	/* write the last array point here */
108	root	1.20	seed_list [index] = seed_list [--seed_size];
109
110			return p;
111	elmex	1.1	}
112
113			/* find free point: randomly look for a square adjacent to this one where
114			we can place a new block without closing a path. We may only look
115			up, down, right, or left. */
116	root	1.14	static int
117	root	1.20	find_free_point (point &p, point pc)
118	root	1.3	{
119	root	1.12	/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
120	root	1.3	int dirlist[4];
121			int count = 0; /* # elements in dirlist */
122	elmex	1.1
123	root	1.20	int xc = pc.x;
124			int yc = pc.y;
125
126	elmex	1.1	/* look up */
127	root	1.3	if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
128	elmex	1.1	{
129	root	1.17	int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
130			+ maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
131	root	1.3
132			if (cleartest == 0)
133	root	1.12	dirlist[count++] = 1;
134	elmex	1.1	}
135
136			/* look down */
137	root	1.3	if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
138	elmex	1.1	{
139	root	1.17	int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
140			+ maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
141	root	1.3
142			if (cleartest == 0)
143	root	1.12	dirlist[count++] = 2;
144	elmex	1.1	}
145
146			/* look right */
147	root	1.3	if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
148	elmex	1.1	{
149	root	1.17	int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
150			+ maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
151	root	1.3
152			if (cleartest == 0)
153	root	1.12	dirlist[count++] = 3;
154	elmex	1.1	}
155
156			/* look left */
157	root	1.3	if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
158	elmex	1.1	{
159	root	1.17	int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
160			+ maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
161	root	1.2
162	root	1.3	if (cleartest == 0)
163	root	1.12	dirlist[count++] = 4;
164	elmex	1.1	}
165
166	root	1.3	if (count == 0)
167			return -1; /* failed to find any clear points */
168	elmex	1.1
169			/* choose a random direction */
170	root	1.12	switch (dirlist [rmg_rndm (count)])
171	elmex	1.1	{
172	root	1.5	case 1: /* up */
173	root	1.20	p.x = xc;
174			p.y = yc + 1;
175	root	1.12	break;
176
177	root	1.5	case 2: /* down */
178	root	1.20	p.x = xc;
179			p.y = yc - 1;
180	root	1.12	break;
181
182	root	1.5	case 3: /* right */
183	root	1.20	p.x = xc + 1;
184			p.y = yc;
185	root	1.12	break;
186
187	root	1.5	case 4: /* left */
188	root	1.20	p.x = xc - 1;
189			p.y = yc;
190	root	1.12	break;
191	elmex	1.1	}
192	root	1.12
193	elmex	1.1	return 1;
194			}
195
196	root	1.13	/* the outsize interface routine: accepts sizes, returns a char
197			** maze. option is a flag for either a sparse or a full maze. Sparse
198	root	1.21	mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
199	root	1.13	void
200	root	1.21	maze_gen (Layout maze, int subtype)
201	root	1.13	{
202	root	1.19	xsize = maze->w;
203			ysize = maze->h;
204	root	1.20	::maze = maze;
205	root	1.19
206	root	1.20	maze->clear ();
207			maze->border ();
208	root	1.13
209	root	1.20	if (xsize < 4 \|\| ysize < 4)
210			return;
211	root	1.13
212	root	1.21	seed_max = xsize * ysize;
213			seed_size = 0;
214			seed_list = salloc<point> (seed_max);
215
216			if (subtype > 0)
217			push_walls ();
218
219			if (subtype == 0 \|\| subtype == 2)
220			for (int i = (xsize + ysize) / 2; i; --i)
221			push (point (rmg_rndm (1, xsize - 2), rmg_rndm (1, ysize - 2)));
222
223			bool full = subtype == 3;
224	root	1.13
225			/* recursively generate the walls of the maze */
226			/* first pop a random starting point */
227	root	1.20	while (seed_size)
228	root	1.21	{
229			point p = pop_rand ();
230
231			for (;;)
232			{
233			point pc;
234
235			maze [p.x][p.y] = '#';
236
237			if (find_free_point (pc, p) < 0)
238			break;
239
240			if (full)
241			push (p);
242
243			if (!rmg_rndm (8))
244			{
245			if (!full)
246			push (pc);
247
248			break;
249			}
250
251			p = pc;
252			}
253			}
254	root	1.13
255			/* clean up our intermediate data structures. */
256	root	1.21	sfree (seed_list, seed_max);
257	root	1.13	}
258
259	root	1.20	#if 0
260	root	1.17	static struct demo
261			{
262			demo ()
263			{
264	root	1.22	Layout layout (40, 25);
265	root	1.17	rmg_rndm.seed (time (0));
266
267			for(int i=1;i<10;++i)
268			{
269	root	1.21	maze_gen (layout, 3);
270	root	1.17	layout.print ();
271			}
272			exit (1);
273			}
274			} demo;
275			#endif