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 <stdio.h>
#include <global.h>

/*#include <random_map.h>*/
#include <maze_gen.h>
#include <time.h>


/* this include solely, and only, is needed for the definition of RANDOM */


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

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

  /* allocate that array, set it up */
  char **maze = (char **) calloc (sizeof (char *), xsize);

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