Enable pathfinding for patrolling monsters who lost their patrol point.

Fixed patrol definitions in maps not actually working.

Tested both by teleporting the minotaur in a labyrinth. About 50 turns
later it arrived back in its lair. :)

Since the minotaur proved to have a high magic resistance, it had plenty
of time to loot the stash at the labyrinth entrance once I'd woken it 
before I finally managed to teleport it away (in wizmode you can force 
monsters not noticing you).

This resulted in 
  "A minotaur, wielding the demon trident "Suyn Oma", and wearing a heavily
   runed ring mail."   o_O

It had also picked up a scroll and a wand. Ouch... (but cool!)


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

12 files changed, 260 insertions, 54 deletions

diff --git a/crawl-ref/source/abyss.cc b/crawl-ref/source/abyss.cc
index 67c4f1dfe0..60b508a33b 100644
--- a/crawl-ref/source/abyss.cc
+++ b/crawl-ref/source/abyss.cc
@@ -68,7 +68,7 @@ static bool place_feature_near( const coord_def &centre,
 }
 
 // Public for abyss generation.
-void generate_abyss(bool spatter)
+void generate_abyss()
 {
     int i, j;                   // loop variables
     int temp_rand;              // probability determination {dlb}
diff --git a/crawl-ref/source/abyss.h b/crawl-ref/source/abyss.h
index ea4e28eb84..61108bae8f 100644
--- a/crawl-ref/source/abyss.h
+++ b/crawl-ref/source/abyss.h
@@ -19,7 +19,7 @@
 /* ***********************************************************************
  * called from: dungeon
  * *********************************************************************** */
-void generate_abyss(bool spatter = false);
+void generate_abyss(void);
 
 
 // last updated 12may2000 {dlb}
diff --git a/crawl-ref/source/dat/lab.des b/crawl-ref/source/dat/lab.des
index 4fb8687c83..fea34066ef 100644
--- a/crawl-ref/source/dat/lab.des
+++ b/crawl-ref/source/dat/lab.des
@@ -51,7 +51,7 @@ ENDMAP
 # Watery exit 
 NAME: labyrinth_watery
 TAGS: minotaur generate_loot no_pool_fixup allow_dup
-MONS: minotaur
+MONS: patrolling minotaur
 SHUFFLE: def
 SUBST: d=~, e=~, f=., c:vvc
 MAP
@@ -70,7 +70,7 @@ ENDMAP
 # Green exit
 NAME: labyrinth_green
 TAGS: minotaur generate_loot allow_dup
-MONS: minotaur
+MONS: patrolling minotaur
 MAP
 ........
 .bbbbbb.
@@ -83,7 +83,7 @@ ENDMAP
 # Spiral exit
 NAME: labyrinth_spiral
 TAGS: minotaur generate_loot allow_dup
-MONS: minotaur
+MONS: patrolling minotaur
 SUBST: c : cvz, z = vc
 MAP
 ............
@@ -103,7 +103,7 @@ ENDMAP
 # Hidden exit, and trapped loot
 NAME: labyrinth_hidden_loot
 TAGS: minotaur generate_loot allow_dup
-MONS: minotaur
+MONS: patrolling minotaur
 NSUBST: d = 1 / %
 SUBST: c : cvv
 MAP
@@ -129,7 +129,7 @@ SHUFFLE: def, ghi, klm
 SUBST: d : c, e : ., f : c
 SUBST: g : c, h : ., i : c
 SUBST: k = <, l = ., m = .
-KMONS: < = minotaur
+KMONS: < = patrolling minotaur
 KFEAT: < = <
 SUBST: c : vvc
 
@@ -158,7 +158,7 @@ ENDMAP
 # Trapped exits - this is evil!
 NAME:    labyrinth_trapped
 TAGS:    minotaur generate_loot allow_dup
-MONS:    minotaur
+MONS:    patrolling minotaur
 NSUBST:  g = 1:. / *:c
 NSUBST:  D = 1:. / *:D
 KFEAT:   d = axe trap / dart trap / needle trap / blade trap
@@ -192,7 +192,7 @@ SUBST: g=., h=., i=., j=., k=., l=., m=.
 SUBST: G=., H=., I=., J=., K=., L=., M=.
 SUBST: Y=*, Z=*
 KFEAT: X = <
-KMONS: X = minotaur
+KMONS: X = patrolling minotaur
 KFEAT: S = granite_statue
 CHANCE: 2
 MAP
diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc
index e3176ed262..d6d9dabdc2 100644
--- a/crawl-ref/source/dungeon.cc
+++ b/crawl-ref/source/dungeon.cc
@@ -1824,7 +1824,7 @@ static builder_rc_type _builder_by_type(int level_number, char level_type)
 
     if (level_type == LEVEL_ABYSS)
     {
-        generate_abyss(true);
+        generate_abyss();
         return (BUILD_SKIP);
     }
 
diff --git a/crawl-ref/source/externs.h b/crawl-ref/source/externs.h
index 6a04a5081b..a5b7c8dae0 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;
+    std::vector<coord_def> travel_path;
     FixedVector<short, NUM_MONSTER_SLOTS> inv;
     monster_spells spells;
     mon_attitude_type attitude;
@@ -1100,6 +1101,7 @@ public:
 
     void timeout_enchantments(int levels);
 
+    bool is_travelling() const;
     bool is_patrolling() const;
     bool needs_transit() const;
     void set_transit(const level_id &destination);
diff --git a/crawl-ref/source/misc.cc b/crawl-ref/source/misc.cc
index d024069bb8..40ffda768f 100644
--- a/crawl-ref/source/misc.cc
+++ b/crawl-ref/source/misc.cc
@@ -1203,12 +1203,35 @@ void generate_random_blood_spatter_on_level()
 {
     int cx, cy;
     int startprob;
-    int max_cluster = 7 + random2(9);
+
+    // startprob is used to initialize the chance for neighbours being
+    // spattered, which will be decreased by 1 per recursion round.
+    // We then use one_chance_in(chance) to determine whether to spatter a
+    // given grid or not. Thus, startprob = 1 means that initially all
+    // surrounding grids will be spattered (3x3), and the _higher_ startprob
+    // the _lower_ the overall chance for spattering and the _smaller_ the
+    // bloodshed area.
+
+    const int max_cluster = 7 + random2(9);
+
+    // Lower chances for large bloodshed areas if we have many clusters,
+    // but increase chances if we have few.
+    // Chances for startprob are [1..3] for 7-9 clusters,
+    //                       ... [1..4] for 10-12 clusters, and
+    //                       ... [2..5] for 13-15 clusters.
+
+    int min_prob = 1;
+    int max_prob = 4;
+    if (max_cluster < 10)
+        max_prob--;
+    else if (max_cluster > 12)
+        min_prob++;
+
     for (int i = 0; i < max_cluster; i++)
     {
         cx = 10 + random2(GXM - 10);
         cy = 10 + random2(GYM - 10);
-        startprob = 1 + random2(4);
+        startprob = min_prob + random2(max_prob);
 
         if (allow_bleeding_on_square(cx, cy))
             env.map[cx][cy].property = FPROP_BLOODY;
diff --git a/crawl-ref/source/mon-util.cc b/crawl-ref/source/mon-util.cc
index bfb310aab0..209220e22f 100644
--- a/crawl-ref/source/mon-util.cc
+++ b/crawl-ref/source/mon-util.cc
@@ -2690,12 +2690,13 @@ 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), 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(),
+      target_x(0), target_y(0), patrol_point(0, 0),
+      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(),
       seen_context("")
 {
+    travel_path.clear();
 }
 
 // Empty destructor to keep auto_ptr happy with incomplete ghost_demon type.
@@ -2742,6 +2743,7 @@ void monsters::reset()
 
     x = y = 0;
     patrol_point = coord_def(0, 0);
+    travel_path.clear();
     ghost.reset(NULL);
 }
 
@@ -2762,6 +2764,7 @@ void monsters::init_with(const monsters &mon)
     target_x          = mon.target_x;
     target_y          = mon.target_y;
     patrol_point      = mon.patrol_point;
+    travel_path       = mon.travel_path;
     inv               = mon.inv;
     spells            = mon.spells;
     attitude          = mon.attitude;
@@ -4662,6 +4665,11 @@ void monsters::destroy_inventory()
     }
 }
 
