From b486dd5a448fbae163fe116e21e9f265bda6b257 Mon Sep 17 00:00:00 2001
From: infiniplex <infiniplex@hotmail.com>
Date: Mon, 16 Jun 2014 15:40:56 -0600
Subject: [PATCH] Improved LUA zonify functionality

---
 crawl-ref/source/dat/dlua/layout/zonify.lua | 84 ++++++++++++++++++++++-------
 1 file changed, 66 insertions(+), 18 deletions(-)

diff --git a/crawl-ref/source/dat/dlua/layout/zonify.lua b/crawl-ref/source/dat/dlua/layout/zonify.lua
index 9c8797b..4e70a61 100644
--- a/crawl-ref/source/dat/dlua/layout/zonify.lua
+++ b/crawl-ref/source/dat/dlua/layout/zonify.lua
@@ -66,30 +66,65 @@ function zonify.walk(x,y,zonemap,fgrid,fcell,fgroup,from,zone)
 end
 
 -- Fills all the zones except the largest num_to_keep
-function zonify.fill_smallest_zones(zonemap,num_to_keep,fgroup,ffill)
+function zonify.fill_smallest_zones(zonemap, num_to_keep, fgroup, ffill, min_zone_size)
 
   if num_to_keep == nil then num_to_keep = 1 end
+  if min_zone_size == nil then min_zone_size = 1 end
+
+  local NO_SUCH_ZONE = -1
+
+  -- we now keep a sorted list of the largest zones so that we
+  --  can handle num_to_keep > 1 cases correctly
+  local largest = {}
+  for n = 1, num_to_keep do
+    largest[n] = {}
+    largest[n].zone = NO_SUCH_ZONE
+    largest[n].size = -999999
+  end
 
-  local largest = nil
-  local count = nil
   for name,group in pairs(zonemap) do
     if type(fgroup) == "function" and fgroup(group) or name==fgroup then
       for i,zone in ipairs(group) do
-        zcount = #(zone.cells)
-        if count == nil or zcount > count then
-          count = zcount
-          largest = zone
+        zsize = #(zone.cells)
+        for n = num_to_keep, 1, -1 do
+          if zsize > min_zone_size and zsize > largest[n].size then
+            -- demote this zone to one position smaller
+            if n < num_to_keep then
+              largest[n+1].zone = largest[n].zone
+              largest[n+1].size = largest[n].size
+            end
+            -- add the new zone here
+            largest[n].zone = zone
+            largest[n].size = zsize
+          else
+            break
+          end
         end
       end
     end
   end
 
-  if largest == nil then return false end
+  -- don't try to fill more zones than we have
+  for n = 1, num_to_keep do
+    if largest[n].zone == nil then
+      num_to_keep = n
+      break
+    end
+  end
+  if num_to_keep <= 0 then
+    return false
+  end
 
   for name,group in pairs(zonemap) do
     if type(fgroup) == "function" and fgroup(group) or name==fgroup then
       for i,zone in ipairs(group) do
-        if zone ~= largest then
+        local replace = true
+        for n = 1, num_to_keep do
+          if zone == largest[n].zone then
+            replace = false
+          end
+        end
+        if replace then
           for c,cell in ipairs(zone.cells) do
             ffill(cell.x,cell.y,cell)
           end
@@ -97,7 +132,6 @@ function zonify.fill_smallest_zones(zonemap,num_to_keep,fgroup,ffill)
       end
     end
   end
-
 end
 
 -- Zonifies the current map based on solidity
@@ -122,15 +156,20 @@ function zonify.map_map(e)
 
 end
 
-function zonify.map_fill_zones(e, num_to_keep, glyph)
+function zonify.map_fill_zones(e, num_to_keep, glyph, min_zone_size)
+  if num_to_keep == nil then num_to_keep = 1 end
   if glyph == nil then glyph = 'x' end
+  if min_zone_size == nil then min_zone_size = 1 end
 
   local zonemap = zonify.map_map(e)
