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 <global.h>

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

/* global variables that everyone needs:  don't want to pass them in
   as parameters every time. */
static int *wall_x_list = 0;
static int *wall_y_list = 0;
static int wall_free_size = 0;
static int xsize, ysize;

/*  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
make_wall_free_list (int xsize, int ysize)
{
  int i, j, count;

  count = 0;                    /* entries already placed in the free list */
  /*allocate it */
  if (wall_free_size < 0)
    return;

  wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
  wall_y_list = (int *)calloc (sizeof (int), wall_free_size);

  /* top and bottom wall */
  for (i = 2; i < xsize - 2; i++)
    {
      wall_x_list[count] = i;
      wall_y_list[count] = 0;
      count++;
      wall_x_list[count] = i;
      wall_y_list[count] = ysize - 1;
      count++;
    }

  /* left and right wall */
  for (j = 2; j < ysize - 2; j++)
    {
      wall_x_list[count] = 0;
      wall_y_list[count] = j;
      count++;
      wall_x_list[count] = xsize - 1;
      wall_y_list[count] = j;
      count++;
    }
}

/* randomly returns one of the elements from the wall point list */
static void
pop_wall_point (int *x, int *y)
{
  int index = rmg_rndm (wall_free_size);

  *x = wall_x_list[index];
  *y = wall_y_list[index];

  /* write the last array point here */
  wall_x_list[index] = wall_x_list[wall_free_size - 1];
  wall_y_list[index] = wall_y_list[wall_free_size - 1];
  wall_free_size--;
}

/* 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 (char **maze, int *x, int *y, int xc, int yc)
{
  /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
  int dirlist[4];
  int count = 0;                /* # elements in dirlist */

  /* 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 */
        *y = yc + 1;
        *x = xc;
        break;

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

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

  return 1;
}

/* recursive routine which will fill every available space in the maze
        with walls*/
static void
fill_maze_full (char **maze, int x, int y)
{
  int xc, yc;

  /* write a wall here */
  maze[x][y] = '#';

  /* decide if we're going to pick from the wall_free_list */
  if (rmg_rndm (2) && wall_free_size > 0)
    {
      pop_wall_point (&xc, &yc);
      fill_maze_full (maze, xc, yc);
    }

  /* change the while to an if for a sparse maze. */
  while (find_free_point (maze, &xc, &yc, x, y) != -1)
    fill_maze_full (maze, xc, yc);
}

/* recursive routine which will fill much of the maze, but will leave
        some free spots (possibly large) toward the center.*/
static void
fill_maze_sparse (char **maze, int x, int y)
{
  int xc, yc;

  /* write a wall here */
  maze[x][y] = '#';

  /* decide if we're going to pick from the wall_free_list */
  if (rmg_rndm (2) && wall_free_size > 0)
    {
      pop_wall_point (&xc, &yc);
      fill_maze_sparse (maze, xc, yc);
    }

  /* change the if to a while for a complete maze. */
  if (find_free_point (maze, &xc, &yc, x, y) != -1)
    fill_maze_sparse (maze, xc, yc);
}