+bool monsters::is_travelling() const
+{
+    return (!travel_path.empty());
+}
+
 bool monsters::is_patrolling() const
 {
     return (patrol_point != coord_def(0, 0));
diff --git a/crawl-ref/source/monplace.cc b/crawl-ref/source/monplace.cc
index f0f56b6fa0..7787b5c63c 100644
--- a/crawl-ref/source/monplace.cc
+++ b/crawl-ref/source/monplace.cc
@@ -691,6 +691,16 @@ int place_monster(mgen_data mg, bool force_pos)
     if (id == -1)
         return (id);
 
+    monsters *mon = &menv[id];
+    if (mg.needs_patrol_point())
+    {
+        mon->patrol_point = coord_def(mon->x, mon->y);
+#ifdef DEBUG_PATHFIND
+        mprf("Monster %s is patrolling around (%d, %d).",
+             mon->name(DESC_PLAIN).c_str(), mon->x, mon->y);
+#endif
+    }
+
     // Message to player from stairwell/gate appearance.
     if (see_grid(mg.pos) && mg.proximity == PROX_NEAR_STAIRS)
     {
@@ -1890,9 +1900,6 @@ int mons_place( mgen_data mg )
             creation->add_ench(ENCH_INVIS);
     }
 
-    if (mg.needs_patrol_point())
-        creation->patrol_point = coord_def(creation->x, creation->y);
-
     return (mid);
 }
 
