--- deliantra/server/random_maps/layout.C	2010/07/03 01:12:44	1.11
+++ deliantra/server/random_maps/layout.C	2010/07/04 22:12:26	1.23
@@ -36,13 +36,12 @@
   // we store the layout in a single contiguous memory layout
   // first part consists of pointers to each column, followed
   // by the actual columns (not rows!)
-  int size = (sizeof (cell *) + sizeof (cell) * h) * w;
-
+  size = (sizeof (cell *) + sizeof (cell) * h) * w;
   data = (cell **)salloc<char> (size);
 
   cell *p = (cell *)(data + w);
 
-  for (int x = w; x--; )
+  for (int x = 0; x < w; ++x)
     data [x] = p + x * h;
 }
 
@@ -58,17 +57,30 @@
   memcpy (data [0], copy.data [0], sizeof (cell) * h * w);
 }
 
-layout::~layout ()
+layout::layout (layout &orig, int x1, int y1, int x2, int y2)
 {
-  int size = (sizeof (cell *) + sizeof (cell) * h) * w;
+  w = x2 - x1;
+  h = y2 - y1;
+
+  // we only allocate space for the pointers
+  size = sizeof (cell *) * w;
+  data = (cell **)salloc<char> (size);
 
+  // and now we point back into the original layout
+  for (int x = 0; x < w; ++x)
+    data [x] = orig.data [x + x1] + y1;
+}
+
+layout::~layout ()
+{
   sfree ((char *)data, size);
 }
 
 void
 layout::fill (char fill)
 {
-  memset (data [0], fill, w * h);
+  //memset (data [0], fill, w * h); // only when contiguous :/
+  fill_rect (0, 0, w, h, fill);
 }
 
 void
@@ -100,8 +112,8 @@
 {
   percent = lerp (percent, 0, 100, 0, 256);
 
-  for (int x = w - 1; --x > 0; )
-    for (int y = h - 1; --y > 0; )
+  for (int x = 0; x < w; ++x)
+    for (int y = 0; y < h; ++y)
       data [x][y] = rmg_rndm (256) > percent ? 0 : '#';
 }
 
@@ -211,22 +223,24 @@
 }
 
 static inline void
