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>

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