@@ -2302,7 +2309,6 @@ bool monster_pathfind::start_pathfind(monsters *mon, coord_def dest, bool msg)
 // Returns true as soon as we encounter the target.
 bool monster_pathfind::calc_path_to_neighbours()
 {
-//    mprf("in calc_path_to_neighbours() for (%d,%d)", pos.x, pos.y);
     coord_def npos;
     int distance, old_dist, total;
 
@@ -2315,7 +2321,9 @@ bool monster_pathfind::calc_path_to_neighbours()
     {
         npos = pos + Compass[dir];
 
-//        mprf("Looking at neighbour (%d,%d)", npos.x, npos.y);
+#ifdef DEBUG_PATHFIND
+        mprf("Looking at neighbour (%d,%d)", npos.x, npos.y);
+#endif
         if (!in_bounds(npos))
             continue;
 
@@ -2324,16 +2332,20 @@ bool monster_pathfind::calc_path_to_neighbours()
 
         distance = dist[pos.x][pos.y] + travel_cost(npos);
         old_dist = dist[npos.x][npos.y];
-//        mprf("old dist: %d, new dist: %d, infinite: %d", old_dist, distance,
-//             INFINITE_DISTANCE);
+#ifdef DEBUG_PATHFIND
+        mprf("old dist: %d, new dist: %d, infinite: %d", old_dist, distance,
+             INFINITE_DISTANCE);
+#endif
         if (distance < old_dist)
         {
             // Calculate new total path length.
             total = distance + estimated_cost(npos);
             if (old_dist == INFINITE_DISTANCE)
             {
-//                mprf("Adding (%d,%d) to hash (total dist = %d)",
-//                     npos.x, npos.y, total);
+#ifdef DEBUG_PATHFIND
+                mprf("Adding (%d,%d) to hash (total dist = %d)",
+                     npos.x, npos.y, total);
+#endif
 
                 add_new_pos(npos, total);
                 if (total > max_length)
@@ -2341,8 +2353,10 @@ bool monster_pathfind::calc_path_to_neighbours()
             }
             else
             {
-//                mprf("Improving (%d,%d) to total dist %d",
-//                     npos.x, npos.y, total);
+#ifdef DEBUG_PATHFIND
+                mprf("Improving (%d,%d) to total dist %d",
+                     npos.x, npos.y, total);
+#endif
 
                 update_pos(npos, total);
             }
@@ -2361,7 +2375,9 @@ bool monster_pathfind::calc_path_to_neighbours()
             // Are we finished?
             if (npos == target)
             {
+#ifdef DEBUG_PATHFIND
                 mpr("Arrived at target.");
+#endif
                 return (true);
             }
         }
@@ -2380,12 +2396,16 @@ bool monster_pathfind::get_best_position()
             std::vector<coord_def> &vec = hash[i];
             pos = vec[vec.size()-1];
             vec.pop_back();
-//            mprf("Returning (%d, %d) as best pos with total dist %d.",
-//                 pos.x, pos.y, min_length);
+#ifdef DEBUG_PATHFIND
+            mprf("Returning (%d, %d) as best pos with total dist %d.",
+                 pos.x, pos.y, min_length);
+#endif
 
             return (true);
         }
-//        mprf("No positions for path length %d.", i);
+#ifdef DEBUG_PATHFIND
+        mprf("No positions for path length %d.", i);
+#endif
     }
 
     // Nothing found? Then there's no path! :(
