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.*/
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);
}

/*  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 = 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. */
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*/
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.*/
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);
}

Revision:	1.12
Committed:	Thu May 8 14:20:19 2008 UTC (16 years ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rel-2_82, rel-2_81, rel-2_80, rel-2_6, rel-2_7, rel-2_72, rel-2_73, rel-2_71, rel-2_76, rel-2_77, rel-2_74, rel-2_75, rel-2_54, rel-2_55, rel-2_56, rel-2_79, rel-2_78, rel-2_61
Changes since 1.11:	+25 -47 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	root	1.9	void
38	root	1.10	maze_gen (Layout maze, int option)
39	root	1.3	{
40	root	1.9	maze->clear ();
41			maze->border ();
42	root	1.3
43	elmex	1.1	/* find how many free wall spots there are */
44	root	1.9	wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
45	root	1.3
46	root	1.9	make_wall_free_list (maze->w, maze->h);
47	elmex	1.1
48			/* return the empty maze */
49	root	1.3	if (wall_free_size <= 0)
50	root	1.9	return;
51	elmex	1.1
52			/* recursively generate the walls of the maze */
53			/* first pop a random starting point */
54	root	1.3	while (wall_free_size > 0)
55			{
56	root	1.9	int i, j;
57
58	root	1.3	pop_wall_point (&i, &j);
59	root	1.8
60	root	1.3	if (option)
61	root	1.9	fill_maze_full (maze, i, j, maze->w, maze->h);
62	root	1.3	else
63	root	1.9	fill_maze_sparse (maze, i, j, maze->w, maze->h);
64	root	1.3	}
65	elmex	1.1
66			/* clean up our intermediate data structures. */
67	root	1.3
68			free (wall_x_list);
69			free (wall_y_list);
70	elmex	1.1	}
71
72			/* the free wall points are those outer points which aren't corners or
73			near corners, and don't have a maze wall growing out of them already. */
74	root	1.3	void
75			make_wall_free_list (int xsize, int ysize)
76			{
77			int i, j, count;
78
79			count = 0; /* entries already placed in the free list */
80			/allocate it /
81			if (wall_free_size < 0)
82			return;
83
84	root	1.8	wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
85			wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
86	elmex	1.1
87			/* top and bottom wall */
88	root	1.3	for (i = 2; i < xsize - 2; i++)
89			{
90			wall_x_list[count] = i;
91			wall_y_list[count] = 0;
92			count++;
93			wall_x_list[count] = i;
94			wall_y_list[count] = ysize - 1;
95			count++;
96			}
97	elmex	1.1
98			/* left and right wall */
99	root	1.3	for (j = 2; j < ysize - 2; j++)
100			{
101			wall_x_list[count] = 0;
102			wall_y_list[count] = j;
103			count++;
104			wall_x_list[count] = xsize - 1;
105			wall_y_list[count] = j;
106			count++;
107			}
108	elmex	1.1	}
109
110			/* randomly returns one of the elements from the wall point list */
111	root	1.3	void
112			pop_wall_point (int x, int y)
113			{
114	root	1.11	int index = rmg_rndm (wall_free_size);
115	root	1.3
116	elmex	1.1	*x = wall_x_list[index];
117			*y = wall_y_list[index];
118			/* write the last array point here */
119	root	1.3	wall_x_list[index] = wall_x_list[wall_free_size - 1];
120			wall_y_list[index] = wall_y_list[wall_free_size - 1];
121	elmex	1.1	wall_free_size--;
122			}
123
124			/* find free point: randomly look for a square adjacent to this one where
125			we can place a new block without closing a path. We may only look
126			up, down, right, or left. */
127	root	1.3	int
128			find_free_point (char *maze, int x, int *y, int xc, int yc, int xsize, int ysize)
129			{
130	root	1.12	/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
131	root	1.3	int dirlist[4];
132			int count = 0; /* # elements in dirlist */
133	elmex	1.1
134			/* look up */
135	root	1.3	if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
136	elmex	1.1	{
137	root	1.3	int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
138
139			cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
140
141			if (cleartest == 0)
142	root	1.12	dirlist[count++] = 1;
143	elmex	1.1	}
144
145			/* look down */
146	root	1.3	if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
147	elmex	1.1	{
148	root	1.3	int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
149
150			cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
151
152			if (cleartest == 0)
153	root	1.12	dirlist[count++] = 2;
154	elmex	1.1	}
155
156			/* look right */
157	root	1.3	if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
158	elmex	1.1	{
159	root	1.3	int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
160
161			cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
162
163			if (cleartest == 0)
164	root	1.12	dirlist[count++] = 3;
165	elmex	1.1	}
166
167			/* look left */
168	root	1.3	if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
169	elmex	1.1	{
170	root	1.3	int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
171
172			cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
173	root	1.2
174	root	1.3	if (cleartest == 0)
175	root	1.12	dirlist[count++] = 4;
176	elmex	1.1	}
177
178	root	1.3	if (count == 0)
179			return -1; /* failed to find any clear points */
180	elmex	1.1
181			/* choose a random direction */
182	root	1.12	switch (dirlist [rmg_rndm (count)])
183	elmex	1.1	{
184	root	1.5	case 1: /* up */
185	root	1.12	*y = yc + 1;
186			*x = xc;
187			break;
188
189	root	1.5	case 2: /* down */
190	root	1.12	*y = yc - 1;
191			*x = xc;
192			break;
193
194	root	1.5	case 3: /* right */
195	root	1.12	*y = yc;
196			*x = xc + 1;
197			break;
198
199	root	1.5	case 4: /* left */
200	root	1.12	*x = xc - 1;
201			*y = yc;
202			break;
203
204	root	1.5	default: /* ??? */
205	root	1.8	return -1;
206
207	elmex	1.1	}
208	root	1.12
209	elmex	1.1	return 1;
210			}
211
212			/* recursive routine which will fill every available space in the maze
213	root	1.3	with walls*/
214			void
215			fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
216			{
217			int xc, yc;
218	elmex	1.1
219			/* write a wall here */
220			maze[x][y] = '#';
221	root	1.3
222	elmex	1.1	/* decide if we're going to pick from the wall_free_list */
223	root	1.11	if (rmg_rndm (4) && wall_free_size > 0)
224	root	1.3	{
225			pop_wall_point (&xc, &yc);
226			fill_maze_full (maze, xc, yc, xsize, ysize);
227			}
228
229			/* change the if to a while for a complete maze. */
230			while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
231	root	1.12	fill_maze_full (maze, xc, yc, xsize, ysize);
232	elmex	1.1	}
233
234			/* recursive routine which will fill much of the maze, but will leave
235	root	1.2	some free spots (possibly large) toward the center.*/
236	root	1.3	void
237			fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
238			{
239			int xc, yc;
240
241	elmex	1.1	/* write a wall here */
242			maze[x][y] = '#';
243	root	1.3
244	elmex	1.1	/* decide if we're going to pick from the wall_free_list */
245	root	1.11	if (rmg_rndm (4) && wall_free_size > 0)
246	root	1.3	{
247			pop_wall_point (&xc, &yc);
248			fill_maze_sparse (maze, xc, yc, xsize, ysize);
249			}
250
251			/* change the if to a while for a complete maze. */
252			if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
253	root	1.8	fill_maze_sparse (maze, xc, yc, xsize, ysize);
254	elmex	1.1	}
255	root	1.12