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, 39 insertions, 0 deletions

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