Atrinik Server  4.0
maze_gen.c
Go to the documentation of this file.
1 /*************************************************************************
2  * Atrinik, a Multiplayer Online Role Playing Game *
3  * *
4  * Copyright (C) 2009-2014 Alex Tokar and Atrinik Development Team *
5  * *
6  * Fork from Crossfire (Multiplayer game for X-windows). *
7  * *
8  * This program is free software; you can redistribute it and/or modify *
9  * it under the terms of the GNU General Public License as published by *
10  * the Free Software Foundation; either version 2 of the License, or *
11  * (at your option) any later version. *
12  * *
13  * This program is distributed in the hope that it will be useful, *
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16  * GNU General Public License for more details. *
17  * *
18  * You should have received a copy of the GNU General Public License *
19  * along with this program; if not, write to the Free Software *
20  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *
21  * *
22  * The author can be reached at admin@atrinik.org *
23  ************************************************************************/
24 
34 #include <global.h>
35 
37 typedef struct free_walls_struct {
40 
43 
47 
48 static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls);
49 static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls);
50 static void make_wall_free_list(int xsize, int ysize, free_walls_struct *free_walls);
51 static void pop_wall_point(int *x, int *y, free_walls_struct *free_walls);
52 static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize);
53 
69 char **maze_gen(int xsize, int ysize, int option)
70 {
71  int i, j;
72  struct free_walls_struct free_walls;
73  /* allocate that array, set it up */
74  char **maze = ecalloc(sizeof(char *), xsize);
75 
76  for (i = 0; i < xsize; i++) {
77  maze[i] = ecalloc(sizeof(char), ysize);
78  }
79 
80  /* Write the outer walls */
81  for (i = 0; i < xsize; i++) {
82  maze[i][0] = maze[i][ysize - 1] = '#';
83  }
84 
85  for (j = 0; j < ysize; j++) {
86  maze[0][j] = maze[xsize - 1][j] = '#';
87  }
88 
89  /* Find how many free wall spots there are */
90  free_walls.wall_free_size = 2 * (xsize - 4) + 2 * (ysize - 4);
91 
92  free_walls.wall_x_list = NULL;
93  free_walls.wall_y_list = NULL;
94 
95  make_wall_free_list(xsize, ysize, &free_walls);
96 
97  /* Return the empty maze */
98  if (free_walls.wall_free_size <= 0) {
99  return maze;
100  }
101 
102  /* recursively generate the walls of the maze */
103  while (free_walls.wall_free_size > 0) {
104  /* first pop a random starting point */
105  pop_wall_point(&i, &j, &free_walls);
106 
107  if (option) {
108  fill_maze_full(maze, i, j, xsize, ysize, &free_walls);
109  } else {
110  fill_maze_sparse(maze, i, j, xsize, ysize, &free_walls);
111  }
112  }
113 
114  /* clean up our intermediate data structures. */
115  efree(free_walls.wall_x_list);
116  efree(free_walls.wall_y_list);
117 
118  return maze;
119 }
120 
134 static void make_wall_free_list(int xsize, int ysize, free_walls_struct *free_walls)
135 {
136  int i, j, count = 0;
137 
138  if (free_walls->wall_free_size < 0) {
139  return;
140  }
141 
142  /* allocate it */
143  free_walls->wall_x_list = ecalloc(sizeof(int), free_walls->wall_free_size);
144  free_walls->wall_y_list = ecalloc(sizeof(int), free_walls->wall_free_size);
145 
146  /* top and bottom wall */
147  for (i = 2; i < xsize - 2; i++) {
148  free_walls->wall_x_list[count] = i;
149  free_walls->wall_y_list[count] = 0;
150  count++;
151 
152  free_walls->wall_x_list[count] = i;
153  free_walls->wall_y_list[count] = ysize - 1;
154  count++;
155  }
156 
157  /* left and right wall */
158  for (j = 2; j < ysize - 2; j++) {
159  free_walls->wall_x_list[count] = 0;
160  free_walls->wall_y_list[count] = j;
161  count++;
162 
163  free_walls->wall_x_list[count] = xsize - 1;
164  free_walls->wall_y_list[count] = j;
165  count++;
166  }
167 }
168 
178 static void pop_wall_point(int *x, int *y, free_walls_struct *free_walls)
179 {
180  int i = rndm(0, free_walls->wall_free_size - 1);
181 
182  *x = free_walls->wall_x_list[i];
183  *y = free_walls->wall_y_list[i];
184 
185  /* Write the last array point here */
186  free_walls->wall_x_list[i] = free_walls->wall_x_list[free_walls->wall_free_size - 1];
187  free_walls->wall_y_list[i] = free_walls->wall_y_list[free_walls->wall_free_size - 1];
188 
189  free_walls->wall_free_size--;
190 }
191 
214 static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
215 {
216  /* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
217  int dirlist[4];
218  /* # elements in dirlist */
219  int count = 0;
220 
221  /* look up */
222  if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) {
223  int cleartest = (int) maze[xc][yc + 1] + (int) maze[xc - 1][yc + 1] + (int) maze[xc + 1][yc + 1];
224 
225  cleartest += (int) maze[xc][yc + 2] + (int) maze[xc - 1][yc + 2] + (int) maze[xc + 1][yc + 2];
226 
227  if (cleartest == 0) {
228  dirlist[count] = 1;
229  count++;
230  }
231  }
232 
233  /* look down */
234  if (yc > 2 && xc > 2 && xc < xsize - 2) {
235  int cleartest = (int) maze[xc][yc - 1] + (int) maze[xc - 1][yc - 1] + (int) maze[xc + 1][yc - 1];
236 
237  cleartest += (int) maze[xc][yc - 2] + (int) maze[xc - 1][yc - 2] + (int) maze[xc + 1][yc - 2];
238 
239  if (cleartest == 0) {
240  dirlist[count] = 2;
241  count++;
242  }
243  }
244 
245  /* look right */
246  if (xc < xsize - 2 && yc > 2 && yc < ysize - 2) {
247  int cleartest = (int) maze[xc + 1][yc] + (int) maze[xc + 1][yc - 1] + (int) maze[xc + 1][yc + 1];
248 
249  cleartest += (int) maze[xc + 2][yc] + (int) maze[xc + 2][yc - 1] + (int) maze[xc + 2][yc + 1];
250 
251  if (cleartest == 0) {
252  dirlist[count] = 3;
253  count++;
254  }
255  }
256 
257  /* look left */
258  if (xc > 2 && yc > 2 && yc < ysize - 2) {
259  int cleartest = (int) maze[xc - 1][yc] + (int) maze[xc - 1][yc - 1] + (int) maze[xc - 1][yc + 1];
260 
261  cleartest += (int) maze[xc - 2][yc] + (int) maze[xc - 2][yc - 1] + (int) maze[xc - 2][yc + 1];
262 
263  if (cleartest == 0) {
264  dirlist[count] = 4;
265  count++;
266  }
267  }
268 
269  /* Failed to find any clear points */
270  if (count == 0) {
271  return -1;
272  }
273 
274  /* choose a random direction */
275  if (count > 1) {
276  count = rndm(0, count - 1);
277  } else {
278  count = 0;
279  }
280 
281  switch (dirlist[count]) {
282  case 1:
283  *y = yc + 1;
284  *x = xc;
285 
286  break;
287 
288  case 2:
289  *y = yc - 1;
290  *x = xc;
291 
292  break;
293 
294  case 3:
295  *y = yc;
296  *x = xc + 1;
297 
298  break;
299 
300  case 4:
301  *x = xc - 1;
302  *y = yc;
303 
304  break;
305 
306  default:
307  return -1;
308  }
309 
310  return 1;
311 }
312 
330 static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls)
331 {
332  int xc, yc;
333 
334  /* Write a wall here */
335  maze[x][y] = '#';
336 
337  /* Decide if we're going to pick from the wall_free_list */
338  if (!rndm_chance(4) && free_walls->wall_free_size > 0) {
339  pop_wall_point(&xc, &yc, free_walls);
340  fill_maze_full(maze, xc, yc, xsize, ysize, free_walls);
341  }
342 
343  /* Change the if to a while for a complete maze. */
344  while (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) {
345  fill_maze_full(maze, xc, yc, xsize, ysize, free_walls);
346  }
347 }
348 
365 static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls)
366 {
367  int xc, yc;
368 
369  /* Write a wall here */
370  maze[x][y] = '#';
371 
372  /* Decide if we're going to pick from the wall_free_list */
373  if (!rndm_chance(4) && free_walls->wall_free_size > 0) {
374  pop_wall_point(&xc, &yc, free_walls);
375  fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls);
376  }
377 
378  /* Change the if to a while for a complete maze. */
379  if (find_free_point(maze, &xc, &yc, x, y, xsize, ysize) != -1) {
380  fill_maze_sparse(maze, xc, yc, xsize, ysize, free_walls);
381  }
382 }
int * wall_x_list
Definition: maze_gen.c:39
static void fill_maze_full(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls)
Definition: maze_gen.c:330
static void fill_maze_sparse(char **maze, int x, int y, int xsize, int ysize, free_walls_struct *free_walls)
Definition: maze_gen.c:365
static int find_free_point(char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
Definition: maze_gen.c:214
struct free_walls_struct free_walls_struct
static void pop_wall_point(int *x, int *y, free_walls_struct *free_walls)
Definition: maze_gen.c:178
char ** maze_gen(int xsize, int ysize, int option)
Definition: maze_gen.c:69
int * wall_y_list
Definition: maze_gen.c:42
static void make_wall_free_list(int xsize, int ysize, free_walls_struct *free_walls)
Definition: maze_gen.c:134