--- deliantra/server/random_maps/layout.C	2010/07/02 15:03:57	1.7
+++ deliantra/server/random_maps/layout.C	2018/11/17 23:33:18	1.33
@@ -1,83 +1,136 @@
 /*
  * This file is part of Deliantra, the Roguelike Realtime MMORPG.
- * 
- * Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
- * Copyright (©) Crossfire Development Team (restored, original file without copyright notice)
- * 
+ *
+ * Copyright (©) 2010,2011,2012,2013,2014,2015,2016 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
  * <http://www.gnu.org/licenses/>.
- * 
+ *
  * The authors can be reached via e-mail to <support@deliantra.net>
  */
 
 #include <global.h>
-#include <random_map.h>
+#include <rmg.h>
 #include <rproto.h>
 
+ecb_noinline void
+layout::alloc (int w, int h)
+{
+  assert (sizeof (cell) == 1);
+
+  this->w = w;
+  this->h = h;
+
+  // 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!)
+  size = (sizeof (cell *) + sizeof (cell) * h) * w;
+  data = (cell **)salloc<char> (size);
+
+  cell *p = (cell *)(data + w);
+
+  for (int x = 0; x < w; ++x)
+    data [x] = p + x * h;
+}
+
 layout::layout (int w, int h)
-: w(w), h(h)
 {
-  int size = (sizeof (char *) + sizeof (char) * h) * w;
+  alloc (w, h);
+}
+
+layout::layout (layout &copy)
+{
+  alloc (copy.w, copy.h);
+
+  memcpy (data [0], copy.data [0], sizeof (cell) * h * w);
+}
 
