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;

/*  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, int xsize, int ysize)
{
  /* 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 = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];

      cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) 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 = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];

      cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) 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 = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];

      cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) 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 = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];

      cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) 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;

      default:                 /* ??? */
        return -1;

    }

  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 xsize, int ysize)
{
  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 (4) && wall_free_size > 0)
    {
      pop_wall_point (&xc, &yc);
      fill_maze_full (maze, xc, yc, xsize, ysize);
    }

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

/* 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 xsize, int ysize)
{
  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 (4) && wall_free_size > 0)
    {
      pop_wall_point (&xc, &yc);
      fill_maze_sparse (maze, xc, yc, xsize, ysize);
    }

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

/* 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 option)
{
  maze->clear ();
  maze->border ();

  /* 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 (option)
        fill_maze_full (maze, i, j, maze->w, maze->h);
      else
        fill_maze_sparse (maze, i, j, maze->w, maze->h);
    }

  /* clean up our intermediate data structures. */

  free (wall_x_list);
  free (wall_y_list);
}

Revision:	1.16
Committed:	Sat Nov 7 18:32:45 2009 UTC (14 years, 6 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-3_0, rel-2_92, rel-2_93
Changes since 1.15:	+22 -0 lines
Log Message:	add copyright notices to .C files
#	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	elmex	1.1
51			/* the free wall points are those outer points which aren't corners or
52			near corners, and don't have a maze wall growing out of them already. */
53	root	1.14	static void
54	root	1.3	make_wall_free_list (int xsize, int ysize)
55			{
56			int i, j, count;
57
58			count = 0; /* entries already placed in the free list */
59			/allocate it /
60			if (wall_free_size < 0)
61			return;
62
63	root	1.8	wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
64			wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
65	elmex	1.1
66			/* top and bottom wall */
67	root	1.3	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	elmex	1.1
77			/* left and right wall */
78	root	1.3	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	elmex	1.1	}
88
89			/* randomly returns one of the elements from the wall point list */
90	root	1.14	static void
91	root	1.3	pop_wall_point (int x, int y)
92			{
93	root	1.11	int index = rmg_rndm (wall_free_size);
94	root	1.3
95	elmex	1.1	*x = wall_x_list[index];
96			*y = wall_y_list[index];
97			/* write the last array point here */
98	root	1.3	wall_x_list[index] = wall_x_list[wall_free_size - 1];
99			wall_y_list[index] = wall_y_list[wall_free_size - 1];
100	elmex	1.1	wall_free_size--;
101			}
102
103			/* find free point: randomly look for a square adjacent to this one where
104			we can place a new block without closing a path. We may only look
105			up, down, right, or left. */
106	root	1.14	static int
107	root	1.3	find_free_point (char *maze, int x, int *y, int xc, int yc, int xsize, int ysize)
108			{
109	root	1.12	/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
110	root	1.3	int dirlist[4];
111			int count = 0; /* # elements in dirlist */
112	elmex	1.1
113			/* look up */
114	root	1.3	if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
115	elmex	1.1	{
116	root	1.3	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	root	1.12	dirlist[count++] = 1;
122	elmex	1.1	}
123
124			/* look down */
125	root	1.3	if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
126	elmex	1.1	{
127	root	1.3	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	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.3	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	root	1.12	dirlist[count++] = 3;
144	elmex	1.1	}
145
146			/* look left */
147	root	1.3	if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
148	elmex	1.1	{
149	root	1.3	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	root	1.2
153	root	1.3	if (cleartest == 0)
154	root	1.12	dirlist[count++] = 4;
155	elmex	1.1	}
156
157	root	1.3	if (count == 0)
158			return -1; /* failed to find any clear points */
159	elmex	1.1
160			/* choose a random direction */
161	root	1.12	switch (dirlist [rmg_rndm (count)])
162	elmex	1.1	{
163	root	1.5	case 1: /* up */
164	root	1.12	*y = yc + 1;
165			*x = xc;
166			break;
167
168	root	1.5	case 2: /* down */
169	root	1.12	*y = yc - 1;
170			*x = xc;
171			break;
172
173	root	1.5	case 3: /* right */
174	root	1.12	*y = yc;
175			*x = xc + 1;
176			break;
177
178	root	1.5	case 4: /* left */
179	root	1.12	*x = xc - 1;
180			*y = yc;
181			break;
182
183	root	1.5	default: /* ??? */
184	root	1.8	return -1;
185
186	elmex	1.1	}
187	root	1.12
188	elmex	1.1	return 1;
189			}
190
191			/* recursive routine which will fill every available space in the maze
192	root	1.3	with walls*/
193	root	1.13	static void
194	root	1.3	fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
195			{
196			int xc, yc;
197	elmex	1.1
198			/* write a wall here */
199			maze[x][y] = '#';
200	root	1.3
201	elmex	1.1	/* decide if we're going to pick from the wall_free_list */
202	root	1.11	if (rmg_rndm (4) && wall_free_size > 0)
203	root	1.3	{
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	root	1.12	fill_maze_full (maze, xc, yc, xsize, ysize);
211	elmex	1.1	}
212
213			/* recursive routine which will fill much of the maze, but will leave
214	root	1.2	some free spots (possibly large) toward the center.*/
215	root	1.13	static void
216	root	1.3	fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
217			{
218			int xc, yc;
219
220	elmex	1.1	/* write a wall here */
221			maze[x][y] = '#';
222	root	1.3
223	elmex	1.1	/* decide if we're going to pick from the wall_free_list */
224	root	1.11	if (rmg_rndm (4) && wall_free_size > 0)
225	root	1.3	{
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	root	1.8	fill_maze_sparse (maze, xc, yc, xsize, ysize);
233	elmex	1.1	}
234	root	1.12
235	root	1.13	/* the outsize interface routine: accepts sizes, returns a char
236			** maze. option is a flag for either a sparse or a full maze. Sparse
237			mazes have sizable rooms. option = 1, full, 0, sparse.*/
238			void
239			maze_gen (Layout maze, int option)
240			{
241			maze->clear ();
242			maze->border ();
243
244			/* find how many free wall spots there are */
245			wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
246
247			make_wall_free_list (maze->w, maze->h);
248
249			/* return the empty maze */
250			if (wall_free_size <= 0)
251			return;
252
253			/* recursively generate the walls of the maze */
254			/* first pop a random starting point */
255			while (wall_free_size > 0)
256			{
257			int i, j;
258
259			pop_wall_point (&i, &j);
260
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);
265			}
266
267			/* clean up our intermediate data structures. */
268
269			free (wall_x_list);
270			free (wall_y_list);
271			}
272