Implement pathfinding for monsters, using the A* algorithm.

It's not actually used anywhere yet, but I've implemented a wizmode
testing function (x on monster, then 'w') that calculates the shortest
path to any playerchosen destination on the level, and it seems to work 
quite well. The monsters tend to take zigzag paths but that should be 
easy enough to smooth out and in any case doesn't matter all that much 
since the player usually won't witness this. Oh, and though I tested 
the whole thing in a labyrinth, it went ridiculously fast! I'd rather
doubted that but Darshan was completely right, as usually. :p

Please don't remove the debugging output yet, I still need them.


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

12 files changed, 361 insertions, 34 deletions

diff --git a/crawl-ref/source/acr.cc b/crawl-ref/source/acr.cc
index 6a93a94b73..969fff663f 100644
--- a/crawl-ref/source/acr.cc
+++ b/crawl-ref/source/acr.cc
@@ -537,7 +537,7 @@ static void _handle_wizard_command( void )
         break;
 
     case 'v':
-        // this command isn't very exciting... feel free to replace
+        // This command isn't very exciting... feel free to replace.
         i = prompt_invent_item( "Value of which item?", MT_INVLIST, -1 );
         if (i == PROMPT_ABORT || !is_random_artefact( you.inv[i] ))
         {
@@ -551,8 +551,8 @@ static void _handle_wizard_command( void )
         break;
 
     case '+':
-        i = prompt_invent_item(
-                "Make an artefact out of which item?", MT_INVLIST, -1 );
+        i = prompt_invent_item( "Make an artefact out of which item?",
+                                MT_INVLIST, -1 );
         if (i == PROMPT_ABORT)
         {
             canned_msg( MSG_OK );
@@ -565,7 +565,7 @@ static void _handle_wizard_command( void )
             break;
         }
 
-        // set j == equipment slot of chosen item, remove old randart benefits
+        // Set j == equipment slot of chosen item, remove old randart benefits.
         for (j = 0; j < NUM_EQUIP; j++)
         {
             if (you.equip[j] == i)
@@ -590,7 +590,7 @@ static void _handle_wizard_command( void )
         break;
 
     case '|':
-        // create all unrandarts
+        // Create all unrandarts.
         for (tmp = 1; tmp < NO_UNRANDARTS; tmp++)
         {
             int islot = get_item_slot();
@@ -609,7 +609,7 @@ static void _handle_wizard_command( void )
             move_item_to_grid( &islot, you.x_pos, you.y_pos );
         }
 
-        // create all fixed artefacts
+        // Create all fixed artefacts.
         for (tmp = SPWPN_START_FIXEDARTS;
              tmp < SPWPN_START_NOGEN_FIXEDARTS; tmp++)
         {
diff --git a/crawl-ref/source/command.cc b/crawl-ref/source/command.cc
index 5f4b35fef0..eb04dafcd5 100644
--- a/crawl-ref/source/command.cc
+++ b/crawl-ref/source/command.cc
@@ -305,10 +305,10 @@ static void _adjust_spells(void)
         return;
     }
 
-    // print out targeted spell:
+    // Print targeted spell.
     mprf( "%c - %s", keyin, spell_title( spell ) );
 
-    // Select target slot
+    // Select target slot.
     keyin = 0;
     while ( !isalpha(keyin) )
     {
@@ -662,6 +662,7 @@ static const char *targeting_help_1 =
     "<w>F</w>: cycle monster friendly/good neutral/neutral/hostile\n"
     "<w>P</w>: apply divine blessing to monster\n"
     "<w>m</w>: move monster or player\n"
+    "<w>w</w>: calculate shortest path to any point on the map\n"
 #endif
 ;
 
diff --git a/crawl-ref/source/debug.cc b/crawl-ref/source/debug.cc
index 5dd91441a7..7337faa475 100644
--- a/crawl-ref/source/debug.cc
+++ b/crawl-ref/source/debug.cc
@@ -3989,7 +3989,6 @@ void wizard_give_monster_item(monsters *mon)
 #endif
 
 #ifdef WIZARD
-
 static void _move_player(int x, int y)
 {
     // no longer held in net
@@ -4064,6 +4063,39 @@ void wizard_move_player_or_monster(int x, int y)
 
     already_moving = false;
 }
+
+void debug_pathfind(int mid)
+{
+    if (mid == NON_MONSTER)
+        return;
+
+    mpr("Choose a destination!");
+#ifdef USE_TILE
+    more();
+#endif
+    coord_def dest;
+    show_map(dest, true);
+    redraw_screen();
+
+    monsters &mon = menv[mid];
+     mprf("Attempting to calculate a path from (%d, %d) to (%d, %d)...",
+          mon.x, mon.y, dest.x, dest.y);
+    monster_pathfind mp;
+    bool success = mp.start_pathfind(&mon, dest, true);
+    if (success)
+    {
+        std::vector<coord_def> path = mp.backtrack();
+        std::string path_str = "";
+        mpr("Here's the shortest path: ");
+        for (unsigned int i = 0; i < path.size(); i++)
+        {
+            snprintf(info, INFO_SIZE, "(%d, %d)  ", path[i].x, path[i].y);
+            path_str += info;
+        }
+
+        mpr(path_str.c_str());
+    }
+}
 #endif
 
 #ifdef DEBUG_DIAGNOSTICS
diff --git a/crawl-ref/source/debug.h b/crawl-ref/source/debug.h
index 6b4039bd8b..700fce055f 100644
--- a/crawl-ref/source/debug.h
+++ b/crawl-ref/source/debug.h
@@ -165,6 +165,7 @@ void debug_make_monster_shout(monsters* mon);
 void debug_apply_monster_blessing(monsters* mon);
 void wizard_give_monster_item(monsters* mon);
 void wizard_move_player_or_monster(int x, int y);
+void debug_pathfind(int mid);
 
 #ifdef DEBUG_DIAGNOSTICS
 void generate_map_stats();
diff --git a/crawl-ref/source/directn.cc b/crawl-ref/source/directn.cc
index feb805e7dc..2933230868 100644
--- a/crawl-ref/source/directn.cc
+++ b/crawl-ref/source/directn.cc
@@ -915,8 +915,17 @@ void direction(dist& moves, targeting_type restricts,
             skip_iter = true;
 
             break;
-#endif
 
+        case CMD_TARGET_WIZARD_PATHFIND:
+            if (!you.wizard || !in_bounds(moves.tx, moves.ty))
+                break;
+            mid = mgrd[moves.tx][moves.ty];
+            if (mid == NON_MONSTER)
+                break;
+
+            debug_pathfind(mid);
+            break;
+#endif
         case CMD_TARGET_DESCRIBE:
             full_describe_square(moves.target());
             force_redraw = true;
@@ -947,10 +956,10 @@ void direction(dist& moves, targeting_type restricts,
 
             // Confirm self-targeting on TARG_ENEMY.
             // Conceivably we might want to confirm on TARG_ANY too.
-            if ( moves.isTarget
-                 && moves.tx == you.x_pos && moves.ty == you.y_pos
-                 && mode == TARG_ENEMY
-                 && !yesno("Really target yourself?", false, 'n'))
+            if (moves.isTarget
+                && moves.tx == you.x_pos && moves.ty == you.y_pos
+                && mode == TARG_ENEMY
+                && !yesno("Really target yourself?", false, 'n'))
             {
                 mesclr();
                 show_prompt = true;
@@ -983,18 +992,17 @@ void direction(dist& moves, targeting_type restricts,
 
         bool have_moved = false;
 
-        if ( old_tx != moves.tx || old_ty != moves.ty )
+        if (old_tx != moves.tx || old_ty != moves.ty)
         {
             have_moved = true;
-            show_beam = show_beam &&
-                find_ray(you.x_pos, you.y_pos, moves.tx, moves.ty, true, ray,
-                         0, true);
+            show_beam = show_beam && find_ray(you.x_pos, you.y_pos, moves.tx,
+                                              moves.ty, true, ray, 0, true);
         }
 
-        if ( force_redraw )
+        if (force_redraw)
             have_moved = true;
 
-        if ( have_moved )
+        if (have_moved)
         {
             // If the target x,y has changed, the beam must have changed.
             if ( show_beam )
@@ -1017,9 +1025,9 @@ void direction(dist& moves, targeting_type restricts,
         {
             viewwindow(true, false);
 #endif
-            if ( show_beam
-                 && in_vlos(grid2viewX(moves.tx), grid2viewY(moves.ty))
-                 && moves.target() != you.pos() )
+            if (show_beam
+                && in_vlos(grid2viewX(moves.tx), grid2viewY(moves.ty))
+                && moves.target() != you.pos() )
             {
                 // Draw the new ray with magenta '*'s, not including
                 // your square or the target square.
@@ -2494,6 +2502,7 @@ command_type targeting_behaviour::get_command(int key)
     case 's':  return CMD_TARGET_WIZARD_MAKE_SHOUT;
     case 'g':  return CMD_TARGET_WIZARD_GIVE_ITEM;
     case 'm':  return CMD_TARGET_WIZARD_MOVE;
+    case 'w':  return CMD_TARGET_WIZARD_PATHFIND;
 #endif
     case 'v':  return CMD_TARGET_DESCRIBE;
     case '?':  return CMD_TARGET_HELP;
diff --git a/crawl-ref/source/enum.h b/crawl-ref/source/enum.h
index 38dae10512..a267d894af 100644
--- a/crawl-ref/source/enum.h
+++ b/crawl-ref/source/enum.h
@@ -601,6 +601,7 @@ enum command_type
     CMD_TARGET_WIZARD_MAKE_SHOUT,
     CMD_TARGET_WIZARD_GIVE_ITEM,
     CMD_TARGET_WIZARD_MOVE,
+    CMD_TARGET_WIZARD_PATHFIND,
     CMD_TARGET_HELP,
 
 #ifdef USE_TILE
diff --git a/crawl-ref/source/items.cc b/crawl-ref/source/items.cc
index 96b3f907a2..0e9dd58955 100644
--- a/crawl-ref/source/items.cc
+++ b/crawl-ref/source/items.cc
@@ -260,7 +260,7 @@ bool dec_inv_item_quantity( int obj, int amount )
         }
 
         you.inv[obj].base_type = OBJ_UNASSIGNED;
-        you.inv[obj].quantity = 0;
+        you.inv[obj].quantity  = 0;
         you.inv[obj].props.clear();
 
         ret = true;
diff --git a/crawl-ref/source/mon-util.cc b/crawl-ref/source/mon-util.cc
index bccde8e679..6e13d29153 100644
--- a/crawl-ref/source/mon-util.cc
+++ b/crawl-ref/source/mon-util.cc
@@ -2772,8 +2772,8 @@ bool mons_class_can_pass(const int mclass, const dungeon_feature_type grid)
     if (mons_is_wall_shielded(mclass))
     {
         // Permanent walls can't be passed through.
-        return (!grid_is_solid(grid) ||
-                   (grid_is_rock(grid) && !grid_is_permarock(grid)));
+        return (!grid_is_solid(grid)
+                || grid_is_rock(grid) && !grid_is_permarock(grid));
     }
 
     return !grid_is_solid(grid);
diff --git a/crawl-ref/source/monplace.cc b/crawl-ref/source/monplace.cc
index 83db1833da..5ea9a3b5d7 100644
--- a/crawl-ref/source/monplace.cc
+++ b/crawl-ref/source/monplace.cc
@@ -17,6 +17,7 @@
 #include "monplace.h"
 
 #include "branch.h"
+#include "directn.h" // for the Compass
 #include "externs.h"
 #include "ghost.h"
 #include "lev-pand.h"
@@ -76,7 +77,7 @@ bool grid_compatible(dungeon_feature_type grid_wanted,
                 && actual_grid <= DNGN_CLEAR_PERMAROCK_WALL);
     }
 
-    // Restricted fountains during generation, so we don't monsters
+    // Restricted fountains during generation, so we don't get monsters
     // "trapped" in fountains for easy killing.
     return (grid_wanted == actual_grid
             || (grid_wanted == DNGN_DEEP_WATER
@@ -2222,3 +2223,246 @@ monster_type rand_dragon( dragon_class_type type )
 
     return (summoned);
 }
+
+
+/////////////////////////////////////////////////////////////////////////////
+// monster_pathfind
+
+monster_pathfind::monster_pathfind()
+    : mons(), target(), min_length(0), dist(), prev()
+{
+}
+
+monster_pathfind::~monster_pathfind()
+{
+}
+
+// Returns true if a path was found, else false.
+bool monster_pathfind::start_pathfind(monsters *mon, coord_def dest, bool msg)
+{
+    mons   = mon;
+
+    // We're doing a reverse search from target to monster.
+    start  = dest;
+    target = coord_def(mon->x, mon->y);
+    pos    = start;
+
+    // Easy enough. :P
+    if (start == target)
+    {
+        if (msg)
+            mpr("The monster is already there!");
+
+        return (true);
+    }
+
+    max_length = min_length = grid_distance(pos.x, pos.y, target.x, target.y);
+//    memset(dist, INFINITE_DISTANCE, sizeof(dist));
+    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
+    {
+        success = calc_path_to_neighbours();
+        if (success)
+            return (true);
+
+        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()
+{
+//    mprf("in calc_path_to_neighbours() for (%d,%d)", pos.x, pos.y);
+    coord_def npos;
+    int distance, old_dist, total;
+    for (int dir = 0; dir < 8; dir++)
+    {
+        npos = pos + Compass[dir];
+
+//        mprf("Looking at neighbour (%d,%d)", npos.x, npos.y);
+        if (!in_bounds(npos))
+            continue;
+
+        if (!traversable(npos))
+            continue;
+
+        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);
+        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);
+
+                add_new_pos(npos, total);
+                if (total > max_length)
+                    max_length = total;
+            }
+            else
+            {
+                mprf("Improving (%d,%d) to total dist %d",
+                     npos.x, npos.y, total);
+
+                update_pos(npos, total);
+            }
+
+            // Update distance start->pos.
+            dist[npos.x][npos.y] = distance;
+
+            // Set backtracking information.
+            // Converts the Compass direction to their counterpart.
+            //      7  0  1
+            //      6  .  2
+            //      5  4  3
+
+            prev[npos.x][npos.y] = (dir + 4) % 8;
+
+            // Are we finished?
+            if (npos == target)
+            {
+                mpr("Arrived at target.");
+                return (true);
+            }
+        }
+    }
+    return (false);
+}
+
+bool monster_pathfind::get_best_position()
+{
+//    mprf("minlength: %d, maxlength: %d", min_length, max_length);
+    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];
+            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);
+
+            return (true);
+        }
+//        mprf("No positions for path length %d.", i);
+    }
+
+    // Nothing found? Then there's no path! :(
+    return (false);
+}
+
+std::vector<coord_def> monster_pathfind::backtrack()
+{
+    mpr("Backtracking...");
+    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));
+        mprf("prev: (%d, %d), pos: (%d, %d)", Compass[dir].x, Compass[dir].y,
+                                              pos.x, pos.y);
+        path.push_back(pos);
+
+        if (pos.x == 0 && pos.y == 0)
+            break;
+    }
+    while (pos != start);
+    ASSERT(pos == start);
+
+    return path;
+}
+
+bool monster_pathfind::traversable(coord_def p)
+{
+    const int montype = mons_is_zombified(mons) ? mons_zombie_base(mons)
+                                                : mons->type;
+
+    if (!monster_habitable_grid(montype, grd(p)))
+    {
+//        mprf("Feature %d is not a habitable grid.", grd(p));
+        return (false);
+    }
+
+    // Don't generate monsters on top of teleport traps.
+    const int trap = trap_at_xy(p.x, p.y);
+    if (trap >= 0)
+    {
+//        mpr("There's a trap here!");
+        if (!_can_place_on_trap(montype, env.trap[trap].type))
+        {
+//            mpr("Monster can't be placed on trap.");
+            return (false);
+        }
+    }
+//    mprf("Grid (%d, %d) is traversable.", p.x, p.y);
+    return (true);
+}
+
+int monster_pathfind::travel_cost(coord_def npos)
+{
+    ASSERT(grid_distance(pos.x, pos.y, npos.x, npos.y) <= 1);
+
+    // TODO: Make traps/shallow water more expensive, etc.
+    return 1;
+}
+
+int monster_pathfind::estimated_cost(coord_def p)
+{
+    return (grid_distance(p.x, p.y, target.x, target.y));
+}
+
+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)
+        {
+//            mpr("Attempting to erase entry.");
+            vec.erase(vec.begin() + i);
+            break;
+        }
+    }
+
+    add_new_pos(npos, total);
+}
diff --git a/crawl-ref/source/monplace.h b/crawl-ref/source/monplace.h
index a4752a9b52..cfa3f9ca4d 100644
--- a/crawl-ref/source/monplace.h
+++ b/crawl-ref/source/monplace.h
@@ -294,4 +294,43 @@ coord_def find_newmons_square_contiguous(monster_type mons_class,
 
 void spawn_random_monsters();
 
+class monster_pathfind
+{
+public:
+    monster_pathfind();
+    virtual ~monster_pathfind();
+
+    // public methods
+    bool start_pathfind(monsters *mon, coord_def dest, bool msg = false);
+    std::vector<coord_def> backtrack(void);
+
+protected:
+    // protected methods
+    bool calc_path_to_neighbours(void);
+    bool traversable(coord_def p);
+    int  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.
+    monsters *mons;
+
+    // Our destination, and the current position we're looking at.
+    coord_def start, target, pos;
+
+    // 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  // MONPLACE_H
diff --git a/crawl-ref/source/store.h b/crawl-ref/source/store.h
index f5f3f52b4a..23277348a3 100644
--- a/crawl-ref/source/store.h
+++ b/crawl-ref/source/store.h
@@ -352,7 +352,7 @@ public:
     void           set_max_size(vec_size size);
     vec_size       get_max_size() const;
 
-    // NOTE: If the const versions of get_value() or [] are given a
+    // NOTE: If the const versions of get_value() or [] are given an
     // index which doesn't exist, they will assert.
     const CrawlStoreValue& get_value(const vec_size &index) const;
     const CrawlStoreValue& operator[] (const vec_size &index) const;
diff --git a/crawl-ref/source/traps.cc b/crawl-ref/source/traps.cc
index a12d2a8bfe..d6646e9dba 100644
--- a/crawl-ref/source/traps.cc
+++ b/crawl-ref/source/traps.cc
@@ -925,23 +925,23 @@ dungeon_feature_type trap_category(trap_type type)
     }
 }                               // end trap_category()
 
-// returns index of the trap for a given (x,y) coordinate pair {dlb}
+// Returns index of the trap for a given (x,y) coordinate pair {dlb}
 int trap_at_xy(int which_x, int which_y)
 {
 
     for (int which_trap = 0; which_trap < MAX_TRAPS; which_trap++)
     {
-        if (env.trap[which_trap].x == which_x &&
-            env.trap[which_trap].y == which_y &&
-            env.trap[which_trap].type != TRAP_UNASSIGNED)
+        if (env.trap[which_trap].x == which_x
+            && env.trap[which_trap].y == which_y
+            && env.trap[which_trap].type != TRAP_UNASSIGNED)
         {
             return (which_trap);
         }
     }
 
-    // no idea how well this will be handled elsewhere: {dlb}
+    // No idea how well this will be handled elsewhere. {dlb}
     return (-1);
-}                               // end trap_at_xy()
+}
 
 trap_type trap_type_at_xy(int x, int y)
 {