From a75d591365f96c937b723259debc4381d17ac616 Mon Sep 17 00:00:00 2001
From: infiniplex <infiniplex@hotmail.com>
Date: Wed, 25 Jun 2014 20:48:17 -0600
Subject: [PATCH 1/4] Added options to join_the_dots LUA function

---
 crawl-ref/source/l_dgnbld.cc | 207 +++++++++++++++++++++++++++++++++++--------
 1 file changed, 168 insertions(+), 39 deletions(-)

diff --git a/crawl-ref/source/l_dgnbld.cc b/crawl-ref/source/l_dgnbld.cc
index 378c32c..7800914 100644
--- a/crawl-ref/source/l_dgnbld.cc
+++ b/crawl-ref/source/l_dgnbld.cc
@@ -344,6 +344,150 @@ static bool _wall_is_empty(map_lines &lines,
     return true;
 }
 
+// Only used for the join_the_dots command.
+struct join_the_dots_path
+{
+    vector<coord_def> cells;
+    int hit_vault_count;
+    int avoid_vault_count;
+};
+
+// This function calculates a possible path joining from to to
+//  and returns a data structure containing the path and the
+//  number of times it hit or almost hit an existing vault.
+static join_the_dots_path _calculate_join_the_dots_path (
+                           map_lines &lines,
+                           const coord_def& from, const coord_def& to,
+                           bool force_straight, bool allow_diagonals)
+{
+    join_the_dots_path path;
+    path.hit_vault_count = 0;
+    path.avoid_vault_count = 0;
+
+    coord_def at = from;
+    while (true) // loop breaks below
+    {
+        // 1. Handle this position
+
+        path.cells.push_back(at);
+        if (env.level_map_mask(at) & MMT_VAULT)
+            path.hit_vault_count++;
+
+        // check done after recording position
+        if (at == to)
+            break;  // exit loop
+
+        // 2. Identify good moves
+
+        // possible next positions
+        int x_move = (at.x < to.x) ? 1 : ((at.x > to.x) ? -1 : 0);
+        int y_move = (at.y < to.y) ? 1 : ((at.y > to.y) ? -1 : 0);
+
+        coord_def next_x  = coord_def(at.x + x_move, at.y);
+        coord_def next_y  = coord_def(at.x,          at.y + y_move);
+        coord_def next_xy = coord_def(at.x + x_move, at.y + y_move);
+
+        // moves that get you closer
+        bool good_x  = (x_move != 0);
+        bool good_y  = (y_move != 0);
+        bool good_xy = (x_move != 0) && (y_move != 0) && allow_diagonals;
+
+        // avoid vaults if possible
+        bool vault_x  = env.level_map_mask(next_x)  & MMT_VAULT;
+        bool vault_y  = env.level_map_mask(next_y)  & MMT_VAULT;
+        bool vault_xy = env.level_map_mask(next_xy) & MMT_VAULT;
+        if (   (!vault_x  && good_x)
+            || (!vault_y  && good_y)
+            || (!vault_xy && good_xy))
+        {
+            // if there is a good path the doesn't hit a vault,
+            //  disable the otherwise-good paths that do
+
+            if (vault_x)  path.avoid_vault_count++;
+            if (vault_y)  path.avoid_vault_count++;
+            if (vault_xy) path.avoid_vault_count++;
+
+            // There is no &&= operator because short-circut
+            //  evaluation can do strange and terrible things
+            //  when combined with function calls.
+            good_x  &= !vault_x;
+            good_y  &= !vault_y;
+            good_xy &= !vault_xy;
+        }
+        else
+        {
+            // there is no way to avoid vaults, so hitting one is OK
+            path.avoid_vault_count += 3;
+        }
+
+        // 3. Choose the next move
+        if (force_straight)
+        {
+            if (good_xy)
+                at = next_xy;
+            else if (good_x)
+                at = next_x;
+            else
+                at = next_y;
+        }
+        else
+        {
+            // allow irregular paths
+
+            // used for movement ratios; our goal is to make a
+            //  path approximately straight in any direction
+            int x_diff = abs(at.x - to.x);
+            int y_diff = abs(at.y - to.y);
+            int sum_diff = x_diff + y_diff;
+            int min_diff = (x_diff < y_diff) ? x_diff : y_diff;
+            int max_diff = sum_diff - min_diff;
+
+            // halve chance because a diagonal is worth 2 other moves
+            if (good_xy && (x_chance_in_y(min_diff, max_diff * 2)
+                            || (!good_x && !good_y)))
+            {
+                at = next_xy;
+            }
+            else if (good_x && (x_chance_in_y(x_diff, sum_diff) || !good_y))
+                at = next_x;
+            else
+                at = next_y;
+        }
+    }
+
+    // path is finished
+    return path;
+}
+
+// Draw the path previously calaculated for the
+//  join_the_dots command.
+static void _draw_join_the_dots_path (map_lines &lines,
+                                      const join_the_dots_path& path,
+                                      const char* passable,
+                                      int thickness, char fill)
+{
+    int delta_min = -thickness / 2;
+    int delta_max = delta_min + thickness;
+    unsigned int count = path.cells.size();
+    for (unsigned int i = 0; i < count; i++)
+    {
+        coord_def center = path.cells[i];
+        for(int dx = delta_min; dx < delta_max; dx++)
+            for(int dy = delta_min; dy < delta_max; dy++)
+            {
+                int x = center.x + dx;
+                int y = center.y + dy;
+
+                // we never change the border
+                if (x >= 1 && x < lines.width()  - 1 &&
+                    y >= 1 && y < lines.height() - 1 &&
+                    !strchr(passable, lines(x, y)))
+                {
+                    lines(x, y) = fill;
+                }
+            }
+    }
+}
 
 
 LUAFN(dgn_count_feature_in_box)