@@ -2394,7 +2414,9 @@ bool monster_pathfind::get_best_position()
 
 std::vector<coord_def> monster_pathfind::backtrack()
 {
+#ifdef DEBUG_PATHFIND
     mpr("Backtracking...");
+#endif
     std::vector<coord_def> path;
     pos = target;
     path.push_back(pos);
@@ -2408,8 +2430,10 @@ std::vector<coord_def> monster_pathfind::backtrack()
         dir = prev[pos.x][pos.y];
         pos = pos + Compass[dir];
         ASSERT(in_bounds(pos));
-//        mprf("prev: (%d, %d), pos: (%d, %d)", Compass[dir].x, Compass[dir].y,
-//                                              pos.x, pos.y);
+#ifdef DEBUG_PATHFIND
+        mprf("prev: (%d, %d), pos: (%d, %d)", Compass[dir].x, Compass[dir].y,
+                                              pos.x, pos.y);
+#endif
         path.push_back(pos);
 
         if (pos.x == 0 && pos.y == 0)
@@ -2426,6 +2450,7 @@ std::vector<coord_def> monster_pathfind::backtrack()
 std::vector<coord_def> monster_pathfind::calc_waypoints()
 {
     std::vector<coord_def> path = backtrack();
+
     // If no path found, nothing to be done.
     if (path.empty())
         return path;
@@ -2442,6 +2467,9 @@ std::vector<coord_def> monster_pathfind::calc_waypoints()
     std::vector<coord_def> waypoints;
     pos = path[0];
 
+#ifdef DEBUG_PATHFIND
+    mpr(EOL "Waypoints:");
+#endif
     for (unsigned int i = 1; i < path.size(); i++)
     {
         if (grid_see_grid(pos.x, pos.y, path[i].x, path[i].y, can_move))
@@ -2450,6 +2478,9 @@ std::vector<coord_def> monster_pathfind::calc_waypoints()
         {
             pos = path[i-1];
             waypoints.push_back(pos);
+#ifdef DEBUG_PATHFIND
+            mprf("waypoint: (%d, %d)", pos.x, pos.y);
+#endif
         }
     }
 
diff --git a/crawl-ref/source/monstuff.cc b/crawl-ref/source/monstuff.cc
index 137838824a..589a3da109 100644
--- a/crawl-ref/source/monstuff.cc
+++ b/crawl-ref/source/monstuff.cc
@@ -2351,9 +2351,10 @@ static void _handle_behaviour(monsters *mon)
     bool isSmart    = (mons_intel(mon->type) > I_ANIMAL);
     bool isScared   = mon->has_ench(ENCH_FEAR);
     bool isMobile   = !mons_is_stationary(mon);
+    bool travelling = mon->is_travelling();
     bool patrolling = mon->is_patrolling();
 
-    // check for confusion -- early out.
+    // Check for confusion -- early out.
     if (mon->has_ench(ENCH_CONFUSION))
     {
         mon->target_x = 10 + random2(GXM - 10);
@@ -2515,7 +2516,7 @@ static void _handle_behaviour(monsters *mon)
                 break;
             }
 
-            // foe gone out of LOS?
+            // Foe gone out of LOS?
             if (!proxFoe)
             {
                 if (patrolling)
@@ -2575,8 +2576,7 @@ static void _handle_behaviour(monsters *mon)
                     break;
                 }
 
-                // hack: smarter monsters will
-                // tend to pursue the player longer.
+                // Hack: smarter monsters will tend to pursue the player longer.
                 int memory = 0;
                 switch (mons_intel(monster_index(mon)))
                 {
@@ -2648,10 +2648,102 @@ 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
-                || one_chance_in(20)
-                || testbits( mon->flags, MF_BATTY ))
+                || !travelling && (one_chance_in(20)
+                                   || testbits( mon->flags, MF_BATTY )))
             {
-                if (patrolling)
+                bool need_target = true;
+                if (travelling)
+                {
+#ifdef DEBUG_PATHFIND
+                    mprf("Monster %s reached target (%d, %d)",
+                         mon->name(DESC_PLAIN).c_str(),
+                         mon->target_x, mon->target_y);
+#endif
+                    need_target = false;
+                    if (mon->x == mon->travel_path[0].x
+                        && mon->y == mon->travel_path[0].y)
+                    {
+                        // Hey, we reached our first waypoint!
+                        mon->travel_path.erase( mon->travel_path.begin() );
+                        if (mon->travel_path.empty())
+                            need_target = true;
+
+                        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);
+#endif
+                    }
+                    else
+                    {
+                        // Apparently we got sidetracked a bit.
+                        // Check the waypoints vector backwards and pick the
+                        // first waypoint we can see.
+
+                        // XXX: Note that this might still not be the best
+                        // 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--)
+                        {
+                            if (grid_see_grid(mon->x, mon->y,
+                                              mon->travel_path[i].x,
+                                              mon->travel_path[i].y, can_move))
+                            {
+                                mon->target_x = mon->travel_path[i].x;
+                                mon->target_y = mon->travel_path[i].y;
+                                erase = i;
+                                break;
+                            }
+                        }
+
+                        if (erase != -1)
+                        {
+                            // Erase all waypoints that came earlier:
+                            // we don't need them anymore.
+                            while (0 < erase--)
+                            {
+                                mon->travel_path.erase(
+                                    mon->travel_path.begin() );
+                            }
+                        }
+                        else
+                        {
+                            // 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))
+                            {
+                                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;
+                                }
+                            }
+                            else
+                            {
+                                mon->travel_path.clear();
+                                need_target = true;
+                            }
+                        }
+                    }
+                }
+
+                if (need_target && patrolling)
                 {
                     if (!_choose_random_patrol_target_grid(mon))
                     {
@@ -2685,14 +2777,39 @@ static void _handle_behaviour(monsters *mon)
                             // pathfinding to find the way back, and animals
                             // could decide to stop patrolling if the path
                             // was too long.
-
-                            mon->target_x = mon->patrol_point.x;
-                            mon->target_y = mon->patrol_point.y;
+                            monster_pathfind mp;
+                            if (mp.start_pathfind(mon, mon->patrol_point, true))
+                            {
+                                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;
+                                }
+                            }
+                            else
+                            {
+                                // Stop patrolling.
+                                mon->patrol_point = coord_def(0, 0);
+                            }
                         }
                     }
