--- deliantra/server/random_maps/maze_gen.C	2010/06/26 23:53:31	1.17
+++ deliantra/server/random_maps/maze_gen.C	2010/06/29 18:27:02	1.22
@@ -37,80 +37,92 @@
    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"
 
+struct point
+{
+  short x;
+  short y;
+
+  point ()
+  {
+  }
+
+  point (int x, int y)
+  : x(x), y(y)
+  {
+  }
+};
+
 /* 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 point *seed_list;
+static int seed_max, seed_size;
+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;
+  assert (seed_size < seed_max);
 
-  count = 0;                    /* entries already placed in the free list */
-  /*allocate it */
-  if (wall_free_size < 0)
-    return;
+  seed_list [seed_size++] = p;
 
-  wall_x_list = (int *)calloc (sizeof (int), wall_free_size);
-  wall_y_list = (int *)calloc (sizeof (int), wall_free_size);
+  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. */
+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)
+static point
+pop_rand ()
 {
-  int index = rmg_rndm (wall_free_size);
+  int index = rmg_rndm (seed_size);
 
-  *x = wall_x_list[index];
-  *y = wall_y_list[index];
+  point p = seed_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. */
 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,109 +170,90 @@
   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)
-{
-  int xc, yc;
-
-  /* write a wall here */
-  maze[x][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_full (maze, xc, yc, xsize, ysize);
-    }
-
-  /* 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);
-}
-
-/* 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;
-
-  /* write a wall here */
-  maze[x][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);
-    }
-
-  /* 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.*/
+mazes have sizable rooms. option = 3=full, 2=braided, 1=sparse, 0=rooms.*/
 void
-maze_gen (Layout maze, int full)
+maze_gen (Layout maze, int subtype)
 {
+  xsize = maze->w;
+  ysize = maze->h;
+  ::maze = maze;
+
   maze->clear ();
   maze->border ();
 
-  /* find how many free wall spots there are */
-  wall_free_size = 2 * (maze->w - 4) + 2 * (maze->h - 4);
+  if (xsize < 4 || ysize < 4)
+    return;
 
-  make_wall_free_list (maze->w, maze->h);
+  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)));
 
-  /* return the empty maze */
-  if (wall_free_size <= 0)
-    return;
+  bool full = subtype == 3;
 
   /* recursively generate the walls of the maze */
   /* first pop a random starting point */
-  while (wall_free_size > 0)
+  while (seed_size)
     {
-      int i, j;
+      point p = pop_rand ();
+
+      for (;;)
+        {
+          point pc;
 
-      pop_wall_point (&i, &j);
+          maze [p.x][p.y] = '#';
 
-      if (full)
-        fill_maze_full (maze, i, j, maze->w, maze->h);
-      else
-        fill_maze_sparse (maze, i, j, maze->w, maze->h);
+          if (find_free_point (pc, p) < 0)
+            break;
+
+          if (full)
+            push (p);
+
+          if (!rmg_rndm (8))
+            {
+              if (!full)
+                push (pc);
+
+              break;
+            }
+
+          p = pc;
+        }
     }
 
   /* clean up our intermediate data structures. */
-
-  free (wall_x_list);
-  free (wall_y_list);
+  sfree (seed_list, seed_max);
 }
 
 #if 0
@@ -268,12 +261,12 @@
 {
   demo ()
   {
-    Layout layout (30, 30);
+    Layout layout (40, 25);
     rmg_rndm.seed (time (0));
 
     for(int i=1;i<10;++i)
       {
-        maze_gen (layout, 1);
+        maze_gen (layout, 3);
         layout.print ();
       }
     exit (1);