Items can now fall through shaft traps (trap doors). The code is rather

simplistic, and it's not currently possible to make a "baited" shaft;
also, there is no threshold weight, so even a single dart will open up
(and thus reveal) a shaft trap.  Breaks savefile compatibility.

Monsters which fall through a shaft now show up 100% of the time on the
player's next visit to the shaft's destination level.  Also, the monster is
placed close to the spot where the player would end up if s/he went through
the same shaft.


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

13 files changed, 313 insertions, 41 deletions

diff --git a/crawl-ref/source/abyss.cc b/crawl-ref/source/abyss.cc
index a3ca3b9a77..a553c4af6f 100644
--- a/crawl-ref/source/abyss.cc
+++ b/crawl-ref/source/abyss.cc
@@ -439,6 +439,7 @@ void area_shift(void)
 
     // And allow monsters in transit another chance to return.
     place_transiting_monsters();
+    place_transiting_items();
 }
 
 void save_abyss_uniques()
@@ -539,6 +540,7 @@ void abyss_teleport( bool new_area )
                             DNGN_FLOOR, DNGN_ALTAR_LUGONU, 50 );
 
     place_transiting_monsters();
+    place_transiting_items();
 }
 
 //////////////////////////////////////////////////////////////////////////////
diff --git a/crawl-ref/source/acr.cc b/crawl-ref/source/acr.cc
index ebe51b8677..da9eeefe63 100644
--- a/crawl-ref/source/acr.cc
+++ b/crawl-ref/source/acr.cc
@@ -2742,6 +2742,21 @@ static void check_banished()
    at some point.
 */
 
+static void check_shafts()
+{
+    for (int i = 0; i < MAX_TRAPS; i++)
+    {
+        trap_struct &trap = env.trap[i];
+
+        if (trap.type != TRAP_SHAFT)
+            continue;
+
+        ASSERT(in_bounds(trap.x, trap.y));
+
+        handle_items_on_shaft(trap.x, trap.y, true);
+    }
+}
+
 static void world_reacts()
 {
     crawl_state.clear_god_acting();
@@ -2756,6 +2771,8 @@ static void world_reacts()
     }
     check_banished();
 
+    check_shafts();
+
     run_environment_effects();
 
     if ( !you.cannot_act() && !you.mutation[MUT_BLURRY_VISION] &&
diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc
index 8b0df8335c..f90c49cb35 100644
--- a/crawl-ref/source/dungeon.cc
+++ b/crawl-ref/source/dungeon.cc
@@ -7343,11 +7343,11 @@ inline static bool dgn_square_travel_ok(const coord_def &c)
 }
 
 // Fill travel_point_distance out from all stone stairs on the level.
