From 4253009d0db24eb91b3daee9459f59a4a18f6142 Mon Sep 17 00:00:00 2001 From: dshaligram Date: Wed, 11 Jul 2007 07:26:56 +0000 Subject: [1734352] Added checks in the dungeon builder to ensure vaults placed at the end of level generation do not isolate parts of the level that were not already isolated. This does not apply to weird level-types such as Labyrinths and the Abyss. Added level veto stats to -mapstat output. git-svn-id: https://crawl-ref.svn.sourceforge.net/svnroot/crawl-ref/trunk@1831 c06c8d41-db1a-0410-9941-cceddc491573 --- crawl-ref/source/debug.cc | 48 +++++++++++- crawl-ref/source/debug.h | 2 + crawl-ref/source/dungeon.cc | 179 ++++++++++++++++++++++++++++++++++++++++---- crawl-ref/source/dungeon.h | 2 +- 4 files changed, 214 insertions(+), 17 deletions(-) diff --git a/crawl-ref/source/debug.cc b/crawl-ref/source/debug.cc index 9bb8a37679..28e0754399 100644 --- a/crawl-ref/source/debug.cc +++ b/crawl-ref/source/debug.cc @@ -2124,21 +2124,38 @@ void debug_card() static std::map mapgen_try_count; static std::map mapgen_use_count; static std::map mapgen_level_mapcounts; +static std::map< level_id, std::pair > mapgen_map_builds; static std::map< level_id, std::set > mapgen_level_mapsused; static std::map mapgen_errors; static std::string mapgen_last_error; static int mg_levels_tried = 0, mg_levels_failed = 0; +static int mg_build_attempts = 0, mg_vetoes = 0; + +void mapgen_report_map_build_start() +{ + mg_build_attempts++; + mapgen_map_builds[level_id::current()].first++; +} + +void mapgen_report_map_veto() +{ + mg_vetoes++; + mapgen_map_builds[level_id::current()].second++; +} static bool mg_do_build_level(int niters) { mesclr(); - mprf("On %s (%d); %d levels, %d failed, %d errors%s, %d maps", + mprf("On %s (%d); %d g, %d fail, %d err%s, %d uniq, " + "%d try, %d (%.2lf%%) vetos", level_id::current().describe().c_str(), niters, mg_levels_tried, mg_levels_failed, mapgen_errors.size(), mapgen_last_error.empty()? "" : (" (" + mapgen_last_error + ")").c_str(), - mapgen_use_count.size()); + mapgen_use_count.size(), + mg_build_attempts, mg_vetoes, + mg_build_attempts? mg_vetoes * 100.0 / mg_build_attempts : 0.0); no_messages mx; for (int i = 0; i < niters; ++i) @@ -2262,6 +2279,33 @@ static void write_mapgen_stats() } } + if (mg_vetoes) + { + fprintf(outf, "\n\nMost vetoed levels:\n"); + std::multimap sortedvetos; + for (std::map< level_id, std::pair >::const_iterator + i = mapgen_map_builds.begin(); i != mapgen_map_builds.end(); + ++i) + { + if (!i->second.second) + continue; + + sortedvetos.insert( + std::pair( i->second.second, i->first )); + } + + int count = 0; + for (std::multimap::reverse_iterator + i = sortedvetos.rbegin(); i != sortedvetos.rend(); ++i) + { + const int vetoes = i->first; + const int tries = mapgen_map_builds[i->second].first; + fprintf(outf, "%3d) %s (%d of %d vetoed, %.2f%%)\n", + ++count, i->second.describe().c_str(), + vetoes, tries, vetoes * 100.0 / tries); + } + } + if (!unused_maps.empty()) { fprintf(outf, "\n\nUnused maps:\n\n"); diff --git a/crawl-ref/source/debug.h b/crawl-ref/source/debug.h index fe9efa0340..e597b8104a 100644 --- a/crawl-ref/source/debug.h +++ b/crawl-ref/source/debug.h @@ -158,6 +158,8 @@ class map_def; void mapgen_report_map_try(const map_def &map); void mapgen_report_map_use(const map_def &map); void mapgen_report_error(const map_def &map, const std::string &err); +void mapgen_report_map_build_start(); +void mapgen_report_map_veto(); #endif #endif diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc index 18cf95e210..533934abf5 100644 --- a/crawl-ref/source/dungeon.cc +++ b/crawl-ref/source/dungeon.cc @@ -29,6 +29,7 @@ #include #include #include +#include #include "AppHdr.h" #include "abyss.h" @@ -93,6 +94,7 @@ struct dist_feat // DUNGEON BUILDERS static void build_dungeon_level(int level_number, int level_type); +static void reset_level(); static bool valid_dungeon_level(int level_number, int level_type); static bool find_in_area(int sx, int sy, int ex, int ey, @@ -178,6 +180,7 @@ static void chequerboard(spec_room &sr, dungeon_feature_type target, dungeon_feature_type floor2); static void roguey_level(int level_number, spec_room &sr); static void morgue(spec_room &sr); +static void dgn_fill_zone(const coord_def &c, int zone); // SPECIAL ROOM BUILDERS static void special_room(int level_number, spec_room &sr); @@ -208,13 +211,16 @@ typedef std::list coord_list; ////////////////////////////////////////////////////////////////////////// // Static data -// Places where monsters should not be randomly generated. +// A mask of vaults and vault-specific flags. map_mask dgn_map_mask; static dgn_region_list vault_zones; static int vault_chance = 9; static std::vector level_vaults; static int minivault_chance = 3; static bool dgn_level_vetoed = false; +static bool use_random_maps = true; +static bool dgn_check_connectivity = false; +static int dgn_zones = 0; static void place_altars() { @@ -249,9 +255,26 @@ bool builder(int level_number, int level_type) int tries = 20; while (tries-- > 0) { +#ifdef DEBUG_DIAGNOSTICS + mapgen_report_map_build_start(); +#endif + dgn_level_vetoed = false; + + reset_level(); + + // If we're getting low on available retries, disable random vaults + // and minivaults (special levels will still be placed). + if (tries < 5) + use_random_maps = false; + build_dungeon_level(level_number, level_type); +#ifdef DEBUG_DIAGNOSTICS + if (dgn_level_vetoed) + mapgen_report_map_veto(); +#endif + if (!dgn_level_vetoed && valid_dungeon_level(level_number, level_type)) return (true); } @@ -266,6 +289,89 @@ bool builder(int level_number, int level_type) return (false); } +static inline bool dgn_grid_is_isolating(const dungeon_feature_type grid) +{ + // 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)); +} + +// Counts the number of mutually unreachable areas in the map, +// excluding isolated zones within vaults (we assume the vault author +// knows what she's doing). This is an easy way to check whether a map +// has isolated parts of the level that were not formerly isolated. +// +// All squares within vaults are treated as non-reachable, to simplify +// life, because vaults may change the level layout and isolate +// different areas without changing the number of isolated areas. +// Here's a before and after example of such a vault that would cause +// problems if we considered floor in the vault as non-isolating (the +// vault is represented as V for walls and o for floor squares in the +// vault). +// +// Before: +// +// xxxxx xxxxx +// x<..x x.2.x +// x.1.x xxxxx 3 isolated zones +// x>..x x.3.x +// xxxxx xxxxx +// +// After: +// +// xxxxx xxxxx +// x<1.x x.2.x +// VVVVVVVVVVoooV 3 isolated zones, but the isolated zones are different. +// x>3.x x...x +// xxxxx xxxxx +// +static int dgn_count_disconnected_zones() +{ + 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_map_mask[x][y]) + continue; + + if (dgn_grid_is_isolating(grd[x][y])) + continue; + + dgn_fill_zone(coord_def(x, y), ++nzones); + } + } + + return (nzones); +} + +static void dgn_fill_zone(const coord_def &c, int zone) +{ + // 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) + { + if (!xi && !yi) + continue; + + const coord_def cp(c.x + xi, c.y + yi); + if (travel_point_distance[cp.x][cp.y] + || dgn_map_mask(cp) + || dgn_grid_is_isolating(grd(cp))) + { + continue; + } + + dgn_fill_zone(cp, zone); + } + } +} + static void mask_vault(const vault_placement &place, unsigned mask) { for (int y = place.y + place.height - 1; y >= place.y; --y) @@ -345,6 +451,8 @@ static void reset_level() vault_zones.clear(); vault_chance = 9; minivault_chance = 3; + use_random_maps = true; + dgn_check_connectivity = false; // blank level with DNGN_ROCK_WALL make_box(0, 0, GXM - 1, GYM - 1, DNGN_ROCK_WALL, DNGN_ROCK_WALL); @@ -520,21 +628,43 @@ static void fixup_branch_stairs() } } +static void dgn_verify_connectivity(unsigned nvaults) +{ + // After placing vaults, make sure parts of the level have not been + // disconnected. + if (!dgn_level_vetoed && dgn_zones && nvaults != level_vaults.size()) + { + const int newzones = dgn_count_disconnected_zones(); + if (newzones > dgn_zones) + { + dgn_level_vetoed = true; +#ifdef DEBUG_DIAGNOSTICS + std::ostringstream vlist; + for (unsigned i = nvaults; i < level_vaults.size(); ++i) + { + if (i > nvaults) + vlist << ", "; + vlist << level_vaults[i].map.name; + } + mprf(MSGCH_DIAGNOSTICS, + "VETO: %s broken by [%s] (had %d zones, " + "now have %d zones.", + level_id::current().describe().c_str(), + vlist.str().c_str(), dgn_zones, newzones); +#endif + } + } +} + static void build_dungeon_level(int level_number, int level_type) { spec_room sr; - reset_level(); build_layout_skeleton(level_number, level_type, sr); if (you.level_type == LEVEL_LABYRINTH || dgn_level_vetoed) return; - // Try to place minivaults that really badly want to be placed. Still - // no guarantees, seeing this is a minivault. - if (!player_in_branch(BRANCH_SHOALS)) - place_special_minivaults(level_number, level_type); - // hook up the special room (if there is one, and it hasn't // been hooked up already in roguey_level()) if (sr.created && !sr.hooked_up) @@ -550,9 +680,6 @@ static void build_dungeon_level(int level_number, int level_type) else if (player_in_branch(BRANCH_SHOALS)) prepare_shoals( level_number ); - place_branch_entrances( level_number, level_type ); - place_extra_vaults(); - if (dgn_level_vetoed) return; @@ -561,13 +688,29 @@ static void build_dungeon_level(int level_number, int level_type) if (!player_in_branch( BRANCH_DIS ) && !player_in_branch( BRANCH_VAULTS )) hide_doors(); - if (!player_in_branch( BRANCH_ECUMENICAL_TEMPLE )) - place_traps(level_number); - // change pre-rock (105) to rock, and pre-floor (106) to floor 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(); + + // Any further vaults must make sure not to disrupt level layout. + dgn_check_connectivity = true; + + // Try to place minivaults that really badly want to be placed. Still + // no guarantees, seeing this is a minivault. + if (!player_in_branch(BRANCH_SHOALS)) + place_special_minivaults(level_number, level_type); + place_branch_entrances( level_number, level_type ); + place_extra_vaults(); + dgn_verify_connectivity(nvaults); + + if (dgn_level_vetoed) + return; + + if (!player_in_branch( BRANCH_ECUMENICAL_TEMPLE )) + place_traps(level_number); + // place items builder_items(level_number, level_type, num_items_wanted(level_number)); @@ -1194,7 +1337,7 @@ static void place_special_minivaults(int level_number, int level_type) return; std::set used; - if (minivault_chance && one_chance_in(minivault_chance)) + if (use_random_maps && minivault_chance && one_chance_in(minivault_chance)) { const int vault = random_map_in_depth(level_id::current(), true); if (vault != -1) @@ -1241,6 +1384,7 @@ static builder_rc_type builder_normal(int level_number, char level_type, // Can't have vaults on you.where_are_you != BRANCH_MAIN_DUNGEON levels if (vault == -1 && player_in_branch(BRANCH_MAIN_DUNGEON) + && use_random_maps && one_chance_in(vault_chance)) { vault = random_map_in_depth(level_id::current()); @@ -1561,6 +1705,7 @@ static void place_specific_stair(dungeon_feature_type stair, static void place_extra_vaults() { if (!player_in_branch(BRANCH_MAIN_DUNGEON) + && use_random_maps && vault_chance && one_chance_in(vault_chance)) { @@ -2661,6 +2806,9 @@ static bool build_minivaults(int level_number, int force_vault, acq_item_class[5] = OBJ_STAVES; acq_item_class[6] = OBJ_MISCELLANY; + if (dgn_check_connectivity && !dgn_zones) + dgn_zones = dgn_count_disconnected_zones(); + map_type vgrid; vault_placement place; vault_main(vgrid, place, force_vault); @@ -3074,6 +3222,9 @@ static bool build_vaults(int level_number, int force_vault, int rune_subst, acq_item_class[5] = OBJ_STAVES; acq_item_class[6] = OBJ_MISCELLANY; + if (dgn_check_connectivity && !dgn_zones) + dgn_zones = dgn_count_disconnected_zones(); + map_type vgrid; vault_placement place; std::vector &target_connections = place.exits; diff --git a/crawl-ref/source/dungeon.h b/crawl-ref/source/dungeon.h index 8912d1d252..f20025371c 100644 --- a/crawl-ref/source/dungeon.h +++ b/crawl-ref/source/dungeon.h @@ -311,7 +311,7 @@ bool flood_find::path_flood( return (false); } - if (!left_vault && vaults && !(*vaults)(dc)) + if (!left_vault && vaults && !(*vaults)[dc.x][dc.y]) left_vault = true; good_square(dc); -- cgit v1.2.3-54-g00ecf