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.
#	User	Rev	Content
1	root	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			/#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