-static coord_def dgn_find_closest_to_stone_stairs()
+static coord_def dgn_find_closest_to_stone_stairs(coord_def base_pos)
 {
     memset(travel_point_distance, 0, sizeof(travel_distance_grid_t));
     init_travel_terrain_check(false);
-    nearest_point np(you.pos());
+    nearest_point np(base_pos);
     for (int y = 0; y < GYM; ++y)
         for (int x = 0; x < GXM; ++x)
             if (!travel_point_distance[x][y] && grid_is_stone_stair(grd[x][y]))
@@ -7377,7 +7377,7 @@ static coord_def dgn_find_labyrinth_entry_point()
 }
 
 coord_def dgn_find_nearby_stair(dungeon_feature_type stair_to_find,
-                                bool find_closest)
+                                coord_def base_pos, bool find_closest)
 {
 #ifdef DEBUG_DIAGNOSTICS
     mprf(MSGCH_DIAGNOSTICS,
@@ -7390,7 +7390,7 @@ coord_def dgn_find_nearby_stair(dungeon_feature_type stair_to_find,
     if (stair_to_find == DNGN_ROCK_STAIRS_UP
         || stair_to_find == DNGN_ROCK_STAIRS_DOWN)
     {
-        const coord_def pos(dgn_find_closest_to_stone_stairs());
+        const coord_def pos(dgn_find_closest_to_stone_stairs(base_pos));
         if (in_bounds(pos))
             return (pos);
     }
@@ -7423,8 +7423,8 @@ coord_def dgn_find_nearby_stair(dungeon_feature_type stair_to_find,
     }
 
     // scan around the player's position first
-    int basex = you.x_pos;
-    int basey = you.y_pos;
+    int basex = base_pos.x;
+    int basey = base_pos.y;
 
     // check for illegal starting point
     if ( !in_bounds(basex, basey) )
diff --git a/crawl-ref/source/dungeon.h b/crawl-ref/source/dungeon.h
index 1b903a8744..c6ee2a3b6f 100644
--- a/crawl-ref/source/dungeon.h
+++ b/crawl-ref/source/dungeon.h
@@ -316,7 +316,7 @@ void place_spec_shop(int level_number, int shop_x, int shop_y,
                      int force_s_type, bool representative = false);
 bool unforbidden(const coord_def &c, unsigned mask);
 coord_def dgn_find_nearby_stair(dungeon_feature_type stair_to_find,
-                                bool find_closest);
+                                coord_def base_pos, bool find_closest);
 
 class mons_spec;
 bool dgn_place_monster(const mons_spec &mspec,
diff --git a/crawl-ref/source/files.cc b/crawl-ref/source/files.cc
index 8376ce6eae..32b75a209b 100644
--- a/crawl-ref/source/files.cc
+++ b/crawl-ref/source/files.cc
@@ -758,7 +758,7 @@ static void place_player_on_stair(branch_type old_branch,
     
     const coord_def where_to_go =
         dgn_find_nearby_stair(static_cast<dungeon_feature_type>(stair_taken),
-                              find_first);
+                              you.pos(), find_first);
     you.moveto(where_to_go);
 }
 
@@ -1037,7 +1037,10 @@ bool load( dungeon_feature_type stair_taken, load_mode_type load_mode,
 
     // Load monsters in transit.
     if (load_mode == LOAD_ENTER_LEVEL)
+    {
         place_transiting_monsters();
+        place_transiting_items();
+    }
 
     redraw_all();
 
diff --git a/crawl-ref/source/misc.cc b/crawl-ref/source/misc.cc
index fbf60e9cee..bc6b0a1b9e 100644
--- a/crawl-ref/source/misc.cc
+++ b/crawl-ref/source/misc.cc
@@ -1092,6 +1092,7 @@ void down_stairs( int old_level, dungeon_feature_type force_stair,
         {
             if (you.flight_mode() == FL_FLY && !force_stair)
                 mpr("You dive down through the shaft.");
+            handle_items_on_shaft(you.x_pos, you.y_pos, false);
         }
         else
             climb_message(stair_find, false, old_level_type);
diff --git a/crawl-ref/source/mon-util.cc b/crawl-ref/source/mon-util.cc
index f08669745c..5352120230 100644
--- a/crawl-ref/source/mon-util.cc
+++ b/crawl-ref/source/mon-util.cc
@@ -5014,6 +5014,8 @@ bool monsters::do_shaft()
                 else
                     mpr("A shaft briefly opens up in the floor!");
             }
+
+            handle_items_on_shaft(this->x, this->y, false);
             return (false);
         }
     }
@@ -5028,6 +5030,8 @@ bool monsters::do_shaft()
     if (simple_monster_message(this, " falls through a shaft!"))
         reveal = true;;
 
+    handle_items_on_shaft(this->x, this->y, false);
+
     // Monster is no longer on this level
     destroy_inventory();
     monster_cleanup(this);
diff --git a/crawl-ref/source/mtransit.cc b/crawl-ref/source/mtransit.cc
index 8361f015bd..20c5510bc1 100644
--- a/crawl-ref/source/mtransit.cc
+++ b/crawl-ref/source/mtransit.cc
@@ -7,20 +7,25 @@
  */
 
 #include "AppHdr.h"
-
 #include "mtransit.h"
+
+#include "dungeon.h"
 #include "items.h"
+#include "monplace.h"
 #include "mon-util.h"
+#include "monstuff.h"
+#include "randart.h"
 #include "stuff.h"
 
 #define MAX_LOST 100
 
 monsters_in_transit the_lost_ones;
+items_in_transit    transiting_items;
 
 static void level_place_lost_monsters(m_transit_list &m);
 static void level_place_followers(m_transit_list &m);
 
-static void cull_lost(m_transit_list &mlist, int how_many)
+static void cull_lost_mons(m_transit_list &mlist, int how_many)
 {
     // First pass, drop non-uniques.
     for (m_transit_list::iterator i = mlist.begin(); i != mlist.end(); )
@@ -41,6 +46,53 @@ static void cull_lost(m_transit_list &mlist, int how_many)
         mlist.erase( mlist.begin() );
 }
 
+static void cull_lost_items(i_transit_list &ilist, int how_many)
+{
+    // First pass, drop non-artifacts.
+    for (i_transit_list::iterator i = ilist.begin(); i != ilist.end(); )
+    {
+        i_transit_list::iterator finger = i++;
+        if (!is_artefact(*finger))
+        {
+            ilist.erase(finger);
+
+            if (--how_many <= MAX_LOST)
+                return;
+        }
+    }
+
+    // Second pass, drop randarts.
+    for (i_transit_list::iterator i = ilist.begin(); i != ilist.end(); )
+    {
+        i_transit_list::iterator finger = i++;
+        if (is_random_artefact(*finger))
+        {
+            ilist.erase(finger);
+
+            if (--how_many <= MAX_LOST)
+                return;
+        }
+    }
+
+    // Third pass, drop unrandarts.
+    for (i_transit_list::iterator i = ilist.begin(); i != ilist.end(); )
+    {
+        i_transit_list::iterator finger = i++;
+        if (is_unrandom_artefact(*finger))
+        {
+            ilist.erase(finger);
+
+            if (--how_many <= MAX_LOST)
+                return;
+        }
+    }
+
+    // If we're still over the limit (unlikely), just lose
+    // the old ones.
+    while (how_many-- > MAX_LOST && !ilist.empty())
+        ilist.erase( ilist.begin() );
+}
+
 m_transit_list *get_transit_list(const level_id &lid)
 {
     monsters_in_transit::iterator i = the_lost_ones.find(lid);
@@ -59,7 +111,7 @@ void add_monster_to_transit(const level_id &lid, const monsters &m)
 
     const int how_many = mlist.size();
     if (how_many > MAX_LOST)
-        cull_lost(mlist, how_many);
+        cull_lost_mons(mlist, how_many);
 }
 
 void place_lost_ones(void (*placefn)(m_transit_list &ml))
@@ -100,8 +152,9 @@ static void level_place_lost_monsters(m_transit_list &m)
     {
         m_transit_list::iterator mon = i++;
 
-        // Transiting monsters have a 50% chance of being placed.
-        if (coinflip())
+        // Monsters transiting to the Abyss have a 50% chance of being
+        // placed, otherwise a 100% chance.
+        if (you.level_type == LEVEL_ABYSS && coinflip())
             continue;
 
         if (place_lost_monster(*mon))
@@ -120,6 +173,55 @@ static void level_place_followers(m_transit_list &m)
     }
 }
 
