--- deliantra/server/random_maps/maze_gen.C	2010/06/26 23:53:31	1.17
+++ deliantra/server/random_maps/maze_gen.C	2010/07/01 01:22:44	1.24
@@ -37,6 +37,8 @@
    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"
@@ -44,73 +46,57 @@
 
 /* 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<point> 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, int xsize, int ysize)
+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 */
     {
@@ -158,125 +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, int xsize, int 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 = 3=full, 2=braided, 1=sparse, 0=rooms.*/
+void
+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;
 
-  /* change the while to an if for a sparse maze. */
-  while (find_free_point (maze, &xc, &yc, x, y, xsize, ysize) != -1)
-    fill_maze_full (maze, xc, yc, xsize, ysize);
-}
+  seeds.reset (xsize * ysize);
 
-/* 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 xsize, int ysize)
-{
-  int xc, yc;
+  if (subtype > 0)
+    push_walls ();
 
-  /* write a wall here */
-  maze[x][y] = '#';
+  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)));
 
-  /* 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);
-    }
+  bool full = subtype == 3;
 
-  /* 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);
-}
+  /* recursively generate the walls of the maze */
+  /* first pop a random starting point */
+  while (seeds.size)
+    {
+      point p = pop_rand ();
 
-/* 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 ();
+      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, maze->w, maze->h);
-      else
-        fill_maze_sparse (maze, i, j, maze->w, maze->h);
+          p = pc;
+        }
     }
 
-  /* clean up our intermediate data structures. */
-
-  free (wall_x_list);
-  free (wall_y_list);
+  seeds.free ();
 }
 
-#if 0
-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