-  zonify.fill_smallest_zones(zonemap,1,"floor",function(x,y,cell) e.mapgrd[x][y] = glyph end)
+  zonify.fill_smallest_zones(zonemap, num_to_keep, "floor",
+                             function(x,y,cell) e.mapgrd[x][y] = glyph end, min_zone_size)
 end
 
-function zonify.map_fill_lava_zones(e, num_to_keep, glyph)
+function zonify.map_fill_lava_zones(e, num_to_keep, glyph, min_zone_size)
+  if num_to_keep == nil then num_to_keep = 1 end
   if glyph == nil then glyph = 'x' end
+  if min_zone_size == nil then min_zone_size = 1 end
 
   local wall = "wxcvbtg"
 
@@ -145,7 +184,8 @@ function zonify.map_fill_lava_zones(e, num_to_keep, glyph)
       return string.find(wall,val.glyph,1,true) and "wall" or "floor"
     end
   )
-  zonify.fill_smallest_zones(zonemap,1,"floor",function(x,y,cell) e.mapgrd[x][y] = glyph end)
+  zonify.fill_smallest_zones(zonemap, num_to_keep, "floor",
+                             function(x,y,cell) e.mapgrd[x][y] = glyph end, min_zone_size)
 end
 
 -- Zonifies the current dungeon grid
@@ -173,18 +213,25 @@ function zonify.grid_group_feature(val)
   return val.passable and "floor" or "wall"
 end
 
-function zonify.grid_fill_zones(num_to_keep,feature)
+function zonify.grid_fill_zones(num_to_keep, feature, min_zone_size)
+  if num_to_keep == nil then num_to_keep = 1 end
   if feature == nil then feature = 'rock_wall' end
+  if min_zone_size == nil then min_zone_size = 1 end
+
   local zonemap = zonify.grid_map()
-  zonify.fill_smallest_zones(zonemap,1,"floor",function(x,y,cell) dgn.grid(x,y,feature) end)
+  zonify.fill_smallest_zones(zonemap, num_to_keep, "floor",
+                             function(x,y,cell) dgn.grid(x,y,feature) end, min_zone_size)
 end
 
 -- This is a little brutish but for some layouts (e.g. swamp) a different pass
 -- is needed to fill in deep water zones and stop flyers/swimmers getting trapped.
 -- TODO: Need to simplify into a single pass that understands connectivity issues
 -- between different zone groups and can handle everything more elegantly.
-function zonify.grid_fill_water_zones(num_to_keep,feature)
+function zonify.grid_fill_water_zones(num_to_keep, feature, min_zone_size)
+  if num_to_keep == nil then num_to_keep = 1 end
   if feature == nil then feature = 'rock_wall' end
+  if min_zone_size == nil then min_zone_size = 1 end
+
   local gxm,gym = dgn.max_bounds()
   local zonemap = zonify.map(
     { x1 = 1, y1 = 1, x2 = gxm-2, y2 = gym-2 },
@@ -195,5 +242,6 @@ function zonify.grid_fill_water_zones(num_to_keep,feature)
       if val.vault then return "vault" end
       return (val.passable or val.feat == "deep_water") and "floor" or "wall"
     end)
-  zonify.fill_smallest_zones(zonemap,1,"floor",function(x,y,cell) dgn.grid(x,y,feature) end)
+  zonify.fill_smallest_zones(zonemap, num_to_keep,"floor",
+                             function(x,y,cell) dgn.grid(x,y,feature) end, min_zone_size)
 end
-- 
1.8.1.2

: require("dlua/layout/zonify.lua")