+void add_item_to_transit(const level_id &lid, const item_def &i)
+{
+    i_transit_list &ilist = transiting_items[lid];
+    ilist.push_back(i);
+
+#ifdef DEBUG_DIAGNOSTICS
+    mprf(MSGCH_DIAGNOSTICS, "Item in transit: %s",
+         i.name(DESC_PLAIN).c_str());
+#endif
+
+    const int how_many = ilist.size();
+    if (how_many > MAX_LOST)
+        cull_lost_items(ilist, how_many);
+}
+
+void place_transiting_items()
+{
+    level_id c = level_id::current();
+
+    items_in_transit::iterator i = transiting_items.find(c);
+    if (i == transiting_items.end())
+        return;
+
+    i_transit_list &ilist = i->second;
+    i_transit_list keep;
+    i_transit_list::iterator item;
+
+    for (item = ilist.begin(); item != ilist.end(); item++)
+    {
+        coord_def pos(item->x, item->y);
+
+        if (!in_bounds(pos))
+        {
+            pos.x = random_range(X_BOUND_1 + 1, X_BOUND_2 - 1);
+            pos.y = random_range(Y_BOUND_1 + 1, Y_BOUND_2 - 1);
+        }
+           
+        const coord_def where_to_go =
+            dgn_find_nearby_stair(DNGN_ROCK_STAIRS_DOWN, pos, true);
+
+        // List of items we couldn't place
+        if (!copy_item_to_grid(*item, where_to_go.x, where_to_go.y))
+            keep.push_back(*item);
+    }
+
+    // Only unplaceable items are kept in list.
+    ilist = keep;
+}
+
 //////////////////////////////////////////////////////////////////////////
 // follower
 
