--- deliantra/server/random_maps/maze_gen.C	2008/05/04 14:12:37	1.11
+++ deliantra/server/random_maps/maze_gen.C	2010/06/29 18:27:02	1.22
@@ -1,3 +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
+ * <http://www.gnu.org/licenses/>.
+ * 
+ * The authors can be reached via e-mail to <support@deliantra.net>
+ */
 
 /* peterm@langmuir.eecs.berkeley.edu:  this function generates a random
 blocked maze with the property that there is only one path from one spot
@@ -15,263 +37,239 @@
    reasonable mazes:  a straightforward recursive random walk maze
    generator would generate a map with a trivial circle-the-outer-wall solution */
 
+#include <vector>
+
 #include <global.h>
 
 #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.*/
-void
-maze_gen (Layout maze, int option)
+struct point
 {
-  maze->clear ();
-  maze->border ();
+  short x;
+  short y;
 
-  /* find how many free wall spots there are */
-  wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
+  point ()
+  {
+  }
+
+  point (int x, int y)
+  : x(x), y(y)
+  {
+  }
+};
 
-  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);
+/* global variables that everyone needs:  don't want to pass them in
+   as parameters every time. */
+static point *seed_list;
+static int seed_max, seed_size;
+static int xsize, ysize;
+static char **maze;
 
-      if (option)
-        fill_maze_full (maze, i, j, maze->w, maze->h);
-      else
-        fill_maze_sparse (maze, i, j, maze->w, maze->h);
-    }
+static void
+push (point p)
+{
+  assert (seed_size < seed_max);
 
-  /* clean up our intermediate data structures. */
+  seed_list [seed_size++] = p;
 
-  free (wall_x_list);
-  free (wall_y_list);
+  maze [p.x][p.y] = '#';
 }
 
 /*  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. */
-void
-make_wall_free_list (int xsize, int ysize)
+static void
+push_walls ()
 {
-  int i, j, count;
-
-  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 < 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 */
-void
-pop_wall_point (int *x, int *y)
+static point
+pop_rand ()
 {
-  int index = rmg_rndm (wall_free_size);
+  int index = rmg_rndm (seed_size);
+
+  point p = seed_list [index];
 
-  *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--;
+  seed_list [index] = seed_list [--seed_size];
+
+  return p;
 }
 
 /* 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. */
-int
-find_free_point (char **maze, int *x, int *y, int xc, int yc, int xsize, int ysize)
+static int
+find_free_point (point &p, point pc)
 {
-
-/* we will randomly pick from this list, 1=up,2=down,3=right,4=left */
+  /* 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 */
     {
-      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];
+      int cleartest = maze[xc][yc + 1] + maze[xc - 1][yc + 1] + maze[xc + 1][yc + 1]
+                    + maze[xc][yc + 2] + maze[xc - 1][yc + 2] + maze[xc + 1][yc + 2];
 
       if (cleartest == 0)
-        {
-          dirlist[count] = 1;
-          count++;
-        }
+        dirlist[count++] = 1;
     }
 
   /* 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];
+      int cleartest = maze[xc][yc - 1] + maze[xc - 1][yc - 1] + maze[xc + 1][yc - 1]
+                    + maze[xc][yc - 2] + maze[xc - 1][yc - 2] + maze[xc + 1][yc - 2];
 
       if (cleartest == 0)
-        {
-          dirlist[count] = 2;
-          count++;
-        }
+        dirlist[count++] = 2;
     }
 
   /* look right */
   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];
+      int cleartest = maze[xc + 1][yc] + maze[xc + 1][yc - 1] + maze[xc + 1][yc + 1]
+                    + maze[xc + 2][yc] + maze[xc + 2][yc - 1] + maze[xc + 2][yc + 1];
 
       if (cleartest == 0)
-        {
-          dirlist[count] = 3;
-          count++;
-        }
+        dirlist[count++] = 3;
     }
 
   /* look left */
   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];
+      int cleartest = maze[xc - 1][yc] + maze[xc - 1][yc - 1] + maze[xc - 1][yc + 1]
+                    + maze[xc - 2][yc] + maze[xc - 2][yc - 1] + maze[xc - 2][yc + 1];
 
       if (cleartest == 0)
