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