Enable monsters to move around glass structures if they can see the

player through the walls. Don't use pathfinding to target other
monsters, only the player! Monsters of different intelligence have
different limits on the distance they may travel to circumvent an
obstacle, i.e. zombies will only use a range of 2, whereas highly 
intelligent monsters can expertly find their way through (transparent) 
labyrinths, though there's a chance they'll forget their target if 
they don't see it, so for very long and winding paths it's likely 
they don't ever arrive.

Will probably affect performance, though I did test on entire levels
turned transparent with Vitrification and things seemed to run more
or less smoothly.

Ideally, monsters should also be able to move around other obstacles
that don't affect visibility (such as water, lava, or statues) but
that is currently not possible.


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

8 files changed, 280 insertions, 46 deletions

diff --git a/crawl-ref/source/externs.h b/crawl-ref/source/externs.h
index 0400009eb0..d3b8a8b7d5 100644
--- a/crawl-ref/source/externs.h
+++ b/crawl-ref/source/externs.h
@@ -1024,6 +1024,7 @@ public:
     unsigned char target_x;
     unsigned char target_y;
     coord_def patrol_point;
+    montravel_target_type travel_target;
     std::vector<coord_def> travel_path;
     FixedVector<short, NUM_MONSTER_SLOTS> inv;
     monster_spells spells;
diff --git a/crawl-ref/source/items.cc b/crawl-ref/source/items.cc
index 354257023a..d4ff6e63fa 100644
--- a/crawl-ref/source/items.cc
+++ b/crawl-ref/source/items.cc
@@ -2247,9 +2247,6 @@ bool item_needs_autopickup(const item_def &item)
 
     std::string itemname;
     return ((Options.autopickups & (1L << item.base_type)
-#ifdef CLUA_BINDINGS
-                    && clua.callbooleanfn(true, "ch_autopickup", "u", &item)
-#endif
                     && !is_useless_item(item) && !is_inedible(item)
                 || _is_forced_autopickup(item, itemname))
             && (Options.pickup_dropped || !(item.flags & ISFLAG_DROPPED))
diff --git a/crawl-ref/source/mon-util.cc b/crawl-ref/source/mon-util.cc
index 3f5f63340b..68ccf0d090 100644
--- a/crawl-ref/source/mon-util.cc
+++ b/crawl-ref/source/mon-util.cc
@@ -2693,7 +2693,7 @@ bool monster_senior(const monsters *m1, const monsters *m2)
 monsters::monsters()
     : type(-1), hit_points(0), max_hit_points(0), hit_dice(0),
       ac(0), ev(0), speed(0), speed_increment(0), x(0), y(0),
-      target_x(0), target_y(0), patrol_point(0, 0),
+      target_x(0), target_y(0), patrol_point(0, 0), travel_target(MTRAV_NONE),
       inv(NON_ITEM), spells(), attitude(ATT_HOSTILE), behaviour(BEH_WANDER),
       foe(MHITYOU), enchantments(), flags(0L), experience(0), number(0),
       colour(BLACK), foe_memory(0), shield_blocks(0), god(GOD_NO_GOD), ghost(),
@@ -2745,7 +2745,8 @@ void monsters::reset()
         mgrd[x][y] = NON_MONSTER;
 
     x = y = 0;
-    patrol_point = coord_def(0, 0);
+    patrol_point  = coord_def(0, 0);
+    travel_target = MTRAV_NONE;
     travel_path.clear();
     ghost.reset(NULL);
 }
@@ -2767,6 +2768,7 @@ void monsters::init_with(const monsters &mon)
     target_x          = mon.target_x;
     target_y          = mon.target_y;
     patrol_point      = mon.patrol_point;
+    travel_target     = mon.travel_target;
     travel_path       = mon.travel_path;
     inv               = mon.inv;
     spells            = mon.spells;
diff --git a/crawl-ref/source/monplace.cc b/crawl-ref/source/monplace.cc
index 4a00052e01..438e03b9d2 100644
--- a/crawl-ref/source/monplace.cc
+++ b/crawl-ref/source/monplace.cc
@@ -2297,8 +2297,9 @@ monster_type summon_any_dragon(dragon_class_type dct)
 /////////////////////////////////////////////////////////////////////////////
 // monster_pathfind
 
