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

1 files changed, 33 insertions, 1 deletions

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