##############################################################
# layout_diamond_mine
#
# A cavelike mine based off diamond shapes.
#
# Places around primary vaults.
#
# There is a grid of potential rooms across the map.  We
#  repeatedly select one at random (weighter towards the center)
#  and add it.  This gives much better control over map size
#  than just giving each room a chance of appearing.
#
NAME:   layout_diamond_mine
DEPTH:  Orc
WEIGHT: 5
ORIENT: encompass
TAGS:   overwritable layout allow_dup unrand layout_type_narrow_caves
TAGS:   unrand no_rotate no_hmirror no_vmirror
{{
  -- information for rooms of differant sizes

  local GLPYH_BY_RADIUS =
    { [4] = { [0] = "c", "-", ".", ".", ":" },
      [5] = { [0] = "c", "-", ".", ".", ":", ":" },
      [6] = { [0] = "c", "c", "-", ".", ".", ":", ":" },
      [7] = { [0] = "c", "c", "-", "-", ".", ".", ":", ":" },
      [8] = { [0] = "c", "c", "-", "-", ".", ".", ":", ":", ":" },
      [9] = { [0] = "c", "c", "-", "-", ".", ".", ".", ":", ":", ":" },
     [10] = { [0] = "c", "c", "-", "-", "-", ".", ".", ".", ":", ":", ":" },
     [11] = { [0] = "c", "c", "-", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":" },
     [12] = { [0] = "c", "c", "c", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":", ":" },
     [13] = { [0] = "c", "c", "c", "-", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":", ":" },
     [14] = { [0] = "c", "c", "c", "-", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":", ":", ":" },
     [15] = { [0] = "c", "c", "c", "c", "-", "-", "-",
                    ".", ".", ".", ".", ":", ":", ":", ":", ":" } }

  -- these are based on where the last "." glyph is in the array above
  local SPACING_BY_RADIUS =
    { [4] =  6,
      [5] =  6,
      [6] =  8,
      [7] =  8,
      [8] = 10,
      [9] = 12,
     [10] = 12,
     [11] = 14,
     [12] = 16,
     [13] = 16,
     [14] = 16,
     [15] = 18 }

  -- these are based on how many rooms fit
  local ROOMS_ACROSS_BY_RADIUS =
    { [4] = 10,
      [5] = 10,
      [6] =  7,
      [7] =  7,
      [8] =  5,
      [9] =  5,
     [10] =  4,
     [11] =  4,
     [12] =  3,
     [13] =  3,
     [14] =  3,
     [15] =  3 }

  -- which glyphs replace which when placing rooms
  local GLYPH_PRIORITY =
   { ["c"] = 0, ["-"] = 1, ["."] = 2, [":"] = 3, ["x"] = 4 }

  -- this function draws a diamond shape with the appropriate
  --  glyphs at different distances from the center
  function draw_diamond (center_x, center_y, radius)
    for dx = -radius, radius do
      for dy = -radius, radius do
        local x = center_x + dx
        local y = center_y + dy
        local abs_sum = math.abs(dx) + math.abs(dy)
        if (abs_sum <= radius) then
          local new_glyph = GLPYH_BY_RADIUS[radius][abs_sum]
          if (GLYPH_PRIORITY[new_glyph] <
              GLYPH_PRIORITY[mapgrd[x][y]]) then
            mapgrd[x][y] = new_glyph
          end
        end
      end
    end
  end

  -- choose parameters for layout

  -- valid room sizes 4 - 15, but middle ones look better
  local room_radius = math.floor(8.5 + you.depth_fraction() * 3
                                     + crawl.random_real() * 4
                                     - crawl.random_real() * 4)
  local ROOM_SPACING = SPACING_BY_RADIUS[room_radius]
  local ROOMS_ACROSS = ROOMS_ACROSS_BY_RADIUS[room_radius]

  local gxm, gym = dgn.max_bounds()
  extend_map{width = gxm, height = gym, fill = 'x'}

  local CENTER_X = gxm/2
  local CENTER_Y = gym/2
  local ROOMS_FROM_CENTER = (ROOMS_ACROSS - 1) / 2

  local MIN_ZONE_SIZE = 20  -- for connectivity

  -- room frequency and distribution
  local room_chance_center = 0.8
  local room_chance_at_1   = 0.5
  local room_chance_decrease = room_chance_center - room_chance_at_1
  local rooms_placed_fraction = 0.3 + crawl.random_real() * 0.1
  if you.at_branch_bottom() then
    rooms_placed_fraction = 0.4 + crawl.random_real() * 0.2
  end

  -- Variables for keeping track of how many rooms we have
  --  already added and which ones.
  --  -> We also keep track of the number of attempts so that we
  --     don't get an infinite loop if there is no room to place
  --     the rooms around the primary vault.
  local ROOM_COUNT_MAX = ROOMS_ACROSS * ROOMS_ACROSS
  local rooms_to_place = math.floor(ROOM_COUNT_MAX * rooms_placed_fraction)
  local rooms_placed_so_far = 0
  local sanity = 0
  local sanity_max = ROOM_COUNT_MAX * 10
  local room_already_placed = {}
  for x = 0, ROOMS_ACROSS - 1 do
    room_already_placed[x] = {}
    for y = 0, ROOMS_ACROSS - 1 do
      room_already_placed[x][y] = false
    end
  end

  -- place the rooms
  while (rooms_placed_so_far < rooms_to_place and sanity < sanity_max) do
    x = crawl.random_range(0, ROOMS_ACROSS - 1)
    y = crawl.random_range(0, ROOMS_ACROSS - 1)
    sanity = sanity + 1

    if (not room_already_placed[x][y]) then
      -- We are using a distribution with equal probability
      --  lines that form a superellipse (n=4).  This should
      --  yield a large map than a simple circle, but not look
      --  as regular as a square distribution.
      local x2 = x / ROOMS_FROM_CENTER - 1
      local y2 = y / ROOMS_FROM_CENTER - 1
      local distance_fraction = math.sqrt(x2*x2*x2*x2 + y2*y2*y2*y2)

      -- Probabilities of room placement fall of quadraticly
      local falloff_factor = distance_fraction * distance_fraction
      local probability = room_chance_center -
                          room_chance_decrease * falloff_factor
      if (crawl.random_real() < probability) then
        -- the position will have a .5 if the number of rooms is even
        local room_x = CENTER_X +
                       math.floor((x - ROOMS_FROM_CENTER) * ROOM_SPACING)
        local room_y = CENTER_Y +
                       math.floor((y - ROOMS_FROM_CENTER) * ROOM_SPACING)
        if (not find_in_area {x1 = room_x - room_radius,
                              y1 = room_y - room_radius,
                              x2 = room_x + room_radius,
                              y2 = room_y + room_radius,
                              find = "", find_vault = true } ) then
          draw_diamond(room_x, room_y, room_radius)
          rooms_placed_so_far = rooms_placed_so_far + 1
          room_already_placed[x][y] = true
        end
      end
    end
  end

  -- crazy substitutions and effects to produce randomness
  subst("c=x")
  subst("-=:")
  smear_map { onto = ":", smear = "x", boxy = true,
              iterations = crawl.random_range(300, 500) }
  subst(":=.")
  if (crawl.coinflip()) then
    spotty_map { replace = "x", fill = ".", boxy = false,
                 iterations = crawl.random_range(50, 100) }
  end

  -- clean up the map
  --  -> the branch bottom must have only one open bubble
  --  -> remove diconnected areas
  --  -> ensure each bubble has a down stairs
  --  -> largest bubble should have the branch exit

  if you.at_branch_bottom() then
    zonify.map_fill_zones(_G, 1, 'x')
  else
    zonify.map_fill_zones(_G, 3, 'x', MIN_ZONE_SIZE)
    zonify.map_fill_zones(_G, 2, 'v', MIN_ZONE_SIZE)
    zonify.map_fill_zones(_G, 1, 'b', MIN_ZONE_SIZE)
    nsubst(". = 1:} / *:.")
    if you.depth() == 0 then
      nsubst(". = 1:{ / *:.")
    end
    nsubst("b = 1:) / *:.")
    nsubst("v = 1:] / *:.")
    shuffle("})]")
  end
}}
# Enforce minimum floor size - this is important
validate {{
  return count_feature_in_box { feat="." } > 600
}}
MAP
ENDMAP