--- deliantra/server/random_maps/maze_gen.C 2010/06/27 16:36:12 1.19
+++ deliantra/server/random_maps/maze_gen.C 2012/10/29 23:55:54 1.29
@@ -1,23 +1,23 @@
/*
* 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)
- *
+ *
+ * Copyright (©) 2005,2006,2007,2008,2009,2010,2011,2012 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
+ * Copyright (©) 1994-2004 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
*/
@@ -37,81 +37,66 @@
reasonable mazes: a straightforward recursive random walk maze
generator would generate a map with a trivial circle-the-outer-wall solution */
+#include
+
#include
-#include "random_map.h"
+#include
#include "rproto.h"
/* global variables that everyone needs: don't want to pass them in
as parameters every time. */
-static int *wall_x_list = 0;
-static int *wall_y_list = 0;
-static int wall_free_size = 0;
+static fixed_stack seeds;
static int xsize, ysize;
+static char **maze;
-/* 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)
+push (point p)
{
- int i, j, count;
-
- count = 0; /* entries already placed in the free list */
- /*allocate it */
- if (wall_free_size < 0)
- return;
+ seeds.push (p);
+ maze [p.x][p.y] = '#';
+}
- wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
- wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
+/* randomly returns one of the elements from the wall point list */
+static point
+pop_rand ()
+{
+ return seeds.remove (rmg_rndm (seeds.size));
+}
+/* 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
+push_walls ()
+{
/* top and bottom wall */
- for (i = 2; i < xsize - 2; i++)
+ for (int x = 2; x < xsize - 2; x++)
{
- wall_x_list[count] = i;
- wall_y_list[count] = 0;
- count++;
- wall_x_list[count] = i;
- wall_y_list[count] = ysize - 1;
- count++;
+ push (point (x, 0));
+ push (point (x, ysize - 1));
}
/* left and right wall */
- for (j = 2; j < ysize - 2; j++)
+ for (int y = 2; y < ysize - 2; y++)
{
- wall_x_list[count] = 0;
- wall_y_list[count] = j;
- count++;
- wall_x_list[count] = xsize - 1;
- wall_y_list[count] = j;
- count++;
+ push (point ( 0, y));
+ push (point (xsize - 1, y));
}
}
-/* randomly returns one of the elements from the wall point list */
-static void
-pop_wall_point (int *x, int *y)
-{
- int index = rmg_rndm (wall_free_size);
-
- *x = wall_x_list[index];
- *y = wall_y_list[index];
-
- /* write the last array point here */
- wall_x_list[index] = wall_x_list[wall_free_size - 1];
- wall_y_list[index] = wall_y_list[wall_free_size - 1];
- wall_free_size--;
-}
-
/* find free point: randomly look for a square adjacent to this one where
we can place a new block without closing a path. We may only look
up, down, right, or left. */
static int
-find_free_point (char **maze, int *x, int *y, int xc, int yc)
+find_free_point (point &p, point pc)
{
/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
int dirlist[4];
int count = 0; /* # elements in dirlist */
+ int xc = pc.x;
+ int yc = pc.y;
+
/* look up */
if (yc < ysize - 2 && xc > 2 && xc < xsize - 2) /* it is valid to look up */
{
@@ -159,128 +144,86 @@
switch (dirlist [rmg_rndm (count)])
{
case 1: /* up */
- *y = yc + 1;
- *x = xc;
+ p.x = xc;
+ p.y = yc + 1;
break;
case 2: /* down */
- *y = yc - 1;
- *x = xc;
+ p.x = xc;
+ p.y = yc - 1;
break;
case 3: /* right */
- *y = yc;
- *x = xc + 1;
+ p.x = xc + 1;
+ p.y = yc;
break;
case 4: /* left */
- *x = xc - 1;
- *y = yc;
+ p.x = xc - 1;
+ p.y = yc;
break;
}
return 1;
}
-/* recursive routine which will fill every available space in the maze
- with walls*/
-static void
-fill_maze_full (char **maze, int x, int y)
+/* 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 = 3=full, 2=braided, 1=sparse, 0=rooms.*/
+void
+maze_gen (layout &maze, int subtype)
{
- int xc, yc;
-
- /* write a wall here */
- maze[x][y] = '#';
+ xsize = maze.w;
+ ysize = maze.h;
+ ::maze = maze;
- /* decide if we're going to pick from the wall_free_list */
- if (rmg_rndm (2) && wall_free_size > 0)
- {
- pop_wall_point (&xc, &yc);
- fill_maze_full (maze, xc, yc);
- }
+ maze.clear ();
+ maze.border ();
- /* change the while to an if for a sparse maze. */
- while (find_free_point (maze, &xc, &yc, x, y) != -1)
- fill_maze_full (maze, xc, yc);
-}
+ if (xsize < 4 || ysize < 4)
+ return;
-/* recursive routine which will fill much of the maze, but will leave
- some free spots (possibly large) toward the center.*/
-static void
-fill_maze_sparse (char **maze, int x, int y)
-{
- int xc, yc;
+ seeds.reset (xsize * ysize);
- /* write a wall here */
- maze[x][y] = '#';
+ if (subtype > 0)
+ push_walls ();
- /* decide if we're going to pick from the wall_free_list */
- if (rmg_rndm (2) && wall_free_size > 0)
- {
- pop_wall_point (&xc, &yc);
- fill_maze_sparse (maze, xc, yc);
- }
+ if (subtype == 0 || subtype == 2)
+ for (int i = (xsize + ysize) / 2; i; --i)
+ push (point (rmg_rndm (1, xsize - 2), rmg_rndm (1, ysize - 2)));
- /* change the if to a while for a complete maze. */
- if (find_free_point (maze, &xc, &yc, x, y) != -1)
- fill_maze_sparse (maze, xc, yc);
-}
+ bool full = subtype == 3;
-/* 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 full)
-{
- maze->clear ();
- maze->border ();
+ /* recursively generate the walls of the maze */
+ /* first pop a random starting point */
+ while (seeds.size)
+ {
+ point p = pop_rand ();
- xsize = maze->w;
- ysize = maze->h;
+ for (;;)
+ {
+ point pc;
- /* find how many free wall spots there are */
- wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
+ maze [p.x][p.y] = '#';
- make_wall_free_list (maze->w, maze->h);
+ if (find_free_point (pc, p) < 0)
+ break;
- /* return the empty maze */
- if (wall_free_size <= 0)
- return;
+ if (full)
+ push (p);
- /* recursively generate the walls of the maze */
- /* first pop a random starting point */
- while (wall_free_size > 0)
- {
- int i, j;
+ if (!rmg_rndm (8))
+ {
+ if (!full)
+ push (pc);
- pop_wall_point (&i, &j);
+ break;
+ }
- if (full)
- fill_maze_full (maze, i, j);
- else
- fill_maze_sparse (maze, i, j);
+ p = pc;
+ }
}
- /* clean up our intermediate data structures. */
-
- free (wall_x_list);
- free (wall_y_list);
+ seeds.free ();
}
-#if 1
-static struct demo
-{
- demo ()
- {
- Layout layout (30, 30);
- rmg_rndm.seed (time (0));
-
- for(int i=1;i<10;++i)
- {
- maze_gen (layout, 1);
- layout.print ();
- }
- exit (1);
- }
-} demo;
-#endif