@@ -634,6 +778,9 @@ LUAFN(dgn_join_the_dots)
     TABLE_INT(ls, y2, -1);
     TABLE_STR(ls, passable, traversable_glyphs);
     TABLE_CHAR(ls, fill, '.');
+    TABLE_BOOL(ls, force_straight, false);
+    TABLE_BOOL(ls, allow_diagonals, false);
+    TABLE_INT(ls, thickness, 1);
 
     if (!_valid_coord(ls, lines, x1, y1))
         return 0;
@@ -646,45 +793,27 @@ LUAFN(dgn_join_the_dots)
     if (from == to)
         return 0;
 
-    coord_def at = from;
-    do
-    {
-        char glyph = lines(at);
-
-        if (!strchr(passable, glyph))
-            lines(at) = fill;
-
-        if (at == to)
-            break;
-
-        if (at.y == to.y || coinflip())
-        {
-            if (at.x < to.x)
-            {
-                at.x++;
-                continue;
-            }
-
-            if (at.x > to.x)
-            {
-                at.x--;
-                continue;
-            }
-        }
-
-        if (at.y > to.y)
-        {
-            at.y--;
-            continue;
-        }
-
-        if (at.y < to.y)
-        {
-            at.y++;
-            continue;
-        }
-    }
-    while (true);
+    // calculate possible paths
+    join_the_dots_path path1 =
+        _calculate_join_the_dots_path(lines, from, to,
+                                      force_straight, allow_diagonals);
+    join_the_dots_path path2 =
+        _calculate_join_the_dots_path(lines, to, from,
+                                      force_straight, allow_diagonals);
+
+    // add better path
+    if (path1.hit_vault_count < path2.hit_vault_count)
+        _draw_join_the_dots_path(lines, path1, passable, thickness, fill);
+    else if (path1.hit_vault_count > path2.hit_vault_count)
+        _draw_join_the_dots_path(lines, path2, passable, thickness, fill);
+    else if (path1.avoid_vault_count < path2.avoid_vault_count)
+        _draw_join_the_dots_path(lines, path1, passable, thickness, fill);
+    else if (path1.avoid_vault_count > path2.avoid_vault_count)
+        _draw_join_the_dots_path(lines, path2, passable, thickness, fill);
+    else if (coinflip())
+        _draw_join_the_dots_path(lines, path1, passable, thickness, fill);
+    else
+        _draw_join_the_dots_path(lines, path2, passable, thickness, fill);
 
     return 0;
 }
-- 
1.8.1.2

