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 (Maze 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 = 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.9
Committed:	Mon Apr 14 22:41:17 2008 UTC (16 years, 1 month ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.8:	+11 -21 lines
Log Message:	refactor random map gen more
#	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 <global.h>
19
20	#include "random_map.h"
21	#include "rproto.h"
22
23	/* global variables that everyone needs: don't want to pass them in
24	as parameters every time. */
25	int *wall_x_list = 0;
26	int *wall_y_list = 0;
27	int wall_free_size = 0;
28
29	/* heuristically, we need to change wall_chance based on the size of
30	the maze. */
31
32	int wall_chance;
33
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	void
38	maze_gen (Maze maze, int option)
39	{
40	maze->clear ();
41	maze->border ();
42
43	/* find how many free wall spots there are */
44	wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
45
46	make_wall_free_list (maze->w, maze->h);
47
48	/* return the empty maze */
49	if (wall_free_size <= 0)
50	return;
51
52	/* recursively generate the walls of the maze */
53	/* first pop a random starting point */
54	while (wall_free_size > 0)
55	{
56	int i, j;
57
58	pop_wall_point (&i, &j);
59
60	if (option)
61	fill_maze_full (maze, i, j, maze->w, maze->h);
62	else
63	fill_maze_sparse (maze, i, j, maze->w, maze->h);
64	}
65
66	/* clean up our intermediate data structures. */
67
68	free (wall_x_list);
69	free (wall_y_list);
70	}
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	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	wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
85	wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
86
87	/* top and bottom wall */
88	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
98	/* left and right wall */
99	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	}
109
110	/* randomly returns one of the elements from the wall point list */
111	void
112	pop_wall_point (int x, int y)
113	{
114	int index = rndm (wall_free_size);
115
116	*x = wall_x_list[index];
117	*y = wall_y_list[index];
118	/* write the last array point here */
119	wall_x_list[index] = wall_x_list[wall_free_size - 1];
120	wall_y_list[index] = wall_y_list[wall_free_size - 1];
121	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	int
128	find_free_point (char *maze, int x, int *y, int xc, int yc, int xsize, int ysize)
129	{
130
131	/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
132	int dirlist[4];
133	int count = 0; /* # elements in dirlist */
134
135	/* look up */
136	if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
137	{
138	int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
139
140	cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
141
142	if (cleartest == 0)
143	{
144	dirlist[count] = 1;
145	count++;
146	}
147	}
148
149	/* look down */
150	if (yc > 2 && xc > 2 && xc < xsize - 2) /* it is valid to look down */
151	{
152	int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
153
154	cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
155
156	if (cleartest == 0)
157	{
158	dirlist[count] = 2;
159	count++;
160	}
161	}
162
163	/* look right */
164	if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) /* it is valid to look left */
165	{
166	int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
167
168	cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
169
170	if (cleartest == 0)
171	{
172	dirlist[count] = 3;
173	count++;
174	}
175	}
176
177	/* look left */
178	if (xc > 2 && yc > 2 && yc < ysize - 2) /* it is valid to look down */
179	{
180	int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
181
182	cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
183
184	if (cleartest == 0)
185	{
186	dirlist[count] = 4;
187	count++;
188	}
189	}
190
191	if (count == 0)
192	return -1; /* failed to find any clear points */
193
194	/* choose a random direction */
195	if (count > 1)
196	count = rndm (count);
197	else
198	count = 0;
199
200	switch (dirlist[count])
201	{
202	case 1: /* up */
203	{
204	*y = yc + 1;
205	*x = xc;
206	break;
207	};
208	case 2: /* down */
209	{
210	*y = yc - 1;
211	*x = xc;
212	break;
213	};
214	case 3: /* right */
215	{
216	*y = yc;
217	*x = xc + 1;
218	break;
219	}
220	case 4: /* left */
221	{
222	*x = xc - 1;
223	*y = yc;
224	break;
225	}
226	default: /* ??? */
227	return -1;
228
229	}
230	return 1;
231	}
232
233	/* recursive routine which will fill every available space in the maze
234	with walls*/
235	void
236	fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
237	{
238	int xc, yc;
239
240	/* write a wall here */
241	maze[x][y] = '#';
242
243	/* decide if we're going to pick from the wall_free_list */
244	if (rndm (4) && wall_free_size > 0)
245	{
246	pop_wall_point (&xc, &yc);
247	fill_maze_full (maze, xc, yc, xsize, ysize);
248	}
249
250	/* change the if to a while for a complete maze. */
251	while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
252	{
253	fill_maze_full (maze, xc, yc, xsize, ysize);
254	}
255	}
256
257	/* recursive routine which will fill much of the maze, but will leave
258	some free spots (possibly large) toward the center.*/
259	void
260	fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
261	{
262	int xc, yc;
263
264	/* write a wall here */
265	maze[x][y] = '#';
266
267	/* decide if we're going to pick from the wall_free_list */
268	if (rndm (4) && wall_free_size > 0)
269	{
270	pop_wall_point (&xc, &yc);
271	fill_maze_sparse (maze, xc, yc, xsize, ysize);
272	}
273
274	/* change the if to a while for a complete maze. */
275	if (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
276	fill_maze_sparse (maze, xc, yc, xsize, ysize);
277	}