Crossfire Server, Trunk  R20513
maze_gen.c
Go to the documentation of this file.
1 /*
2  * Crossfire -- cooperative multi-player graphical RPG and adventure game
3  *
4  * Copyright (c) 1999-2013 Mark Wedel and the Crossfire Development Team
5  * Copyright (c) 1992 Frank Tore Johansen
6  *
7  * Crossfire is free software and comes with ABSOLUTELY NO WARRANTY. You are
8  * welcome to redistribute it under certain conditions. For details, please
9  * see COPYING and LICENSE.
10  *
11  * The authors can be reached via e-mail at <crossfire@metalforge.org>.
12  */
13 
21 /* we need to maintain a list of wall points to generate
22  * reasonable mazes: a straightforward recursive random walk maze
23  * generator would generate a map with a trivial circle-the-outer-wall solution
24  */
25 
26 #include <stdlib.h>
27 #include <stdio.h>
28 #include <global.h>
29 #include <maze_gen.h>
30 #include <time.h>
31 
33 typedef struct free_walls_struct {
34  int *wall_x_list;
35  int *wall_y_list;
38 
39 static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *);
40 static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *);
41 static void make_wall_free_list(int xsize, int ysize, free_walls_struct *);
42 static void pop_wall_point(int *x, int *y, free_walls_struct *);
43 static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize);
44 
58 char **maze_gen(int xsize, int ysize, int option)
59 {
60  int i, j;
61  struct free_walls_struct free_walls;
62 
63  /* allocate that array, set it up */
64  char **maze = (char **)calloc(sizeof(char *), xsize);
65  for (i = 0; i < xsize; i++) {
66  maze[i] = (char *)calloc(sizeof(char), ysize);
67  }
68 
69  /* write the outer walls */
70  for (i = 0; i < xsize; i++) {
71  maze[i][0] = maze[i][ysize-1] = '#';
72  }
73  for (j = 0; j < ysize; j++) {
74  maze[0][j] = maze[xsize-1][j] = '#';
75  }
76 
77 
78  /* find how many free wall spots there are */
79  free_walls.wall_free_size = 2*(xsize-4)+2*(ysize-4);
80  free_walls.wall_x_list = NULL;
81  free_walls.wall_y_list = NULL;
82 
83  make_wall_free_list(xsize, ysize, &free_walls);
84 
85  /* return the empty maze */
86  if (free_walls.wall_free_size <= 0) {
87  return maze;
88  }
89 
90  /* recursively generate the walls of the maze */
91  /* first pop a random starting point */
92  while (free_walls.wall_free_size > 0) {
93  pop_wall_point(&i, &j, &free_walls);
94  if (option) {
95  fill_maze_full(maze, i, j, xsize, ysize, &free_walls);
96  } else {
97  fill_maze_sparse(maze, i, j, xsize, ysize, &free_walls);
98  }
99  }
100 
101  /* clean up our intermediate data structures. */
102  free(free_walls.wall_x_list);
103  free(free_walls.wall_y_list);
104 
105  return maze;
106 }
107 
118 static void make_wall_free_list(int xsize, int ysize, free_walls_struct *free_walls)
119 {
120  int i, j, count;
121 
122  count = 0; /* entries already placed in the free list */
123  /*allocate it*/
124  if (free_walls->wall_free_size < 0) {
125  return;
126  }
127  free_walls->wall_x_list = (int *)calloc(sizeof(int), free_walls->wall_free_size);
128  free_walls->wall_y_list = (int *)calloc(sizeof(int), free_walls->wall_free_size);
129 
130 
131  /* top and bottom wall */
132  for (i = 2; i < xsize-2; i++) {
133  free_walls->wall_x_list[count] = i;
134  free_walls->wall_y_list[count] = 0;
135  count++;
136  free_walls->wall_x_list[count] = i;
137  free_walls->wall_y_list[count] = ysize-1;
138  count++;
139  }
140 
141  /* left and right wall */
142  for (j = 2; j < ysize-2; j++) {
143  free_walls->wall_x_list[count] = 0;
144  free_walls->wall_y_list[count] = j;
145  count++;
146  free_walls->wall_x_list[count] = xsize-1;
147  free_walls->wall_y_list[count] = j;
148  count++;
149  }
150 }
151 
160 static void pop_wall_point(int *x, int *y, free_walls_struct *free_walls)
161 {
162  int index = RANDOM()%free_walls->wall_free_size;
163  *x = free_walls->wall_x_list[index];
164  *y = free_walls->wall_y_list[index];
165  /* write the last array point here */
166  free_walls->wall_x_list[index] = free_walls->wall_x_list[free_walls->wall_free_size-1];
167  free_walls->wall_y_list[index] = free_walls->wall_y_list[free_walls->wall_free_size-1];
168  free_walls->wall_free_size--;
169 }
170 
189 static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
190 {
191  /* we will randomly pick from this list, 1=up, 2=down, 3=right, 4=left */
192  int dirlist[4];
193  int count = 0; /* # elements in dirlist */
194 
195  /* look up */
196  if (yc < ysize-2 && xc > 2 && xc < xsize-2) {
197  int cleartest = (int)maze[xc][yc+1]+(int)maze[xc-1][yc+1]+(int)maze[xc+1][yc+1];
198 
199  cleartest += (int)maze[xc][yc+2]+(int)maze[xc-1][yc+2]+(int)maze[xc+1][yc+2];
200  if (cleartest == 0) {
201  dirlist[count] = 1;
202  count++;
203  }
204  }
205 
206  /* look down */
207  if (yc > 2 && xc > 2 && xc < xsize-2) {
208  int cleartest = (int)maze[xc][yc-1]+(int)maze[xc-1][yc-1]+(int)maze[xc+1][yc-1];
209 
210  cleartest += (int)maze[xc][yc-2]+(int)maze[xc-1][yc-2]+(int)maze[xc+1][yc-2];
211  if (cleartest == 0) {
212  dirlist[count] = 2;
213  count++;
214  }
215  }
216 
217 
218  /* look right */
219  if (xc < xsize-2 && yc > 2 && yc < ysize-2) {
220  int cleartest = (int)maze[xc+1][yc]+(int)maze[xc+1][yc-1]+(int)maze[xc+1][yc+1];
221 
222  cleartest += (int)maze[xc+2][yc]+(int)maze[xc+2][yc-1]+(int)maze[xc+2][yc+1];
223  if (cleartest == 0) {
224  dirlist[count] = 3;
225  count++;
226  }
227  }
228 
229 
230  /* look left */
231  if (xc > 2 && yc > 2 && yc < ysize-2) {
232  int cleartest = (int)maze[xc-1][yc]+(int)maze[xc-1][yc-1]+(int)maze[xc-1][yc+1];
233 
234  cleartest += (int)maze[xc-2][yc]+(int)maze[xc-2][yc-1]+(int)maze[xc-2][yc+1];
235  if (cleartest == 0) {
236  dirlist[count] = 4;
237  count++;
238  }
239  }
240 
241  if (count == 0) {
242  return -1; /* failed to find any clear points */
243  }
244 
245  /* choose a random direction */
246  if (count > 1) {
247  count = RANDOM()%count;
248  } else {
249  count = 0;
250  }
251  switch (dirlist[count]) {
252  case 1: { /* up */
253  *y = yc+1;
254  *x = xc;
255  break;
256  };
257 
258  case 2: { /* down */
259  *y = yc-1;
260  *x = xc;
261  break;
262  };
263 
264  case 3: { /* right */
265  *y = yc;
266  *x = xc+1;
267  break;
268  }
269 
270  case 4: { /* left */
271  *x = xc-1;
272  *y = yc;
273  break;
274  }
275 
276  default: { /* ??? */
277  return -1;
278  }
279  }
280  return 1;
281 }
282 
298 static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls)
299 {
300  int xc, yc;
301 
302  /* write a wall here */
303  maze[x][y] = '#';
304 
305  /* decide if we're going to pick from the wall_free_list */
306  if (RANDOM()%4 && free_walls->wall_free_size > 0) {
307  pop_wall_point(&xc, &yc, free_walls);
308  fill_maze_full(maze, xc, yc, xsize, ysize, free_walls);
309  }
310 
311  /* change the if to a while for a complete maze. */
312  while (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) {
313  fill_maze_full(maze, xc, yc, xsize, ysize, free_walls);
314  }
315 }
316 
331 static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls)
332 {
333  int xc, yc;
334 
335  /* write a wall here */
336  maze[x][y] = '#';
337 
338  /* decide if we're going to pick from the wall_free_list */
339  if (RANDOM()%4 && free_walls->wall_free_size > 0) {
340  pop_wall_point(&xc, &yc, free_walls);
341  fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls);
342  }
343 
344  /* change the if to a while for a complete maze. */
345  if (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) {
346  fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls);
347  }
348 }
int * wall_x_list
X coordinates of free spots for walls.
Definition: maze_gen.c:34
static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *)
Recursive routine which will fill every available space in the maze with walls.
Definition: maze_gen.c:298
Global type definitions and header inclusions.
static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *)
Recursive routine which will fill much of the maze, but will leave some free spots (possibly large) t...
Definition: maze_gen.c:331
int wall_free_size
Number of items in wall_x_list and wall_y_list.
Definition: maze_gen.c:36
static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
Randomly look for a square adjacent to this one where we can place a new block without closing a path...
Definition: maze_gen.c:189
struct free_walls_struct free_walls_struct
Contains free walls in the map.
static void pop_wall_point(int *x, int *y, free_walls_struct *)
Randomly returns one of the elements from the wall point list.
Definition: maze_gen.c:160
#define RANDOM()
Definition: define.h:679
Contains free walls in the map.
Definition: maze_gen.c:33
char ** maze_gen(int xsize, int ysize, int option)
This function generates a random blocked maze with the property that there is only one path from one ...
Definition: maze_gen.c:58
int * wall_y_list
Y coordinates of free spots for walls.
Definition: maze_gen.c:35
static void make_wall_free_list(int xsize, int ysize, free_walls_struct *)
Inits the list of points where we can put walls on.
Definition: maze_gen.c:118