-  col = (char **)salloc<char> (size);
+layout::layout (layout &orig, int x1, int y1, int x2, int y2)
+{
+  w = x2 - x1;
+  h = y2 - y1;
 
-  char *data = (char *)(col + w);
+  // we only allocate space for the pointers
+  size = sizeof (cell *) * w;
+  data = (cell **)salloc<char> (size);
 
-  for (int x = w; x--; )
-    col [x] = data + x * h;
+  // 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 ()
 {
-  int size = (sizeof (char *) + sizeof (char) * h) * w;
-
-  sfree ((char *)col, size);
+  sfree ((char *)data, size);
 }
 
-void
+ecb_noinline void
 layout::fill (char fill)
 {
-  memset (col [0], fill, w * h);
+  //memset (data [0], fill, w * h); // only when contiguous :/
+  fill_rect (0, 0, w, h, fill);
 }
 
-void
+ecb_noinline void
+layout::replace (char from, char to)
+{
+  for (int x = 0; x < w; ++x)
+    for (int y = 0; y < h; ++y)
+      if (data [x][y] == from)
+        data [x][y] = to;
+}
+
+ecb_noinline void
 layout::rect (int x1, int y1, int x2, int y2, char fill)
 {
-  for (; x1 < x2; ++x1)
-    memset (col [x1] + y1, fill, y2 - y1);
+  --x2;
+
+  memset (data [x1] + y1, fill, y2 - y1);
+  memset (data [x2] + y1, fill, y2 - y1);
+
+  while (++x1 < x2)
+    data [x1][y1] = data [x1][y2 - 1] = fill;
 }
 
-void layout::border (char fill)
+ecb_noinline void
+layout::fill_rect (int x1, int y1, int x2, int y2, char fill)
 {
-  for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill;
-  for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill;
+  for (; x1 < x2; ++x1)
+    memset (data [x1] + y1, fill, y2 - y1);
 }
 
 void
+layout::border (char fill)
+{
+  rect (0, 0, w, h, fill);
+}
+
+ecb_noinline void
 layout::fill_rand (int percent)
 {
   percent = lerp (percent, 0, 100, 0, 256);
 
-  for (int x = w - 1; --x > 0; )
-    for (int y = h - 1; --y > 0; )
-      col [x][y] = rmg_rndm (256) > percent ? 0 : '#';
+  for (int x = 0; x < w; ++x)
+    for (int y = 0; y < h; ++y)
+      data [x][y] = rmg_rndm (256) > percent ? 0 : '#';
 }
 
 /////////////////////////////////////////////////////////////////////////////
 
 // erode by cellular automata
-void
+ecb_noinline void
 layout::erode_1_2 (int c1, int c2, int repeat)
 {
   layout neu (w, h);
@@ -106,7 +159,7 @@
                   int nx = x + dds [i][0];
                   int ny = y + dds [i][1];
 
-                  if (!IN_RANGE_EXC (nx, 0, w) || !IN_RANGE_EXC (ny, 0, h) || !col [nx][ny])
+                  if (!IN_RANGE_EXC (nx, 0, w) || !IN_RANGE_EXC (ny, 0, h) || !data [nx][ny])
                     {
                       n1 += dds [i][2];
                       n2++;
@@ -130,7 +183,7 @@
     {
       for (int x = 0; x < w; x++)
         {
-          U8 c = (U8)col [x][y];
+          U8 c = (U8)data [x][y];
 
           if (!c)
             c = ' ';
@@ -153,7 +206,7 @@
 
 typedef fixed_stack<point> pointlist;
 
-static noinline void
+ecb_noinline static void
 push_flood_fill (layout &dist, pointlist &seeds, int x, int y)
 {
   if (dist [x][y])
@@ -174,30 +227,38 @@
 
   while (--y >= y0)
     {
-      if (x >          0) push_flood_fill (dist, seeds, x - 1, y);
-      if (x < dist.w - 1) push_flood_fill (dist, seeds, x + 1, y);
+      if (x >          0 && !dist [x - 1][y]) push_flood_fill (dist, seeds, x - 1, y);
+      if (x < dist.w - 1 && !dist [x + 1][y]) push_flood_fill (dist, seeds, x + 1, y);
     }
 }
 
-static inline void
-make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d)
+static void inline
+make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d, int perturb)
 {
   for (;;)
     {
-      if (x >               1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1)
-        --x;
-      else if (x < dist.w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1)
-        ++x;
-      else if (y >          1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1)
-        --y;
-      else if (y < dist.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1)
-        ++y;
-      else
-        break;
+      point neigh[4];
+      int ncnt = 0;
+
+      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 [perturb ? rmg_rndm (ncnt) : 0];
+
+      seeds.push (p);
+
+      x = p.x;
+      y = p.y;
 
       d = dist [x][y];
       dist [x][y] = 1;
-      seeds.push (point (x, y));
     }
 }
 
@@ -214,43 +275,36 @@
   seeds.push (point (x, y));
 }
 
-void
-layout::isolation_remover (bool dirty)
+// isolation remover, works on a "distance" map
+// the map must be initialised with 0 == rooms, 255 = walls
+ecb_noinline static void
+isolation_remover (layout &dist, unsigned int perturb = 2)
 {
-  layout dist (w, h);
-
   // dist contains
   // 0 == invisited rooms
   // 1 == visited rooms
   // 2+ shortest distance to random near room
 
-  // phase 1, initialise dist array, find seed
+  clamp_it (perturb, 0, 2);
+
+  // phase 1, find seed
   int cnt = 0;
   int x, y;
 
-  for (int i = 0; i < w; ++i)
-    for (int j = 0; j < h; ++j)
-      {
-        if (col [i][j] == '#')
-          dist [i][j] = U8 (255);
-        else
-          {
-            dist [i][j] = 0;
-            if (!rmg_rndm (++cnt))
-              x = i, y = j;
-          }
-      }
+  for (int i = 0; i < dist.w; ++i)
+    for (int j = 0; j < dist.h; ++j)
+      if (!dist [i][j]  && !rmg_rndm (++cnt))
+        x = i, y = j;
 
   if (!cnt)
     {
       // map is completely massive, this is not good,
       // so make it empty instead.
-      clear ();
-      border ();
+      dist.fill (1);
       return;
     }
 
-  fixed_stack<point> seeds (w * h * 5);
+  fixed_stack<point> seeds (dist.w * dist.h * 5);
 
   // found first free space - picking the first one gives
   // us a slight bias for tunnels, but usually you won't
@@ -260,11 +314,17 @@
   // phase 2, while we have seeds, if
   // seed is empty, floodfill, else grow
 
+  int rem_index = 0; // used to remove "somewhat ordered"
+
   while (seeds.size)
     {
       coroapi::cede_to_tick ();
 
-      point p = seeds.remove (rmg_rndm (seeds.size));
+      int i = perturb
+              ? rmg_rndm (max (0, seeds.size - 8), seeds.size - 1)
+              : rem_index ++ % seeds.size;
+
+      point p = seeds.remove (i);
 
       x = p.x;
       y = p.y;
@@ -272,13 +332,8 @@
       if (!dist [x][y])
         {
           // found new isolated area, make tunnel
-          if (!dirty)
-            push_flood_fill (dist, seeds, x, y);
-
-          make_tunnel (dist, seeds, x, y, 255);
-
-          if (dirty)
-            push_flood_fill (dist, seeds, x, y);
+          push_flood_fill (dist, seeds, x, y);
+          make_tunnel (dist, seeds, x, y, 254, perturb);
         }
       else
         {
@@ -291,52 +346,24 @@
           if (y >          0) maybe_push (dist, seeds, x, y - 1, d);
         }
     }
-
-  // now copy the tunnels over
-  for (int x = 0; x < w; ++x)
-    for (int y = 0; y < h; ++y)
-      if (col [x][y] == '#' && dist [x][y] == 1)
-        col [x][y] = 0;
 }
 
-/////////////////////////////////////////////////////////////////////////////
-
-// inspired mostly by http://www.jimrandomh.org/misc/caves.txt
 void
-layout::gen_cave (int subtype)
+layout::isolation_remover (int perturb)
 {
-  switch (subtype)
-    {
-      // a rough cave
-      case 0:
-        fill_rand (rmg_rndm (80, 95));
-        break;
+  layout dist (w - 2, h - 2); // map without border
 
-      // 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;
+  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;
 
-      // somewhat open, roundish
-      case 2:
-        fill_rand (45);
-        erode_1_2 (5,  0, 5);
-        erode_1_2 (5, 1, 1);
-        break;
+  ::isolation_remover (dist, perturb);
 
-      // 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 ();
+  // now copy the tunnels over
+  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;
 }
 
 /////////////////////////////////////////////////////////////////////////////
@@ -348,10 +375,10 @@
 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);
+  coroapi::cede_to_tick ();
+
+  fixed_stack<point> doorloc (w * h);
 
   /* make a list of possible door locations */
   for (int i = 1; i < w - 1; i++)
@@ -360,34 +387,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 */
         {
-          col [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
@@ -409,7 +423,7 @@
       for (int j = 0; j < sym_layout.h; j++)
         {
           sym_layout[i                   ][j] =
-          sym_layout[sym_layout.w - i - 1][j] = col[i][j];
+          sym_layout[sym_layout.w - i - 1][j] = data [i][j];
         }
 
   if (symmetry == SYMMETRY_Y)
@@ -417,7 +431,7 @@
       for (int j = 0; j < sym_layout.h / 2 + 1; j++)
         {
           sym_layout[i][j                   ] =
-          sym_layout[i][sym_layout.h - j - 1] = col[i][j];
+          sym_layout[i][sym_layout.h - j - 1] = data [i][j];
         }
 
   if (symmetry == SYMMETRY_XY)
@@ -427,7 +441,7 @@
           sym_layout[i                   ][j                   ] =
           sym_layout[i                   ][sym_layout.h - j - 1] =
           sym_layout[sym_layout.w - i - 1][j                   ] =
-          sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = col[i][j];
+          sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = data [i][j];
         }
 
   /* need to run the isolation remover for some layouts */
@@ -455,6 +469,8 @@
 void
 layout::rotate (int rotation)
 {
+  coroapi::cede_to_tick ();
+
   switch (rotation & 3)
     {
       case 2:                  /* a reflection */
@@ -463,7 +479,7 @@
 
           for (int i = 0; i < w; i++)                   /* copy a reflection back */
             for (int j = 0; j < h; j++)
-              new_layout [i][j] = col [w - i - 1][h - j - 1];
+              new_layout [i][j] = data [w - i - 1][h - j - 1];
 
           swap (new_layout);
         }
@@ -477,12 +493,12 @@
           if (rotation == 1)    /* swap x and y */
             for (int i = 0; i < w; i++)
               for (int j = 0; j < h; j++)
-                new_layout [j][i] = col [i][j];
+                new_layout [j][i] = data [i][j];
 
           if (rotation == 3) /* swap x and y */
             for (int i = 0; i < w; i++)
               for (int j = 0; j < h; j++)
-                new_layout [j][i] = col [w - i - 1][h - j - 1];
+                new_layout [j][i] = data [w - i - 1][h - j - 1];
 
           swap (new_layout);
         }
@@ -519,7 +535,7 @@
  *	4	match on (i+1, j+1)
  * and the possible combinations thereof.
  */
-static int noinline
+ecb_noinline static int
 calc_pattern (char ch, layout &maze, int i, int j)
 {
   int pattern = 0;
@@ -616,12 +632,14 @@
 
   new_layout.clear ();
 
+  coroapi::cede_to_tick ();
+
   for (int i = 0; i < w; i++)
     for (int j = 0; j < h; j++)
-      switch (col [i][j])
+      switch (data [i][j])
         {
-          case '#': expand_wall (new_layout, i, j, *this); break; 
-          case 'D': expand_door (new_layout, i, j, *this); break; 
+          case '#': expand_wall (new_layout, i, j, *this); break;
+          case 'D': expand_door (new_layout, i, j, *this); break;
           default:  expand_misc (new_layout, i, j, *this); break;
         }
 
@@ -707,7 +725,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 */
 
@@ -735,6 +753,8 @@
 {
   int tries = w * h / 30;
 
+  coroapi::cede_to_tick ();
+
   for (int ti = 0; ti < tries; ti++)
     {
       /* starting location for looking at creating a door */
@@ -766,8 +786,121 @@
     }
 }
 
+//-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);
+    }
+
+  coroapi::cede_to_tick ();
+}
+
+// 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 ();
+
+  // exits currently do not work so well, as they
+  // are currently often found together, so nuke entrances
+  maze.replace ('<', ' ');
+
+  maze.isolation_remover (0);
+}
+
+//+GPL
+
 /*  function selects the maze function and gives it whatever
     arguments it needs.  */
 void
@@ -836,42 +969,60 @@
 
         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 ()
   {
     rmg_rndm.seed (time (0));
+    extern void hack();hack ();
 
-    for(int i=1;i<10;i)
+    for(int i=1;i<100;i++)
       {
-        layout maze (10, 10);
-        maze.fill_rand (90);
+        layout maze (40, 30);
+        maze.fill_rand (99);
         maze.border ();
-        maze.isolation_remover ();
-        maze.doorify ();
-        maze.symmetrize (rmg_rndm (2, 4));
-        maze.rotate (rmg_rndm (4));
-        maze.expand2x ();
+        maze.isolation_remover (2);
         maze.print ();
       }