@@ -141,12 +243,40 @@ bool follower::place(bool near_player)
 {
     for (int i = 0; i < MAX_MONSTERS - 5; ++i)
     {
+        // Find first empty slot in menv and copy monster into it.
         monsters &m = menv[i];
         if (m.alive())
             continue;
-
         m = mons;
-        if (m.find_place_to_live(near_player))
+
+        bool placed = false;
+
+        // In certain instances (currently, falling through a shaft)
+        // try to place monster a close as possible to its previous
+        // <x,y> coordinates.
+        if (!near_player && you.level_type == LEVEL_DUNGEON
+            && in_bounds(m.pos()))
+        {
+            const coord_def where_to_go =
+                dgn_find_nearby_stair(DNGN_ROCK_STAIRS_DOWN,
+                                      m.pos(), true);
+
+            if (monster_habitable_grid(&m, grd(where_to_go)))
+            {
+                if (where_to_go == you.pos())
+                    near_player = true;
+                else
+                {
+                    mgrd[where_to_go.x][where_to_go.y] = monster_index(&m);
+                    placed = true;
+                }
+            }
+        }
+
+        if (!placed)
+            placed = m.find_place_to_live(near_player);
+
+        if (placed)
         {
 #ifdef DEBUG_DIAGNOSTICS
             mprf(MSGCH_DIAGNOSTICS, "Placed follower: %s",
diff --git a/crawl-ref/source/mtransit.h b/crawl-ref/source/mtransit.h
index aebea8806d..4726922118 100644
--- a/crawl-ref/source/mtransit.h
+++ b/crawl-ref/source/mtransit.h
@@ -29,13 +29,20 @@ struct follower
 typedef std::list<follower> m_transit_list;
 typedef std::map<level_id, m_transit_list> monsters_in_transit;
 
+typedef std::list<item_def> i_transit_list;
+typedef std::map<level_id, i_transit_list> items_in_transit;
+
 extern monsters_in_transit the_lost_ones;
+extern items_in_transit    transiting_items;
 
 m_transit_list *get_transit_list(const level_id &where);
 void add_monster_to_transit(const level_id &dest, const monsters &m);
+void add_item_to_transit(const level_id &dest, const item_def &i);
 
 // Places (some of the) monsters eligible to be placed on this level.
 void place_transiting_monsters();
 void place_followers();
 
+void place_transiting_items();
+
 #endif
diff --git a/crawl-ref/source/player.cc b/crawl-ref/source/player.cc
index 53fdbf656f..65917af34b 100644
--- a/crawl-ref/source/player.cc
+++ b/crawl-ref/source/player.cc
@@ -5144,31 +5144,7 @@ bool actor::will_trigger_shaft() const
 
 level_id actor::shaft_dest() const
 {
-    if (you.level_type != LEVEL_DUNGEON)
-        return level_id::current();
-
-    level_id lev        = level_id::current();
-    int      curr_depth = subdungeon_depth(you.where_are_you, you.your_level);
-
-    lev.depth += ((pos().x + pos().y) % 3) + 1;
-
-    if (lev.depth > your_branch().depth)
-        lev.depth = your_branch().depth;
-
-    if (lev.depth == curr_depth)
-        return lev;
-
-    // Only shafts on the level immediately above a dangerous branch
-    // bottom will take you to that dangerous bottom, and shafts can't
-    // be created during level generation time.
-    if (your_branch().dangerous_bottom_level
-        && lev.depth == your_branch().depth
-        && (your_branch().depth - curr_depth) > 1)
-    {
-        lev.depth--;
-    }
-
-    return lev;
+    return generic_shaft_dest(pos());
 }
 
 bool actor::airborne() const
@@ -6521,6 +6497,7 @@ bool player::do_shaft()
         if (airborne() || total_weight() == 0)
         {
             mpr("A shaft briefly opens up underneath you!");
+            handle_items_on_shaft(you.x_pos, you.y_pos, false);
             return (true);
         }
 
diff --git a/crawl-ref/source/tags.cc b/crawl-ref/source/tags.cc
index c16e20005f..53f856911f 100644
--- a/crawl-ref/source/tags.cc
+++ b/crawl-ref/source/tags.cc
@@ -106,10 +106,12 @@ static void tag_construct_you(struct tagHeader &th);
 static void tag_construct_you_items(struct tagHeader &th);
 static void tag_construct_you_dungeon(struct tagHeader &th);
 static void tag_construct_lost_monsters(tagHeader &th);
+static void tag_construct_lost_items(tagHeader &th);
 static void tag_read_you(struct tagHeader &th, char minorVersion);
 static void tag_read_you_items(struct tagHeader &th, char minorVersion);
 static void tag_read_you_dungeon(struct tagHeader &th);
 static void tag_read_lost_monsters(tagHeader &th, int minorVersion);
+static void tag_read_lost_items(tagHeader &th, int minorVersion);
 
 static void tag_construct_level(struct tagHeader &th);
 static void tag_construct_level_items(struct tagHeader &th);
@@ -586,6 +588,7 @@ void tag_construct(struct tagHeader &th, int tagID)
             break;
         case TAG_LOST_MONSTERS:
             tag_construct_lost_monsters(th);
+            tag_construct_lost_items(th);
             break;
         default:
             // I don't know how to make that!
@@ -687,6 +690,7 @@ int tag_read(FILE *fp, char minorVersion)
             break;
         case TAG_LOST_MONSTERS:
             tag_read_lost_monsters(th, minorVersion);
+            tag_read_lost_items(th, minorVersion);
             break;
         default:
             // I don't know how to read that!
@@ -1085,6 +1089,17 @@ static void marshall_follower_list(tagHeader &th, const m_transit_list &mlist)
     }
 }
 
+static void marshall_item_list(tagHeader &th, const i_transit_list &ilist)
+{
+    marshallShort( th, ilist.size() );
+    
+    for (i_transit_list::const_iterator ii = ilist.begin();
+         ii != ilist.end(); ++ii)
+    {
+        marshallItem( th, *ii );
+    }
+}
+
 static m_transit_list unmarshall_follower_list(tagHeader &th)
 {
     m_transit_list mlist;
@@ -1101,12 +1116,34 @@ static m_transit_list unmarshall_follower_list(tagHeader &th)
     return (mlist);
 }
 
+static i_transit_list unmarshall_item_list(tagHeader &th)
+{
+    i_transit_list ilist;
+    
+    const int size = unmarshallShort(th);
+
+    for (int i = 0; i < size; ++i)
+    {
+        item_def item;
+        unmarshallItem(th, item);
+        ilist.push_back(item);
+    }
+
+    return (ilist);
+}
+
 static void tag_construct_lost_monsters(tagHeader &th)
 {
     marshallMap( th, the_lost_ones, marshall_level_id,
                  marshall_follower_list );
 }
 
+static void tag_construct_lost_items(tagHeader &th)
+{
+    marshallMap( th, transiting_items, marshall_level_id,
+                 marshall_item_list );
+}
+
 static void tag_read_you(struct tagHeader &th, char minorVersion)
 {
     char buff[20];      // For birth date
@@ -1467,6 +1504,14 @@ static void tag_read_lost_monsters(tagHeader &th, int minorVersion)
                   unmarshall_level_id, unmarshall_follower_list);
 }
 
+static void tag_read_lost_items(tagHeader &th, int minorVersion)
+{
+    transiting_items.clear();
+    
+    unmarshallMap(th, transiting_items,
+                  unmarshall_level_id, unmarshall_item_list);
+}
+
 // ------------------------------- level tags ---------------------------- //
 
 static void tag_construct_level(struct tagHeader &th)
diff --git a/crawl-ref/source/traps.cc b/crawl-ref/source/traps.cc
index db6d7b1f49..78bfa5c997 100644
--- a/crawl-ref/source/traps.cc
+++ b/crawl-ref/source/traps.cc
@@ -25,6 +25,7 @@
 #include "misc.h"
 #include "mon-util.h"
 #include "monstuff.h"
+#include "mtransit.h"
 #include "ouch.h"
 #include "place.h"
 #include "player.h"
@@ -960,6 +961,89 @@ bool is_valid_shaft_level(const level_id &place)
     return ((branch.depth - place.depth) >= min_delta);
 }
 
