The level-builder now enforces the constraint that every contiguous region on a level must include at least one stair (ekiM). This guarantee does not apply to areas inside vaults (the builder assumes vault-designers are sane) and does not apply to certain branches (Swamp, Shoals, the branches of Hell), or the non-Dungeon areas (Abyss, Pan, Bazaars).

git-svn-id: https://crawl-ref.svn.sourceforge.net/svnroot/crawl-ref/trunk@4169 c06c8d41-db1a-0410-9941-cceddc491573

9 files changed, 307 insertions, 83 deletions

diff --git a/crawl-ref/source/branch.cc b/crawl-ref/source/branch.cc
index 728ce416ff..9f906d4411 100644
--- a/crawl-ref/source/branch.cc
+++ b/crawl-ref/source/branch.cc
@@ -163,7 +163,7 @@ Branch branches[] = {
       NULL, NULL, NULL, NULL,
       5, 'L', false, false },
 
-    { BRANCH_SWAMP, BRANCH_LAIR, 5, 3, 0, 0,
+    { BRANCH_SWAMP, BRANCH_LAIR, 5, 3, BFLAG_ISLANDED, 0,
       DNGN_ENTER_SWAMP, DNGN_RETURN_FROM_SWAMP,
       "Swamp", "the Swamp", "Swamp",
       NULL,
@@ -172,7 +172,7 @@ Branch branches[] = {
       NULL, NULL, NULL, NULL,
       0, 'S', false, true },
     
-    { BRANCH_SHOALS, BRANCH_LAIR, 5, 4, 0, 0,
+    { BRANCH_SHOALS, BRANCH_LAIR, 5, 4, BFLAG_ISLANDED, 0,
       DNGN_ENTER_SHOALS, DNGN_RETURN_FROM_SHOALS,
       "Shoals", "the Shoals", "Shoal",
       NULL,
@@ -254,7 +254,7 @@ Branch branches[] = {
       NULL, NULL, NULL, NULL,
       0, 'U', false, false },
 
-    { BRANCH_DIS, BRANCH_VESTIBULE_OF_HELL, 7, -1, 0, 0,
+    { BRANCH_DIS, BRANCH_VESTIBULE_OF_HELL, 7, -1, BFLAG_ISLANDED, 0,
       DNGN_ENTER_DIS, NUM_FEATURES, // sentinel
       "Dis", "the Iron City of Dis", "Dis",
       NULL,
@@ -263,7 +263,7 @@ Branch branches[] = {
       NULL, NULL, NULL, NULL,
       0, 'I', true, true },
 
-    { BRANCH_GEHENNA, BRANCH_VESTIBULE_OF_HELL, 7, -1, 0, 0,
+    { BRANCH_GEHENNA, BRANCH_VESTIBULE_OF_HELL, 7, -1, BFLAG_ISLANDED, 0,
       DNGN_ENTER_GEHENNA, NUM_FEATURES, // sentinel
       "Gehenna", "Gehenna", "Geh",
       NULL,
@@ -272,7 +272,7 @@ Branch branches[] = {
       NULL, NULL, NULL, NULL,
       0, 'N', true, true },
 
-    { BRANCH_COCYTUS, BRANCH_VESTIBULE_OF_HELL, 7, -1, 0, 0,
+    { BRANCH_COCYTUS, BRANCH_VESTIBULE_OF_HELL, 7, -1, BFLAG_ISLANDED, 0,
       DNGN_ENTER_COCYTUS, NUM_FEATURES, // sentinel
       "Cocytus", "Cocytus", "Coc",
       NULL,
@@ -281,7 +281,7 @@ Branch branches[] = {
       NULL, NULL, NULL, NULL,
       0, 'X', true, true },
 
-    { BRANCH_TARTARUS, BRANCH_VESTIBULE_OF_HELL, 7, -1, 0, 0,
+    { BRANCH_TARTARUS, BRANCH_VESTIBULE_OF_HELL, 7, -1, BFLAG_ISLANDED, 0,
       DNGN_ENTER_TARTARUS, NUM_FEATURES, // sentinel
       "Tartarus", "Tartarus", "Tar",
       NULL,
diff --git a/crawl-ref/source/branch.h b/crawl-ref/source/branch.h
index 3427537cfc..08abfaaa14 100644
--- a/crawl-ref/source/branch.h
+++ b/crawl-ref/source/branch.h
@@ -21,7 +21,9 @@ enum branch_flag_type
     BFLAG_NO_TELE_CONTROL = (1 << 0), // Teleport control not allowed.
     BFLAG_NOT_MAPPABLE    = (1 << 1), // Branch levels not mappable.
     BFLAG_NO_MAGIC_MAP    = (1 << 2), // Branch levels can't be magic mapped.
-    BFLAG_HAS_ORB         = (1 << 3)  // Orb is on the floor in this branch
+    BFLAG_HAS_ORB         = (1 << 3), // Orb is on the floor in this branch
+
+    BFLAG_ISLANDED        = (1 << 4)  // May have isolated zones with no stairs.
 };
 
 struct Branch
diff --git a/crawl-ref/source/chardump.cc b/crawl-ref/source/chardump.cc
index 8e26e59668..cc2f9f5671 100644
--- a/crawl-ref/source/chardump.cc
+++ b/crawl-ref/source/chardump.cc
@@ -1133,7 +1133,7 @@ static std::string morgue_directory()
     return (dir);
 }
 
-static void dump_map(const char* fname)
+void dump_map(FILE *fp)
 {
     // Duplicate the screenshot() trick.
     FixedVector<unsigned, NUM_DCHAR_TYPES> char_table_bk;
@@ -1142,14 +1142,10 @@ static void dump_map(const char* fname)
     init_char_table(CSET_ASCII);
     init_feature_table();
 
-    FILE* fp = fopen(fname, "w");
-    if ( !fp )
-        return;
-
     int min_x = GXM-1, max_x = 0, min_y = GYM-1, max_y = 0;
 
-    for (int i = 0; i < GXM; i++)
-        for (int j = 0; j < GYM; j++)
+    for (int i = X_BOUND_1; i <= X_BOUND_2; i++)
+        for (int j = Y_BOUND_1; j <= Y_BOUND_2; j++)
             if (env.map[i][j].known())
             {
                 if ( i > max_x )
@@ -1168,13 +1164,23 @@ static void dump_map(const char* fname)
             fputc( env.map[x][y].glyph(), fp );
         fputc('\n', fp);
     }
-    fclose(fp);
 
     // Restore char and feature tables
     Options.char_table = char_table_bk;
     init_feature_table();
 }
 
+void dump_map(const char* fname)
+{
+    FILE* fp = fopen(fname, "w");
+    if ( !fp )
+        return;
+
+    dump_map(fp);
+
+    fclose(fp);    
+}
+
 static bool write_dump(
         const std::string &fname,
         dump_params &par)
diff --git a/crawl-ref/source/chardump.h b/crawl-ref/source/chardump.h
index f6870ebc8c..311b934a99 100644
--- a/crawl-ref/source/chardump.h
+++ b/crawl-ref/source/chardump.h
@@ -16,6 +16,7 @@
 #define CHARDUMP_H
 
 #include <string>
+#include <cstdio>
 
 enum item_origin_dump_selector
 {
@@ -36,6 +37,8 @@ bool dump_char(const std::string &fname,
                bool show_prices,
                bool full_id = false,
                const scorefile_entry *se = NULL);
+void dump_map(const char* fname);
+void dump_map(FILE *fp);
 void resists_screen();
 void display_notes();
 std::string munge_description(const std::string &inStr);
diff --git a/crawl-ref/source/dat/large.des b/crawl-ref/source/dat/large.des
index 47919d6009..517ba01d53 100644
--- a/crawl-ref/source/dat/large.des
+++ b/crawl-ref/source/dat/large.des
@@ -291,8 +291,8 @@ MONS: nothing
 SUBST: *:*$, |=|.
 : end
 : if you.absdepth() > 24 then
-MONS: red draconian/green draconian/yellow draconian/pale draconian/black draconian/grey draconian/purple draconian
-MONS: grey draconian monk/pale draconian knight/green draconian annihilator/purple draconian knight
+MONS: red draconian/green draconian/yellow draconian/pale draconian/black draconian/purple draconian
+MONS: pale draconian knight/green draconian annihilator/purple draconian knight
 MONS: red draconian scorcher/white draconian zealot/yellow draconian caller/black draconian shifter
 MONS: lindwurm/death drake/swamp drake, plant/weight:1 oklob plant
 SUBST: w:wl
diff --git a/crawl-ref/source/debug.cc b/crawl-ref/source/debug.cc
index deda8d5eca..50ded9bba9 100644
--- a/crawl-ref/source/debug.cc
+++ b/crawl-ref/source/debug.cc
@@ -38,6 +38,7 @@
 
 #include "beam.h"
 #include "branch.h"
+#include "chardump.h"
 #include "cio.h"
 #include "decks.h"
 #include "delay.h"
@@ -3737,6 +3738,71 @@ void mapgen_report_map_veto()
     mapgen_map_builds[level_id::current()].second++;    
 }
 
+static map_mask mg_MapMask;
+
+static bool _mg_region_flood(const coord_def &c, int region, bool flag)
+{
+    bool found_exit = false;
+    
+    mg_MapMask(c) = region;
+
+    if (flag)
+    {
+        env.map(c).flags = 0;
+        set_terrain_mapped(c.x, c.y);
+    }
+
+    const dungeon_feature_type ft = grd(c);
+    if (is_travelable_stair(ft))
+        found_exit = true;
+
+    for (int yi = -1; yi <= 1; ++yi)
+        for (int xi = -1; xi <= 1; ++xi)
+        {
+            if (!xi && !yi)
+                continue;
+            
+            coord_def ci = c + coord_def(xi, yi);
+            if (!in_bounds(ci) || mg_MapMask(ci) || !dgn_square_is_passable(ci))
+                continue;
+
+            if (_mg_region_flood(ci, region, flag))
+                found_exit = true;
+        }
+    return (found_exit);
+}
+
+static bool _mg_is_disconnected_level()
+{
+    // Don't care about non-Dungeon levels.
+    if (you.level_type != LEVEL_DUNGEON
+        || (branches[you.where_are_you].branch_flags & BFLAG_ISLANDED))
+        return (false);
+    
+    std::vector<coord_def> region_seeds;
+
+    mg_MapMask.init(0);
+
+    coord_def c;
+    int region = 0;
+    int good_regions = 0;
+    for (c.y = 0; c.y < GYM; ++c.y)
+        for (c.x = 0; c.x < GXM; ++c.x)
+            if (!mg_MapMask(c) && dgn_square_is_passable(c))
+            {
+                if (_mg_region_flood(c, ++region, false))
+                    ++good_regions;
+                else
+                    region_seeds.push_back(c);
+            }
+
+    mg_MapMask.init(0);
+    for (int i = 0, size = region_seeds.size(); i < size; ++i)
+        _mg_region_flood(region_seeds[i], 1, true);
+    
+    return (good_regions < region);
+}
+
 static bool mg_do_build_level(int niters)
 {
     if (niters > 1)
@@ -3761,7 +3827,63 @@ static bool mg_do_build_level(int niters)
 
         ++mg_levels_tried;
         if (!builder(you.your_level, you.level_type))
+        {
             ++mg_levels_failed;
+            continue;
+        }
+
+        for (int y = 0; y < GYM; ++y)
+            for (int x = 0; x < GXM; ++x)
+            {
+                switch (grd[x][y])
+                {
+                case DNGN_SECRET_DOOR:
+                    grd[x][y] = DNGN_CLOSED_DOOR;
+                    break;
+                default:
+                    break;
+                }
+            }
+
+        {
+            unwind_bool wiz(you.wizard, true);
+            magic_mapping(1000, 100, true, true);
+        }
+        if (_mg_is_disconnected_level())
+        {
+            extern std::vector<vault_placement> Level_Vaults;
+            std::string vaults;
+            for (int j = 0, size = Level_Vaults.size(); j < size; ++j)
+            {
+                if (j && !vaults.empty())
+                    vaults += ", ";
+                vaults += Level_Vaults[j].map.name;
+            }
+
+            if (!vaults.empty())
+                vaults = " (" + vaults + ")";
+
+            extern std::string dgn_Build_Method;
+            mprf(MSGCH_WARN,
+                 "Bad (disconnected) level on %s%s",
+                 level_id::current().describe().c_str(),
+                 vaults.c_str());
+            FILE *fp = fopen("map.dump", "w");
+            fprintf(fp, "Bad (disconnected) level (%s) on %s%s.\n\n",
+                    dgn_Build_Method.c_str(),
+                    level_id::current().describe().c_str(),
+                    vaults.c_str());
+
+            // Mapping would only have mapped squares that the player can
+            // reach - explicitly map the full level.
+            for (int y = 0; y < GYM; ++y)
+                for (int x = 0; x < GXM; ++x)
+                    set_envmap_obj(x, y, grd[x][y]);
+            
+            dump_map(fp);
+            
+            return (false);
+        }
     }
     return (true);
 }
@@ -3787,7 +3909,7 @@ static std::vector<level_id> mg_dungeon_places()
     return (places);
 }
 
-static void mg_build_dungeon()
+static bool mg_build_dungeon()
 {
     const std::vector<level_id> places = mg_dungeon_places();
 
@@ -3800,8 +3922,9 @@ static void mg_build_dungeon()
         if (you.level_type == LEVEL_PORTAL_VAULT)
             you.level_type_name = "bazaar";
         if (!mg_do_build_level(1))
-            return;
+            return (false);
     }
+    return (true);
 }
 
 static void mg_build_levels(int niters)
@@ -3824,7 +3947,8 @@ static void mg_build_levels(int niters)
         
         you.uniq_map_tags.clear();
         you.uniq_map_names.clear();
-        mg_build_dungeon();
+        if (!mg_build_dungeon())
+            break;
     }
 }
 
diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc
index ea4e30f654..cd938d2d8b 100644
--- a/crawl-ref/source/dungeon.cc
+++ b/crawl-ref/source/dungeon.cc
@@ -248,8 +248,9 @@ static void _dgn_set_floor_colours();
 // Static data
 
 // A mask of vaults and vault-specific flags.
-map_mask dgn_map_mask;
-std::vector<vault_placement> level_vaults;
+map_mask dgn_Map_Mask;
+std::vector<vault_placement> Level_Vaults;
+std::string dgn_Build_Method;
 
 static int vault_chance = 9;
 static int minivault_chance = 3;
@@ -344,10 +345,10 @@ bool builder(int level_number, int level_type)
 
 void level_welcome_messages()
 {
-    for (int i = 0, size = level_vaults.size(); i < size; ++i)
+    for (int i = 0, size = Level_Vaults.size(); i < size; ++i)
     {
         const std::vector<std::string> &msgs
-            = level_vaults[i].map.welcome_messages;
+            = Level_Vaults[i].map.welcome_messages;
         for (int j = 0, msize = msgs.size(); j < msize; ++j)
             mpr(msgs[j].c_str());
     }
@@ -355,8 +356,8 @@ void level_welcome_messages()
 
 void level_clear_vault_memory()
 {
-    level_vaults.clear();
-    dgn_map_mask.init(0);
+    Level_Vaults.clear();
+    dgn_Map_Mask.init(0);
 }
 
 static void _dgn_load_colour_grid()
@@ -475,42 +476,68 @@ static void _dgn_register_vault(const map_def &map)
     }
 }
 
-static inline bool _dgn_grid_is_passable(dungeon_feature_type grid)
+bool dgn_square_is_passable(const coord_def &c)
 {
-    // Rock wall check is superfluous, but is the most common case.
-    return !(grid == DNGN_ROCK_WALL
-             || (grid_is_solid(grid) && grid != DNGN_CLOSED_DOOR
-                 && grid != DNGN_SECRET_DOOR));
-}
-
-static inline bool _dgn_square_is_passable(const coord_def &c)
-{
-    return (!(dgn_map_mask(c) & MMT_OPAQUE) && _dgn_grid_is_passable(grd(c)));
+    return (!(dgn_Map_Mask(c) & MMT_OPAQUE) &&
+            is_travelsafe_square(c.x, c.y, false, true));
 }
 
 static inline void _dgn_point_record_stub(const coord_def &) { }
 
 template <class point_record>
-static void _dgn_fill_zone( const coord_def &c, int zone, point_record &prec,
-                            bool (*passable)(const coord_def &)
-                                = _dgn_square_is_passable)
-{
+static bool _dgn_fill_zone(
+    const coord_def &start, int zone,
+    point_record &record_point,
+    bool (*passable)(const coord_def &) = dgn_square_is_passable,
+    bool (*iswanted)(const coord_def &) = NULL)
+{
+    bool ret = false;
+    std::list<coord_def> points[2];
+    int cur = 0;
+    
     // No bounds checks, assuming the level has at least one layer of
     // rock border.
-    travel_point_distance[c.x][c.y] = zone;
-    for (int yi = -1; yi <= 1; ++yi)
-        for (int xi = -1; xi <= 1; ++xi)
+
+    for (points[cur].push_back(start); !points[cur].empty(); )
+    {
+        for (std::list<coord_def>::const_iterator i = points[cur].begin();
+             i != points[cur].end(); ++i)
         {
-            if (!xi && !yi)
-                continue;
+            const coord_def &c(*i);
 
-            const coord_def cp(c.x + xi, c.y + yi);
-            if (travel_point_distance[cp.x][cp.y] || !passable(cp))
-                continue;
+            travel_point_distance[c.x][c.y] = zone;
 
-            prec(cp);
-            _dgn_fill_zone(cp, zone, prec);
+            if (iswanted && iswanted(c))
+                ret = true;
+            
+            for (int yi = -1; yi <= 1; ++yi)
+            {
+                for (int xi = -1; xi <= 1; ++xi)
+                {
+                    if (!xi && !yi)
+                        continue;
+                
+                    const coord_def cp(c.x + xi, c.y + yi);
+                    if (!map_bounds(cp)
+                        || travel_point_distance[cp.x][cp.y] || !passable(cp))
+                        continue;
+
+                    travel_point_distance[cp.x][cp.y] = zone;
+                    record_point(cp);
+                    points[!cur].push_back(cp);
+                }
+            }
         }
+
+        points[cur].clear();
+        cur = !cur;
+    }
+    return (ret);    
+}
+
+static bool _is_exit_stair(const coord_def &c)
+{
+    return is_travelable_stair(grd(c));
 }
 
 // Counts the number of mutually unreachable areas in the map,
@@ -542,20 +569,33 @@ static void _dgn_fill_zone( const coord_def &c, int zone, point_record &prec,
 //   x>3.x    x...x
 //   xxxxx    xxxxx
 //
-static int _dgn_count_disconnected_zones()
+// If count_stairless is true, returns the number of regions that have no
+// stairs in them.
+//
+static int _dgn_count_disconnected_zones(bool choose_stairless)
 {
     memset(travel_point_distance, 0, sizeof(travel_distance_grid_t));
     int nzones = 0;
     for (int y = 0; y < GYM; ++y)
         for (int x = 0; x < GXM; ++x)
         {
-            if (travel_point_distance[x][y]
-                || !_dgn_square_is_passable(coord_def(x, y)))
+            if (!map_bounds(x, y)
+                || travel_point_distance[x][y]
+                || !dgn_square_is_passable(coord_def(x, y)))
             {
                 continue;
             }
 
-            _dgn_fill_zone(coord_def(x, y), ++nzones, _dgn_point_record_stub);
+            bool found_exit_stair =
+                _dgn_fill_zone(coord_def(x, y), ++nzones,
+                               _dgn_point_record_stub,
+                               dgn_square_is_passable,
+                               choose_stairless? _is_exit_stair : NULL);
+
+            // If we want only stairless zones, screen out zones that did
+            // have stairs.
+            if (choose_stairless && found_exit_stair)
+                --nzones;            
         }
 
     return (nzones);
@@ -589,7 +629,7 @@ static void _mask_vault(const vault_placement &place, unsigned mask)
         for (int x = place.pos.x + place.size.x - 1; x >= place.pos.x; --x)
         {
             if (place.map.in_map(coord_def(x - place.pos.x, y - place.pos.y)))
-                dgn_map_mask[x][y] |= mask;
+                dgn_Map_Mask[x][y] |= mask;
         }
 }
 
@@ -620,8 +660,8 @@ static void _register_place(const vault_placement &place)
 
                 if (spec != NULL)
                 {
-                    dgn_map_mask[x][y] |= (short)spec->map_mask.flags_set;
-                    dgn_map_mask[x][y] &= ~((short)spec->map_mask.flags_unset);
+                    dgn_Map_Mask[x][y] |= (short)spec->map_mask.flags_set;
+                    dgn_Map_Mask[x][y] &= ~((short)spec->map_mask.flags_unset);
                 }
             }
     
@@ -667,7 +707,7 @@ static bool _has_connected_downstairs_from(const coord_def &c)
     ff.add_feat(DNGN_STONE_STAIRS_DOWN_III);
     ff.add_feat(DNGN_ESCAPE_HATCH_DOWN);
 
-    coord_def where = ff.find_first_from(c, dgn_map_mask);
+    coord_def where = ff.find_first_from(c, dgn_Map_Mask);
     return (where.x || !ff.did_leave_vault());
 }
 
@@ -690,6 +730,7 @@ static bool _valid_dungeon_level(int level_number, int level_type)
 
 static void _reset_level()
 {
+    dgn_Build_Method.clear();
     level_clear_vault_memory();
     dgn_colour_grid.reset(NULL);
     
@@ -971,7 +1012,7 @@ static void _fixup_duplicate_stairs()
                     grd(stair_list[s1]) = DNGN_FLOOR;
 
                     coord_def where = ff.find_first_from(stair_list[s1],
-                        dgn_map_mask);
+                        dgn_Map_Mask);
                     if (where.x)
                     {
                         grd(stair_list[s2]) = replace;
@@ -1019,19 +1060,22 @@ static void _fixup_duplicate_stairs()
 
 static void _dgn_verify_connectivity(unsigned nvaults)
 {
+    if (dgn_level_vetoed)
+        return;
+
     // After placing vaults, make sure parts of the level have not been
     // disconnected.
-    if (!dgn_level_vetoed && dgn_zones && nvaults != level_vaults.size())
+    if (dgn_zones && nvaults != Level_Vaults.size())
     {
-        const int newzones = _dgn_count_disconnected_zones();
+        const int newzones = _dgn_count_disconnected_zones(false);
 
 #ifdef DEBUG_DIAGNOSTICS
         std::ostringstream vlist;
-        for (unsigned i = nvaults; i < level_vaults.size(); ++i)
+        for (unsigned i = nvaults; i < Level_Vaults.size(); ++i)
         {
             if (i > nvaults)
                 vlist << ", ";
-            vlist << level_vaults[i].map.name;
+            vlist << Level_Vaults[i].map.name;
         }
         mprf(MSGCH_DIAGNOSTICS, "Dungeon has %d zones after placing %s.",
              newzones, vlist.str().c_str());
@@ -1046,8 +1090,23 @@ static void _dgn_verify_connectivity(unsigned nvaults)
                  level_id::current().describe().c_str(),
                  vlist.str().c_str(), dgn_zones, newzones);
 #endif
+            return;
         }
-    }    
+    }
+
+    // Also check for isolated regions that have no stairs.
+    if (you.level_type == LEVEL_DUNGEON
+        && !(branches[you.where_are_you].branch_flags & BFLAG_ISLANDED)
+        && _dgn_count_disconnected_zones(true) > 0)
+    {
+        dgn_level_vetoed = true;
+#ifdef DEBUG_DIAGNOSTICS
+        mprf(MSGCH_DIAGNOSTICS,
+             "VETO: %s has isolated areas with no stairs.",
+             level_id::current().describe().c_str());
+#endif
+        return;
+    }
 }
 
 static void _build_dungeon_level(int level_number, int level_type)
@@ -1090,7 +1149,7 @@ static void _build_dungeon_level(int level_number, int level_type)
     _replace_area( 0,0,GXM-1,GYM-1, DNGN_BUILDER_SPECIAL_WALL, DNGN_ROCK_WALL );
     _replace_area( 0,0,GXM-1,GYM-1, DNGN_BUILDER_SPECIAL_FLOOR, DNGN_FLOOR );
 
-    const unsigned nvaults = level_vaults.size();
+    const unsigned nvaults = Level_Vaults.size();
 
     // Any further vaults must make sure not to disrupt level layout.
     dgn_check_connectivity = true;
@@ -1101,6 +1160,13 @@ static void _build_dungeon_level(int level_number, int level_type)
         _place_minivaults();
     _place_branch_entrances( level_number, level_type );
     _place_extra_vaults();
+
+    // place shops, if appropriate. This must be protected by the connectivity
+    // check.
+    if ( level_type == LEVEL_DUNGEON && your_branch().has_shops )
+        _place_shops(level_number);
+
+    // any vault-placement activity must happen before this check.
     _dgn_verify_connectivity(nvaults);
     
     if (dgn_level_vetoed)
@@ -1115,10 +1181,6 @@ static void _build_dungeon_level(int level_number, int level_type)
     // place monsters
     _builder_monsters(level_number, level_type, _num_mons_wanted(level_type));
 
-    // place shops, if appropriate
-    if ( level_type == LEVEL_DUNGEON && your_branch().has_shops )
-        _place_shops(level_number);
-
     _fixup_walls();
     _fixup_branch_stairs();
 
@@ -1806,7 +1868,7 @@ static void _portal_vault_level(int level_number)
         _plan_main(level_number, 0);
         _place_minivaults(level_name, 1, 1, true);
 
-        if (level_vaults.empty())
+        if (Level_Vaults.empty())
         {
             mprf(MSGCH_WARN, "No maps or tags named '%s'.",
                  level_name);
@@ -3380,7 +3442,7 @@ static bool _safe_minivault_place(int v1x, int v1y,
             if (lines[vy - v1y][vx - v1x] == ' ')
                 continue;
 
-            if (dgn_map_mask[vx][vy])
+            if (dgn_Map_Mask[vx][vy])
                 return (false);
 
             const dungeon_feature_type dfeat = grd[vx][vy];
@@ -3457,7 +3519,7 @@ static bool _build_minivaults(int level_number, int force_vault,
     acq_item_class[6] = OBJ_MISCELLANY;
 
     if (dgn_check_connectivity && !dgn_zones)
-        dgn_zones = _dgn_count_disconnected_zones();
+        dgn_zones = _dgn_count_disconnected_zones(false);
     
     map_type vgrid;
     vault_placement place;
@@ -3477,7 +3539,7 @@ static bool _build_minivaults(int level_number, int force_vault,
 
     place.pos = coord_def(v1x, v1y);
 
-    level_vaults.push_back(place);
+    Level_Vaults.push_back(place);
 
 #ifdef DEBUG_DIAGNOSTICS
     if (crawl_state.map_stat_gen)
@@ -3556,7 +3618,7 @@ static void _build_rooms(const dgn_region_list &excluded,
                 random_range(MAPGEN_BORDER,
                              GYM - MAPGEN_BORDER - 1 - myroom.size.y));
         }
-        while (myroom.overlaps(excluded, dgn_map_mask) && overlap_tries-- > 0);
+        while (myroom.overlaps(excluded, dgn_Map_Mask) && overlap_tries-- > 0);
 
         if (overlap_tries < 0)
             continue;
@@ -3963,7 +4025,7 @@ bool dgn_place_map(int map, bool generating_level, bool clobber,
     // Activate any markers within the map.
     if (did_map && !generating_level)
     {
-        const vault_placement &vp = level_vaults[level_vaults.size() - 1];
+        const vault_placement &vp = Level_Vaults[Level_Vaults.size() - 1];
         for (int y = vp.pos.y; y < vp.pos.y + vp.size.y; ++y)
             for (int x = vp.pos.x; x < vp.pos.x + vp.size.x; ++x)
             {
@@ -4001,10 +4063,11 @@ static bool _build_secondary_vault(int level_number, int vault,
                                    bool clobber, bool no_exits,
                                    const coord_def &where)
 {
+    dgn_zones = _dgn_count_disconnected_zones(false);
     if (_build_vaults(level_number, vault, rune_subst, true, true,
                       generating_level, clobber, no_exits, where))
     {
-        const vault_placement &vp = level_vaults[ level_vaults.size() - 1 ];
+        const vault_placement &vp = Level_Vaults[ Level_Vaults.size() - 1 ];
         _connect_vault(vp);
 
         return (true);
@@ -4033,7 +4096,7 @@ static bool _build_vaults(int level_number, int force_vault, int rune_subst,
     acq_item_class[6] = OBJ_MISCELLANY;
 
     if (dgn_check_connectivity && !dgn_zones)
-        dgn_zones = _dgn_count_disconnected_zones();
+        dgn_zones = _dgn_count_disconnected_zones(false);
     
     map_type vgrid;
     vault_placement place;
@@ -4092,7 +4155,7 @@ static bool _build_vaults(int level_number, int force_vault, int rune_subst,
 
     // Must do this only after target_connections is finalised, or the vault
     // exits will not be correctly set.
-    level_vaults.push_back(place);
+    Level_Vaults.push_back(place);
 
 #ifdef DEBUG_DIAGNOSTICS
     if (crawl_state.map_stat_gen)
@@ -4793,7 +4856,7 @@ static void _replace_area( int sx, int sy, int ex, int ey,
 // With apologies to Metallica.
 bool unforbidden(const coord_def &c, unsigned mask)
 {
-    return (!mask || !(dgn_map_mask(c) & mask));
+    return (!mask || !(dgn_Map_Mask(c) & mask));
 }
 
 struct coord_comparator
@@ -5451,6 +5514,8 @@ static object_class_type _item_in_shop(unsigned char shop_type)
 
 static void _spotty_level(bool seeded, int iterations, bool boxy)
 {
+    dgn_Build_Method = "spotty_level";
+    
     // assumes starting with a level full of rock walls (1)
     int i, j, k, l;
 
@@ -5543,6 +5608,8 @@ static void _spotty_level(bool seeded, int iterations, bool boxy)
 
 static void _bigger_room()
 {
+    dgn_Build_Method = "bigger_room";
+    
     unsigned char i, j;
 
     for (i = 10; i < (GXM - 10); i++)
@@ -5576,6 +5643,8 @@ static void _bigger_room()
 // various plan_xxx functions
 static void _plan_main(int level_number, int force_plan)
 {
+    dgn_Build_Method = "plan_main";
+    
     // possible values for do_stairs:
     //  0 - stairs already done
     //  1 - stairs already done, do spotty
@@ -5620,6 +5689,8 @@ static void _plan_main(int level_number, int force_plan)
 
 static char _plan_1()
 {
+    dgn_Build_Method = "plan_1";
+    
     int temp_rand = 0;          // probability determination {dlb}
 
     unsigned char width = (10 - random2(7));    // value range of [4,10] {dlb}
@@ -5688,6 +5759,8 @@ static char _plan_1()
 // just a cross:
 static char _plan_2()
 {
+    dgn_Build_Method = "plan_2";
+    
     char width2 = (5 - random2(5));     // value range of [1,5] {dlb}
 
     _replace_area(10, (35 - width2), (GXM - 10), (35 + width2),
@@ -5700,7 +5773,8 @@ static char _plan_2()
 
 static char _plan_3()
 {
-
+    dgn_Build_Method = "plan_3";
+    
     /* Draws a room, then another and links them together, then another and etc
        Of course, this can easily end up looking just like a make_trail level.
      */
@@ -5791,6 +5865,8 @@ static char _plan_3()
 static char _plan_4(char forbid_x1, char forbid_y1, char forbid_x2,
                     char forbid_y2, dungeon_feature_type force_wall)
 {
+    dgn_Build_Method = "plan_4";
+    
     // a more chaotic version of city level
     int temp_rand;              // req'd for probability checking
 
@@ -5894,6 +5970,8 @@ static char _plan_4(char forbid_x1, char forbid_y1, char forbid_x2,
 
 static char _plan_5()
 {
+    dgn_Build_Method = "plan_5";
+    
     unsigned char imax = 5 + random2(20);       // value range of [5,24] {dlb}
 
     for (unsigned char i = 0; i < imax; i++)
@@ -5912,6 +5990,8 @@ static char _plan_5()
 
 static char _plan_6(int level_number)
 {
+    dgn_Build_Method = "plan_6";
+    
     spec_room sr;
 
     // circle of standing stones (well, kind of)
@@ -5966,6 +6046,8 @@ static char _plan_6(int level_number)
 static bool _octa_room(spec_room &sr, int oblique_max,
                        dungeon_feature_type type_floor)
 {
+    dgn_Build_Method = "octa_room";
+    
     int x,y;
 
     // hack - avoid lava in the crypt {gdl}
@@ -6281,7 +6363,7 @@ static void _labyrinth_level(int level_number)
     }
     else
     {
-        const vault_placement &rplace = *(level_vaults.end() - 1);
+        const vault_placement &rplace = *(Level_Vaults.end() - 1);
         if (rplace.map.has_tag("generate_loot"))
         {
             for (int y = rplace.pos.y;
diff --git a/crawl-ref/source/dungeon.h b/crawl-ref/source/dungeon.h
index 7edc1acf49..d5da281228 100644
--- a/crawl-ref/source/dungeon.h
+++ b/crawl-ref/source/dungeon.h
@@ -55,7 +55,7 @@ const int MAKE_GOOD_ITEM = 351;
 typedef char map_type[MAP_SIDE + 1][MAP_SIDE + 1];
 typedef FixedArray<unsigned short, GXM, GYM> map_mask;
 
-extern map_mask dgn_map_mask;
+extern map_mask dgn_Map_Mask;
 
 // Map mask constants.
 
@@ -334,4 +334,11 @@ bool unset_level_flags(unsigned long flags, bool silent = false);
 void dgn_set_lt_callback(std::string level_type_name,
                          std::string callback_name);
 
+// Returns true if the given square is okay for use by any character,
+// but always false for squares in non-transparent vaults. This
+// function returns sane results only immediately after dungeon generation
+// (specifically, saving and restoring a game discards information on the
+// vaults used in the current level).
+bool dgn_square_is_passable(const coord_def &c);
+
 #endif
diff --git a/crawl-ref/source/maps.cc b/crawl-ref/source/maps.cc
index 7e4b2a95ea..05e691ae48 100644
--- a/crawl-ref/source/maps.cc
+++ b/crawl-ref/source/maps.cc
@@ -178,7 +178,7 @@ static bool bad_map_place(const map_def &map,
             if (lines[y - sy][x - sx] == ' ')
                 continue;
 
-            if (dgn_map_mask[x][y])
+            if (dgn_Map_Mask[x][y])
                 return (true);
 
             if (igrd[x][y] != NON_ITEM || mgrd[x][y] != NON_MONSTER)