text: /**
   * @file
   * @brief Misc abyss specific functions.
  **/
  
  #include "AppHdr.h"
  
  #include "abyss.h"
  
  #include <algorithm>
  #include <cmath>
  #include <cstdlib>
  #include <queue>
  
  #include "act-iter.h"
  #include "areas.h"
  #include "bloodspatter.h"
  #include "branch.h"
  #include "cloud.h"
  #include "colour.h"
  #include "coordit.h"
  #include "dbg-scan.h"
  #include "dbg-util.h"
  #include "delay.h"
  #include "dgn-overview.h"
  #include "dgn-proclayouts.h"
  #include "tile-env.h"
  #include "files.h"
  #include "god-companions.h" // hep stuff
  #include "god-passive.h" // passive_t::slow_abyss
  #include "hiscores.h"
  #include "item-prop.h"
  #include "item-status-flag-type.h"
  #include "items.h"
  #include "libutil.h"
  #include "mapmark.h"
  #include "maps.h"
  #include "message.h"
  #include "mon-cast.h"
  #include "mon-death.h"
  #include "mon-pathfind.h"
  #include "mon-pick.h"
  #include "mon-place.h"
  #include "mon-transit.h"
  #include "notes.h"
  #include "output.h" // redraw_screens
  #include "religion.h"
  #include "spl-clouds.h" // big_cloud
  #include "stash.h"
  #include "state.h"
  #include "stairs.h"
  #include "stringutil.h"
  #include "terrain.h"
  #include "rltiles/tiledef-dngn.h"
  #include "tileview.h"
  #include "timed-effects.h"
  #include "traps.h"
  #include "travel.h"
  #include "view.h"
  #include "xom.h"
  
  const coord_def ABYSS_CENTRE(GXM / 2, GYM / 2);
  
  static const int ABYSSAL_RUNE_MAX_ROLL = 200;
  
  abyss_state abyssal_state;
  
  static ProceduralLayout *abyssLayout = nullptr, *levelLayout = nullptr;
  
  typedef priority_queue<ProceduralSample, vector<ProceduralSample>, ProceduralSamplePQCompare> sample_queue;
  
  static sample_queue abyss_sample_queue;
  static vector<dungeon_feature_type> abyssal_features;
  static list<monster*> displaced_monsters;
  
  static void abyss_area_shift();
  static void _push_items();
  static void _push_displaced_monster(monster* mon);
  
  // If not_seen is true, don't place the feature where it can be seen from
  // the centre. Returns the chosen location, or INVALID_COORD if it
  // could not be placed.
  static coord_def _place_feature_near(const coord_def &centre,
                                       int radius,
                                       dungeon_feature_type candidate,
                                       dungeon_feature_type replacement,
                                       int tries, bool not_seen = false)
  {
      coord_def cp = INVALID_COORD;
      for (int i = 0; i < tries; ++i)
      {
          coord_def offset;
          offset.x = random_range(-radius, radius);
          offset.y = random_range(-radius, radius);
          cp = centre + offset;
  
          if (cp == centre || !in_bounds(cp))
              continue;
  
          if (not_seen && cell_see_cell_nocache(cp, centre))
              continue;
  
          if (env.grid(cp) == candidate)
          {
              dprf(DIAG_ABYSS, "Placing %s at (%d,%d)",
                   dungeon_feature_name(replacement),
                   cp.x, cp.y);
              env.grid(cp) = replacement;
              return cp;
          }
      }
      return INVALID_COORD;
  }
  
  // Returns a feature suitable for use in the proto-Abyss level.
  static dungeon_feature_type _abyss_proto_feature()
  {
      return random_choose_weighted(3000, DNGN_FLOOR,
                                     600, DNGN_ROCK_WALL,
                                     300, DNGN_STONE_WALL,
                                     100, DNGN_METAL_WALL,
                                       1, DNGN_CLOSED_DOOR);
  }
  
  static void _write_abyssal_features()
  {
      if (abyssal_features.empty())
          return;
  
      dprf(DIAG_ABYSS, "Writing a mock-up of old level.");
      ASSERT((int)abyssal_features.size() == sqr(2 * LOS_RADIUS + 1));
      const int scalar = 0xFF;
      int index = 0;
      for (int x = -LOS_RADIUS; x <= LOS_RADIUS; x++)
      {
          for (int y = -LOS_RADIUS; y <= LOS_RADIUS; y++)
          {
              coord_def p(x, y);
              const int dist = p.rdist();
              p += ABYSS_CENTRE;
  
              int chance = pow(0.98, dist * dist) * scalar;
              if (!map_masked(p, MMT_VAULT))
              {
                  if (dist < 2 || x_chance_in_y(chance, scalar))
                  {
                      if (abyssal_features[index] != DNGN_UNSEEN)
                      {
                          env.grid(p) = abyssal_features[index];
                          env.level_map_mask(p) = MMT_VAULT;
                          if (cell_is_solid(p))
                              delete_cloud(p);
                          if (monster* mon = monster_at(p))
                              _push_displaced_monster(mon);
                      }
                  }
                  else
                  {
                      //Entombing the player is lame.
                      env.grid(p) = DNGN_FLOOR;
                  }
              }
  
              ++index;
          }
      }
  
      _push_items();
      abyssal_features.clear();
  }
  
  // Returns the roll to use to check if we want to create an abyssal rune.
  static int _abyssal_rune_roll()
  {
      if (you.runes[RUNE_ABYSSAL] || you.depth < ABYSSAL_RUNE_MIN_LEVEL)
          return -1;
      const bool god_favoured = have_passive(passive_t::attract_abyssal_rune);
  
      const double depth = you.depth + god_favoured;
  
      return (int) pow(100.0, depth/(1 + brdepth[BRANCH_ABYSS]));
  }
  
  static void _abyss_fixup_vault(const vault_placement *vp)
  {
      for (vault_place_iterator vi(*vp); vi; ++vi)
      {
          const coord_def p(*vi);
          const dungeon_feature_type feat(env.grid(p));
          if (feat_is_stair(feat)
              && feat != DNGN_EXIT_ABYSS
              && feat != DNGN_ABYSSAL_STAIR
              && !feat_is_portal_entrance(feat))
          {
              env.grid(p) = DNGN_FLOOR;
          }
  
          tile_init_flavour(p);
      }
  }
  
  static bool _abyss_place_map(const map_def *mdef)
  {
      // This is to prevent the player position from being updated by vaults
      // until after everything is done.
      unwind_bool gen(crawl_state.generating_level, true);
  
      try
      {
          if (dgn_safe_place_map(mdef, true, false, INVALID_COORD))
          {
              _abyss_fixup_vault(env.level_vaults.back().get());
              return true;
          }
      }
      catch (dgn_veto_exception &e)
      {
          dprf(DIAG_ABYSS, "Abyss map placement vetoed: %s", e.what());
      }
      return false;
  }
  
  static bool _abyss_place_vault_tagged(const map_bitmask &abyss_genlevel_mask,
                                        const string &tag)
  {
      const map_def *map = random_map_for_tag(tag, true, true, MB_FALSE);
      if (map)
      {
          unwind_vault_placement_mask vaultmask(&abyss_genlevel_mask);
          return _abyss_place_map(map);
      }
      return false;
  }
  
  static void _abyss_postvault_fixup()
  {
      fixup_misplaced_items();
      link_items();
      dgn_make_transporters_from_markers();
      env.markers.activate_all();
  }
  
  static bool _abyss_place_rune_vault(const map_bitmask &abyss_genlevel_mask)
  {
      // Make sure we're not about to link bad items.
      debug_item_scan();
  
      bool result = false;
      int tries = 10;
      do
      {
          result = _abyss_place_vault_tagged(abyss_genlevel_mask, "abyss_rune");
      }
      while (!result && --tries);
  
      // Make sure the rune is linked.
      // XXX: I'm fairly sure this does nothing if result == false,
      //      but leaving it alone for now. -- Grunt
      _abyss_postvault_fixup();
      return result;
  }
  
  static bool _abyss_place_rune(const map_bitmask &abyss_genlevel_mask)
  {
      // Use a rune vault if there's one.
      if (_abyss_place_rune_vault(abyss_genlevel_mask))
          return true;
  
      coord_def chosen_spot;
      int places_found = 0;
  
      // Pick a random spot to drop the rune. We specifically do not use
      // random_in_bounds and similar, because we may be dealing with a
      // non-rectangular region, and we want to place the rune fairly.
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
      {
          const coord_def p(*ri);
          if (abyss_genlevel_mask(p)
              && env.grid(p) == DNGN_FLOOR && env.igrid(p) == NON_ITEM
              && one_chance_in(++places_found))
          {
              chosen_spot = p;
          }
      }
  
      if (places_found)
      {
          dprf(DIAG_ABYSS, "Placing abyssal rune at (%d,%d)",
               chosen_spot.x, chosen_spot.y);
          int item_ind  = items(true, OBJ_RUNES, RUNE_ABYSSAL, 0);
          if (item_ind != NON_ITEM)
              item_colour(env.item[item_ind]);
          move_item_to_grid(&item_ind, chosen_spot);
          return item_ind != NON_ITEM;
      }
  
      return false;
  }
  
  // Returns true if items can be generated on the given square.
  static bool _abyss_square_accepts_items(const map_bitmask &abyss_genlevel_mask,
                                          coord_def p)
  {
      return abyss_genlevel_mask(p)
             && env.grid(p) == DNGN_FLOOR
             && env.igrid(p) == NON_ITEM
             && !map_masked(p, MMT_VAULT);
  }
  
  static int _abyss_create_items(const map_bitmask &abyss_genlevel_mask,
                                 bool placed_abyssal_rune)
  {
      // During game start, number and level of items mustn't be higher than
      // that on level 1.
      int num_items = 150, items_level = 52;
      int items_placed = 0;
  
      if (player_in_starting_abyss())
      {
          num_items   = 3 + roll_dice(3, 11);
          items_level = 0;
      }
  
      const int abyssal_rune_roll = _abyssal_rune_roll();
      bool should_place_abyssal_rune = false;
      vector<coord_def> chosen_item_places;
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
      {
          if (_abyss_square_accepts_items(abyss_genlevel_mask, *ri))
          {
              if (items_placed < num_items && one_chance_in(200))
              {
                  // [ds] Don't place abyssal rune in this loop to avoid
                  // biasing rune placement toward the north-west of the
                  // abyss level. Instead, make a note of whether we
                  // decided to place the abyssal rune at all, and if we
                  // did, place it randomly somewhere in the map at the
                  // end of the item-gen pass. We may as a result create
                  // (num_items + 1) items instead of num_items, which
                  // is acceptable.
                  if (!placed_abyssal_rune && !should_place_abyssal_rune
                      && abyssal_rune_roll != -1
                      && x_chance_in_y(abyssal_rune_roll, ABYSSAL_RUNE_MAX_ROLL))
                  {
                      should_place_abyssal_rune = true;
                  }
  
                  chosen_item_places.push_back(*ri);
              }
          }
      }
  
      if (!placed_abyssal_rune && should_place_abyssal_rune)
      {
          if (_abyss_place_rune(abyss_genlevel_mask))
              ++items_placed;
      }
  
      for (const coord_def &place : chosen_item_places)
      {
          if (_abyss_square_accepts_items(abyss_genlevel_mask, place))
          {
              int thing_created = items(true, OBJ_RANDOM, OBJ_RANDOM,
                                        items_level);
              move_item_to_grid(&thing_created, place);
              if (thing_created != NON_ITEM)
                  items_placed++;
          }
      }
  
      return items_placed;
  }
  
  static string _who_banished(const string &who)
  {
      return who.empty() ? who : " (" + who + ")";
  }
  
  static int _banished_depth(const int power)
  {
      // Linear, with the max going from (1,1) to (25,5)
      // and the min going from (9,1) to (27,5)
      // Currently using HD for power
  
      // This means an orc will send you to A:1, an orc warrior
      // has a small chance of A:2,
      // Elves have a good shot at sending you to A:3, but won't
      // always
      // Ancient Liches are sending you to A:5 and there's nothing
      // you can do about that.
      const int maxdepth = div_rand_round((power + 5), 6);
      const int mindepth = (4 * power + 7) / 23;
      return min(5, max(1, random_range(mindepth, maxdepth)));
  }
  
  void banished(const string &who, const int power)
  {
      ASSERT(!crawl_state.game_is_arena());
      if (brdepth[BRANCH_ABYSS] == -1)
          return;
  
      if (player_in_branch(BRANCH_ABYSS))
      {
          if (level_id::current().depth < brdepth[BRANCH_ABYSS])
              down_stairs(DNGN_ABYSSAL_STAIR);
          else
          {
              // On Abyss:5 we can't go deeper; cause a shift to a new area
              mprf(MSGCH_BANISHMENT, "You are banished to a different region of the Abyss.");
              abyss_teleport();
          }
          return;
      }
  
      const int depth = _banished_depth(power);
      const string what = make_stringf("Cast into level %d of the Abyss", depth)
                        + _who_banished(who);
      take_note(Note(NOTE_MESSAGE, 0, 0, what), true);
  
      stop_delay(true);
      run_animation(ANIMATION_BANISH, UA_BRANCH_ENTRY, false);
      push_features_to_abyss();
      floor_transition(DNGN_ENTER_ABYSS, orig_terrain(you.pos()),
                       level_id(BRANCH_ABYSS, depth), true);
      // This is an honest abyss entry, mark milestone
      mark_milestone("abyss.enter",
          "was cast into the Abyss!" + _who_banished(who), "parent");
  
      // Xom just might decide to interfere.
      if (you_worship(GOD_XOM) && who != "Xom" && who != "wizard command"
          && who != "a distortion unwield")
      {
          xom_maybe_reverts_banishment(false, false);
      }
  }
  
  void push_features_to_abyss()
  {
      abyssal_features.clear();
  
      for (int x = -LOS_RADIUS; x <= LOS_RADIUS; x++)
      {
          for (int y = -LOS_RADIUS; y <= LOS_RADIUS; y++)
          {
              coord_def p(x, y);
  
              p += you.pos();
  
              dungeon_feature_type feature = map_bounds(p) ? env.grid(p) : DNGN_UNSEEN;
              feature = sanitize_feature(feature);
              abyssal_features.push_back(feature);
          }
      }
  }
  
  static bool _abyss_check_place_feat(coord_def p,
                                      const int feat_chance,
                                      int *feats_wanted,
                                      bool *use_map,
                                      dungeon_feature_type which_feat,
                                      const map_bitmask &abyss_genlevel_mask)
  {
      if (!which_feat)
          return false;
  
      const bool place_feat = feat_chance && one_chance_in(feat_chance);
  
      if (place_feat && feats_wanted)
          ++*feats_wanted;
  
      // Don't place features in bubbles.
      int wall_count = 0;
      for (adjacent_iterator ai(p); ai; ++ai)
          wall_count += cell_is_solid(p);
      if (wall_count > 6)
          return false;
  
      // There's no longer a need to check for features under items,
      // since we're working on fresh grids that are guaranteed
      // item-free.
      if (place_feat || (feats_wanted && *feats_wanted > 0))
      {
          dprf(DIAG_ABYSS, "Placing abyss feature: %s.",
               dungeon_feature_name(which_feat));
  
          // When placing Abyss exits, try to use a vault if we have one.
          if (which_feat == DNGN_EXIT_ABYSS
              && use_map && *use_map
              && _abyss_place_vault_tagged(abyss_genlevel_mask, "abyss_exit"))
          {
              *use_map = false;
  
              // Link the vault-placed items.
              _abyss_postvault_fixup();
          }
          else if (!abyss_genlevel_mask(p))
              return false;
          else
              env.grid(p) = which_feat;
  
          if (feats_wanted)
              --*feats_wanted;
          return true;
      }
      return false;
  }
  
  static dungeon_feature_type _abyss_pick_altar()
  {
      // Lugonu has a flat 50% chance of corrupting the altar.
      if (coinflip())
          return DNGN_ALTAR_LUGONU;
  
      god_type god;
  
      do
      {
          god = random_god();
      }
      while (is_good_god(god));
  
      return altar_for_god(god);
  }
  
  static bool _abyssal_rune_at(const coord_def p)
  {
      for (stack_iterator si(p); si; ++si)
          if (si->is_type(OBJ_RUNES, RUNE_ABYSSAL))
              return true;
      return false;
  }
  
  class xom_abyss_feature_amusement_check
  {
  private:
      bool exit_was_near;
      bool rune_was_near;
  
  private:
      bool abyss_exit_nearness() const
      {
          // env.map_knowledge().known() doesn't work on unmappable levels because
          // mapping flags are not set on such levels.
          for (radius_iterator ri(you.pos(), LOS_DEFAULT); ri; ++ri)
              if (env.grid(*ri) == DNGN_EXIT_ABYSS && env.map_knowledge(*ri).seen())
                  return true;
  
          return false;
      }
  
      bool abyss_rune_nearness() const
      {
          // See above comment about env.map_knowledge().known().
          for (radius_iterator ri(you.pos(), LOS_DEFAULT); ri; ++ri)
              if (env.map_knowledge(*ri).seen() && _abyssal_rune_at(*ri))
                  return true;
          return false;
      }
  
  public:
      xom_abyss_feature_amusement_check()
      {
          exit_was_near = abyss_exit_nearness();
          rune_was_near = abyss_rune_nearness();
      }
  
      // If the player was almost to the exit when it disappeared, Xom
      // is extremely amused. He's also extremely amused if the player
      // winds up right next to an exit when there wasn't one there
      // before. The same applies to Abyssal runes.
      ~xom_abyss_feature_amusement_check()
      {
          // Update known terrain
          viewwindow();
          update_screen();
  
          const bool exit_is_near = abyss_exit_nearness();
          const bool rune_is_near = abyss_rune_nearness();
  
          if (exit_was_near && !exit_is_near || rune_was_near && !rune_is_near)
              xom_is_stimulated(200, "Xom snickers loudly.", true);
  
          if (!rune_was_near && rune_is_near || !exit_was_near && exit_is_near)
              xom_is_stimulated(200);
      }
  };
  
  static void _abyss_lose_monster(monster& mons)
  {
      if (mons.needs_abyss_transit())
          mons.set_transit(level_id(BRANCH_ABYSS));
      // make sure we don't end up with an invalid hep ancestor
      else if (hepliaklqana_ancestor() == mons.mid)
      {
          simple_monster_message(mons, " is pulled into the Abyss.",
                  MSGCH_BANISHMENT);
          remove_companion(&mons);
          you.duration[DUR_ANCESTOR_DELAY] = random_range(50, 150); //~5-15 turns
      }
  
      mons.destroy_inventory();
      monster_cleanup(&mons);
  }
  
  // If a sanctuary exists and is in LOS, moves it to keep it in the
  // same place relative to the player's location after a shift. If the
  // sanctuary is not in player LOS, removes it.
  static void _abyss_move_sanctuary(const coord_def abyss_shift_start_centre,
                                    const coord_def abyss_shift_end_centre)
  {
      if (env.sanctuary_time > 0 && in_bounds(env.sanctuary_pos))
      {
          if (you.see_cell(env.sanctuary_pos))
          {
              env.sanctuary_pos += (abyss_shift_end_centre -
                                    abyss_shift_start_centre);
          }
          else
              remove_sanctuary();
      }
  }
  
  static void _push_displaced_monster(monster* mon)
  {
      displaced_monsters.push_back(mon);
  }
  
  static void _place_displaced_monsters()
  {
      for (monster *mon : displaced_monsters)
      {
          if (mon->alive() && !mon->find_home_near_place(mon->pos()))
          {
              maybe_bloodify_square(mon->pos());
              // hep messaging is done in _abyss_lose_monster
              if (you.can_see(*mon) && hepliaklqana_ancestor() != mon->mid)
              {
                  simple_monster_message(*mon, " is pulled into the Abyss.",
                          MSGCH_BANISHMENT);
              }
              _abyss_lose_monster(*mon);
  
          }
      }
  
      displaced_monsters.clear();
  }
  
  static bool _pushy_feature(dungeon_feature_type feat)
  {
      // Only completely impassible features and lava will push items.
      // In particular, deep water will not push items, because the item
      // will eventually become accessible again through abyss morphing.
  
      // Perhaps this should instead be merged with (the complement of)
      // _item_safe_square() in terrain.cc. Unlike this function, that
      // one treats traps as unsafe, but closed doors as safe.
      return feat_is_solid(feat) || feat == DNGN_LAVA;
  }
  
  static void _push_items()
  {
      for (int i = 0; i < MAX_ITEMS; i++)
      {
          item_def& item(env.item[i]);
          if (!item.defined() || !in_bounds(item.pos) || item.held_by_monster())
              continue;
  
          if (env.item[i].flags & ISFLAG_SUMMONED)
          {
              // this is here because of hep-related crashes that no one has
              // figured out. Under some circumstances, a hep ancestor can drop
              // its items in the abyss in a stack of copies(??), and when they
              // do, on the next abyss morph the call below to move_item_to_grid
              // will trigger a crash, softlocking the player out of abyss.
              // Therefore, preemptively clean things up until someone figures
              // out this bug. See
              // https://crawl.develz.org/mantis/view.php?id=11756 among others.
              debug_dump_item(item.name(DESC_PLAIN).c_str(),
                  i, item, "Cleaning up buggy summoned item!");
              destroy_item(i);
              continue;
          }
          if (!_pushy_feature(env.grid(item.pos)))
              continue;
  
          for (distance_iterator di(item.pos); di; ++di)
              if (!_pushy_feature(env.grid(*di)))
              {
                  int j = i;
                  move_item_to_grid(&j, *di, true);
                  break;
              }
      }
  }
  
  // Deletes everything on the level at the given position.
  // Things that are wiped:
  // 1. Dungeon terrain (set to DNGN_UNSEEN)
  // 2. Monsters (the player is unaffected)
  // 3. Items
  // 4. Clouds
  // 5. Terrain properties
  // 6. Terrain colours
  // 7. Vault (map) mask
  // 8. Vault id mask
  // 9. Map markers
  
  static void _abyss_wipe_square_at(coord_def p, bool saveMonsters=false)
  {
      // Nuke terrain.
      destroy_shop_at(p);
      destroy_trap(p);
  
      // Nuke vault flag.
      if (map_masked(p, MMT_VAULT))
          env.level_map_mask(p) &= ~MMT_VAULT;
  
      env.grid(p) = DNGN_UNSEEN;
  
      // Nuke items.
      if (env.igrid(p) != NON_ITEM)
          dprf(DIAG_ABYSS, "Nuke item stack at (%d, %d)", p.x, p.y);
      lose_item_stack(p);
  
      // Nuke monster.
      if (monster* mon = monster_at(p))
      {
          ASSERT(mon->alive());
  
          if (saveMonsters)
              _push_displaced_monster(mon);
          else
              _abyss_lose_monster(*mon);
      }
  
      // Delete cloud.
      delete_cloud(p);
  
      env.pgrid(p)        = terrain_property_t{};
      env.grid_colours(p) = 0;
  #ifdef USE_TILE
      tile_env.bk_fg(p)   = 0;
      tile_env.bk_bg(p)   = 0;
      tile_env.bk_cloud(p)= 0;
  #endif
      tile_clear_flavour(p);
      tile_init_flavour(p);
  
      env.level_map_mask(p) = 0;
      env.level_map_ids(p)  = INVALID_MAP_INDEX;
  
      remove_markers_and_listeners_at(p);
  
      env.map_knowledge(p).clear();
      if (env.map_forgotten)
          (*env.map_forgotten)(p).clear();
      env.map_seen.set(p, false);
  #ifdef USE_TILE
      tile_forget_map(p);
  #endif
      StashTrack.update_stash(p);
  }
  
  // Removes monsters, clouds, dungeon features, and items from the
  // level, torching all squares for which the supplied mask is false.
  static void _abyss_wipe_unmasked_area(const map_bitmask &abyss_preserve_mask)
  {
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
          if (!abyss_preserve_mask(*ri))
              _abyss_wipe_square_at(*ri);
  }
  
  // Moves everything at src to dst.
  static void _abyss_move_entities_at(coord_def src, coord_def dst)
  {
      dgn_move_entities_at(src, dst, true, true, true);
  }
  
  // Move all vaults within the mask by the specified delta.
  static void _abyss_move_masked_vaults_by_delta(const coord_def delta)
  {
      set<int> vault_indexes;
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
      {
          const int vi = env.level_map_ids(*ri);
          if (vi != INVALID_MAP_INDEX)
              vault_indexes.insert(vi);
      }
  
      for (auto i : vault_indexes)
      {
          vault_placement &vp(*env.level_vaults[i]);
  #ifdef DEBUG_DIAGNOSTICS
          const coord_def oldp = vp.pos;
  #endif
          vp.pos += delta;
          dprf(DIAG_ABYSS, "Moved vault (%s) from (%d,%d)-(%d,%d)",
               vp.map.name.c_str(), oldp.x, oldp.y, vp.pos.x, vp.pos.y);
      }
  }
  
  /**
   * Updates the destination of a transporter that has been shifted to a new
   * center. Assumes that the transporter itself and its position marker have
   * already been moved.
   *
   * @param pos            Transporter's new (and current) location.
   * @param source_center  Center of where the transporter's vault area was
   *                       shifted from.
   * @param target_center  Center of where the transporter's vault area is being
   *                       shifted to.
   * @param shift_area     A map_bitmask of the entire area being shifted.
  
   */
  static void _abyss_update_transporter(const coord_def &pos,
                                        const coord_def &source_centre,
                                        const coord_def &target_centre,
                                        const map_bitmask &shift_area)
  {
      if (env.grid(pos) != DNGN_TRANSPORTER)
          return;
  
      // Get the marker, since we will need to modify it.
      map_position_marker *marker =
          get_position_marker_at(pos, DNGN_TRANSPORTER);
      if (!marker || marker->dest == INVALID_COORD)
          return;
  
      // Original destination is not being preserved, so disable the transporter.
      if (!shift_area.get(marker->dest))
      {
          marker->dest = INVALID_COORD;
          return;
      }
  
      marker->dest = marker->dest - source_centre + target_centre;
  }
  
  // Moves the player, monsters, terrain and items in the square (circle
  // in movement distance) around the player with the given radius to
  // the square centred on target_centre.
  //
  // Assumes:
  // a) target can be truncated if not fully in bounds
  // b) source and target areas may overlap
  //
  static void _abyss_move_entities(coord_def target_centre,
                                   map_bitmask *shift_area_mask)
  {
      const coord_def source_centre = you.pos();
      const coord_def delta = (target_centre - source_centre).sgn();
      const map_bitmask original_area_mask = *shift_area_mask;
  
      // When moving a region, walk backward to handle overlapping
      // ranges correctly.
      coord_def direction = -delta;
  
      if (!direction.x)
          direction.x = 1;
      if (!direction.y)
          direction.y = 1;
  
      coord_def start(MAPGEN_BORDER, MAPGEN_BORDER);
      coord_def end(GXM - 1 - MAPGEN_BORDER, GYM - 1 - MAPGEN_BORDER);
  
      if (direction.x == -1)
          swap(start.x, end.x);
      if (direction.y == -1)
          swap(start.y, end.y);
  
      end += direction;
  
      for (int y = start.y; y != end.y; y += direction.y)
      {
          for (int x = start.x; x != end.x; x += direction.x)
          {
              const coord_def src(x, y);
              if (!shift_area_mask->get(src))
                  continue;
  
              shift_area_mask->set(src, false);
  
              const coord_def dst = src - source_centre + target_centre;
              if (map_bounds_with_margin(dst, MAPGEN_BORDER))
              {
                  shift_area_mask->set(dst);
                  // Wipe the dstination clean before dropping things on it.
                  _abyss_wipe_square_at(dst);
                  _abyss_move_entities_at(src, dst);
                  _abyss_update_transporter(dst, source_centre, target_centre,
                                            original_area_mask);
              }
              else
              {
                  // Wipe the source clean even if the dst is not in bounds.
                  _abyss_wipe_square_at(src);
              }
          }
      }
  
      _abyss_move_masked_vaults_by_delta(target_centre - source_centre);
  }
  
  static void _abyss_expand_mask_to_cover_vault(map_bitmask *mask,
                                                int map_index)
  {
      dprf(DIAG_ABYSS, "Expanding mask to cover vault %d (nvaults: %u)",
           map_index, (unsigned int)env.level_vaults.size());
      const vault_placement &vp = *env.level_vaults[map_index];
      for (vault_place_iterator vpi(vp); vpi; ++vpi)
          mask->set(*vpi);
  }
  
  // Identifies the smallest square around the given source that can be
  // shifted without breaking up any vaults.
  static void _abyss_identify_area_to_shift(coord_def source, int radius,
                                            map_bitmask *mask)
  {
      mask->reset();
  
      set<int> affected_vault_indexes;
      for (rectangle_iterator ri(source, radius); ri; ++ri)
      {
          if (!map_bounds_with_margin(*ri, MAPGEN_BORDER))
              continue;
  
          mask->set(*ri);
  
          const int map_index = env.level_map_ids(*ri);
          if (map_index != INVALID_MAP_INDEX)
              affected_vault_indexes.insert(map_index);
      }
  
      for (auto i : affected_vault_indexes)
          _abyss_expand_mask_to_cover_vault(mask, i);
  }
  
  static void _abyss_invert_mask(map_bitmask *mask)
  {
      for (rectangle_iterator ri(0); ri; ++ri)
          mask->set(*ri, !mask->get(*ri));
  }
  
  // Moves everything in the given radius around the player (where radius=0 =>
  // only the player) to another part of the level, centred on target_centre.
  // Everything not in the given radius is wiped to DNGN_UNSEEN and the provided
  // map_bitmask is set to true for all wiped squares.
  //
  // Things that are moved:
  // 1. Dungeon terrain
  // 2. Actors (player + monsters)
  // 3. Items
  // 4. Clouds
  // 5. Terrain properties
  // 6. Terrain colours
  // 7. Vaults
  // 8. Vault (map) mask
  // 9. Vault id mask
  // 10. Map markers
  //
  // After the shift, any vaults that are no longer referenced in the id
  // mask will be discarded. If those vaults had any unique tags or
  // names, the tag/name will NOT be unregistered.
  //
  // Assumes:
  // a) radius >= LOS_RADIUS
  // b) All points in the source and target areas are in bounds.
  static void _abyss_shift_level_contents_around_player(
      int radius,
      coord_def target_centre,
      map_bitmask &abyss_destruction_mask)
  {
      const coord_def source_centre = you.pos();
  
      abyssal_state.major_coord += (source_centre - ABYSS_CENTRE);
  
      ASSERT(radius >= LOS_RADIUS);
      // This should only really happen due to wizmode blink/movement.
      // 1KB: ... yet at least Xom "swap with monster" triggers it.
      //ASSERT(map_bounds_with_margin(source_centre, radius));
      //ASSERT(map_bounds_with_margin(target_centre, radius));
  
      _abyss_identify_area_to_shift(source_centre, radius,
                                    &abyss_destruction_mask);
  
      // Shift sanctuary centre if it's close.
      _abyss_move_sanctuary(you.pos(), target_centre);
  
      // Zap everything except the area we're shifting, so that there's
      // nothing in the way of moving stuff.
      _abyss_wipe_unmasked_area(abyss_destruction_mask);
  
      // Move stuff to its new home. This will also move the player.
      _abyss_move_entities(target_centre, &abyss_destruction_mask);
  
      // [ds] Rezap everything except the shifted area. NOTE: the old
      // code did not do this, leaving a repeated swatch of Abyss behind
      // at the old location for every shift; discussions between Linley
      // and dpeg on ##crawl confirm that this (repeated swatch of
      // terrain left behind) was not intentional.
      _abyss_wipe_unmasked_area(abyss_destruction_mask);
  
      // So far we've used the mask to track the portions of the level we're
      // preserving. The inverse of the mask represents the area to be filled
      // with brand new abyss:
      _abyss_invert_mask(&abyss_destruction_mask);
  
      // Update env.level_vaults to discard any vaults that are no longer in
      // the picture.
      dgn_erase_unused_vault_placements();
  }
  
  static void _abyss_generate_monsters(int nmonsters)
  {
      if (crawl_state.disables[DIS_SPAWNS])
          return;
  
      mgen_data mg;
      mg.proximity = PROX_ANYWHERE;
  
      for (int mcount = 0; mcount < nmonsters; mcount++)
      {
          mg.cls = pick_random_monster(level_id::current());
          if (!invalid_monster_type(mg.cls))
              mons_place(mg);
      }
  }
  
  
  void maybe_shift_abyss_around_player()
  {
      ASSERT(player_in_branch(BRANCH_ABYSS));
      if (map_bounds_with_margin(you.pos(),
                                 MAPGEN_BORDER + ABYSS_AREA_SHIFT_RADIUS + 1))
      {
          return;
      }
  
      dprf(DIAG_ABYSS, "Shifting abyss at (%d,%d)", you.pos().x, you.pos().y);
  
      abyss_area_shift();
      if (you.pet_target != MHITYOU)
          you.pet_target = MHITNOT;
  
  #ifdef DEBUG_DIAGNOSTICS
      int j = count_if(begin(env.item), end(env.item), mem_fn(&item_def::defined));
  
      dprf(DIAG_ABYSS, "Number of items present: %d", j);
  
      j = 0;
      for (monster_iterator mi; mi; ++mi)
          ++j;
  
      dprf(DIAG_ABYSS, "Number of monsters present: %d", j);
      dprf(DIAG_ABYSS, "Number of clouds present: %d", int(env.cloud.size()));
  #endif
  }
  
  void save_abyss_uniques()
  {
      for (monster_iterator mi; mi; ++mi)
          if (mi->needs_abyss_transit()
              && !testbits(mi->flags, MF_TAKING_STAIRS))
          {
              mi->set_transit(level_id(BRANCH_ABYSS));
          }
  }
  
  static bool _in_wastes(const coord_def &p)
  {
      return p.x > 0 && p.x < 0x7FFFFFF && p.y > 0 && p.y < 0x7FFFFFF;
  }
  
  static level_id _get_random_level()
  {
      vector<level_id> levels;
      for (branch_iterator it; it; ++it)
      {
          if (it->id == BRANCH_VESTIBULE || it->id == BRANCH_ABYSS
              || it->id == BRANCH_SHOALS)
          {
              continue;
          }
          for (int j = 1; j <= brdepth[it->id]; ++j)
          {
              const level_id id(it->id, j);
              // for pregen, this will use levels the player hasn't seen yet
              if (is_existing_level(id))
                  levels.push_back(id);
          }
      }
      if (levels.empty())
      {
          // Let this fail later on.
          return level_id(static_cast<branch_type>(BRANCH_DUNGEON), 1);
      }
  
      return levels[hash_with_seed(levels.size(), abyssal_state.seed)];
  }
  
  /**************************************************************/
  /* Fixed layouts (ie, those that depend only on abyss coords) */
  /**************************************************************/
  const static WastesLayout wastes;
  const static DiamondLayout diamond30(3,0);
  const static DiamondLayout diamond21(2,1);
  const static ColumnLayout column2(2);
  const static ColumnLayout column26(2,6);
  const static ProceduralLayout* regularLayouts[] =
  {
      &diamond30, &diamond21, &column2, &column26,
  };
  const static vector<const ProceduralLayout*> layout_vec(regularLayouts,
      regularLayouts + ARRAYSZ(regularLayouts));
  const static WorleyLayout worleyL(123456, layout_vec);
  const static RoilingChaosLayout chaosA(8675309, 450);
  const static RoilingChaosLayout chaosB(7654321, 400);
  const static RoilingChaosLayout chaosC(24324,   380);
  const static RoilingChaosLayout chaosD(24816,   500);
  const static NewAbyssLayout newAbyssLayout(7629);
  const static ProceduralLayout* mixedLayouts[] =
  {
      &chaosA, &worleyL, &chaosB, &chaosC, &chaosD, &newAbyssLayout,
  };
  const static vector<const ProceduralLayout*> mixed_vec(mixedLayouts,
      mixedLayouts + ARRAYSZ(mixedLayouts));
  const static WorleyLayout layout(4321, mixed_vec);
  const static ProceduralLayout* baseLayouts[] = { &newAbyssLayout, &layout };
  const static vector<const ProceduralLayout*> base_vec(baseLayouts,
      baseLayouts + ARRAYSZ(baseLayouts));
  const static WorleyLayout baseLayout(314159, base_vec, 5.0);
  const static RiverLayout rivers(1800, baseLayout);
  // This one is not fixed: [0] is a level pulled from the current game
  static vector<const ProceduralLayout*> complex_vec(2);
  
  static ProceduralSample _abyss_grid(const coord_def &p)
  {
      const coord_def pt = p + abyssal_state.major_coord;
  
      if (_in_wastes(pt))
      {
          ProceduralSample sample = wastes(pt, abyssal_state.depth);
          abyss_sample_queue.push(sample);
          return sample;
      }
  
      if (abyssLayout == nullptr)
      {
          const level_id lid = _get_random_level();
          levelLayout = new LevelLayout(lid, 5, rivers);
          complex_vec[0] = levelLayout;
          complex_vec[1] = &rivers; // const
          abyssLayout = new WorleyLayout(23571113, complex_vec, 6.1);
          if (is_existing_level(lid))
          {
              auto &vault_list =  you.vault_list[level_id::current()];
              vault_list.push_back("base: " + lid.describe(false));
          }
      }
  
      const ProceduralSample sample = (*abyssLayout)(pt, abyssal_state.depth);
      ASSERT(sample.feat() > DNGN_UNSEEN);
  
      abyss_sample_queue.push(sample);
      return sample;
  }
  
  static cloud_type _cloud_from_feat(const dungeon_feature_type &ft)
  {
      switch (ft)
      {
          case DNGN_CLOSED_DOOR:
          case DNGN_OPEN_DOOR:
          case DNGN_METAL_WALL:
              return CLOUD_GREY_SMOKE;
          case DNGN_CRYSTAL_WALL:
          case DNGN_ROCK_WALL:
          case DNGN_SLIMY_WALL:
          case DNGN_STONE_WALL:
          case DNGN_PERMAROCK_WALL:
              return random_choose(CLOUD_BLUE_SMOKE, CLOUD_PURPLE_SMOKE);
          case DNGN_CLEAR_ROCK_WALL:
          case DNGN_CLEAR_STONE_WALL:
          case DNGN_CLEAR_PERMAROCK_WALL:
          case DNGN_GRATE:
          case DNGN_CLOSED_CLEAR_DOOR:
          case DNGN_OPEN_CLEAR_DOOR:
              return CLOUD_MIST;
          case DNGN_ORCISH_IDOL:
          case DNGN_GRANITE_STATUE:
          case DNGN_LAVA:
              return CLOUD_BLACK_SMOKE;
          case DNGN_DEEP_WATER:
          case DNGN_SHALLOW_WATER:
          case DNGN_FOUNTAIN_BLUE:
              return one_chance_in(5) ? CLOUD_RAIN : CLOUD_BLUE_SMOKE;
          case DNGN_FOUNTAIN_SPARKLING:
              return CLOUD_RAIN;
          default:
              return CLOUD_NONE;
      }
  }
  
  static dungeon_feature_type _veto_dangerous_terrain(dungeon_feature_type feat)
  {
      if (feat == DNGN_DEEP_WATER)
          return DNGN_SHALLOW_WATER;
      if (feat == DNGN_LAVA)
          return DNGN_FLOOR;
      if (feat_is_solid(feat))
          return DNGN_FLOOR;
  
      return feat;
  }
  
  static void _update_abyss_terrain(const coord_def &p,
      const map_bitmask &abyss_genlevel_mask, bool morph)
  {
      const coord_def rp = p - abyssal_state.major_coord;
      // ignore dead coordinates
      if (!in_bounds(rp))
          return;
  
      const dungeon_feature_type currfeat = env.grid(rp);
  
      // Don't decay vaults.
      if (map_masked(rp, MMT_VAULT))
          return;
  
      switch (currfeat)
      {
          case DNGN_EXIT_ABYSS:
          case DNGN_ABYSSAL_STAIR:
              return;
          default:
              break;
      }
  
      if (feat_is_altar(currfeat))
          return;
  
      if (!abyss_genlevel_mask(rp))
          return;
  
      if (currfeat != DNGN_UNSEEN && !morph)
          return;
  
      // What should have been there previously?  It might not be because
      // of external changes such as digging.
      const ProceduralSample sample = _abyss_grid(rp);
  
      // Enqueue the update, but don't morph.
      if (_abyssal_rune_at(rp))
          return;
  
      dungeon_feature_type feat = sample.feat();
  
      // Don't replace open doors with closed doors!
      if (feat_is_door(currfeat) && feat_is_door(feat))
          return;
  
      // Veto dangerous terrain.
      if (you.pos() == rp)
          feat = _veto_dangerous_terrain(feat);
      // Veto morph when there's a submerged monster (or a plant) below you.
      if (you.pos() == rp && env.mgrid(rp) != NON_MONSTER)
          feat = currfeat;
  
      // If the selected grid is already there, *or* if we're morphing and
      // the selected grid should have been there, do nothing.
      if (feat != currfeat)
      {
          env.grid(rp) = feat;
          if (feat == DNGN_FLOOR && in_los_bounds_g(rp))
          {
              cloud_type cloud = _cloud_from_feat(currfeat);
              int cloud_life = _in_wastes(abyssal_state.major_coord) ? 5 : 2;
              cloud_life += random2(2); // force a sequence point, just in case
              if (cloud != CLOUD_NONE)
                  check_place_cloud(_cloud_from_feat(currfeat), rp, cloud_life, 0, 3);
          }
          else if (feat_is_solid(feat))
              delete_cloud(rp);
          monster* mon = monster_at(rp);
          if (mon && !monster_habitable_grid(mon, feat))
              _push_displaced_monster(mon);
      }
  }
  
  static void _destroy_all_terrain(bool vaults)
  {
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
      {
          if (vaults && env.level_map_mask(*ri) & MMT_VAULT)
              continue;
          env.level_map_mask(*ri) = MMT_TURNED_TO_FLOOR;
      }
  }
  
  static void _ensure_player_habitable(bool dig_instead)
  {
      dungeon_feature_type feat = env.grid(you.pos());
      if (!you.can_pass_through_feat(feat) || is_feat_dangerous(feat))
      {
          bool shoved = you.shove();
          if (!shoved)
          {
              // legal only if we just placed a vault
              ASSERT(dig_instead);
              env.grid(you.pos()) = DNGN_FLOOR;
          }
      }
  }
  
  static void _abyss_apply_terrain(const map_bitmask &abyss_genlevel_mask,
                                   bool morph = false, bool now = false)
  {
      // The chance is reciprocal to these numbers.
      const int exit_chance = you.runes[RUNE_ABYSSAL] ? 1250
                              : 7500 - 1250 * (you.depth - 1);
  
      int exits_wanted  = 0;
      int altars_wanted = 0;
      bool use_abyss_exit_map = true;
      bool used_queue = false;
      if (morph && !abyss_sample_queue.empty())
      {
          int ii = 0;
          used_queue = true;
          while (!abyss_sample_queue.empty()
              && abyss_sample_queue.top().changepoint() < abyssal_state.depth)
          {
              ++ii;
              coord_def p = abyss_sample_queue.top().coord();
              _update_abyss_terrain(p, abyss_genlevel_mask, morph);
              abyss_sample_queue.pop();
          }
  /*
          if (ii)
              dprf(DIAG_ABYSS, "Examined %d features.", ii);
  */
      }
  
      int ii = 0;
      int delta = you.time_taken * (you.abyss_speed + 40) / 200;
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
      {
          const coord_def p(*ri);
          const coord_def abyss_coord = p + abyssal_state.major_coord;
          bool turned_to_floor = map_masked(p, MMT_TURNED_TO_FLOOR);
          if (used_queue && !turned_to_floor)
              continue;
  
          if (turned_to_floor && (now || x_chance_in_y(delta, 50))
              || !turned_to_floor && !used_queue)
          {
              ++ii;
              _update_abyss_terrain(abyss_coord, abyss_genlevel_mask, morph);
              env.level_map_mask(p) &= ~MMT_TURNED_TO_FLOOR;
          }
          if (morph)
              continue;
  
          // Place abyss exits, stone arches, and altars to liven up the scene
          // (only on area creation, not on morphing).
          _abyss_check_place_feat(p, exit_chance,
                                  &exits_wanted,
                                  &use_abyss_exit_map,
                                  DNGN_EXIT_ABYSS,
                                  abyss_genlevel_mask)
          ||
          _abyss_check_place_feat(p, 10000,
                                  &altars_wanted,
                                  nullptr,
                                  _abyss_pick_altar(),
                                  abyss_genlevel_mask)
          ||
          level_id::current().depth < brdepth[BRANCH_ABYSS]
          && _abyss_check_place_feat(p, 1900, nullptr, nullptr,
                                     DNGN_ABYSSAL_STAIR,
                                     abyss_genlevel_mask);
      }
      if (ii)
          dprf(DIAG_ABYSS, "Nuked %d features", ii);
      _ensure_player_habitable(false);
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
          ASSERT_RANGE(env.grid(*ri), DNGN_UNSEEN + 1, NUM_FEATURES);
  }
  
  static int _abyss_place_vaults(const map_bitmask &abyss_genlevel_mask)
  {
      unwind_vault_placement_mask vaultmask(&abyss_genlevel_mask);
  
      int vaults_placed = 0;
  
      bool extra = false;
      const int maxvaults = 6;
      int tries = 0;
      while (vaults_placed < maxvaults)
      {
          const map_def *map = random_map_in_depth(level_id::current(), extra);
          if (map)
          {
              if (_abyss_place_map(map) && !map->is_extra_vault())
              {
                  extra = true;
  
                  if (!one_chance_in(2 + (++vaults_placed)))
                      break;
              }
              else
              {
                  if (tries++ >= 100)
                      break;
  
                  continue;
              }
  
          }
          else
          {
              if (extra)
                  break;
              else
              {
                  extra = true;
                  continue;
              }
          }
      }
  
      return vaults_placed;
  }
  
  static void _generate_area(const map_bitmask &abyss_genlevel_mask)
  {
      // Any rune on the floor prevents the abyssal rune from being generated.
      const bool placed_abyssal_rune = find_floor_item(OBJ_RUNES);
  
      dprf(DIAG_ABYSS, "_generate_area(). turns_on_level: %d, rune_on_floor: %s",
           env.turns_on_level, placed_abyssal_rune? "yes" : "no");
  
      _abyss_apply_terrain(abyss_genlevel_mask);
  
      // Make sure we're not about to link bad items.
      debug_item_scan();
      _abyss_place_vaults(abyss_genlevel_mask);
  
      // Link the vault-placed items.
      _abyss_postvault_fixup();
  
      _abyss_create_items(abyss_genlevel_mask, placed_abyssal_rune);
      setup_environment_effects();
  
      _ensure_player_habitable(true);
  
      // Abyss has a constant density.
      env.density = 0;
  }
  
  static void _initialize_abyss_state()
  {
      abyssal_state.major_coord.x = rng::get_uint32() & 0x7FFFFFFF;
      abyssal_state.major_coord.y = rng::get_uint32() & 0x7FFFFFFF;
      abyssal_state.seed = rng::get_uint32() & 0x7FFFFFFF;
      abyssal_state.phase = 0.0;
      abyssal_state.depth = rng::get_uint32() & 0x7FFFFFFF;
      abyssal_state.destroy_all_terrain = false;
      abyssal_state.level = _get_random_level();
      abyss_sample_queue = sample_queue(ProceduralSamplePQCompare());
  }
  
  void set_abyss_state(coord_def coord, uint32_t depth)
  {
      abyssal_state.major_coord = coord;
      abyssal_state.depth = depth;
      abyssal_state.seed = rng::get_uint32() & 0x7FFFFFFF;
      abyssal_state.phase = 0.0;
      abyssal_state.destroy_all_terrain = true;
      abyss_sample_queue = sample_queue(ProceduralSamplePQCompare());
      you.moveto(ABYSS_CENTRE);
      map_bitmask abyss_genlevel_mask(true);
      _abyss_apply_terrain(abyss_genlevel_mask, true, true);
  }
  
  static void abyss_area_shift()
  {
      dprf(DIAG_ABYSS, "area_shift() - player at pos (%d, %d)",
           you.pos().x, you.pos().y);
  
      {
          xom_abyss_feature_amusement_check xomcheck;
  
          // A teleport may move you back to the center, resulting in a (0,0)
          // shift. The code can't handle those. We still to forget the map,
          // spawn new monsters or allow return from transit, though.
          if (you.pos() != ABYSS_CENTRE)
          {
              // Use a map mask to track the areas that the shift destroys and
              // that must be regenerated by _generate_area.
              map_bitmask abyss_genlevel_mask;
              _abyss_shift_level_contents_around_player(
                  ABYSS_AREA_SHIFT_RADIUS, ABYSS_CENTRE, abyss_genlevel_mask);
              _generate_area(abyss_genlevel_mask);
          }
          forget_map(true);
  
          // Update LOS at player's new abyssal vacation retreat.
          los_changed();
      }
  
      // Place some monsters to keep the abyss party going.
      int num_monsters = 15 + you.depth * (1 + coinflip());
      _abyss_generate_monsters(num_monsters);
  
      // And allow monsters in transit another chance to return.
      place_transiting_monsters();
  
      auto &vault_list =  you.vault_list[level_id::current()];
  #ifdef DEBUG
      vault_list.push_back("[shift]");
  #endif
      const auto &level_vaults = level_vault_names();
      vault_list.insert(vault_list.end(),
                          level_vaults.begin(), level_vaults.end());
  
  
      check_map_validity();
      // TODO: should dactions be rerun at this point instead? That would cover
      // this particular case...
      gozag_detect_level_gold(false);
  }
  
  void destroy_abyss()
  {
      if (abyssLayout)
      {
          delete abyssLayout;
          abyssLayout = nullptr;
          delete levelLayout;
          levelLayout = nullptr;
      }
  }
  
  static colour_t _roll_abyss_floor_colour()
  {
      return random_choose_weighted<colour_t>(
           108, BLUE,
           632, GREEN,
           // no CYAN (silence)
           932, RED,
           488, MAGENTA,
           433, BROWN,
          3438, LIGHTGRAY,
           // no DARKGREY (out of LOS)
           766, LIGHTBLUE,
           587, LIGHTGREEN,
           794, LIGHTCYAN,
           566, LIGHTRED,
           313, LIGHTMAGENTA,
           // no YELLOW (halo)
           890, WHITE,
            50, ETC_FIRE);
  }
  
  static colour_t _roll_abyss_rock_colour()
  {
      return random_choose_weighted<colour_t>(
           130, BLUE,
           409, GREEN,
           // no CYAN (metal)
           770, RED,
           522, MAGENTA,
          1292, BROWN,
           // no LIGHTGRAY (stone)
           // no DARKGREY (out of LOS)
           570, LIGHTBLUE,
           705, LIGHTGREEN,
           // no LIGHTCYAN (glass)
          1456, LIGHTRED,
           377, LIGHTMAGENTA,
           105, YELLOW,
           101, WHITE,
            60, ETC_FIRE);
  }
  
  static void _abyss_generate_new_area()
  {
      _initialize_abyss_state();
      dprf(DIAG_ABYSS, "Abyss Coord (%d, %d)",
           abyssal_state.major_coord.x, abyssal_state.major_coord.y);
      remove_sanctuary();
  
      env.floor_colour = _roll_abyss_floor_colour();
      env.rock_colour = _roll_abyss_rock_colour();
      tile_init_flavour();
  
      map_bitmask abyss_genlevel_mask;
      _abyss_wipe_unmasked_area(abyss_genlevel_mask);
      dgn_erase_unused_vault_placements();
  
      you.moveto(ABYSS_CENTRE);
      abyss_genlevel_mask.init(true);
      _generate_area(abyss_genlevel_mask);
      if (one_chance_in(5))
      {
          _place_feature_near(you.pos(), LOS_RADIUS,
                              DNGN_FLOOR, DNGN_ALTAR_LUGONU, 50);
      }
  
      los_changed();
      place_transiting_monsters();
  }
  
  // Check if there is a path between the abyss centre and an exit location.
  static bool _abyss_has_path(const coord_def &to)
  {
      ASSERT(env.grid(to) == DNGN_EXIT_ABYSS);
  
      monster_pathfind pf;
      return pf.init_pathfind(ABYSS_CENTRE, to);
  }
  
  // Generate the initial (proto) Abyss level. The proto Abyss is where
  // the player lands when they arrive in the Abyss from elsewhere.
  // _generate_area generates all other Abyss areas.
  void generate_abyss()
  {
      env.level_build_method += " abyss";
      env.level_layout_types.insert("abyss");
      destroy_abyss();
  
  retry:
      _initialize_abyss_state();
  
      dprf(DIAG_ABYSS, "generate_abyss(); turn_on_level: %d",
           env.turns_on_level);
  
      // Generate the initial abyss without vaults. Vaults are horrifying.
      _abyss_generate_new_area();
      _write_abyssal_features();
      map_bitmask abyss_genlevel_mask(true);
      _abyss_apply_terrain(abyss_genlevel_mask);
  
      env.grid(you.pos()) = _veto_dangerous_terrain(env.grid(you.pos()));
      _place_displaced_monsters();
  
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
          ASSERT(env.grid(*ri) > DNGN_UNSEEN);
      check_map_validity();
  
      // If we're starting out in the Abyss, make sure the starting grid is
      // an altar to Lugonu and there's an exit near-by.
      // Otherwise, we start out on floor and there's a chance there's an
      // altar near-by.
      if (player_in_starting_abyss())
      {
          env.grid(ABYSS_CENTRE) = DNGN_ALTAR_LUGONU;
          const coord_def eloc = _place_feature_near(ABYSS_CENTRE, LOS_RADIUS + 2,
                                                     DNGN_FLOOR, DNGN_EXIT_ABYSS,
                                                     50, true);
          // Now make sure there is a path from the abyss centre to the exit.
          // If for some reason an exit could not be placed, don't bother.
          if (eloc == INVALID_COORD || !_abyss_has_path(eloc))
              goto retry;
      }
      else
      {
          env.grid(ABYSS_CENTRE) = DNGN_FLOOR;
          if (one_chance_in(5))
          {
              _place_feature_near(ABYSS_CENTRE, LOS_RADIUS,
                                  DNGN_FLOOR, DNGN_ALTAR_LUGONU, 50);
          }
      }
  
      setup_environment_effects();
  }
  
  static void _increase_depth()
  {
      int delta = you.time_taken * (you.abyss_speed + 40) / 200;
      if (!have_passive(passive_t::slow_abyss))
          delta *= 2;
      if (you.duration[DUR_TELEPORT])
          delta *= 5;
      const double theta = abyssal_state.phase;
      double depth_change = delta * (0.2 + 2.8 * pow(sin(theta/2), 10.0));
      abyssal_state.depth += depth_change;
      abyssal_state.phase += delta / 100.0;
      if (abyssal_state.phase > PI)
          abyssal_state.phase -= PI;
  }
  
  void abyss_morph()
  {
      if (abyssal_state.destroy_all_terrain)
      {
          _destroy_all_terrain(false);
          abyssal_state.destroy_all_terrain = false;
      }
      if (!player_in_branch(BRANCH_ABYSS))
          return;
      _increase_depth();
      map_bitmask abyss_genlevel_mask(true);
      dgn_erase_unused_vault_placements();
      _abyss_apply_terrain(abyss_genlevel_mask, true);
      _place_displaced_monsters();
      _push_items();
      // TODO: does gozag gold detection need to be here too?
      los_changed();
  }
  
  // Force the player one level deeper in the abyss during an abyss teleport with
  // probability:
  //   (XL + 4 - Depth)^2 / (27^2 * (Depth + 5))
  //
  // Consequences of this formula:
  // - Chance to be pulled deeper increases with XL and decreases with current
  //   abyss depth.
  // - Characters at XL 1 have about a 0.1% chance of getting pulled from A:1.
  // - Characters at XL 13 have chances for getting pulled from A:1/A:2/A:3/A:4
  //   of about 5.9%/4.4%/3.3%/2.6%.
  // - Characters at XL 27 have chances for getting pulled from A:1/A:2/A:3/A:4
  //   of about 20.6%/16.5%/13.4%/11.1%.
  static bool _abyss_force_descent()
  {
      const int depth = level_id::current().depth;
      const int xl_factor = you.experience_level + 4 - depth;
      return x_chance_in_y(xl_factor * xl_factor, 729 * (5 + depth));
  }
  
  void abyss_teleport()
  {
      xom_abyss_feature_amusement_check xomcheck;
      dprf(DIAG_ABYSS, "New area Abyss teleport.");
  
      if (level_id::current().depth < brdepth[BRANCH_ABYSS]
          && _abyss_force_descent())
      {
          down_stairs(DNGN_ABYSSAL_STAIR);
          more();
          return;
      }
  
      mprf(MSGCH_BANISHMENT, "You are suddenly pulled into a different region of"
          " the Abyss!");
      _abyss_generate_new_area();
      _write_abyssal_features();
      env.grid(you.pos()) = _veto_dangerous_terrain(env.grid(you.pos()));
  
      stop_delay(true);
      forget_map(false);
      clear_excludes();
      gozag_detect_level_gold(false);
      auto &vault_list =  you.vault_list[level_id::current()];
  #ifdef DEBUG
      vault_list.push_back("[tele]");
  #endif
      const auto &level_vaults = level_vault_names();
      vault_list.insert(vault_list.end(),
                          level_vaults.begin(), level_vaults.end());
  
      more();
  }
  
  //////////////////////////////////////////////////////////////////////////////
  // Abyss effects in other levels, courtesy Lugonu.
  
  struct corrupt_env
  {
      int rock_colour, floor_colour, secondary_floor_colour;
      corrupt_env()
          : rock_colour(BLACK), floor_colour(BLACK),
             secondary_floor_colour(MAGENTA)
      { }
  
      int pick_floor_colour() const
      {
          return random2(10) < 2 ? secondary_floor_colour : floor_colour;
      }
  };
  
  static void _place_corruption_seed(const coord_def &pos, int duration)
  {
      env.markers.add(new map_corruption_marker(pos, duration));
      // Corruption markers don't need activation, though we might
      // occasionally miss other unactivated markers by clearing.
      env.markers.clear_need_activate();
  }
  
  static void _initialise_level_corrupt_seeds(int power)
  {
      const int low = power * 40 / 100, high = power * 140 / 100;
      const int nseeds = random_range(-1, min(2 + power / 110, 4), 2);
  
      const int aux_seed_radius = 4;
  
      dprf("Placing %d corruption seeds (power: %d)", nseeds, power);
  
      // The corruption centreed on the player is free.
      _place_corruption_seed(you.pos(), high + 300);
  
      for (int i = 0; i < nseeds; ++i)
      {
          coord_def where;
          int tries = 100;
          while (tries-- > 0)
          {
              where = dgn_random_point_from(you.pos(), aux_seed_radius, 2);
              if (env.grid(where) == DNGN_FLOOR && !env.markers.find(where, MAT_ANY))
                  break;
              where.reset();
          }
  
          if (!where.origin())
              _place_corruption_seed(where, random_range(low, high, 2) + 300);
      }
  }
  
  static bool _incorruptible(monster_type mt)
  {
      return mons_is_abyssal_only(mt) || mons_class_holiness(mt) == MH_HOLY;
  }
  
  // Create a corruption spawn at the given position. Returns false if further
  // monsters should not be placed near this spot (overcrowding), true if
  // more monsters can fit in.
  static bool _spawn_corrupted_servant_near(const coord_def &pos)
  {
      // Chance to fail to place a monster (but allow continued attempts).
      if (x_chance_in_y(100, 200 + you.skill(SK_INVOCATIONS, 25)))
          return true;
  
      // Thirty tries for a place.
      for (int i = 0; i < 30; ++i)
      {
          int offsetX = random2avg(4, 3);
          offsetX += random2(3); // force a sequence point between random calls
          int offsetY = random2avg(4, 3);
          offsetY += random2(3); // ditto
          coord_def p;
          p.x = pos.x + random_choose(offsetX, -offsetX);
          p.y = pos.y + random_choose(offsetY, -offsetY);
          if (!in_bounds(p) || actor_at(p))
              continue;
  
          monster_type mons = pick_monster(level_id(BRANCH_ABYSS), _incorruptible);
          ASSERT(mons);
          if (!monster_habitable_grid(mons, env.grid(p)))
              continue;
          mgen_data mg(mons, BEH_NEUTRAL, p);
          mg.set_summoned(0, 5, 0).set_non_actor_summoner("Lugonu's corruption");
          mg.place = BRANCH_ABYSS;
          return create_monster(mg);
      }
  
      return false;
  }
  
  static void _apply_corruption_effect(map_marker *marker, int duration)
  {
      if (!duration)
          return;
  
      map_corruption_marker *cmark = dynamic_cast<map_corruption_marker*>(marker);
      if (cmark->duration < 1)
          return;
  
      const int neffects = max(div_rand_round(duration, 5), 1);
  
      for (int i = 0; i < neffects; ++i)
      {
          if (x_chance_in_y(cmark->duration, 4000)
              && !_spawn_corrupted_servant_near(cmark->pos))
          {
              break;
          }
      }
      cmark->duration -= duration;
  }
  
  void run_corruption_effects(int duration)
  {
      for (map_marker *mark : env.markers.get_all(MAT_CORRUPTION_NEXUS))
      {
          if (mark->get_type() != MAT_CORRUPTION_NEXUS)
              continue;
  
          _apply_corruption_effect(mark, duration);
      }
  }
  
  static bool _is_grid_corruptible(const coord_def &c)
  {
      if (c == you.pos())
          return false;
  
      const dungeon_feature_type feat = env.grid(c);
  
      // Stairs and portals cannot be corrupted.
      if (feat_stair_direction(feat) != CMD_NO_CMD)
          return false;
  
      switch (feat)
      {
      case DNGN_PERMAROCK_WALL:
      case DNGN_CLEAR_PERMAROCK_WALL:
      case DNGN_OPEN_SEA:
      case DNGN_LAVA_SEA:
      case DNGN_TRANSPORTER_LANDING: // entry already taken care of as stairs
          return false;
  
      case DNGN_METAL_WALL:
      case DNGN_CRYSTAL_WALL:
          return one_chance_in(4);
  
      case DNGN_STONE_WALL:
      case DNGN_CLEAR_STONE_WALL:
          return one_chance_in(3);
  
      case DNGN_ROCK_WALL:
      case DNGN_CLEAR_ROCK_WALL:
          return !one_chance_in(3);
  
      default:
          return true;
      }
  }
  
  // Returns true if the square has <= 4 traversable neighbours.
  static bool _is_crowded_square(const coord_def &c)
  {
      int neighbours = 0;
      for (int xi = -1; xi <= 1; ++xi)
          for (int yi = -1; yi <= 1; ++yi)
          {
              if (!xi && !yi)
                  continue;
  
              const coord_def n(c.x + xi, c.y + yi);
              if (!in_bounds(n) || !feat_is_traversable(env.grid(n)))
                  continue;
  
              if (++neighbours > 4)
                  return false;
          }
  
      return true;
  }
  
  // Returns true if the square has all opaque neighbours.
  static bool _is_sealed_square(const coord_def &c)
  {
      for (adjacent_iterator ai(c); ai; ++ai)
          if (!feat_is_opaque(env.grid(*ai)))
              return false;
  
      return true;
  }
  
  static void _corrupt_square_flavor(const corrupt_env &cenv, const coord_def &c)
  {
      dungeon_feature_type feat = env.grid(c);
      int floor = cenv.pick_floor_colour();
  
      if (feat == DNGN_ROCK_WALL || feat == DNGN_METAL_WALL
          || feat == DNGN_STONE_WALL || feat == DNGN_TREE)
      {
          env.grid_colours(c) = cenv.rock_colour;
      }
      else if (feat == DNGN_FLOOR)
          env.grid_colours(c) = floor;
  
      // if you add new features to this, you'll probably need to do some
      // hand-tweaking in tileview.cc apply_variations.
      // TODO: these tile assignments here seem to get overridden in
      // apply_variations, or not used at all...what gives?
      if (feat == DNGN_ROCK_WALL)
      {
          tileidx_t idx = tile_dngn_coloured(TILE_WALL_ABYSS,
                                             cenv.rock_colour);
          tile_env.flv(c).wall = idx + random2(tile_dngn_count(idx));
      }
      else if (feat == DNGN_FLOOR)
      {
          tileidx_t idx = tile_dngn_coloured(TILE_FLOOR_NERVES,
                                             floor);
          tile_env.flv(c).floor = idx + random2(tile_dngn_count(idx));
      }
      else if (feat == DNGN_STONE_WALL)
      {
          // recoloring stone and metal is also impacted heavily by the rolls
          // in _is_grid_corruptible
          tileidx_t idx = tile_dngn_coloured(TILE_DNGN_STONE_WALL,
                                             cenv.rock_colour);
          tile_env.flv(c).wall = idx + random2(tile_dngn_count(idx));
      }
      else if (feat == DNGN_METAL_WALL)
      {
          tileidx_t idx = tile_dngn_coloured(TILE_DNGN_METAL_WALL,
                                             cenv.rock_colour);
          tile_env.flv(c).wall = idx + random2(tile_dngn_count(idx));
      }
      else if (feat == DNGN_TREE)
      {
          tileidx_t idx = tile_dngn_coloured(TILE_DNGN_TREE,
                                             cenv.rock_colour);
          // trees only have yellow, lightred, red, and darkgray (dead)
          if (idx == TILE_DNGN_TREE)
              idx = tile_dngn_coloured(TILE_DNGN_TREE, DARKGREY);
          env.grid_colours(c) = DARKGREY;
          tile_env.flv(c).wall = idx + random2(tile_dngn_count(idx));
      }
  }
  
  static void _corrupt_square(const corrupt_env &cenv, const coord_def &c)
  {
      // Ask dungeon_change_terrain to preserve things that are not altars.
      // This only actually matters for malign gateways and features that happen
      // to be on squares that happen to contain map markers (e.g. sealed doors,
      // which come with their own markers). MAT_CORRUPTION_NEXUS is a marker,
      // and some of those are certainly nearby, but they only appear on
      // DNGN_FLOOR. preserve_features=true would ordinarily cause
      // dungeon_terrain_changed to protect stairs/branch entries/portals as
      // well, but _corrupt_square is not called on squares containing those
      // features.
      bool preserve_features = true;
      dungeon_feature_type feat = DNGN_UNSEEN;
      if (feat_altar_god(env.grid(c)) != GOD_NO_GOD)
      {
          preserve_features = false;
          if (!one_chance_in(3))
              feat = DNGN_ALTAR_LUGONU;
      }
      else
          feat = _abyss_proto_feature();
  
      if (feat_is_trap(feat)
          || feat == DNGN_UNSEEN
          || (feat_is_traversable(env.grid(c)) && !feat_is_traversable(feat)
              && coinflip()))
      {
          feat = DNGN_FLOOR;
      }
  
      if (feat_is_traversable(env.grid(c)) && !feat_is_traversable(feat)
          && _is_crowded_square(c))
      {
          return;
      }
  
      if (!feat_is_traversable(env.grid(c)) && feat_is_traversable(feat)
          && _is_sealed_square(c))
      {
          return;
      }
  
      if (feat == DNGN_EXIT_ABYSS)
          feat = DNGN_ENTER_ABYSS;
  
      // If we are trying to place a wall on top of a creature or item, try to
      // move it aside. If this fails, simply place floor instead.
      actor* act = actor_at(c);
      if (feat_is_solid(feat) && (env.igrid(c) != NON_ITEM || act))
      {
          push_items_from(c, nullptr);
          push_actor_from(c, nullptr, true);
          if (actor_at(c) || env.igrid(c) != NON_ITEM)
              feat = DNGN_FLOOR;
      }
  
      dungeon_terrain_changed(c, feat, preserve_features, true);
      _corrupt_square_flavor(cenv, c);
  }
  
  static void _corrupt_level_features(const corrupt_env &cenv)
  {
      vector<coord_def> corrupt_seeds;
  
      for (const map_marker *mark : env.markers.get_all(MAT_CORRUPTION_NEXUS))
          corrupt_seeds.push_back(mark->pos);
  
      for (rectangle_iterator ri(MAPGEN_BORDER); ri; ++ri)
      {
          int idistance = GXM + GYM;
          for (const coord_def &seed : corrupt_seeds)
              idistance = min(idistance, (*ri - seed).rdist());
  
          const int ground_zero_radius = 2;
  
          // Corruption odds are 100% within 2 squares, decaying to 30%
          // at LOS range (radius 7). Even if the corruption roll is made,
          // the feature still gets a chance to resist if it's a wall.
          const int corrupt_perc_chance =
              (idistance <= ground_zero_radius) ? 1000 :
              max(0, 1000 - (sqr(idistance) - sqr(ground_zero_radius)) * 700 / 45);
  
          // linear function that is at 30% at range 7, 15% at radius 20,
          // maxed to 1%. Only affects outside of range 7. For cells within los
          // that don't make the regular roll, this also gives them a 50%
          // chance to get flavor-only corruption.
          const int corrupt_flavor_chance =
              (idistance <= 7) ? (corrupt_perc_chance + 1000) / 2 :
              max(10, 380 - 150 * idistance / 13);
  
          const int roll = random2(1000);
  
          if (roll < corrupt_perc_chance && _is_grid_corruptible(*ri))
              _corrupt_square(cenv, *ri);
          else if (roll < corrupt_flavor_chance && _is_grid_corruptible(*ri))
              _corrupt_square_flavor(cenv, *ri);
      }
  }
  
  static bool _is_level_corrupted()
  {
      if (player_in_branch(BRANCH_ABYSS))
          return true;
  
      return !!env.markers.find(MAT_CORRUPTION_NEXUS);
  }
  
  bool is_level_incorruptible(bool quiet)
  {
      if (_is_level_corrupted())
      {
          if (!quiet)
              mpr("This place is already infused with evil and corruption.");
          return true;
      }
  
      return false;
  }
  
  static void _corrupt_choose_colours(corrupt_env *cenv)
  {
      colour_t colour = BLACK;
      do
      {
          colour = random_uncommon_colour();
      }
      while (colour == env.rock_colour || colour == LIGHTGREY || colour == WHITE);
      cenv->rock_colour = colour;
  
      do
      {
          colour = random_uncommon_colour();
      }
      while (colour == env.floor_colour || colour == LIGHTGREY
             || colour == WHITE);
      cenv->floor_colour = colour;
  }
  
  bool lugonu_corrupt_level(int power)
  {
      if (is_level_incorruptible())
          return false;
  
      simple_god_message("'s Hand of Corruption reaches out!");
      take_note(Note(NOTE_MESSAGE, 0, 0, make_stringf("Corrupted %s",
                level_id::current().describe().c_str()).c_str()));
      mark_corrupted_level(level_id::current());
  
      flash_view(UA_PLAYER, MAGENTA);
  
      _initialise_level_corrupt_seeds(power);
  
      corrupt_env cenv;
      _corrupt_choose_colours(&cenv);
      _corrupt_level_features(cenv);
      run_corruption_effects(300);
  
  #ifndef USE_TILE_LOCAL
      // Allow extra time for the flash to linger.
      scaled_delay(1000);
  #endif
  
      return true;
  }
  
  /// If the player has earned enough XP, spawn an exit or stairs down.
  void abyss_maybe_spawn_xp_exit()
  {
      if (!player_in_branch(BRANCH_ABYSS)
          || !you.props.exists(ABYSS_STAIR_XP_KEY)
          || you.props[ABYSS_STAIR_XP_KEY].get_int() > 0
          || !in_bounds(you.pos())
          || feat_is_critical(env.grid(you.pos())))
      {
          return;
      }
      const bool stairs = !at_branch_bottom()
                          && you.props.exists(ABYSS_SPAWNED_XP_EXIT_KEY)
                          && coinflip()
                          && you.props[ABYSS_SPAWNED_XP_EXIT_KEY].get_bool();
  
      destroy_wall(you.pos()); // fires listeners etc even if it wasn't a wall
      env.grid(you.pos()) = stairs ? DNGN_ABYSSAL_STAIR : DNGN_EXIT_ABYSS;
      big_cloud(CLOUD_TLOC_ENERGY, &you, you.pos(), 3 + random2(3), 3, 3);
      redraw_screen(); // before the force-more
      update_screen();
      mprf(MSGCH_BANISHMENT,
           "The substance of the Abyss twists violently,"
           " and a gateway leading %s appears!", stairs ? "down" : "out");
  
      you.props[ABYSS_STAIR_XP_KEY] = EXIT_XP_COST;
      you.props[ABYSS_SPAWNED_XP_EXIT_KEY] = true;
  }
  