From 3a0a35d37184828b26976aca228cd73bfafd82a8 Mon Sep 17 00:00:00 2001
From: infiniplex <infiniplex@hotmail.com>
Date: Fri, 27 Jun 2014 11:57:35 -0600
Subject: [PATCH 2/4] Updated layout_misc_corridors for improved join_the_dots

---
 crawl-ref/source/dat/des/builder/layout.des | 33 ++++++++++++++++++++++++-----
 1 file changed, 28 insertions(+), 5 deletions(-)

diff --git a/crawl-ref/source/dat/des/builder/layout.des b/crawl-ref/source/dat/des/builder/layout.des
index 26fd799..eb4b690 100644
--- a/crawl-ref/source/dat/des/builder/layout.des
+++ b/crawl-ref/source/dat/des/builder/layout.des
@@ -759,21 +759,42 @@ ENDMAP
 # Previously named "layout_misc".
 #
 # TODO: Wider paths for Zot, then add at weight 20.
-# TODO: Straight paths for Crypt, Zot.
 #
 NAME:   layout_misc_corridors
 DEPTH:  Lair, Snake, Crypt
 WEIGHT: 5 (Lair), 20 (Snake), 20 (Crypt)
 ORIENT: encompass
 TAGS:   overwritable layout allow_dup unrand layout_type_corridors
+TAGS:   no_rotate no_vmirror no_hmirror
 {{
     function random_coord(max_x, max_y)
-        return crawl.random2(max_x - 20) + 10,
-               crawl.random2(max_y - 20) + 10
+        local x = crawl.random2(max_x - 16) + 8
+        local y = crawl.random2(max_y - 16) + 8
+        local sanity = 0
+        while (dgn.in_vault(x, y) and sanity < 10) do
+            x = crawl.random2(max_x - 16) + 8
+            y = crawl.random2(max_y - 16) + 8
+            sanity = sanity + 1
+        end
+        return x, y
     end
 
     local gxm, gym = dgn.max_bounds()
+
     local corridors = crawl.random_range(15, 25)
+    local force_straight = false
+    if you.branch() == "Crypt" then
+        force_straight = true
+    end
+
+    local area_fraction = 1;
+    local x_min, x_max, y_min, y_max = primary_vault_dimensions()
+    if x_min ~= nil then
+        local vault_area = (x_max - x_min + 1) * (y_max - y_min + 1)
+        local total_area = (gxm - 2) * (gym - 2)
+        area_fraction = 1 - (vault_area / total_area)
+        corridors = math.ceil(corridors * area_fraction)
+    end
 
     extend_map { width = gxm, height = gym, fill = 'x' }
 
@@ -783,13 +804,15 @@ TAGS:   overwritable layout allow_dup unrand layout_type_corridors
     while corridors > 0 do
         new_x, new_y = random_coord(gxm, gym)
 
-        join_the_dots { x1 = x, y1 = y, x2 = new_x, y2 = new_y }
+        join_the_dots { x1 = x, y1 = y, x2 = new_x, y2 = new_y,
+                        force_straight = force_straight }
 
         x, y = new_x, new_y
         corridors = corridors - 1
     end
 
-    spotty_map { boxy = true, iterations = 100 }
+    local iterations = math.floor(crawl.random_range(75, 125) * area_fraction)
+    spotty_map { boxy = true, iterations = iterations }
 
     theme.level_material(_G)
 }}
-- 
1.8.1.2

From 9efcc46f346bc8f11d1fa682c6c428a1a3ea6726 Mon Sep 17 00:00:00 2001
From: infiniplex <infiniplex@hotmail.com>
Date: Fri, 27 Jun 2014 12:02:55 -0600
Subject: [PATCH 3/4] Added Zot version to layout_misc_corridors

---
 crawl-ref/source/dat/des/builder/layout.des | 21 ++++++++++++++++-----
 1 file changed, 16 insertions(+), 5 deletions(-)

diff --git a/crawl-ref/source/dat/des/builder/layout.des b/crawl-ref/source/dat/des/builder/layout.des
index eb4b690..fc43420 100644
--- a/crawl-ref/source/dat/des/builder/layout.des
+++ b/crawl-ref/source/dat/des/builder/layout.des
@@ -758,11 +758,9 @@ ENDMAP
 # This replaces dungeon.cc:_plan_5().
 # Previously named "layout_misc".
 #