-make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d)
+make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d, int perturb)
 {
   for (;;)
     {
       point neigh[4];
       int ncnt = 0;
 
-      if (x >          1 && U8 (dist [x - 1][y]) <= d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y);
-      if (x < dist.w - 2 && U8 (dist [x + 1][y]) <= d && dist [x + 1][y] > 1) neigh [ncnt++] = point (x + 1, y);
-      if (y >          1 && U8 (dist [x][y - 1]) <= d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1);
-      if (y < dist.h - 2 && U8 (dist [x][y + 1]) <= d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1);
+      d += perturb > 1;
+
+      if (x >          0 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y);
+      if (x < dist.w - 1 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) neigh [ncnt++] = point (x + 1, y);
+      if (y >          0 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1);
+      if (y < dist.h - 1 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1);
 
       if (!ncnt)
         return;
 
-      point &p = neigh [rmg_rndm (ncnt)];
+      point p = neigh [perturb ? rmg_rndm (ncnt) : 0];
 
       seeds.push (p);
 
@@ -254,13 +268,15 @@
 // isolation remover, works on a "distance" map
 // the map must be initialised with 0 == rooms, 255 = walls
 static void noinline
-isolation_remover (layout &dist)
+isolation_remover (layout &dist, unsigned int perturb = 2)
 {
   // dist contains
   // 0 == invisited rooms
   // 1 == visited rooms
   // 2+ shortest distance to random near room
 
+  clamp_it (perturb, 0, 2);
+
   // phase 1, find seed
   int cnt = 0;
   int x, y;
@@ -274,8 +290,7 @@
     {
       // map is completely massive, this is not good,
       // so make it empty instead.
-      dist.clear ();
-      dist.border (255);
+      dist.fill (1);
       return;
     }
 
@@ -302,7 +317,7 @@
         {
           // found new isolated area, make tunnel
           push_flood_fill (dist, seeds, x, y);
-          make_tunnel (dist, seeds, x, y, 255);
+          make_tunnel (dist, seeds, x, y, 254, perturb);
         }
       else
         {
@@ -318,65 +333,25 @@
 }
 
 void
-layout::isolation_remover ()
+layout::isolation_remover (int perturb)
 {
-  layout dist (w, h);
+  layout dist (w - 2, h - 2); // map without border
 
-  for (int x = 0; x < w; ++x)
-    for (int y = 0; y < h; ++y)
-      dist [x][y] = data [x][y] == '#' ? U8 (255) : 0;
+  for (int x = 1; x < w - 1; ++x)
+    for (int y = 1; y < h - 1; ++y)
+      dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0;
 
-  ::isolation_remover (dist);
+  ::isolation_remover (dist, perturb);
 
   // now copy the tunnels over
-  for (int x = 0; x < w; ++x)
-    for (int y = 0; y < h; ++y)
-      if (data [x][y] == '#' && dist [x][y] == 1)
+  for (int x = 1; x < w - 1; ++x)
+    for (int y = 1; y < h - 1; ++y)
+      if (data [x][y] == '#' && dist [x - 1][y - 1] == 1)
         data [x][y] = 0;
 }
 
 /////////////////////////////////////////////////////////////////////////////
 
-// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
-void
-layout::gen_cave (int subtype)
-{
-  switch (subtype)
-    {
-      // a rough cave
-      case 0:
-        fill_rand (rmg_rndm (85, 97));
-        break;
-
-      // corridors
-      case 1:
-        fill_rand (rmg_rndm (5, 40));
-        erode_1_2 (5,  2, 10);
-        erode_1_2 (5, -1, 10);
-        erode_1_2 (5,  2, 1);
-        break;
-
-      // somewhat open, roundish
-      case 2:
-        fill_rand (45);
-        erode_1_2 (5,  0, 5);
-        erode_1_2 (5, 1, 1);
-        break;
-
-      // wide open, some room-like structures
-      case 3:
-        fill_rand (45);
-        erode_1_2 (5,  2, 4);
-        erode_1_2 (5, -1, 3);
-        break;
-    }
-
-  border ();
-  isolation_remover ();
-}
-
-/////////////////////////////////////////////////////////////////////////////
-
 //+GPL
 
 /*  puts doors at appropriate locations in a maze. */
@@ -384,10 +359,8 @@
 layout::doorify ()
 {
   int ndoors = w * h / 60;      /* reasonable number of doors. */
-  int doorlocs = 0;             /* # of available doorlocations */
 
-  uint16 *doorlist_x = salloc<uint16> (w * h);
-  uint16 *doorlist_y = salloc<uint16> (w * h);
+  fixed_stack<point> doorloc (w * h);
 
   /* make a list of possible door locations */
   for (int i = 1; i < w - 1; i++)
@@ -396,34 +369,21 @@
         int sindex = surround_flag (*this, i, j);
 
         if (sindex == 3 || sindex == 12)        /* these are possible door sindex */
-          {
-            doorlist_x [doorlocs] = i;
-            doorlist_y [doorlocs] = j;
-            doorlocs++;
-          }
+          doorloc.push (point (i, j));
       }
 
-  while (ndoors > 0 && doorlocs > 0)
+  while (ndoors && doorloc.size)
     {
-      int di = rmg_rndm (doorlocs);
-      int i = doorlist_x [di];
-      int j = doorlist_y [di];
-      int sindex = surround_flag (*this, i, j);
+      point p = doorloc.remove (rmg_rndm (doorloc.size));
+
+      int sindex = surround_flag (*this, p.x, p.y);
 
       if (sindex == 3 || sindex == 12)  /* these are possible door sindex */
         {
-          data [i][j] = 'D';
-          ndoors--;
+          data [p.x][p.y] = 'D';
+          --ndoors;
         }
-
-      /* reduce the size of the list */
-      doorlocs--;
-      doorlist_x[di] = doorlist_x [doorlocs];
-      doorlist_y[di] = doorlist_y [doorlocs];
     }
-
-  sfree (doorlist_x, w * h);
-  sfree (doorlist_y, w * h);
 }
 
 /* takes a map and makes it symmetric: adjusts Xsize and
@@ -743,7 +703,7 @@
 }
 
 int
-make_wall (char **maze, int x, int y, int dir)
+make_wall (layout &maze, int x, int y, int dir)
 {
   maze[x][y] = 'D';             /* mark a door */
 
@@ -802,8 +762,114 @@
     }
 }
 
+//-GPL
+
 /////////////////////////////////////////////////////////////////////////////
 
+// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
+void
+layout::gen_cave (int subtype)
+{
+  switch (subtype)
+    {
+      // a rough cave
+      case 0:
+        fill_rand (rmg_rndm (85, 97));
+        break;
+
+      // corridors
+      case 1:
+        fill_rand (rmg_rndm (5, 40));
+        erode_1_2 (5,  2, 10);
+        erode_1_2 (5, -1, 10);
+        erode_1_2 (5,  2, 1);
+        break;
+
+      // somewhat open, some room-like structures
+      case 2:
+        fill_rand (45);
+        erode_1_2 (5,  2, 4);
+        erode_1_2 (5, -1, 3);
+        break;
+
+      // wide open, roundish
+      case 3:
+        fill_rand (45);
+        erode_1_2 (5,  0, 5);
+        erode_1_2 (5, 1, 1);
+        break;
+    }
+
+  border ();
+  isolation_remover (1);
+}
+
+void
+layout::gen_castle ()
+{
+  fill ('#');
+
+  for (int n = w * h / 30 + 1; n--; )
+    {
+      int rw = rmg_rndm (6, 10);
+      int rh = rmg_rndm (6, 10);
+
+      if (rw > w || rh > h)
+        continue;
+
+      int rx = rmg_rndm (0, w - rw);
+      int ry = rmg_rndm (0, h - rh);
+
+      rect (rx, ry, rx + rw, ry + rh, '#');
+      fill_rect (rx + 1, ry + 1, rx + rw - 1, ry + rh - 1, 0);
+    }
+
+  border ();
+  isolation_remover (0);
+}
+
+static void
+gen_mixed_ (layout &maze, random_map_params *RP)
+{
+  if (maze.w > maze.h && maze.w > 16)
+    {
+      int m = rmg_rndm (8, maze.w - 8);
+
+      layout m1 (maze, 0, 0, m     , maze.h); gen_mixed_ (m1, RP);
+      layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP);
+    }
+  else if (maze.h > 16)
+    {
+      int m = rmg_rndm (8, maze.h - 8);
+
+      layout m1 (maze, 0, 0, maze.w, m     ); gen_mixed_ (m1, RP);
+      layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP);
+    }
+  else
+    {
+      RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1;
+
+      if (RP->map_layout_style == LAYOUT_MULTIPLE)
+        ++RP->map_layout_style;
+
+      maze.generate (RP);
+    }
+}
+
+// recursive subdivision with random sublayouts
+static void
+gen_mixed (layout &maze, random_map_params *RP)
+{
+  random_map_params &rp = *new random_map_params (RP);
+  gen_mixed_ (maze, &rp);
+  delete &rp;
+
+  maze.border ();
+  maze.isolation_remover (0);
+}
+
+//+GPL
+
 /*  function selects the maze function and gives it whatever
     arguments it needs.  */
 void
@@ -872,26 +938,47 @@
 
         break;
 
-      default:
-        abort ();
-    }
+      case LAYOUT_CASTLE:
+        gen_castle ();
 
-  /*  rotate the maze randomly */
-  rotate (rmg_rndm (4));
+        if (rmg_rndm (2))
+          doorify ();
 
-  symmetrize (RP->symmetry_used);
+        break;
 
-#if 0
-  print ();//D
-#endif
+      case LAYOUT_MULTIPLE:
+        gen_mixed (*this, RP);
+        break;
 
-  if (RP->expand2x)
-    expand2x ();
+      default:
+        abort ();
+    }
 }
 
 //-GPL
 
 #if 0
+static void
+gen_village (layout &maze)
+{
+  maze.clear ();
+  maze.border ();
+
+  for (int n = maze.w * maze.h / 200 + 1; n--; )
+    {
+      int rw = rmg_rndm (6, 10);
+      int rh = rmg_rndm (6, 10);
+
+      int rx = rmg_rndm (2, maze.w - rw - 2);
+      int ry = rmg_rndm (2, maze.h - rh - 2);
+
+      maze.rect (rx, ry, rx + rw, ry + rh, '#');
+    }
+
+  maze.border ();
+  maze.isolation_remover (2);
+}
+
 static struct demo
 {
   demo ()
@@ -900,11 +987,11 @@
 
     for(int i=1;i<100;i++)
       {
-        layout maze (40, 25);
-        maze.fill_rand (85);
-        maze.border ();
-        maze.isolation_remover ();
+        layout maze (40, 30);
+        gen_village (maze);
+        maze.doorify ();
         maze.print ();
+        exit(0);
       }
 
     exit (1);