--- deliantra/server/random_maps/layout.C	2010/07/03 02:19:10	1.14
+++ deliantra/server/random_maps/layout.C	2011/04/23 04:56:52	1.28
@@ -1,8 +1,8 @@
 /*
  * 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 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
@@ -22,10 +22,10 @@
  */
 
 #include <global.h>
-#include <random_map.h>
+#include <rmg.h>
 #include <rproto.h>
 
-void
+void noinline
 layout::alloc (int w, int h)
 {
   assert (sizeof (cell) == 1);
@@ -76,13 +76,23 @@
   sfree ((char *)data, size);
 }
 
-void
+void noinline
 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
+void noinline
+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;
+}
+
+void noinline
 layout::rect (int x1, int y1, int x2, int y2, char fill)
 {
   --x2;
@@ -94,32 +104,33 @@
     data [x1][y1] = data [x1][y2 - 1] = fill;
 }
 
-void
+void noinline
 layout::fill_rect (int x1, int y1, int x2, int y2, char fill)
 {
   for (; x1 < x2; ++x1)
     memset (data [x1] + y1, fill, y2 - y1);
 }
 
-void layout::border (char fill)
+void
+layout::border (char fill)
 {
   rect (0, 0, w, h, fill);
 }
 
-void
+void noinline
 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; )
+  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
+void noinline
 layout::erode_1_2 (int c1, int c2, int repeat)
 {
   layout neu (w, h);
@@ -221,23 +232,25 @@
     }
 }
 
-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 (;;)
     {
       point neigh[4];
       int ncnt = 0;
 
-      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);
+      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);
 
@@ -265,13 +278,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;
@@ -299,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;
@@ -312,7 +333,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
         {
@@ -328,7 +349,7 @@
 }
 
 void
-layout::isolation_remover ()
+layout::isolation_remover (int perturb)
 {
   layout dist (w - 2, h - 2); // map without border
 
@@ -336,7 +357,7 @@
     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 = 1; x < w - 1; ++x)
@@ -347,46 +368,6 @@
 
 /////////////////////////////////////////////////////////////////////////////
 
-// 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. */
@@ -394,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++)
@@ -406,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 */
         {
-          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
@@ -501,6 +469,8 @@
 void
 layout::rotate (int rotation)
 {
+  coroapi::cede_to_tick ();
+
   switch (rotation & 3)
     {
       case 2:                  /* a reflection */
@@ -662,6 +632,8 @@
 
   new_layout.clear ();
 
+  coroapi::cede_to_tick ();
+
   for (int i = 0; i < w; i++)
     for (int j = 0; j < h; j++)
       switch (data [i][j])
@@ -753,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 */
 
@@ -781,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 */
@@ -812,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
@@ -882,38 +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<100;i++)
       {
-        layout maze (40, 25);
-        maze.fill_rand (85);
+        layout maze (40, 30);
+        maze.fill_rand (99);
         maze.border ();
-        maze.isolation_remover ();
+        maze.isolation_remover (2);
         maze.print ();
       }