+                    else
+                    {
+#ifdef DEBUG_PATHFIND
+                        mprf("Monster %s (pp: %d, %d) is now patrolling to (%d, %d)",
+                             mon->name(DESC_PLAIN).c_str(),
+                             mon->patrol_point.x, mon->patrol_point.y,
+                             mon->target_x, mon->target_y);
+#endif
+                    }
                 }
-                else
+                else if (need_target)
                 {
+#ifdef DEBUG_PATHFIND
+                    if (!testbits( mon->flags, MF_BATTY ))
+                        mprf("Monster is wandering randomly.");
+#endif
                     mon->target_x = 10 + random2(GXM - 10);
                     mon->target_y = 10 + random2(GYM - 10);
                 }
@@ -2742,7 +2859,7 @@ static void _handle_behaviour(monsters *mon)
             if (isHealthy)
                 new_beh = BEH_SEEK;
 
-            // foe gone out of LOS?
+            // Foe gone out of LOS?
             if (!proxFoe)
             {
                 if ((isFriendly || proxPlayer) && !isNeutral && !patrolling)
diff --git a/crawl-ref/source/religion.cc b/crawl-ref/source/religion.cc
index 7d62b5ac1d..0df93e66e5 100644
--- a/crawl-ref/source/religion.cc
+++ b/crawl-ref/source/religion.cc
@@ -57,6 +57,7 @@
 #include "makeitem.h"
 #include "message.h"
 #include "misc.h"
+#include "mon-util.h"
 #include "monplace.h"
 #include "monstuff.h"
 #include "mutation.h"
@@ -4360,9 +4361,15 @@ void beogh_convert_orc(monsters *orc, bool emergency,
     // The monster is not really *created* friendly, but should it
     // become hostile later on, it won't count as a good kill.
     orc->flags |= MF_CREATED_FRIENDLY;
-
     orc->flags |= MF_GOD_GIFT;
 
+    if (orc->is_patrolling())
+    {
+        // Make orcs stop patrolling and forget their patrol point,
+        // they're supposed to follow you now.
+        orc->patrol_point = coord_def(0, 0);
+    }
+
     if (!orc->alive())
         orc->hit_points = std::min(random_range(1, 4), orc->max_hit_points);
 
diff --git a/crawl-ref/source/tags.cc b/crawl-ref/source/tags.cc
index 5e5cd91e76..77f024c952 100644
--- a/crawl-ref/source/tags.cc
+++ b/crawl-ref/source/tags.cc
@@ -1769,6 +1769,12 @@ static void marshall_monster(writer &th, const monsters &m)
     marshallByte(th, m.target_x);
     marshallByte(th, m.target_y);
     marshallCoord(th, m.patrol_point);
+
+    // monster pathfinding (TAG_MINOR_PATHFIND)
+    marshallShort(th, m.travel_path.size());
+    for (unsigned int i = 0; i < m.travel_path.size(); i++)
+        marshallCoord(th, m.travel_path[i]);
+
     marshallLong(th, m.flags);
     marshallLong(th, m.experience);
 
@@ -2034,6 +2040,17 @@ 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_PATHFIND)
+    {
+        const int len = unmarshallShort(th);
+        for (int i = 0; i < len; ++i)
+        {
+            coord_def c;
+            unmarshallCoord(th, c);
+            m.travel_path.push_back(c);
+        }
+    }
+
     m.flags           = unmarshallLong(th);
     m.experience      = static_cast<unsigned long>(unmarshallLong(th));
 
diff --git a/crawl-ref/source/tags.h b/crawl-ref/source/tags.h
index ae16aef150..9aea5c2ce1 100644
--- a/crawl-ref/source/tags.h
+++ b/crawl-ref/source/tags.h
@@ -43,21 +43,22 @@ enum tag_file_type   // file types supported by tag system
 
 enum tag_major_version
 {
-    TAG_MAJOR_START = 5,
+    TAG_MAJOR_START   = 5,
     TAG_MAJOR_VERSION = 5
 };
 
 // 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_VERSION = 8       // 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_VERSION  = 9      // Current version
 };