-# TODO: Wider paths for Zot, then add at weight 20.
-#
 NAME:   layout_misc_corridors
-DEPTH:  Lair, Snake, Crypt
-WEIGHT: 5 (Lair), 20 (Snake), 20 (Crypt)
+DEPTH:  Lair, Snake, Crypt, Zot
+WEIGHT: 20, 5 (Lair)
 ORIENT: encompass
 TAGS:   overwritable layout allow_dup unrand layout_type_corridors
 TAGS:   no_rotate no_vmirror no_hmirror
@@ -783,8 +781,18 @@ TAGS:   no_rotate no_vmirror no_hmirror
 
     local corridors = crawl.random_range(15, 25)
     local force_straight = false
+    local allow_diagonals = false
+    local max_thickness = 1
     if you.branch() == "Crypt" then
         force_straight = true
+    elseif you.branch() == "Zot" then
+        corridors = crawl.random_range(10, 16)
+        force_straight = true
+        allow_diagonals = crawl.coinflip(3)
+        max_thickness = 3
+    end
+    if you.at_branch_bottom() then
+        corridors = math.floor(corridors * (1.2 + crawl.random_real() * 0.3))
     end
 
     local area_fraction = 1;
@@ -804,8 +812,11 @@ TAGS:   no_rotate no_vmirror no_hmirror
     while corridors > 0 do
         new_x, new_y = random_coord(gxm, gym)
 
+        local thickness = crawl.random_range(1, max_thickness)
         join_the_dots { x1 = x, y1 = y, x2 = new_x, y2 = new_y,
-                        force_straight = force_straight }
+                        force_straight = force_straight,
+                        allow_diagonals = allow_diagonals,
+                        thickness = thickness }
 
         x, y = new_x, new_y
         corridors = corridors - 1
-- 
1.8.1.2

From 62fcf1dc1bf0f6fabe3c319f5852d6ebe9827c8b Mon Sep 17 00:00:00 2001
From: infiniplex <infiniplex@hotmail.com>
Date: Fri, 27 Jun 2014 12:14:35 -0600
Subject: [PATCH 4/4] Add Elf variant to layout_rooms

---
 crawl-ref/source/dat/des/builder/layout.des | 22 ++++++++++++++--------
 1 file changed, 14 insertions(+), 8 deletions(-)

diff --git a/crawl-ref/source/dat/des/builder/layout.des b/crawl-ref/source/dat/des/builder/layout.des
index fc43420..ee7677e 100644
--- a/crawl-ref/source/dat/des/builder/layout.des
+++ b/crawl-ref/source/dat/des/builder/layout.des
@@ -430,24 +430,28 @@ ENDMAP
 #
 # This replaces dungeon.cc:_plan_3().
 #
-# TODO: Make Elf version and add at weight 10.
+# TODO: Differentiate Elf version more
+#       Improve room generation
+#       Make random_room_point work correctly for new room types
 #
 NAME:   layout_rooms
-DEPTH:  D, Snake, Crypt, Pan
-WEIGHT: 15 (D), 15 (Snake), 10 (Crypt), 10 (Pan)
+DEPTH:  D, Elf, Snake, Crypt, Pan
+WEIGHT: 15 (D), 10 (Elf), 15 (Snake), 10 (Crypt), 10 (Pan)
 ORIENT: encompass
 TAGS:   overwritable layout allow_dup unrand layout_type_rooms
 {{
+    local is_elf_branch = you.branch() == "Elf"
+
     function draw_room(room)
         local room_type = 0
-        if you.branch() == "Elf" then
+        if is_elf_branch then
+           room_type = 1
+        else
            if crawl.coinflip() then
-             room_type = 1
+             room_type = 0
            else
              room_type = 2
            end
-        else
-           room_type = crawl.random2(3)
         end
         if room_type == 0 then
             -- rectangular
@@ -512,7 +516,9 @@ TAGS:   overwritable layout allow_dup unrand layout_type_rooms
             x1 = start.x,
             y1 = start.y,
             x2 = finish.x,
-            y2 = finish.y})
+            y2 = finish.y,
+            force_straight  = is_elf_branch,
+            allow_diagonals = is_elf_branch})
     end
 
     local gxm, gym = dgn.max_bounds()
-- 
1.8.1.2