-        {
-          dirlist[count] = 4;
-          count++;
-        }
+        dirlist[count++] = 4;
     }
 
   if (count == 0)
     return -1;                  /* failed to find any clear points */
 
   /* choose a random direction */
-  if (count > 1)
-    count = rmg_rndm (count);
-  else
-    count = 0;
-
-  switch (dirlist[count])
+  switch (dirlist [rmg_rndm (count)])
     {
       case 1:                  /* up */
-        {
-          *y = yc + 1;
-          *x = xc;
-          break;
-        };
+        p.x = xc;
+        p.y = yc + 1;
+        break;
+
       case 2:                  /* down */
-        {
-          *y = yc - 1;
-          *x = xc;
-          break;
-        };
+        p.x = xc;
+        p.y = yc - 1;
+        break;
+
       case 3:                  /* right */
-        {
-          *y = yc;
-          *x = xc + 1;
-          break;
-        }
+        p.x = xc + 1;
+        p.y = yc;
+        break;
+        
       case 4:                  /* left */
-        {
-          *x = xc - 1;
-          *y = yc;
-          break;
-        }
-      default:                 /* ??? */
-        return -1;
-
+        p.x = xc - 1;
+        p.y = yc;
+        break;
     }
+
   return 1;
 }
 
-/* recursive routine which will fill every available space in the maze
-        with walls*/
+/* 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
-fill_maze_full (char **maze, int x, int y, int xsize, int ysize)
+maze_gen (Layout maze, int subtype)
 {
-  int xc, yc;
+  xsize = maze->w;
+  ysize = maze->h;
+  ::maze = maze;
 
-  /* write a wall here */
-  maze[x][y] = '#';
+  maze->clear ();
+  maze->border ();
 
-  /* decide if we're going to pick from the wall_free_list */
-  if (rmg_rndm (4) && wall_free_size > 0)
-    {
-      pop_wall_point (&xc, &yc);
-      fill_maze_full (maze, xc, yc, xsize, ysize);
-    }
+  if (xsize < 4 || ysize < 4)
+    return;
+
+  seed_max = xsize * ysize;
+  seed_size = 0;
+  seed_list = salloc<point> (seed_max);
+
+  if (subtype > 0)
+    push_walls ();
+
+  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.  */
-  while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
+  bool full = subtype == 3;
+
+  /* recursively generate the walls of the maze */
+  /* first pop a random starting point */
+  while (seed_size)
     {
-      fill_maze_full (maze, xc, yc, xsize, ysize);
-    }
-}
+      point p = pop_rand ();
 
-/* recursive routine which will fill much of the maze, but will leave
-        some free spots (possibly large) toward the center.*/
-void
-fill_maze_sparse (char **maze, int x, int y, int xsize, int ysize)
-{
-  int xc, yc;
+      for (;;)
+        {
+          point pc;
 
-  /* write a wall here */
-  maze[x][y] = '#';
+          maze [p.x][p.y] = '#';
 
-  /* decide if we're going to pick from the wall_free_list */
-  if (rmg_rndm (4) && wall_free_size > 0)
-    {
-      pop_wall_point (&xc, &yc);
-      fill_maze_sparse (maze, xc, yc, xsize, ysize);
+          if (find_free_point (pc, p) < 0)
+            break;
+
+          if (full)
+            push (p);
+
+          if (!rmg_rndm (8))
+            {
+              if (!full)
+                push (pc);
+
+              break;
+            }
+
+          p = pc;
+        }
     }
 
-  /* 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);
+  /* clean up our intermediate data structures. */
+  sfree (seed_list, seed_max);
 }
+
+#if 0
+static struct demo
+{
+  demo ()
+  {
+    Layout layout (40, 25);
+    rmg_rndm.seed (time (0));
+
+    for(int i=1;i<10;++i)
+      {
+        maze_gen (layout, 3);
+        layout.print ();
+      }
+    exit (1);
+  }
+} demo;
+#endif