server/random_maps/maze_gen.C


/* 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. */
int *wall_x_list = 0;
int *wall_y_list = 0;
int wall_free_size = 0;

/*  heuristically, we need to change wall_chance based on the size of
    the maze. */

int wall_chance;

/* 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.*/

Maze
maze_gen (int xsize, int ysize, int option)
{
  int i, j;

  Maze maze (xsize, ysize);

  /* write the outer walls */
  for (i = 0; i < xsize; i++) maze[i][0] = maze[i][ysize - 1] = '#';
  for (j = 0; j < ysize; j++) maze[0][j] = maze[xsize - 1][j] = '#';

  /* find how many free wall spots there are */
  wall_free_size = 2 * (xsize - 4) + 2 * (ysize - 4);

  make_wall_free_list (xsize, ysize);

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

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

      if (option)
        fill_maze_full (maze, i, j, xsize, ysize);
      else
        fill_maze_sparse (maze, i, j, xsize, ysize);
    }

  /* clean up our intermediate data structures. */

  free (wall_x_list);
  free (wall_y_list);

  return maze;
}

/*  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. */
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 */
void
pop_wall_point (int *x, int *y)
{
  int index = 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. */
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;
          count++;
        }
    }


  /* 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;
          count++;
        }
    }


  /* 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;
          count++;
        }
    }


  /* 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;
          count++;
        }
    }

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

  /* choose a random direction */
  if (count > 1)
    count = rndm (count);
  else
    count = 0;

  switch (dirlist[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*/

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