Split monster_pathfind out into mon-pathfind.cc.

11 files changed, 618 insertions, 588 deletions

diff --git a/crawl-ref/source/dungeon.cc b/crawl-ref/source/dungeon.cc
index 8e59c7f94b..b4c0600289 100644
--- a/crawl-ref/source/dungeon.cc
+++ b/crawl-ref/source/dungeon.cc
@@ -43,6 +43,7 @@
 #include "misc.h"
 #include "mon-util.h"
 #include "mon-place.h"
+#include "mon-pathfind.h"
 #include "notes.h"
 #include "place.h"
 #include "player.h"
diff --git a/crawl-ref/source/effects.cc b/crawl-ref/source/effects.cc
index 99f01b41f9..f79a6a95d9 100644
--- a/crawl-ref/source/effects.cc
+++ b/crawl-ref/source/effects.cc
@@ -44,6 +44,7 @@
 #include "mon-cast.h"
 #include "mon-iter.h"
 #include "mon-place.h"
+#include "mon-pathfind.h"
 #include "mon-stuff.h"
 #include "mon-util.h"
 #include "mutation.h"
diff --git a/crawl-ref/source/makefile.obj b/crawl-ref/source/makefile.obj
index c67b008aad..54c3a0d705 100644
--- a/crawl-ref/source/makefile.obj
+++ b/crawl-ref/source/makefile.obj
@@ -105,6 +105,7 @@ mon-gear.o \
 mon-grow.o \
 mon-info.o \
 mon-iter.o \
+mon-pathfind.o \
 mon-pick.o \
 mon-util.o \
 mon-place.o \
diff --git a/crawl-ref/source/misc.cc b/crawl-ref/source/misc.cc
index e78751def9..9030989fc0 100644
--- a/crawl-ref/source/misc.cc
+++ b/crawl-ref/source/misc.cc
@@ -51,6 +51,7 @@
 #include "mapmark.h"
 #include "message.h"
 #include "mon-place.h"
+#include "mon-pathfind.h"
 #include "mon-iter.h"
 #include "mon-util.h"
 #include "mon-stuff.h"
diff --git a/crawl-ref/source/mon-behv.cc b/crawl-ref/source/mon-behv.cc
index 9868e8dcda..685beec247 100644
--- a/crawl-ref/source/mon-behv.cc
+++ b/crawl-ref/source/mon-behv.cc
@@ -17,6 +17,7 @@
 #include "los.h"
 #include "mon-iter.h"
 #include "mon-place.h"
+#include "mon-pathfind.h"
 #include "mon-stuff.h"
 #include "mon-util.h"
 #include "random.h"
