[ViewVC] Diff of: cvs/deliantra/server/random

Comparing deliantra/server/random_maps/layout.C (file contents):
Revision 1.2 by root, Wed Jun 30 23:03:40 2010 UTC vs.
Revision 1.3 by root, Thu Jul 1 01:22:44 2010 UTC

  */
 #include <global.h>
 #include <random_map.h>
-LayoutData::LayoutData (int w, int h)
+Layout::Layout (int w, int h)
 : w(w), h(h)
 {
   int size = (sizeof (char *) + sizeof (char) * h) * w;
   col = (char **)salloc<char> (size);
   for (int x = w; x--; )
     col [x] = data + x * h;
 }
-LayoutData::~LayoutData ()
+Layout::~Layout ()
 {
   int size = (sizeof (char *) + sizeof (char) * h) * w;
   sfree ((char *)col, size);
 }
 void
-LayoutData::fill (char fill)
+Layout::fill (char fill)
 {
   memset (col [0], fill, w * h);
 }
 void
-LayoutData::rect (int x1, int y1, int x2, int y2, char fill)
+Layout::rect (int x1, int y1, int x2, int y2, char fill)
 {
   for (; x1 < x2; ++x1)
     memset (col [x1] + y1, fill, y2 - y1);
 }
-void LayoutData::border (char fill)
+void Layout::border (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;
 }
 void
-LayoutData::fill_rand (int percent)
+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; )
 /////////////////////////////////////////////////////////////////////////////
 // erode by cellular automata
 void
