Merged client pathfinder changes.

2 files changed, 32 insertions, 6 deletions

diff --git a/ChangeLog b/ChangeLog
index 20e214a3..72b89bc1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,7 @@
+2006-09-09  Guillaume Melquiond  <guillaume.melquiond@gmail.com>
+
+	* src/map.cpp: Merged client pathfinder changes.
+
 2006-09-04  Guillaume Melquiond  <guillaume.melquiond@gmail.com>
 
 	* src/mapcomposite.cpp, src/mapcomposite.h, src/state.cpp: Fixed wrong
diff --git a/src/map.cpp b/src/map.cpp
index 6487b700..ec6767af 100644
--- a/src/map.cpp
+++ b/src/map.cpp
@@ -123,6 +123,8 @@ Map::getMetaTile(int x, int y)
     return &metaTiles[x + y * width];
 }
 
+static int const basicCost = 100;
+
 std::list<PATH_NODE>
 Map::findPath(int startX, int startY, int destX, int destY)
 {
@@ -201,13 +203,27 @@ Map::findPath(int startX, int startY, int destX, int destY)
                     }
                 }
 
-                // Calculate G cost for this route, 10 for moving straight and
-                // 14 for moving diagonal
-                int Gcost = curr.tile->Gcost + ((dx == 0 || dy == 0) ? 10 : 14);
+                // Calculate G cost for this route, ~sqrt(2) for moving diagonal
+                int Gcost = curr.tile->Gcost +
+                    (dx == 0 || dy == 0 ? basicCost : basicCost * 362 / 256);
+
+                /* Demote an arbitrary direction to speed pathfinding by
+                   adding a defect (TODO: change depending on the desired
+                   visual effect, e.g. a cross-product defect toward
+                   destination).
+                   Important: as long as the total defect along any path is
+                   less than the basicCost, the pathfinder will still find one
+                   of the shortest paths! */
+                if (dx == 0 || dy == 0)
+                {
+                    // Demote horizontal and vertical directions, so that two
+                    // consecutive directions cannot have the same Fcost.
+                    ++Gcost;
+                }
 
                 // Skip if Gcost becomes too much
                 // Warning: probably not entirely accurate
-                if (Gcost > 200)
+                if (Gcost > 20 * basicCost)
                 {
                     continue;
                 }
@@ -215,8 +231,14 @@ Map::findPath(int startX, int startY, int destX, int destY)
                 if (newTile->whichList != onOpenList)
                 {
                     // Found a new tile (not on open nor on closed list)
-                    // Update Hcost of the new tile using Manhatten distance
-                    newTile->Hcost = 10 * (abs(x - destX) + abs(y - destY));
+
+                    /* Update Hcost of the new tile. The pathfinder does not
+                       work reliably if the heuristic cost is higher than the
+                       real cost. In particular, using Manhattan distance is
+                       forbidden here. */
+                    int dx = std::abs(x - destX), dy = std::abs(y - destY);
+                    newTile->Hcost = std::abs(dx - dy) * basicCost +
+                        std::min(dx, dy) * (basicCost * 362 / 256);
 
                     // Set the current tile as the parent of the new tile
                     newTile->parentX = curr.x;