diff --git a/crawl-ref/source/mon-pathfind.cc b/crawl-ref/source/mon-pathfind.cc
new file mode 100644
index 0000000000..a919adc204
--- /dev/null
+++ b/crawl-ref/source/mon-pathfind.cc
@@ -0,0 +1,535 @@
+#include "AppHdr.h"
+
+#include "mon-pathfind.h"
+
+#include "coord.h"
+#include "directn.h"
+#include "env.h"
+#include "mon-place.h"
+#include "mon-stuff.h"
+#include "mon-util.h"
+#include "monster.h"
+#include "terrain.h"
+#include "traps.h"
+
+/////////////////////////////////////////////////////////////////////////////
+// monster_pathfind
+
+// The pathfinding is an implementation of the A* algorithm. Beginning at the
+// destination square we check all neighbours of a given grid, estimate the
+// distance needed for any shortest path including this grid and push the
+// result into a hash. We can then easily access all points with the shortest
+// distance estimates and then check _their_ neighbours and so on.
+// The algorithm terminates once we reach the monster position since - because
+// of the sorting of grids by shortest distance in the hash - there can be no
+// path between start and target that is shorter than the current one. There
+// could be other paths that have the same length but that has no real impact.
+// If the hash has been cleared and the start grid has not been encountered,
+// then there's no path that matches the requirements fed into monster_pathfind.
+// (These requirements are usually preference of habitat of a specific monster
+// or a limit of the distance between start and any grid on the path.)
+
+int mons_tracking_range(const monsters *mon)
+{
+
+    int range = 0;
+    switch (mons_intel(mon))
+    {
+    case I_PLANT:
+        range = 2;
+        break;
+    case I_INSECT:
+        range = 4;
+        break;
+    case I_ANIMAL:
+        range = 5;
+        break;
+    case I_NORMAL:
+        range = LOS_RADIUS;
+        break;
+    default:
+        // Highly intelligent monsters can find their way
+        // anywhere. (range == 0 means no restriction.)
+        break;
+    }
+
+    if (range)
+    {
+        if (mons_is_native_in_branch(mon))
+            range += 3;
+        else if (mons_class_flag(mon->type, M_BLOOD_SCENT))
+            range++;
+    }
+
+    return (range);
+}
+
+//#define DEBUG_PATHFIND
+monster_pathfind::monster_pathfind()
+    : mons(), target(), range(0), min_length(0), max_length(0), dist(), prev()
+{
+}
+
+monster_pathfind::~monster_pathfind()
+{
+}
+
+void monster_pathfind::set_range(int r)
+{
+    if (r >= 0)
+        range = r;
+}
+
+coord_def monster_pathfind::next_pos(const coord_def &c) const
+{
+    return c + Compass[prev[c.x][c.y]];
+}
+
+// The main method in the monster_pathfind class.
+// Returns true if a path was found, else false.
+bool monster_pathfind::init_pathfind(const monsters *mon, coord_def dest,
+                                     bool diag, bool msg, bool pass_unmapped)
+{
+    mons   = mon;
+
+    // We're doing a reverse search from target to monster.
+    start  = dest;
+    target = mon->pos();
+    pos    = start;
+    allow_diagonals   = diag;
+    traverse_unmapped = pass_unmapped;
+
+    // Easy enough. :P
+    if (start == target)
+    {
+        if (msg)
+            mpr("The monster is already there!");
+
+        return (true);
+    }
+
+    return start_pathfind(msg);
+}
+
+bool monster_pathfind::init_pathfind(coord_def src, coord_def dest, bool diag,
+                                     bool msg)
+{
+    start  = src;
+    target = dest;
+    pos    = start;
+    allow_diagonals = diag;
+
+    // Easy enough. :P
+    if (start == target)
+        return (true);
+
+    return start_pathfind(msg);
+}
+
+bool monster_pathfind::start_pathfind(bool msg)
+{
+    // NOTE: We never do any traversable() check for the starting square
+    //       (target). This means that even if the target cannot be reached
+    //       we may still find a path leading adjacent to this position, which
+    //       is desirable if e.g. the player is hovering over deep water
+    //       surrounded by shallow water or floor, or if a foe is hiding in
+    //       a wall.
+    //       If the surrounding squares also are not traversable, we return
+    //       early that no path could be found.
+
+    max_length = min_length = grid_distance(pos.x, pos.y, target.x, target.y);
+    for (int i = 0; i < GXM; i++)
+        for (int j = 0; j < GYM; j++)
+            dist[i][j] = INFINITE_DISTANCE;
+
+    dist[pos.x][pos.y] = 0;
+
+    bool success = false;
+    do
+    {
+        // Calculate the distance to all neighbours of the current position,
+        // and add them to the hash, if they haven't already been looked at.
+        success = calc_path_to_neighbours();
+        if (success)
+            return (true);
+
+        // Pull the position with shortest distance estimate to our target grid.
+        success = get_best_position();
+
+        if (!success)
+        {
+            if (msg)
+            {
+                mprf("Couldn't find a path from (%d,%d) to (%d,%d).",
+                     target.x, target.y, start.x, start.y);
+            }
+            return (false);
+        }
+    }
+    while (true);
+}
+
+// Returns true as soon as we encounter the target.
+bool monster_pathfind::calc_path_to_neighbours()
+{
+    coord_def npos;
+    int distance, old_dist, total;
+
+    // For each point, we look at all neighbour points. Check the orthogonals
+    // last, so that, should an orthogonal and a diagonal direction have the
+    // same total travel cost, the orthogonal will be picked first, and thus
+    // zigzagging will be significantly reduced.
+    //
+    //      1  0  3       This means directions are looked at, in order,
+    //       \ | /        1, 3, 5, 7 (diagonals) followed by 0, 2, 4, 6
+    //      6--.--2       (orthogonals). This is achieved by the assignment
+    //       / | \        of (dir = 0) once dir has passed 7.
+    //      7  4  5
+    //
+    for (int dir = 1; dir < 8; (dir += 2) == 9 && (dir = 0))
+    {
+        // Skip diagonal movement.
+        if (!allow_diagonals && (dir % 2))
+            continue;
+
+        npos = pos + Compass[dir];
+
+#ifdef DEBUG_PATHFIND
+        mprf("Looking at neighbour (%d,%d)", npos.x, npos.y);
+#endif
+        if (!in_bounds(npos))
+            continue;
+
+        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
+        mprf("old dist: %d, new dist: %d, infinite: %d", old_dist, distance,
+             INFINITE_DISTANCE);
+#endif
+        // If the new distance is better than the old one (initialised with
+        // INFINITE), update the position.
+        if (distance < old_dist)
+        {
+            // Calculate new total path length.
+            total = distance + estimated_cost(npos);
+            if (old_dist == INFINITE_DISTANCE)
+            {
+#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)
+                    max_length = total;
+            }
+            else
+            {
+#ifdef DEBUG_PATHFIND
+                mprf("Improving (%d,%d) to total dist %d",
+                     npos.x, npos.y, total);
+#endif
+
+                update_pos(npos, total);
+            }
+
+            // Update distance start->pos.
+            dist[npos.x][npos.y] = distance;
+
+            // Set backtracking information.
+            // Converts the Compass direction to its counterpart.
+            //      0  1  2         4  5  6
+            //      7  .  3   ==>   3  .  7       e.g. (3 + 4) % 8          = 7
+            //      6  5  4         2  1  0            (7 + 4) % 8 = 11 % 8 = 3
+
+            prev[npos.x][npos.y] = (dir + 4) % 8;
+
+            // Are we finished?
+            if (npos == target)
+            {
+#ifdef DEBUG_PATHFIND
+                mpr("Arrived at target.");
+#endif
+                return (true);
+            }
+        }
+    }
+    return (false);
+}
+
+// Starting at known min_length (minimum total estimated path distance), check
+// the hash for existing vectors, then pick the last entry of the first vector
+// that matches. Update min_length, if necessary.
+bool monster_pathfind::get_best_position()
+{
+    for (int i = min_length; i <= max_length; i++)
+    {
+        if (!hash[i].empty())
+        {
+            if (i > min_length)
+                min_length = i;
+
+            std::vector<coord_def> &vec = hash[i];
+            // Pick the last position pushed into the vector as it's most
+            // likely to be close to the target.
+            pos = vec[vec.size()-1];
+            vec.pop_back();
+
+#ifdef DEBUG_PATHFIND
+            mprf("Returning (%d, %d) as best pos with total dist %d.",
+                 pos.x, pos.y, min_length);
+#endif
+
+            return (true);
+        }
+#ifdef DEBUG_PATHFIND
+        mprf("No positions for path length %d.", i);
+#endif
+    }
+
+    // Nothing found? Then there's no path! :(
+    return (false);
+}
+
+// Using the prev vector backtrack from start to target to find all steps to
+// take along the shortest path.
+std::vector<coord_def> monster_pathfind::backtrack()
+{
+#ifdef DEBUG_PATHFIND
+    mpr("Backtracking...");
+#endif
+    std::vector<coord_def> path;
+    pos = target;
+    path.push_back(pos);
+
+    if (pos == start)
+        return path;
+
+    int dir;
+    do
+    {
+        dir = prev[pos.x][pos.y];
+        pos = pos + Compass[dir];
+        ASSERT(in_bounds(pos));
+#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)
+            break;
+    }
+    while (pos != start);
+    ASSERT(pos == start);
+
+    return (path);
+}
+
+// Reduces the path coordinates to only a couple of key waypoints needed
+// to reach the target. Waypoints are chosen such that from one waypoint you
+// can see (and, more importantly, reach) the next one. Note that
+// can_go_straight() is probably rather too conservative in these estimates.
+// This is done because Crawl's pathfinding - once a target is in sight and easy
+// reach - is both very robust and natural, especially if we want to flexibly
+// avoid plants and other monsters in the way.
+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;
+
+    dungeon_feature_type can_move;
+    if (mons_amphibious(mons))
+        can_move = DNGN_DEEP_WATER;
+    else
+        can_move = DNGN_SHALLOW_WATER;
+
+    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 (can_go_straight(pos, path[i], can_move))
+            continue;
+        else
+        {
+            pos = path[i-1];
+            waypoints.push_back(pos);
+#ifdef DEBUG_PATHFIND
+            mprf("waypoint: (%d, %d)", pos.x, pos.y);
+#endif
+        }
+    }
+
+    // Add the actual target to the list of waypoints, so we can later check
+    // whether a tracked enemy has moved too much, in case we have to update
+    // the path.
+    if (pos != path[path.size() - 1])
+        waypoints.push_back(path[path.size() - 1]);
+
+    return (waypoints);
+}
+
+bool monster_pathfind::traversable(const coord_def p)
+{
+    if (traverse_unmapped && grd(p) == DNGN_UNSEEN)
+        return (true);
+
+    if (mons)
+        return mons_traversable(p);
+
+    return (!feat_is_solid(grd(p)) && !feat_destroys_items(grd(p)));
+}
+
+// Checks whether a given monster can pass over a certain position, respecting
+// its preferred habit and capability of flight or opening doors.
+bool monster_pathfind::mons_traversable(const coord_def p)
+{
+    const monster_type montype = mons_is_zombified(mons) ? mons_zombie_base(mons)
+                                                         : mons->type;
+
+    if (!mons->is_habitable_feat(grd(p)))
+        return (false);
+
+    // Monsters that can't open doors won't be able to pass them.
+    if (feat_is_closed_door(grd(p)) || grd(p) == DNGN_SECRET_DOOR)
+    {
+        if (mons_is_zombified(mons))
+        {
+            if (mons_class_itemuse(montype) < MONUSE_OPEN_DOORS)
+                return (false);
+        }
+        else if (mons_itemuse(mons) < MONUSE_OPEN_DOORS)
+            return (false);
+    }
+
+    // Your friends only know about doors you know about, unless they feel
+    // at home in this branch.
+    if (grd(p) == DNGN_SECRET_DOOR && mons->friendly()
+        && (mons_intel(mons) < I_NORMAL || !mons_is_native_in_branch(mons)))
+    {
+        return (false);
+    }
+
+    const trap_def* ptrap = find_trap(p);
+    if (ptrap)
+    {
+        const trap_type tt = ptrap->type;
+
+        // Don't allow allies to pass over known (to them) Zot traps.
+        if (tt == TRAP_ZOT
+            && ptrap->is_known(mons)
+            && mons->friendly())
+        {
+            return (false);
+        }
+
+        // Monsters cannot travel over teleport traps.
+        if (!can_place_on_trap(montype, tt))
+            return (false);
+    }
+
+    return (true);
+}
+
+int monster_pathfind::travel_cost(coord_def npos)
+{
+    if (mons)
+        return mons_travel_cost(npos);
+
+    return (1);
+}
+
+// Assumes that grids that really cannot be entered don't even get here.
+// (Checked by traversable().)
+int monster_pathfind::mons_travel_cost(coord_def npos)
+{
+    ASSERT(grid_distance(pos, npos) <= 1);
+
+    // Doors need to be opened.
+    if (feat_is_closed_door(grd(npos)) || grd(npos) == DNGN_SECRET_DOOR)
+        return 2;
+
+    const int montype = mons_is_zombified(mons) ? mons_zombie_base(mons)
+                                                : mons->type;
+
+    const bool airborne = mons_airborne(montype, -1, false);
+
+    // Travelling through water, entering or leaving water is more expensive
+    // for non-amphibious monsters, so they'll avoid it where possible.
+    // (The resulting path might not be optimal but it will lead to a path
+    // a monster of such habits is likely to prefer.)
+    // Only tested for shallow water since they can't enter deep water anyway.
+    if (!airborne && !mons_class_amphibious(montype)
+        && (grd(pos) == DNGN_SHALLOW_WATER || grd(npos) == DNGN_SHALLOW_WATER))
+    {
+        return 2;
+    }
+
+    // Try to avoid (known) traps.
+    const trap_def* ptrap = find_trap(npos);
+    if (ptrap)
+    {
+        const bool knows_trap = ptrap->is_known(mons);
+        const trap_type tt = ptrap->type;
+        if (tt == TRAP_ALARM || tt == TRAP_ZOT)
+        {
+            // Your allies take extra precautions to avoid known alarm traps.
+            // Zot traps are considered intraversable.
+            if (knows_trap && mons->friendly())
+                return (3);
+
+            // To hostile monsters, these traps are completely harmless.
+            return 1;
+        }
+
+        // Mechanical traps can be avoided by flying, as can shafts, and
+        // tele traps are never traversable anyway.
+        if (knows_trap && !airborne)
+            return 2;
+    }
+
+    return 1;
+}
+
+// The estimated cost to reach a grid is simply max(dx, dy).
+int monster_pathfind::estimated_cost(coord_def p)
+{
+    return (grid_distance(p, target));
+}
+
+void monster_pathfind::add_new_pos(coord_def npos, int total)
+{
+    hash[total].push_back(npos);
+}
+
+void monster_pathfind::update_pos(coord_def npos, int total)
+{
+    // Find hash position of old distance and delete it,
+    // then call_add_new_pos.
+    int old_total = dist[npos.x][npos.y] + estimated_cost(npos);
+
+    std::vector<coord_def> &vec = hash[old_total];
+    for (unsigned int i = 0; i < vec.size(); i++)
+    {
+        if (vec[i] == npos)
+        {
+            vec.erase(vec.begin() + i);
+            break;
+        }
+    }
+
+    add_new_pos(npos, total);
+}
diff --git a/crawl-ref/source/mon-pathfind.h b/crawl-ref/source/mon-pathfind.h
new file mode 100644
index 0000000000..590fb3f777
--- /dev/null
+++ b/crawl-ref/source/mon-pathfind.h
@@ -0,0 +1,69 @@
+#ifndef MON_PATHFIND_H
+#define MON_PATHFIND_H
+
+class monsters;
+
+int mons_tracking_range(const monsters *mon);
+
+class monster_pathfind
+{
+public:
+    monster_pathfind();
+    virtual ~monster_pathfind();
+    
+    // public methods  
+    void set_range(int r);
+    coord_def next_pos(const coord_def &p) const;
+    bool init_pathfind(const monsters *mon, coord_def dest,
+                       bool diag = true, bool msg = false,
+                       bool pass_unmapped = false);
+    bool init_pathfind(coord_def src, coord_def dest,
+                       bool diag = true, bool msg = false);
+    bool start_pathfind(bool msg = false);
+    std::vector<coord_def> backtrack(void);
+    std::vector<coord_def> calc_waypoints(void);
+
+protected:
+    // protected methods
+    bool calc_path_to_neighbours(void);
+    bool traversable(coord_def p);
+    int  travel_cost(coord_def npos);
+    bool mons_traversable(coord_def p);
+    int  mons_travel_cost(coord_def npos);
+    int  estimated_cost(coord_def npos);
+    void add_new_pos(coord_def pos, int total);
+    void update_pos(coord_def pos, int total);
+    bool get_best_position(void);
+
+
+    // The monster trying to find a path.
+    const monsters *mons;
+
+    // Our destination, and the current position we're looking at.
+    coord_def start, target, pos;
+
+    // If false, do not move diagonally along the path.
+    bool allow_diagonals;
+
+    // If true, unmapped terrain is treated as traversable no matter the
+    // monster involved.
+    // (Used for player estimates of whether a monster can travel somewhere.)
+    bool traverse_unmapped;
+
+    // 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;
+
+    // The array of distances from start to any already tried point.
+    int dist[GXM][GYM];
+    // An array to store where we came from on a given shortest path.
+    int prev[GXM][GYM];
+
+    FixedVector<std::vector<coord_def>, GXM * GYM> hash;
+};
+
+#endif
+
diff --git a/crawl-ref/source/mon-place.cc b/crawl-ref/source/mon-place.cc
index 57990844ff..e03177d26d 100644
--- a/crawl-ref/source/mon-place.cc
+++ b/crawl-ref/source/mon-place.cc
@@ -124,7 +124,7 @@ bool monster_habitable_grid(const monsters *m,
                                    m->cannot_move()));
 }
 