+//#define DEBUG_PATHFIND
 monster_pathfind::monster_pathfind()
-    : mons(), target(), min_length(0), dist(), prev()
+    : mons(), target(), range(0), min_length(0), max_length(0), dist(), prev()
 {
 }
 
@@ -2306,6 +2307,12 @@ monster_pathfind::~monster_pathfind()
 {
 }
 
+void monster_pathfind::set_range(int r)
+{
+    if (r >= 0)
+        range = r;
+}
+
 // Returns true if a path was found, else false.
 bool monster_pathfind::start_pathfind(monsters *mon, coord_def dest, bool msg)
 {
@@ -2386,6 +2393,10 @@ bool monster_pathfind::calc_path_to_neighbours()
         if (!traversable(npos))
             continue;
 
+        // Ignore this grid if it takes us above the allowed distance.
+        if (range && estimated_cost(npos) > range)
+            continue;
+
         distance = dist[pos.x][pos.y] + travel_cost(npos);
         old_dist = dist[npos.x][npos.y];
 #ifdef DEBUG_PATHFIND
diff --git a/crawl-ref/source/monplace.h b/crawl-ref/source/monplace.h
index 7ff492d728..ddc2d01458 100644
--- a/crawl-ref/source/monplace.h
+++ b/crawl-ref/source/monplace.h
@@ -318,6 +318,7 @@ public:
     virtual ~monster_pathfind();
 
     // public methods
+    void set_range(int r);
     bool start_pathfind(monsters *mon, coord_def dest, bool msg = false);
     std::vector<coord_def> backtrack(void);
     std::vector<coord_def> calc_waypoints(void);
@@ -339,6 +340,9 @@ protected:
     // Our destination, and the current position we're looking at.
     coord_def start, target, pos;
 
+    // Maximum range to search between start and target. None, if zero.
+    int range;
+
     // Currently shortest and longest possible total length of the path.
     int min_length;
     int max_length;
diff --git a/crawl-ref/source/monstuff.cc b/crawl-ref/source/monstuff.cc
index 09f156a371..fbc9538e1d 100644
--- a/crawl-ref/source/monstuff.cc
+++ b/crawl-ref/source/monstuff.cc
@@ -2321,7 +2321,7 @@ static bool _choose_random_patrol_target_grid(monsters *mon)
     return (count_grids);
 }
 
-
+//#define DEBUG_PATHFIND
 //---------------------------------------------------------------
 //
 // handle_behaviour
@@ -2342,6 +2342,8 @@ static void _handle_behaviour(monsters *mon)
     bool isNeutral  = mons_neutral(mon);
     bool wontAttack = mons_wont_attack(mon);
     bool proxPlayer = mons_near(mon);
+    bool trans_wall_block = trans_wall_blocking(mon->x, mon->y);
+
 #ifdef WIZARD
     // If stealth is greater than actually possible (wizmode level)
     // pretend the player isn't there, but only for hostile monsters.
@@ -2365,6 +2367,15 @@ static void _handle_behaviour(monsters *mon)
         return;
     }
 
+    dungeon_feature_type can_move;
+    if (mons_amphibious(mons_is_zombified(mon) ?
+        mon->base_monster : mon->type))
+    {
+        can_move = DNGN_DEEP_WATER;
+    }
+    else
+        can_move = DNGN_SHALLOW_WATER;
+
     // Validate current target exists.
     if (mon->foe != MHITNOT && mon->foe != MHITYOU
         && menv[mon->foe].type == -1)
@@ -2454,7 +2465,7 @@ static void _handle_behaviour(monsters *mon)
         mon->foe = MHITYOU;
     }
 
