diff options
| -rw-r--r-- | ChangeLog | 4 | ||||
| -rw-r--r-- | src/map.cpp | 34 |
2 files changed, 32 insertions, 6 deletions
@@ -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; |