-inline static bool _mons_airborne(int mcls, int flies, bool paralysed)
+bool mons_airborne(int mcls, int flies, bool paralysed)
 {
     if (flies == -1)
         flies = mons_class_flies(mcls);
@@ -171,7 +171,7 @@ bool monster_habitable_grid(monster_type montype,
     // [dshaligram] Flying creatures are all DNGN_FLOOR, so we
     // only have to check for the additional valid grids of deep
     // water and lava.
-    if (_mons_airborne(montype, flies, paralysed)
+    if (mons_airborne(montype, flies, paralysed)
         && (actual_grid == DNGN_LAVA || actual_grid == DNGN_DEEP_WATER))
     {
         return (true);
@@ -467,7 +467,7 @@ monster_type pick_random_monster(const level_id &place, int power,
     return (mon_type);
 }
 
-static bool _can_place_on_trap(int mon_type, trap_type trap)
+bool can_place_on_trap(int mon_type, trap_type trap)
 {
     if (trap == TRAP_TELEPORT)
         return (false);
@@ -544,7 +544,7 @@ static monster_type _resolve_monster_type(monster_type mon_type,
 
                 // Don't generate monsters on top of teleport traps.
                 const trap_def* ptrap = find_trap(pos);
-                if (ptrap && !_can_place_on_trap(mon_type, ptrap->type))
+                if (ptrap && !can_place_on_trap(mon_type, ptrap->type))
                     continue;
 
                 // Check whether there's a stair
@@ -713,7 +713,7 @@ static bool _valid_monster_generation_location(
     // Don't generate monsters on top of teleport traps.
     // (How did they get there?)
     const trap_def* ptrap = find_trap(mg_pos);
-    if (ptrap && !_can_place_on_trap(mg.cls, ptrap->type))
+    if (ptrap && !can_place_on_trap(mg.cls, ptrap->type))
         return (false);
 
     return (true);
@@ -2981,528 +2981,6 @@ monster_type summon_any_dragon(dragon_class_type dct)
 }
 
 /////////////////////////////////////////////////////////////////////////////
-// monster_pathfind
-
-// The pathfinding is an implementation of the A* algorithm. Beginning at the
-// destination square we check all neighbours of a given grid, estimate the
-// distance needed for any shortest path including this grid and push the
-// result into a hash. We can then easily access all points with the shortest
-// distance estimates and then check _their_ neighbours and so on.
-// The algorithm terminates once we reach the monster position since - because
-// of the sorting of grids by shortest distance in the hash - there can be no
-// path between start and target that is shorter than the current one. There
-// could be other paths that have the same length but that has no real impact.
-// If the hash has been cleared and the start grid has not been encountered,
-// then there's no path that matches the requirements fed into monster_pathfind.
-// (These requirements are usually preference of habitat of a specific monster
-// or a limit of the distance between start and any grid on the path.)
-
-int mons_tracking_range(const monsters *mon)
-{
-
-    int range = 0;
-    switch (mons_intel(mon))
-    {
-    case I_PLANT:
-        range = 2;
-        break;
-    case I_INSECT:
-        range = 4;
-        break;
-    case I_ANIMAL:
-        range = 5;
-        break;
-    case I_NORMAL:
-        range = LOS_RADIUS;
-        break;
-    default:
-        // Highly intelligent monsters can find their way
-        // anywhere. (range == 0 means no restriction.)
-        break;
-    }
-
-    if (range)
-    {
-        if (mons_is_native_in_branch(mon))
-            range += 3;
-        else if (mons_class_flag(mon->type, M_BLOOD_SCENT))
-            range++;
-    }
-
-    return (range);
-}
-
-//#define DEBUG_PATHFIND
-monster_pathfind::monster_pathfind()
-    : mons(), target(), range(0), min_length(0), max_length(0), dist(), prev()
-{
-}
-
-monster_pathfind::~monster_pathfind()
-{
-}
-
-void monster_pathfind::set_range(int r)
-{
-    if (r >= 0)
-        range = r;
-}
-
-coord_def monster_pathfind::next_pos(const coord_def &c) const
-{
-    return c + Compass[prev[c.x][c.y]];
-}
-
-// The main method in the monster_pathfind class.
-// Returns true if a path was found, else false.
-bool monster_pathfind::init_pathfind(const monsters *mon, coord_def dest,
-                                     bool diag, bool msg, bool pass_unmapped)
-{
-    mons   = mon;
-
-    // We're doing a reverse search from target to monster.
-    start  = dest;
-    target = mon->pos();
-    pos    = start;
-    allow_diagonals   = diag;
-    traverse_unmapped = pass_unmapped;
-
-    // Easy enough. :P
-    if (start == target)
-    {
-        if (msg)
-            mpr("The monster is already there!");
-
-        return (true);
-    }
-
-    return start_pathfind(msg);
-}
-
-bool monster_pathfind::init_pathfind(coord_def src, coord_def dest, bool diag,
-                                     bool msg)
-{
-    start  = src;
-    target = dest;
-    pos    = start;
-    allow_diagonals = diag;
-
-    // Easy enough. :P
-    if (start == target)
-        return (true);
-
-    return start_pathfind(msg);
-}
-
-bool monster_pathfind::start_pathfind(bool msg)
-{
-    // NOTE: We never do any traversable() check for the starting square
-    //       (target). This means that even if the target cannot be reached
-    //       we may still find a path leading adjacent to this position, which
-    //       is desirable if e.g. the player is hovering over deep water
-    //       surrounded by shallow water or floor, or if a foe is hiding in
-    //       a wall.
-    //       If the surrounding squares also are not traversable, we return
-    //       early that no path could be found.
-
-    max_length = min_length = grid_distance(pos.x, pos.y, target.x, target.y);
-    for (int i = 0; i < GXM; i++)
-        for (int j = 0; j < GYM; j++)
-            dist[i][j] = INFINITE_DISTANCE;
-
-    dist[pos.x][pos.y] = 0;
-
-    bool success = false;
-    do
-    {
-        // Calculate the distance to all neighbours of the current position,
-        // and add them to the hash, if they haven't already been looked at.
-        success = calc_path_to_neighbours();
-        if (success)
-            return (true);
-
-        // Pull the position with shortest distance estimate to our target grid.
-        success = get_best_position();
-
-        if (!success)
-        {
-            if (msg)
-            {
-                mprf("Couldn't find a path from (%d,%d) to (%d,%d).",
-                     target.x, target.y, start.x, start.y);
-            }
-            return (false);
-        }
-    }
-    while (true);
-}
-
-// Returns true as soon as we encounter the target.
-bool monster_pathfind::calc_path_to_neighbours()
-{
-    coord_def npos;
-    int distance, old_dist, total;
-
-    // For each point, we look at all neighbour points. Check the orthogonals
-    // last, so that, should an orthogonal and a diagonal direction have the
-    // same total travel cost, the orthogonal will be picked first, and thus
-    // zigzagging will be significantly reduced.
-    //
-    //      1  0  3       This means directions are looked at, in order,
-    //       \ | /        1, 3, 5, 7 (diagonals) followed by 0, 2, 4, 6
-    //      6--.--2       (orthogonals). This is achieved by the assignment
-    //       / | \        of (dir = 0) once dir has passed 7.
-    //      7  4  5
-    //
-    for (int dir = 1; dir < 8; (dir += 2) == 9 && (dir = 0))
-    {
-        // Skip diagonal movement.
-        if (!allow_diagonals && (dir % 2))
-            continue;
-
-        npos = pos + Compass[dir];
-
-#ifdef DEBUG_PATHFIND
-        mprf("Looking at neighbour (%d,%d)", npos.x, npos.y);
-#endif
-        if (!in_bounds(npos))
-            continue;
-
-        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
-        mprf("old dist: %d, new dist: %d, infinite: %d", old_dist, distance,
-             INFINITE_DISTANCE);
-#endif
-        // If the new distance is better than the old one (initialised with
-        // INFINITE), update the position.
-        if (distance < old_dist)
-        {
-            // Calculate new total path length.
-            total = distance + estimated_cost(npos);
-            if (old_dist == INFINITE_DISTANCE)
-            {
-#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)
-                    max_length = total;
-            }
-            else
-            {
-#ifdef DEBUG_PATHFIND
-                mprf("Improving (%d,%d) to total dist %d",
-                     npos.x, npos.y, total);
-#endif
-
-                update_pos(npos, total);
-            }
-
-            // Update distance start->pos.
-            dist[npos.x][npos.y] = distance;
-
-            // Set backtracking information.
-            // Converts the Compass direction to its counterpart.
-            //      0  1  2         4  5  6
-            //      7  .  3   ==>   3  .  7       e.g. (3 + 4) % 8          = 7
-            //      6  5  4         2  1  0            (7 + 4) % 8 = 11 % 8 = 3
-
-            prev[npos.x][npos.y] = (dir + 4) % 8;
-
-            // Are we finished?
-            if (npos == target)
-            {
-#ifdef DEBUG_PATHFIND
-                mpr("Arrived at target.");
-#endif
-                return (true);
-            }
-        }
-    }
-    return (false);
-}
-
-// Starting at known min_length (minimum total estimated path distance), check
-// the hash for existing vectors, then pick the last entry of the first vector
-// that matches. Update min_length, if necessary.
-bool monster_pathfind::get_best_position()
-{
-    for (int i = min_length; i <= max_length; i++)
-    {
-        if (!hash[i].empty())
-        {
-            if (i > min_length)
-                min_length = i;
-
-            std::vector<coord_def> &vec = hash[i];
-            // Pick the last position pushed into the vector as it's most
-            // likely to be close to the target.
-            pos = vec[vec.size()-1];
-            vec.pop_back();
-
-#ifdef DEBUG_PATHFIND
-            mprf("Returning (%d, %d) as best pos with total dist %d.",
-                 pos.x, pos.y, min_length);
-#endif
-
-            return (true);
-        }
-#ifdef DEBUG_PATHFIND
-        mprf("No positions for path length %d.", i);
-#endif
-    }
-
-    // Nothing found? Then there's no path! :(
-    return (false);
-}
-
-// Using the prev vector backtrack from start to target to find all steps to
-// take along the shortest path.
-std::vector<coord_def> monster_pathfind::backtrack()
-{
-#ifdef DEBUG_PATHFIND
-    mpr("Backtracking...");
-#endif
-    std::vector<coord_def> path;
-    pos = target;
-    path.push_back(pos);
-
-    if (pos == start)
-        return path;
-
-    int dir;
-    do
-    {
-        dir = prev[pos.x][pos.y];
-        pos = pos + Compass[dir];
-        ASSERT(in_bounds(pos));
-#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)
-            break;
-    }
-    while (pos != start);
-    ASSERT(pos == start);
-
-    return (path);
-}
-
-// Reduces the path coordinates to only a couple of key waypoints needed
-// to reach the target. Waypoints are chosen such that from one waypoint you
-// can see (and, more importantly, reach) the next one. Note that
-// can_go_straight() is probably rather too conservative in these estimates.
-// This is done because Crawl's pathfinding - once a target is in sight and easy
-// reach - is both very robust and natural, especially if we want to flexibly
-// avoid plants and other monsters in the way.
-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;
-
-    dungeon_feature_type can_move;
-    if (mons_amphibious(mons))
-        can_move = DNGN_DEEP_WATER;
-    else
-        can_move = DNGN_SHALLOW_WATER;
-
-    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 (can_go_straight(pos, path[i], can_move))
-            continue;
-        else
-        {
-            pos = path[i-1];
-            waypoints.push_back(pos);
-#ifdef DEBUG_PATHFIND
-            mprf("waypoint: (%d, %d)", pos.x, pos.y);
-#endif
-        }
-    }
-
-    // Add the actual target to the list of waypoints, so we can later check
-    // whether a tracked enemy has moved too much, in case we have to update
-    // the path.
-    if (pos != path[path.size() - 1])
-        waypoints.push_back(path[path.size() - 1]);
-
-    return (waypoints);
-}
-
-bool monster_pathfind::traversable(const coord_def p)
-{
-    if (traverse_unmapped && grd(p) == DNGN_UNSEEN)
-        return (true);
-
-    if (mons)
-        return mons_traversable(p);
-
-    return (!feat_is_solid(grd(p)) && !feat_destroys_items(grd(p)));
-}
-
-// Checks whether a given monster can pass over a certain position, respecting
-// its preferred habit and capability of flight or opening doors.
-bool monster_pathfind::mons_traversable(const coord_def p)
-{
-    const monster_type montype = mons_is_zombified(mons) ? mons_zombie_base(mons)
-                                                         : mons->type;
-
-    if (!monster_habitable_grid(montype, grd(p)))
-        return (false);
-
-    // Monsters that can't open doors won't be able to pass them.
-    if (feat_is_closed_door(grd(p)) || grd(p) == DNGN_SECRET_DOOR)
-    {
-        if (mons_is_zombified(mons))
-        {
-            if (mons_class_itemuse(montype) < MONUSE_OPEN_DOORS)
-                return (false);
-        }
-        else if (mons_itemuse(mons) < MONUSE_OPEN_DOORS)
-            return (false);
-    }
-
-    // Your friends only know about doors you know about, unless they feel
-    // at home in this branch.
-    if (grd(p) == DNGN_SECRET_DOOR && mons->friendly()
-        && (mons_intel(mons) < I_NORMAL || !mons_is_native_in_branch(mons)))
-    {
-        return (false);
-    }
-
-    const trap_def* ptrap = find_trap(p);
-    if (ptrap)
-    {
-        const trap_type tt = ptrap->type;
-
-        // Don't allow allies to pass over known (to them) Zot traps.
-        if (tt == TRAP_ZOT
-            && ptrap->is_known(mons)
-            && mons->friendly())
-        {
-            return (false);
-        }
-
-        // Monsters cannot travel over teleport traps.
-        if (!_can_place_on_trap(montype, tt))
-            return (false);
-    }
-
-    return (true);
-}
-
-int monster_pathfind::travel_cost(coord_def npos)
-{
-    if (mons)
-        return mons_travel_cost(npos);
-
-    return (1);
-}
-
-// Assumes that grids that really cannot be entered don't even get here.
-// (Checked by traversable().)
-int monster_pathfind::mons_travel_cost(coord_def npos)
-{
-    ASSERT(grid_distance(pos, npos) <= 1);
-
-    // Doors need to be opened.
-    if (feat_is_closed_door(grd(npos)) || grd(npos) == DNGN_SECRET_DOOR)
-        return 2;
-
-    const int montype = mons_is_zombified(mons) ? mons_zombie_base(mons)
-                                                : mons->type;
-
-    const bool airborne = _mons_airborne(montype, -1, false);
-
-    // Travelling through water, entering or leaving water is more expensive
-    // for non-amphibious monsters, so they'll avoid it where possible.
-    // (The resulting path might not be optimal but it will lead to a path
-    // a monster of such habits is likely to prefer.)
-    // Only tested for shallow water since they can't enter deep water anyway.
-    if (!airborne && !mons_class_amphibious(montype)
-        && (grd(pos) == DNGN_SHALLOW_WATER || grd(npos) == DNGN_SHALLOW_WATER))
-    {
-        return 2;
-    }
-
-    // Try to avoid (known) traps.
-    const trap_def* ptrap = find_trap(npos);
-    if (ptrap)
-    {
-        const bool knows_trap = ptrap->is_known(mons);
-        const trap_type tt = ptrap->type;
-        if (tt == TRAP_ALARM || tt == TRAP_ZOT)
-        {
-            // Your allies take extra precautions to avoid known alarm traps.
-            // Zot traps are considered intraversable.
-            if (knows_trap && mons->friendly())
-                return (3);
-
-            // To hostile monsters, these traps are completely harmless.
-            return 1;
-        }
-
-        // Mechanical traps can be avoided by flying, as can shafts, and
-        // tele traps are never traversable anyway.
-        if (knows_trap && !airborne)
-            return 2;
-    }
-
-    return 1;
-}
-
-// The estimated cost to reach a grid is simply max(dx, dy).
-int monster_pathfind::estimated_cost(coord_def p)
-{
-    return (grid_distance(p, target));
-}
-
-void monster_pathfind::add_new_pos(coord_def npos, int total)
-{
-    hash[total].push_back(npos);
-}
-
-void monster_pathfind::update_pos(coord_def npos, int total)
-{
-    // Find hash position of old distance and delete it,
-    // then call_add_new_pos.
-    int old_total = dist[npos.x][npos.y] + estimated_cost(npos);
-
-    std::vector<coord_def> &vec = hash[old_total];
-    for (unsigned int i = 0; i < vec.size(); i++)
-    {
-        if (vec[i] == npos)
-        {
-            vec.erase(vec.begin() + i);
-            break;
-        }
-    }
-
-    add_new_pos(npos, total);
-}
-
-/////////////////////////////////////////////////////////////////////////////
 //
 // Random monsters for portal vaults.
 //
diff --git a/crawl-ref/source/mon-place.h b/crawl-ref/source/mon-place.h
index 533f0943dc..dd3523acdc 100644
--- a/crawl-ref/source/mon-place.h
+++ b/crawl-ref/source/mon-place.h
@@ -346,68 +346,9 @@ void get_vault_mon_list(std::vector<mons_spec> &list);
 
 void setup_vault_mon_list();
 
-int mons_tracking_range(const monsters *mon);
-
 monsters* get_free_monster();
 
-class monster_pathfind
-{
-public:
-    monster_pathfind();
-    virtual ~monster_pathfind();
-
-    // public methods
-    void set_range(int r);
-    coord_def next_pos(const coord_def &p) const;
-    bool init_pathfind(const monsters *mon, coord_def dest,
-                       bool diag = true, bool msg = false,
-                       bool pass_unmapped = false);
-    bool init_pathfind(coord_def src, coord_def dest,
-                       bool diag = true, bool msg = false);
-    bool start_pathfind(bool msg = false);
-    std::vector<coord_def> backtrack(void);
-    std::vector<coord_def> calc_waypoints(void);
-
-protected:
-    // protected methods
-    bool calc_path_to_neighbours(void);
-    bool traversable(coord_def p);
-    int  travel_cost(coord_def npos);
-    bool mons_traversable(coord_def p);
-    int  mons_travel_cost(coord_def npos);
-    int  estimated_cost(coord_def npos);
-    void add_new_pos(coord_def pos, int total);
-    void update_pos(coord_def pos, int total);
-    bool get_best_position(void);
-
-
-    // The monster trying to find a path.
-    const monsters *mons;
-
-    // Our destination, and the current position we're looking at.
-    coord_def start, target, pos;
-
-    // If false, do not move diagonally along the path.
-    bool allow_diagonals;
-
-    // If true, unmapped terrain is treated as traversable no matter the
-    // monster involved.
-    // (Used for player estimates of whether a monster can travel somewhere.)
-    bool traverse_unmapped;
-
-    // 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;
-
-    // The array of distances from start to any already tried point.
-    int dist[GXM][GYM];
-    // An array to store where we came from on a given shortest path.
-    int prev[GXM][GYM];
-
-    FixedVector<std::vector<coord_def>, GXM * GYM> hash;
-};
+bool can_place_on_trap(int mon_type, trap_type trap);
+bool mons_airborne(int mcls, int flies, bool paralysed);
 
 #endif  // MONPLACE_H
diff --git a/crawl-ref/source/shout.cc b/crawl-ref/source/shout.cc
index 64378ed7ad..25edbe3ee9 100644
--- a/crawl-ref/source/shout.cc
+++ b/crawl-ref/source/shout.cc
@@ -17,6 +17,7 @@
 #include "mon-behv.h"
 #include "mon-iter.h"
 #include "mon-place.h"
+#include "mon-pathfind.h"
 #include "monster.h"
 #include "mon-stuff.h"
 #include "options.h"
diff --git a/crawl-ref/source/wiz-mon.cc b/crawl-ref/source/wiz-mon.cc
index 3701d344a0..1bb1622dbb 100644
--- a/crawl-ref/source/wiz-mon.cc
+++ b/crawl-ref/source/wiz-mon.cc
@@ -21,6 +21,7 @@
 #include "macro.h"
 #include "message.h"
 #include "mon-place.h"
+#include "mon-pathfind.h"
 #include "mon-speak.h"
 #include "mon-stuff.h"
 #include "mon-iter.h"