-LayoutData::erode_1_2 (int c1, int c2, int repeat)
+Layout::erode_1_2 (int c1, int c2, int repeat)
 {
-  LayoutData neu (w, h);
+  Layout neu (w, h);
   while (repeat--)
     {
       for (int x = 0; x < w; ++x)
         {
 }
 /////////////////////////////////////////////////////////////////////////////
 void
-LayoutData::print ()
+Layout::print ()
 {
   for (int y = 0; y < h; y++)
     {
       for (int x = 0; x < w; x++)
         {
 // isolation remover - ensures single connected area
 typedef fixed_stack<point> pointlist;
 static noinline void
-push_flood_fill (LayoutData &maze, LayoutData &dist, pointlist &seeds, int x, int y)
+push_flood_fill (Layout &dist, pointlist &seeds, int x, int y)
 {
-  if (maze [x][y])
+  if (dist [x][y])
     return;
-  while (y > 0 && !maze [x][y - 1])
+  while (y > 0 && !dist [x][y - 1])
     --y;
   int y0 = y;
-  while (y < maze.h && !maze [x][y])
+  while (y < dist.h && !dist [x][y])
     {
       seeds.push (point (x, y));
-      maze [x][y] = 1;
       dist [x][y] = 1;
       ++y;
     }
   while (--y >= y0)
     {
-      if (x >          0) push_flood_fill (maze, dist, seeds, x - 1, y);
+      if (x >          0) push_flood_fill (dist, seeds, x - 1, y);
-      if (x < maze.w - 1) push_flood_fill (maze, dist, seeds, x + 1, y);
+      if (x < dist.w - 1) push_flood_fill (dist, seeds, x + 1, y);
     }
 }
 static inline void
-make_tunnel (LayoutData &maze, LayoutData &dist, pointlist &seeds, int x, int y, U8 d)
+make_tunnel (Layout &dist, pointlist &seeds, int x, int y, U8 d)
 {
   for (;;)
     {
-      seeds.push (point (x, y));
-      maze [x][y] = 1;
-      dist [x][y] = 1;
       if (x >               1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1)
         --x;
-      else if (x < maze.w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1)
+      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 < maze.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1)
+      else if (y < dist.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1)
         ++y;
       else
         break;
       d = dist [x][y];
+      dist [x][y] = 1;
+      seeds.push (point (x, y));
     }
+}
+static void inline
+maybe_push (Layout &dist, pointlist &seeds, int x, int y, U8 d)
+{
+  char &D = dist [x][y];
+  if (U8 (D) > d) // if wall and higher distance, lower distance
+    D = d;
+  else if (D) // otherwise, if it's no room, this space is uninteresting
+    return;
+  seeds.push (point (x, y));
 }
 static void
-isolation_remover (LayoutData &maze, bool dirty)
+isolation_remover (Layout &maze, bool dirty)
 {
-  LayoutData dist (maze.w, maze.h);
+  Layout dist (maze.w, maze.h);
-  dist.fill (255);
+  // dist contains
+  // 0 == invisited rooms
+  // 1 == visited rooms
+  // 2+ shortest distance to random near room
+  // phase 1, initialise dist array, find seed
+  int cnt = 0;
+  int x, y;
+  for (int i = 0; i < maze.w; ++i)
+    for (int j = 0; j < maze.h; ++j)
+      {
+        if (maze [i][j] == '#')
+          dist [i][j] = U8 (255);
+        else
+          {
+            dist [i][j] = 0;
+            if (!rmg_rndm (++cnt))
+              x = i, y = j;
+          }
+      }
+  if (!cnt)
+    return;
-  fixed_stack<point> seeds (maze.w * maze.h * 4);
+  fixed_stack<point> seeds (maze.w * maze.h * 5);
-  // phase 1, find seed
+  // found first free space - picking the first one gives
-  for (int x = 1; x < maze.w; ++x)
+  // us a slight bias for tunnels, but usually you won't
-    for (int y = 1; y < maze.h; ++y)
+  // notice that in-game
+  seeds.push (point (x, y));
+  // phase 2, while we have seeds, if
+  // seed is empty, floodfill, else grow
+  while (seeds.size)
+    {
+      coroapi::cede_to_tick ();
+      point p = seeds.remove (rmg_rndm (seeds.size));
+      x = p.x;
+      y = p.y;
-      if (!maze [x][y])
+      if (!dist [x][y])
         {
-          // found first free space - picking the first one gives
-          // us a slight bias for tunnels, but usually you won't
-          // notice that in-game
-          seeds.push (point (x, y));
-          // phase 2, while we have seeds, if
-          // seed is empty, floodfill, else grow
-          while (seeds.size)
-            {
-              coroapi::cede_to_tick ();
-              point p = seeds.remove (rmg_rndm (seeds.size));
-              x = p.x;
-              y = p.y;
-              if (!maze [x][y])
-                {
-                  // found new isolated area, make tunnel?
+          // found new isolated area, make tunnel
-                  if (!dirty)
+          if (!dirty)
-                    push_flood_fill (maze, dist, seeds, x, y);
+            push_flood_fill (dist, seeds, x, y);
-                  make_tunnel (maze, dist, seeds, x, y, 255);
+          make_tunnel (dist, seeds, x, y, 255);
-                  if (dirty)
+          if (dirty)
-                    push_flood_fill (maze, dist, seeds, x, y);
+            push_flood_fill (dist, seeds, x, y);
-                }
-              else
-                {
-                  U8 d = U8 (dist [x][y]) + 1;
-                  if (x < maze.w - 1 && U8 (dist [x + 1][y]) > d)
-                    {
-                      dist [x + 1][y] = d;
-                      seeds.push (point (x + 1, y));
-                    }
-                  if (x > 0          && U8 (dist [x - 1][y]) > d)
-                    {
-                      dist [x - 1][y] = d;
-                      seeds.push (point (x - 1, y));
-                    }
-                  if (y < maze.h - 1 && U8 (dist [x][y + 1]) > d)
-                    {
-                      dist [x][y + 1] = d;
-                      seeds.push (point (x, y + 1));
-                    }
-                  if (y > 0          && U8 (dist [x][y - 1]) > d)
-                    {
-                      dist [x][y - 1] = d;
-                      seeds.push (point (x, y - 1));
-                    }
-                }
-            }
-          goto success;
         }
+      else
+        {
+          // nothing here, continue to expand
+          U8 d = U8 (dist [x][y]) + 1;
-success:
+          if (x < dist.w - 1) maybe_push (dist, seeds, x + 1, y, d);
+          if (x >          0) maybe_push (dist, seeds, x - 1, y, d);
+          if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d);
+          if (y >          0) maybe_push (dist, seeds, x, y - 1, d);
+        }
+    }
-  // we mark free but visited floors as 1, undo this here
+  // now copy the tunnels over
   for (int x = 0; x < maze.w; ++x)
     for (int y = 0; y < maze.h; ++y)
-      if (maze [x][y] == 1)
+      if (maze [x][y] == '#' && dist [x][y] == 1)
         maze [x][y] = 0;
 }
 void
-LayoutData::isolation_remover (bool dirty)
+Layout::isolation_remover (bool dirty)
 {
   ::isolation_remover (*this, dirty);
 }
 /////////////////////////////////////////////////////////////////////////////
 // inspired mostly by http://www.jimrandomh.org/misc/caves.txt
 void
-LayoutData::gen_cave (int subtype)
+Layout::gen_cave (int subtype)
 {
   switch (subtype)
     {
       // a rough cave
       case 0:
     Layout maze (40, 25);
     rmg_rndm.seed (time (0));
     for(int i=1;i<10;i)
       {
-        maze->gen_cave (3);
+        maze.fill_rand (97);
+        maze.border ();
+        maze.isolation_remover ();
-        maze->print ();
+        maze.print ();
       }
     exit (1);
   }
 } demo;

Diff Legend

-–
+Removed lines
-+
+Added lines
-<
+Changed lines
->
+Changed lines

Comparing deliantra/server/random_maps/layout.C (file contents): Revision 1.2 by root, Wed Jun 30 23:03:40 2010 UTC vs. Revision 1.3 by root, Thu Jul 1 01:22:44 2010 UTC

Diff Legend

Comparing deliantra/server/random_maps/layout.C (file contents):
Revision 1.2 by root, Wed Jun 30 23:03:40 2010 UTC vs.
Revision 1.3 by root, Thu Jul 1 01:22:44 2010 UTC