+level_id generic_shaft_dest(level_pos lpos)
+{
+    level_id  lid = lpos.id;
+    coord_def pos = lpos.pos;
+
+    if (lid.level_type != LEVEL_DUNGEON)
+        return lid;
+
+    int      curr_depth = lid.depth;
+    Branch   &branch    = branches[lid.branch];
+
+    lid.depth += ((pos.x + pos.y) % 3) + 1;
+
+    if (lid.depth > branch.depth)
+        lid.depth = branch.depth;
+
+    if (lid.depth == curr_depth)
+        return lid;
+
+    // Only shafts on the level immediately above a dangerous branch
+    // bottom will take you to that dangerous bottom, and shafts can't
+    // be created during level generation time.
+    if (branch.dangerous_bottom_level
+        && lid.depth == branch.depth
+        && (branch.depth - curr_depth) > 1)
+    {
+        lid.depth--;
+    }
+
+    return lid;
+}
+
+level_id generic_shaft_dest(coord_def pos)
+{
+    return generic_shaft_dest(level_pos(level_id::current(), pos));
+}
+
+void handle_items_on_shaft(int x, int y, bool open_shaft)
+{
+    if (!is_valid_shaft_level())
+        return;
+
+    coord_def pos(x, y);
+    level_id  dest = generic_shaft_dest(pos);
+
+    if (dest == level_id::current())
+        return;
+
+    int o = igrd(pos);
+
+    if (o == NON_ITEM)
+        return;
+
+    igrd(pos) = NON_ITEM;
+
+    if (is_terrain_seen(pos) && open_shaft)
+    {
+        mpr("A shaft opens up in the floor!");
+        grd(pos) = DNGN_TRAP_NATURAL;
+    }
+
+    while (o != NON_ITEM)
+    {
+        int next = mitm[o].link;
+
+        if (is_valid_item( mitm[o] ))
+        {
+            if (is_terrain_seen(pos))
+            {
+                mprf("%s falls through the shaft.",
+                     mitm[o].name(DESC_INVENTORY).c_str());
+            }
+            add_item_to_transit(dest, mitm[o]);
+
+            mitm[o].base_type = OBJ_UNASSIGNED;
+            mitm[o].quantity = 0;
+            mitm[o].props.clear();
+        }
+
+        o = next;
+    }
+}
+
 static int num_traps_default(int level_number, const level_id &place)
 {
     return random2avg(9, 2);
diff --git a/crawl-ref/source/traps.h b/crawl-ref/source/traps.h
index 1853cf5313..793789a935 100644
--- a/crawl-ref/source/traps.h
+++ b/crawl-ref/source/traps.h
@@ -64,7 +64,9 @@ dungeon_feature_type trap_category(trap_type type);
 int trap_at_xy(int x, int y);
 trap_type trap_type_at_xy(int x, int y);
 
-bool is_valid_shaft_level(const level_id &place = level_id::current());
+bool     is_valid_shaft_level(const level_id &place = level_id::current());
+level_id generic_shaft_dest(coord_def pos);
+void     handle_items_on_shaft(int x, int y, bool open_shaft);
 
 int       num_traps_for_place(int level_number = -1,
                               const level_id &place = level_id::current());