--- deliantra/server/random_maps/maze_gen.C 2006/08/13 17:16:03 1.1
+++ deliantra/server/random_maps/maze_gen.C 2009/11/07 18:32:45 1.16
@@ -1,4 +1,25 @@
-
+/*
+ * This file is part of Deliantra, the Roguelike Realtime MMORPG.
+ *
+ * Copyright (©) 2005,2006,2007,2008,2009 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
+ * Copyright (©) Crossfire Development Team (restored, original file without copyright notice)
+ *
+ * Deliantra is free software: you can redistribute it and/or modify it under
+ * the terms of the Affero GNU General Public License as published by the
+ * Free Software Foundation, either version 3 of the License, or (at your
+ * option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the Affero GNU General Public License
+ * and the GNU General Public License along with this program. If not, see
+ * .
+ *
+ * The authors can be reached via e-mail to
+ */
/* peterm@langmuir.eecs.berkeley.edu: this function generates a random
blocked maze with the property that there is only one path from one spot
@@ -16,278 +37,236 @@
reasonable mazes: a straightforward recursive random walk maze
generator would generate a map with a trivial circle-the-outer-wall solution */
-#include
#include
-/*#include */
-#include
-#include
-
-
-/* this include solely, and only, is needed for the definition of RANDOM */
-
+#include "random_map.h"
+#include "rproto.h"
/* 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 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;
-}
-
-
+static int *wall_x_list = 0;
+static int *wall_y_list = 0;
+static int wall_free_size = 0;
/* 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. */
+static 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;
-void make_wall_free_list(int xsize, int ysize) {
- int i,j,count;
+ wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
+ wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
- 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 2 && xc < xsize-2) /* it is valid to 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++;
- }
- }
+ 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;
+ }
/* look down */
- if(yc > 2 && xc > 2 && xc < xsize-2) /* it is valid to 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++;
- }
- }
+ 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;
+ }
/* look right */
- if(xc < xsize- 2 && yc > 2 && yc < ysize-2) /* it is valid to look left */
+ 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++;
- }
- }
+ 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;
+ }
/* look left */
- if(xc > 2 && yc > 2 && yc < ysize-2) /* it is valid to look down */
+ 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++;
- }
+ 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;
}
- if(count==0) return -1; /* failed to find any clear points */
+ 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: /* ??? */
+ switch (dirlist [rmg_rndm (count)])
{
- return -1;
+ 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*/
+ with walls*/
+static void
+fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
+{
+ int xc, yc;
-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);
- }
-}
+ if (rmg_rndm (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.*/
+ some free spots (possibly large) toward the center.*/
+static void
+fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
+{
+ int xc, yc;
-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);
- }
+ if (rmg_rndm (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);
}
+/* 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.*/
+void
+maze_gen (Layout maze, int option)
+{
+ maze->clear ();
+ maze->border ();
+
+ /* find how many free wall spots there are */
+ wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
+
+ make_wall_free_list (maze->w, maze->h);
+
+ /* return the empty maze */
+ if (wall_free_size <= 0)
+ return;
+
+ /* recursively generate the walls of the maze */
+ /* first pop a random starting point */
+ while (wall_free_size > 0)
+ {
+ int i, j;
+ pop_wall_point (&i, &j);
-
-
-
+ if (option)
+ fill_maze_full (maze, i, j, maze->w, maze->h);
+ else
+ fill_maze_sparse (maze, i, j, maze->w, maze->h);
+ }
+
+ /* clean up our intermediate data structures. */
+
+ free (wall_x_list);
+ free (wall_y_list);
+}
-