From 751964878b50152dc63d6d02f3455edd7939d013 Mon Sep 17 00:00:00 2001 From: Guillaume Melquiond Date: Sat, 9 Sep 2006 08:00:51 +0000 Subject: Merged client pathfinder changes. --- ChangeLog | 4 ++++ src/map.cpp | 34 ++++++++++++++++++++++++++++------ 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 + + * src/map.cpp: Merged client pathfinder changes. + 2006-09-04 Guillaume Melquiond * 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 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; -- cgit v1.2.3-70-g09d2