/* 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 = 1, full, 0, sparse.*/
void
maze_gen (Layout maze, int full)
{
  maze->clear ();
  maze->border ();

  xsize = maze->w;
  ysize = maze->h;

  /* find how many free wall spots there are */
  wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);

  make_wall_free_list (maze->w, maze->h);

  /* return the empty maze */
  if (wall_free_size <= 0)
    return;

  /* recursively generate the walls of the maze */
  /* first pop a random starting point */
  while (wall_free_size > 0)
    {
      int i, j;

      pop_wall_point (&i, &j);

      if (full)
        fill_maze_full (maze, i, j);
      else
        fill_maze_sparse (maze, i, j);
    }

  /* clean up our intermediate data structures. */

  free (wall_x_list);
  free (wall_y_list);
}

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

    for(int i=1;i<10;++i)
      {
        maze_gen (layout, 1);
        layout.print ();
      }
    exit (1);
  }
} demo;
#endif
Revision:	1.19
Committed:	Sun Jun 27 16:36:12 2010 UTC (13 years, 10 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.18:	+16 -12 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			#include <global.h>
41	root	1.3
42	root	1.8	#include "random_map.h"
43			#include "rproto.h"
44	elmex	1.1
45			/* global variables that everyone needs: don't want to pass them in
46			as parameters every time. */
47	root	1.14	static int *wall_x_list = 0;
48			static int *wall_y_list = 0;
49			static int wall_free_size = 0;
50	root	1.19	static int xsize, ysize;
51	elmex	1.1
52			/* the free wall points are those outer points which aren't corners or
53			near corners, and don't have a maze wall growing out of them already. */
54	root	1.14	static void
55	root	1.3	make_wall_free_list (int xsize, int ysize)
56			{
57			int i, j, count;
58
59			count = 0; /* entries already placed in the free list */
60			/allocate it /
61			if (wall_free_size < 0)
62			return;
63
64	root	1.8	wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
65			wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
66	elmex	1.1
67			/* top and bottom wall */
68	root	1.3	for (i = 2; i < xsize - 2; i++)
69			{
70			wall_x_list[count] = i;
71			wall_y_list[count] = 0;
72			count++;
73			wall_x_list[count] = i;
74			wall_y_list[count] = ysize - 1;
75			count++;
76			}
77	elmex	1.1
78			/* left and right wall */
79	root	1.3	for (j = 2; j < ysize - 2; j++)
80			{
81			wall_x_list[count] = 0;
82			wall_y_list[count] = j;
83			count++;
84			wall_x_list[count] = xsize - 1;
85			wall_y_list[count] = j;
86			count++;
87			}
88	elmex	1.1	}
89
90			/* randomly returns one of the elements from the wall point list */
91	root	1.14	static void
92	root	1.3	pop_wall_point (int x, int y)
93			{
94	root	1.11	int index = rmg_rndm (wall_free_size);
95	root	1.3
96	elmex	1.1	*x = wall_x_list[index];
97			*y = wall_y_list[index];
98	root	1.17
99	elmex	1.1	/* write the last array point here */
100	root	1.3	wall_x_list[index] = wall_x_list[wall_free_size - 1];
101			wall_y_list[index] = wall_y_list[wall_free_size - 1];
102	elmex	1.1	wall_free_size--;
103			}
104
105			/* find free point: randomly look for a square adjacent to this one where
106			we can place a new block without closing a path. We may only look
107			up, down, right, or left. */
108	root	1.14	static int
109	root	1.19	find_free_point (char *maze, int x, int *y, int xc, int yc)
110	root	1.3	{
111	root	1.12	/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
112	root	1.3	int dirlist[4];
113			int count = 0; /* # elements in dirlist */
114	elmex	1.1
115			/* look up */
116	root	1.3	if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
117	elmex	1.1	{
118	root	1.17	int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
119			+ maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
120	root	1.3
121			if (cleartest == 0)
122	root	1.12	dirlist[count++] = 1;
123	elmex	1.1	}
124
125			/* look down */
126	root	1.3	if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
127	elmex	1.1	{
128	root	1.17	int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
129			+ maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
130	root	1.3
131			if (cleartest == 0)
132	root	1.12	dirlist[count++] = 2;
133	elmex	1.1	}
134
135			/* look right */
136	root	1.3	if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
137	elmex	1.1	{
138	root	1.17	int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
139			+ maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
140	root	1.3
141			if (cleartest == 0)
142	root	1.12	dirlist[count++] = 3;
143	elmex	1.1	}
144
145			/* look left */
146	root	1.3	if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
147	elmex	1.1	{
148	root	1.17	int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
149			+ maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
150	root	1.2
151	root	1.3	if (cleartest == 0)
152	root	1.12	dirlist[count++] = 4;
153	elmex	1.1	}
154
155	root	1.3	if (count == 0)
156			return -1; /* failed to find any clear points */
157	elmex	1.1
158			/* choose a random direction */
159	root	1.12	switch (dirlist [rmg_rndm (count)])
160	elmex	1.1	{
161	root	1.5	case 1: /* up */
162	root	1.12	*y = yc + 1;
163			*x = xc;
164			break;
165
166	root	1.5	case 2: /* down */
167	root	1.12	*y = yc - 1;
168			*x = xc;
169			break;
170
171	root	1.5	case 3: /* right */
172	root	1.12	*y = yc;
173			*x = xc + 1;
174			break;
175
176	root	1.5	case 4: /* left */
177	root	1.12	*x = xc - 1;
178			*y = yc;
179			break;
180	elmex	1.1	}
181	root	1.12
182	elmex	1.1	return 1;
183			}
184
185			/* recursive routine which will fill every available space in the maze
186	root	1.3	with walls*/
187	root	1.13	static void
188	root	1.19	fill_maze_full (char **maze, int x, int y)
189	root	1.3	{
190			int xc, yc;
191	elmex	1.1
192			/* write a wall here */
193			maze[x][y] = '#';
194	root	1.3
195	elmex	1.1	/* decide if we're going to pick from the wall_free_list */
196	root	1.18	if (rmg_rndm (2) && wall_free_size > 0)
197	root	1.3	{
198			pop_wall_point (&xc, &yc);
199	root	1.19	fill_maze_full (maze, xc, yc);
200	root	1.3	}
201
202	root	1.17	/* change the while to an if for a sparse maze. */
203	root	1.19	while (find_free_point (maze, &xc, &yc, x, y) != -1)
204			fill_maze_full (maze, xc, yc);
205	elmex	1.1	}
206
207			/* recursive routine which will fill much of the maze, but will leave
208	root	1.2	some free spots (possibly large) toward the center.*/
209	root	1.13	static void
210	root	1.19	fill_maze_sparse (char **maze, int x, int y)
211	root	1.3	{
212			int xc, yc;
213
214	elmex	1.1	/* write a wall here */
215			maze[x][y] = '#';
216	root	1.3
217	elmex	1.1	/* decide if we're going to pick from the wall_free_list */
218	root	1.18	if (rmg_rndm (2) && wall_free_size > 0)
219	root	1.3	{
220			pop_wall_point (&xc, &yc);
221	root	1.19	fill_maze_sparse (maze, xc, yc);
222	root	1.3	}
223
224	root	1.17	/* change the if to a while for a complete maze. */
225	root	1.19	if (find_free_point (maze, &xc, &yc, x, y) != -1)
226			fill_maze_sparse (maze, xc, yc);
227	elmex	1.1	}
228	root	1.12
229	root	1.13	/* the outsize interface routine: accepts sizes, returns a char
230			** maze. option is a flag for either a sparse or a full maze. Sparse
231			mazes have sizable rooms. option = 1, full, 0, sparse.*/
232			void
233	root	1.17	maze_gen (Layout maze, int full)
234	root	1.13	{
235			maze->clear ();
236			maze->border ();
237
238	root	1.19	xsize = maze->w;
239			ysize = maze->h;
240
241	root	1.13	/* find how many free wall spots there are */
242			wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
243
244			make_wall_free_list (maze->w, maze->h);
245
246			/* return the empty maze */
247			if (wall_free_size <= 0)
248			return;
249
250			/* recursively generate the walls of the maze */
251			/* first pop a random starting point */
252			while (wall_free_size > 0)
253			{
254			int i, j;
255
256			pop_wall_point (&i, &j);
257
258	root	1.17	if (full)
259	root	1.19	fill_maze_full (maze, i, j);
260	root	1.13	else
261	root	1.19	fill_maze_sparse (maze, i, j);
262	root	1.13	}
263
264			/* clean up our intermediate data structures. */
265
266			free (wall_x_list);
267			free (wall_y_list);
268			}
269
270	root	1.19	#if 1
271	root	1.17	static struct demo
272			{
273			demo ()
274			{
275			Layout layout (30, 30);
276			rmg_rndm.seed (time (0));
277
278			for(int i=1;i<10;++i)
279			{
280			maze_gen (layout, 1);
281			layout.print ();
282			}
283			exit (1);
284			}
285			} demo;
286			#endif