Crossfire Server, Trunk  R213250
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, int _unused_layers)
59 {
60  int i, j;
61  struct free_walls_struct free_walls;
62 
63  (void)_unused_layers;
64 
65  /* allocate that array, set it up */
66  char **maze = (char **)calloc(sizeof(char *), xsize);
67  for (i = 0; i < xsize; i++) {
68  maze[i] = (char *)calloc(sizeof(char), ysize);
69  }
70 
71  /* write the outer walls */
72  for (i = 0; i < xsize; i++) {
73  maze[i][0] = maze[i][ysize-1] = '#';
74  }
75  for (j = 0; j < ysize; j++) {
76  maze[0][j] = maze[xsize-1][j] = '#';
77  }
78 
79 
80  /* find how many free wall spots there are */
81  free_walls.wall_free_size = 2*(xsize-4)+2*(ysize-4);
82  free_walls.wall_x_list = NULL;
83  free_walls.wall_y_list = NULL;
84 
85  make_wall_free_list(xsize, ysize, &free_walls);
86 
87  /* return the empty maze */
88  if (free_walls.wall_free_size <= 0) {
89  return maze;
90  }
91 
92  /* recursively generate the walls of the maze */
93  /* first pop a random starting point */
94  while (free_walls.wall_free_size > 0) {
95  pop_wall_point(&i, &j, &free_walls);
96  if (option) {
97  fill_maze_full(maze, i, j, xsize, ysize, &free_walls);
98  } else {
99  fill_maze_sparse(maze, i, j, xsize, ysize, &free_walls);
100  }
101  }
102 
103  /* clean up our intermediate data structures. */
104  free(free_walls.wall_x_list);
105  free(free_walls.wall_y_list);
106 
107  return maze;
108 }
109 
120 static void make_wall_free_list(int xsize, int ysize, free_walls_struct *free_walls)
121 {
122  int i, j, count;
123 
124  count = 0; /* entries already placed in the free list */
125  /*allocate it*/
126  if (free_walls->wall_free_size < 0) {
127  return;
128  }
129  free_walls->wall_x_list = (int *)calloc(sizeof(int), free_walls->wall_free_size);
130  free_walls->wall_y_list = (int *)calloc(sizeof(int), free_walls->wall_free_size);
131 
132 
133  /* top and bottom wall */
134  for (i = 2; i < xsize-2; i++) {
135  free_walls->wall_x_list[count] = i;
136  free_walls->wall_y_list[count] = 0;
137  count++;
138  free_walls->wall_x_list[count] = i;
139  free_walls->wall_y_list[count] = ysize-1;
140  count++;
141  }
142 
143  /* left and right wall */
144  for (j = 2; j < ysize-2; j++) {
145  free_walls->wall_x_list[count] = 0;
146  free_walls->wall_y_list[count] = j;
147  count++;
148  free_walls->wall_x_list[count] = xsize-1;
149  free_walls->wall_y_list[count] = j;
150  count++;
151  }
152 }
153 
162 static void pop_wall_point(int *x, int *y, free_walls_struct *free_walls)
163 {
164  int index = RANDOM()%free_walls->wall_free_size;
165  *x = free_walls->wall_x_list[index];
166  *y = free_walls->wall_y_list[index];
167  /* write the last array point here */
168  free_walls->wall_x_list[index] = free_walls->wall_x_list[free_walls->wall_free_size-1];
169  free_walls->wall_y_list[index] = free_walls->wall_y_list[free_walls->wall_free_size-1];
170  free_walls->wall_free_size--;
171 }
172 
191 static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
192 {
193  /* we will randomly pick from this list, 1=up, 2=down, 3=right, 4=left */
194  int dirlist[4];
195  int count = 0; /* # elements in dirlist */
196 
197  /* look up */
198  if (yc < ysize-2 && xc > 2 && xc < xsize-2) {
199  int cleartest = (int)maze[xc][yc+1]+(int)maze[xc-1][yc+1]+(int)maze[xc+1][yc+1];
200 
201  cleartest += (int)maze[xc][yc+2]+(int)maze[xc-1][yc+2]+(int)maze[xc+1][yc+2];
202  if (cleartest == 0) {
203  dirlist[count] = 1;
204  count++;
205  }
206  }
207 
208  /* look down */
209  if (yc > 2 && xc > 2 && xc < xsize-2) {
210  int cleartest = (int)maze[xc][yc-1]+(int)maze[xc-1][yc-1]+(int)maze[xc+1][yc-1];
211 
212  cleartest += (int)maze[xc][yc-2]+(int)maze[xc-1][yc-2]+(int)maze[xc+1][yc-2];
213  if (cleartest == 0) {
214  dirlist[count] = 2;
215  count++;
216  }
217  }
218 
219 
220  /* look right */
221  if (xc < xsize-2 && yc > 2 && yc < ysize-2) {
222  int cleartest = (int)maze[xc+1][yc]+(int)maze[xc+1][yc-1]+(int)maze[xc+1][yc+1];
223 
224  cleartest += (int)maze[xc+2][yc]+(int)maze[xc+2][yc-1]+(int)maze[xc+2][yc+1];
225  if (cleartest == 0) {
226  dirlist[count] = 3;
227  count++;
228  }
229  }
230 
231 
232  /* look left */
233  if (xc > 2 && yc > 2 && yc < ysize-2) {
234  int cleartest = (int)maze[xc-1][yc]+(int)maze[xc-1][yc-1]+(int)maze[xc-1][yc+1];
235 
236  cleartest += (int)maze[xc-2][yc]+(int)maze[xc-2][yc-1]+(int)maze[xc-2][yc+1];
237  if (cleartest == 0) {
238  dirlist[count] = 4;
239  count++;
240  }
241  }
242 
243  if (count == 0) {
244  return -1; /* failed to find any clear points */
245  }
246 
247  /* choose a random direction */
248  if (count > 1) {
249  count = RANDOM()%count;
250  } else {
251  count = 0;
252  }
253  switch (dirlist[count]) {
254  case 1: { /* up */
255  *y = yc+1;
256  *x = xc;
257  break;
258  };
259 
260  case 2: { /* down */
261  *y = yc-1;
262  *x = xc;
263  break;
264  };
265 
266  case 3: { /* right */
267  *y = yc;
268  *x = xc+1;
269  break;
270  }
271 
272  case 4: { /* left */
273  *x = xc-1;
274  *y = yc;
275  break;
276  }
277 
278  default: { /* ??? */
279  return -1;
280  }
281  }
282  return 1;
283 }
284 
300 static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls)
301 {
302  int xc, yc;
303 
304  /* write a wall here */
305  maze[x][y] = '#';
306 
307  /* decide if we're going to pick from the wall_free_list */
308  if (RANDOM()%4 && free_walls->wall_free_size > 0) {
309  pop_wall_point(&xc, &yc, free_walls);
310  fill_maze_full(maze, xc, yc, xsize, ysize, free_walls);
311  }
312 
313  /* change the if to a while for a complete maze. */
314  while (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) {
315  fill_maze_full(maze, xc, yc, xsize, ysize, free_walls);
316  }
317 }
318 
333 static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls)
334 {
335  int xc, yc;
336 
337  /* write a wall here */
338  maze[x][y] = '#';
339 
340  /* decide if we're going to pick from the wall_free_list */
341  if (RANDOM()%4 && free_walls->wall_free_size > 0) {
342  pop_wall_point(&xc, &yc, free_walls);
343  fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls);
344  }
345 
346  /* change the if to a while for a complete maze. */
347  if (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) {
348  fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls);
349  }
350 }
static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *)
Definition: maze_gen.c:300
int * wall_x_list
Definition: maze_gen.c:34
static void make_wall_free_list(int xsize, int ysize, free_walls_struct *)
Definition: maze_gen.c:120
static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *)
Definition: maze_gen.c:333
static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
Definition: maze_gen.c:191
struct free_walls_struct free_walls_struct
char ** maze_gen(int xsize, int ysize, int option, int _unused_layers)
Definition: maze_gen.c:58
static void pop_wall_point(int *x, int *y, free_walls_struct *)
Definition: maze_gen.c:162
#define RANDOM()
Definition: define.h:681
int * wall_y_list
Definition: maze_gen.c:35