-    // validate target again
+    // Validate target again.
     if (mon->foe != MHITNOT && mon->foe != MHITYOU
         && menv[mon->foe].type == -1)
     {
@@ -2473,8 +2484,8 @@ static void _handle_behaviour(monsters *mon)
         {
             if (mon->foe == MHITYOU)
             {
-                foe_x = you.x_pos;
-                foe_y = you.y_pos;
+                foe_x   = you.x_pos;
+                foe_y   = you.y_pos;
                 proxFoe = proxPlayer;   // take invis into account
             }
             else
@@ -2493,7 +2504,7 @@ static void _handle_behaviour(monsters *mon)
         beh_type new_beh       = mon->behaviour;
         unsigned short new_foe = mon->foe;
 
-        // take care of monster state changes
+        // Take care of monster state changes.
         switch (mon->behaviour)
         {
         case BEH_SLEEP:
@@ -2522,6 +2533,17 @@ static void _handle_behaviour(monsters *mon)
             // Foe gone out of LOS?
             if (!proxFoe)
             {
+                if (mon->foe == MHITYOU && travelling
+                    && mon->travel_target == MTRAV_PLAYER)
+                {
+#ifdef DEBUG_PATHFIND
+                    mpr("Player out of LoS... start wandering.");
+#endif
+                    new_beh = BEH_WANDER;
+                    // We've got a target, so we'll continue on our way.
+                    break;
+                }
+
                 if (patrolling)
                 {
                     new_foe = MHITNOT;
@@ -2550,7 +2572,7 @@ static void _handle_behaviour(monsters *mon)
                     {
                         if (mon->foe == MHITYOU)
                         {
-                            if (check_awaken(mon))
+                            if (random2(you.skills[SK_STEALTH]/3))
                             {
                                 mon->target_x = you.x_pos;
                                 mon->target_y = you.y_pos;
@@ -2606,6 +2628,147 @@ static void _handle_behaviour(monsters *mon)
             // by updating target x,y.
             if (mon->foe == MHITYOU)
             {
+                if (proxPlayer && !trans_wall_block)
+                {
+                    if (travelling && mon->travel_target != MTRAV_PATROL)
+                    {
+                        mon->travel_path.clear();
+                        mon->travel_target = MTRAV_NONE;
+                    }
+                }
+                else if (proxPlayer && trans_wall_block
+                         && (mon->travel_target != MTRAV_UNREACHABLE
+                             || one_chance_in(8)))
+                {
+#ifdef DEBUG_PATHFIND
+                    mprf("%s: Player out of reach! What now?",
+                         mon->name(DESC_PLAIN).c_str());
+#endif
+                    // If we're already on our way, do nothing.
+                    if (travelling && mon->travel_target == MTRAV_PLAYER)
+                    {
+#ifdef DEBUG_PATHFIND
+                        mpr("Already travelling...");
+#endif
+                        int len = mon->travel_path.size();
+                        coord_def targ = mon->travel_path[len - 1];
+                        if (grid_see_grid(targ.x, targ.y, you.x_pos, you.y_pos)
+                            && !trans_wall_blocking(targ.x, targ.y))
+                        {
+#ifdef DEBUG_PATHFIND
+                            mpr("Target still valid...");
+#endif
+                            // Current target still valid?
+                            if (mon->x == mon->travel_path[0].x
+                                && mon->y == mon->travel_path[0].y)
+                            {
+                                // Get next waypoint.
+                                mon->travel_path.erase(
+                                    mon->travel_path.begin() );
+
+                                if (!mon->travel_path.empty())
+                                {
+                                    mon->target_x = mon->travel_path[0].x;
+                                    mon->target_y = mon->travel_path[0].y;
+                                    break;
+                                }
+                            }
+                            else if (grid_see_grid(mon->x, mon->y,
+                                                   mon->travel_path[0].x,
+                                                   mon->travel_path[0].y,
+                                                   can_move))
+                            {
+                                mon->target_x = mon->travel_path[0].x;
+                                mon->target_y = mon->travel_path[0].y;
+                                break;
+                            }
+                        }
+                    }
+
+                    // Use pathfinding to find a (new) path to the player.
+                    const int dist = grid_distance(mon->x, mon->y,
+                                                   you.x_pos, you.y_pos);
+
+#ifdef DEBUG_PATHFIND
+                    mprf("Need to calculate a path... (dist = %d)", dist);
+#endif
+                    const bool native =
+                        mons_is_native_in_branch(mon, you.where_are_you);
+
+                    int range = 0;
+                    switch (mons_intel(mon->type))
+                    {
+                    case I_PLANT:
+                        range = 2;
+                        break;
+                    case I_INSECT:
+                        range = 3;
+                        break;
+                    case I_ANIMAL:
+                        range = 5;
+                        break;
+                    case I_NORMAL:
+                        range = 10;
+                        break;
+                    default:
+                        // Highly intelligent monsters can find their way
+                        // anywhere.
+                        range = 0;
+                        break;
+                    }
+
+                    if (range && native)
+                        range += 3;
+
+                    if (range > 0 && dist > range)
+                    {
+                        mon->travel_target = MTRAV_UNREACHABLE;
+#ifdef DEBUG_PATHFIND
+                        mprf("Distance too great, don't attempt pathfinding! (%s)",
+                             mon->name(DESC_PLAIN).c_str());
+#endif
+                    }
+                    else
+                    {
+#ifdef DEBUG_PATHFIND
+                        mprf("Need a path for %s from (%d, %d) to (%d, %d), "
+                             "max. dist = %d",
+                             mon->name(DESC_PLAIN).c_str(), mon->x, mon->y,
+                             you.x_pos, you.y_pos, range);
+#endif
+                        monster_pathfind mp;
+                        if (range > 0)
+                            mp.set_range(range);
+                        if (mp.start_pathfind(mon, coord_def(you.x_pos,
+                                                             you.y_pos)))
+                        {
+                            mon->travel_path = mp.calc_waypoints();
+                            if (!mon->travel_path.empty())
+                            {
+                                // Okay then, we found a path. Let's use it!
+                                mon->target_x = mon->travel_path[0].x;
+                                mon->target_y = mon->travel_path[0].y;
+                                mon->travel_target = MTRAV_PLAYER;
+                                break;
+                            }
+                            else
+                            {
+#ifdef DEBUG_PATHFIND
+                                mpr("No path found!");
+#endif
+                                mon->travel_target = MTRAV_UNREACHABLE;
+                            }
+                        }
+                        else
+                        {
+#ifdef DEBUG_PATHFIND
+                            mpr("No path found!");
+#endif
+                            mon->travel_target = MTRAV_UNREACHABLE;
+                        }
+                    }
+                }
+
                 // Sometimes, your friends will wander a bit.
                 if (isFriendly && one_chance_in(8))
                 {
@@ -2651,8 +2814,8 @@ static void _handle_behaviour(monsters *mon)
             // wandering monsters at least appear to have some sort of
             // attention span.  -- bwr
             if (mon->x == mon->target_x && mon->y == mon->target_y
-                || !travelling && (one_chance_in(20)
-                                   || testbits( mon->flags, MF_BATTY )))
+                || one_chance_in(20)
+                || testbits( mon->flags, MF_BATTY ))
             {
                 bool need_target = true;
                 if (travelling)
@@ -2666,20 +2829,37 @@ static void _handle_behaviour(monsters *mon)
                     if (mon->x == mon->travel_path[0].x
                         && mon->y == mon->travel_path[0].y)
                     {
+#ifdef DEBUG_PATHFIND
+                        mpr("Arrived at first waypoint.");
+#endif
                         // Hey, we reached our first waypoint!
                         mon->travel_path.erase( mon->travel_path.begin() );
                         if (mon->travel_path.empty())
+                        {
+#ifdef DEBUG_PATHFIND
+                            mpr("We reached the end of our path: stop "
+                                "travelling.");
+#endif
+                            mon->travel_target = MTRAV_NONE;
                             need_target = true;
-
-                        mon->target_x = mon->travel_path[0].x;
-                        mon->target_y = mon->travel_path[0].y;
+                        }
+                        else
+                        {
+                            mon->target_x = mon->travel_path[0].x;
+                            mon->target_y = mon->travel_path[0].y;
 #ifdef DEBUG_PATHFIND
-                        mprf("Next waypoint: (%d, %d)",
-                             mon->target_x, mon->target_y);
+                            mprf("Next waypoint: (%d, %d)",
+                                 mon->target_x, mon->target_y);
 #endif
+                        }
                     }
-                    else
+                    else if (!grid_see_grid(mon->x, mon->y,
+                                            mon->travel_path[0].x,
+                                            mon->travel_path[0].y, can_move))
                     {
+#ifdef DEBUG_PATHFIND
+                        mpr("Can't see waypoint grid.");
+#endif
                         // Apparently we got sidetracked a bit.
                         // Check the waypoints vector backwards and pick the
                         // first waypoint we can see.
@@ -2688,16 +2868,6 @@ static void _handle_behaviour(monsters *mon)
                         // thing to do since another path might be even
                         // *closer* to our actual target now.
 
-                        dungeon_feature_type can_move;
-                        if (mons_amphibious(mons_is_zombified(mon) ?
-                            mon->base_monster : mon->type))
-                        {
-                            can_move = DNGN_DEEP_WATER;
-                        }
-                        else
-                            can_move = DNGN_SHALLOW_WATER;
-
-
                         int erase = -1;  // Erase how many waypoints?
                         for (unsigned int i = mon->travel_path.size() - 1;
                              i >= 0; i--)
@@ -2713,8 +2883,12 @@ static void _handle_behaviour(monsters *mon)
                             }
                         }
 
-                        if (erase != -1)
+                        if (erase > 0)
                         {
+#ifdef DEBUG_PATHFIND
+                            mprf("Need to erase %d of %d waypoints.",
+                                 erase, mon->travel_path.size());
+#endif
                             // Erase all waypoints that came earlier:
                             // we don't need them anymore.
                             while (0 < erase--)
@@ -2727,8 +2901,10 @@ static void _handle_behaviour(monsters *mon)
                         {
                             // We can't reach our old path from our current
                             // position, so calculate a new path instead.
+/*
                             monster_pathfind mp;
-                            if (mp.start_pathfind(mon, mon->patrol_point, true))
+                            int len = mon->travel_path.size();
+                            if (mp.start_pathfind(mon, mon->travel_path[len-1]))
                             {
                                 mon->travel_path = mp.calc_waypoints();
                                 if (!mon->travel_path.empty())
@@ -2736,18 +2912,33 @@ static void _handle_behaviour(monsters *mon)
                                     mon->target_x = mon->travel_path[0].x;
                                     mon->target_y = mon->travel_path[0].y;
                                 }
+                                else
+                                {
+                                    mon->travel_target = MTRAV_NONE;
+                                    need_target = true;
+                                }
                             }
                             else
                             {
+*/
+                                // Or just forget about the whole thing.
                                 mon->travel_path.clear();
+                                mon->travel_target = MTRAV_NONE;
                                 need_target = true;
-                            }
+//                            }
                         }
                     }
+                    else
+                    {
+#ifdef DEBUG_PATHFIND
+                        mpr("All clear. Continue travelling.");
+#endif
+                    }
                 }
 
                 if (need_target && patrolling)
                 {
+                    need_target = false;
                     if (!_choose_random_patrol_target_grid(mon))
                     {
                         // If we couldn't find a target that is within easy
@@ -2771,6 +2962,8 @@ static void _handle_behaviour(monsters *mon)
                             {
                                 // Stop patrolling.
                                 mon->patrol_point = coord_def(0, 0);
+                                mon->travel_target = MTRAV_NONE;
+                                need_target = true;
                             }
                         }
                         else
@@ -2781,19 +2974,27 @@ static void _handle_behaviour(monsters *mon)
                             // could decide to stop patrolling if the path
                             // was too long.
                             monster_pathfind mp;
-                            if (mp.start_pathfind(mon, mon->patrol_point, true))
+                            if (mp.start_pathfind(mon, mon->patrol_point))
                             {
                                 mon->travel_path = mp.calc_waypoints();
                                 if (!mon->travel_path.empty())
                                 {
                                     mon->target_x = mon->travel_path[0].x;
                                     mon->target_y = mon->travel_path[0].y;
+                                    mon->travel_target = MTRAV_PATROL;
+                                }
+                                else
+                                {
+                                    mon->target_x = mon->patrol_point.x;
+                                    mon->target_y = mon->patrol_point.y;
                                 }
                             }
                             else
                             {
                                 // Stop patrolling.
-                                mon->patrol_point = coord_def(0, 0);
+                                mon->patrol_point  = coord_def(0, 0);
+                                mon->travel_target = MTRAV_NONE;
+                                need_target = true;
                             }
                         }
                     }
@@ -2807,7 +3008,8 @@ static void _handle_behaviour(monsters *mon)
 #endif
                     }
                 }
-                else if (need_target)
+
+                if (need_target)
                 {
 #ifdef DEBUG_PATHFIND
                     if (!testbits( mon->flags, MF_BATTY ))
@@ -2825,11 +3027,19 @@ static void _handle_behaviour(monsters *mon)
                 && one_chance_in( isSmart ? 60 : 20 ))
             {
                 new_foe = MHITNOT;
+                if (travelling && mon->travel_target != MTRAV_PATROL)
+                {
+#ifdef DEBUG_PATHFIND
+                    mpr("It's been too long! Stop travelling.");
+#endif
+                    mon->travel_path.clear();
+                    mon->travel_target = MTRAV_NONE;
+                }
             }
             break;
 
         case BEH_FLEE:
-            // check for healed
+            // Check for healed.
             if (isHealthy && !isScared)
                 new_beh = BEH_SEEK;
 
diff --git a/crawl-ref/source/tags.cc b/crawl-ref/source/tags.cc
index 77f024c952..caa83181df 100644
--- a/crawl-ref/source/tags.cc
+++ b/crawl-ref/source/tags.cc
@@ -1769,6 +1769,8 @@ static void marshall_monster(writer &th, const monsters &m)
     marshallByte(th, m.target_x);
     marshallByte(th, m.target_y);
     marshallCoord(th, m.patrol_point);
+    int help = m.travel_target;
+    marshallByte(th, help);
 
     // monster pathfinding (TAG_MINOR_PATHFIND)
     marshallShort(th, m.travel_path.size());
@@ -2040,6 +2042,12 @@ static void unmarshall_monster(reader &th, monsters &m)
     if (_tag_minor_version >= TAG_MINOR_MPATROL)
         unmarshallCoord(th, m.patrol_point);
 
+    if (_tag_minor_version >= TAG_MINOR_TRTARGET)
+    {
+        int help = unmarshallByte(th);
+        m.travel_target = static_cast<montravel_target_type>(help);
+    }
+
     if (_tag_minor_version >= TAG_MINOR_PATHFIND)
     {
         const int len = unmarshallShort(th);
diff --git a/crawl-ref/source/tags.h b/crawl-ref/source/tags.h
index 9aea5c2ce1..dfe48b17e6 100644
--- a/crawl-ref/source/tags.h
+++ b/crawl-ref/source/tags.h
@@ -50,15 +50,16 @@ enum tag_major_version
 // Minor version will be reset to zero when major version changes.
 enum tag_minor_version
 {
-    TAG_MINOR_PIETY    = 2,     // Added piety_hysteresis
-    TAG_MINOR_QUIVER   = 3,     // Added quiver
-    TAG_MINOR_MAPMARK  = 4,     // Added sizes to map markers
-    TAG_MINOR_MONNAM   = 5,     // Monsters get individual names
-    TAG_MINOR_MONBASE  = 6,     // Zombie base monster gets its own field.
-    TAG_MINOR_FPICKUP  = 7,     // Added pickup option for allied monsters.
-    TAG_MINOR_MPATROL  = 8,     // Added monster patrol points.
-    TAG_MINOR_PATHFIND = 9,     // Added monster pathfinding.
-    TAG_MINOR_VERSION  = 9      // Current version
+    TAG_MINOR_PIETY    =  2,     // Added piety_hysteresis
+    TAG_MINOR_QUIVER   =  3,     // Added quiver
+    TAG_MINOR_MAPMARK  =  4,     // Added sizes to map markers
+    TAG_MINOR_MONNAM   =  5,     // Monsters get individual names
+    TAG_MINOR_MONBASE  =  6,     // Zombie base monster gets its own field.
+    TAG_MINOR_FPICKUP  =  7,     // Added pickup option for allied monsters.
+    TAG_MINOR_MPATROL  =  8,     // Added monster patrol points.
+    TAG_MINOR_PATHFIND =  9,     // Added monster pathfinding.
+    TAG_MINOR_TRTARGET = 10,     // Added travel target.
+    TAG_MINOR_VERSION  = 10      // Current version
 };