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