From 23dbe100fb468c6268a94bcb3c448948fd686d62 Mon Sep 17 00:00:00 2001 From: Star Rauchenberger Date: Tue, 6 Jul 2021 13:31:37 -0400 Subject: Improved eight-direction pathfinding In the past, not using the "cardinal directions only" flag resulted in awkward and unintuitive paths. Two changes were made to the algorithm to improve these paths. One, nodes in the graph are now a pair of a position and the direction taken to get there. This way, a small penalty can be applied whenever a turn is taken, which should incentivise paths with fewer turns (which should be simpler). This change theoretically affects the cardinal mode as well, but in practice it is unlikely to change the paths that would've been generated. This also multiplies the search space by eight (four in cardinal mode), but so far it does not appear to be a significant resource drain. Two, the heuristic used in eight-directions mode is now octile distance, instead of dominant axis distance. Additionally, the real cost of moving diagonally is ~sqrt(2) instead of 1. This somewhat disincentivises diagonal movement, since it is no longer considered the same as cardinal movement (even though cardinal and diagonal movement occurs at the same speed), but the turning penalty makes moving diagonally more favourable than zigzagging cardinally to reach a diagonal destination. Most scripted movement in the game is likely to use cardinal mode because that mirrors the way most scripted movement in Mother 3 works, but in some cases (the Hinawa event on the cliff) diagonal movement just looks better, and thus it's useful to have the improved pathfinding algorithm. --- src/behaviour_system.cpp | 55 ++++++++++++++++++++++++++++++------------------ src/direction.h | 4 ++++ 2 files changed, 39 insertions(+), 20 deletions(-) (limited to 'src') diff --git a/src/behaviour_system.cpp b/src/behaviour_system.cpp index f4dc388..06e4ae0 100644 --- a/src/behaviour_system.cpp +++ b/src/behaviour_system.cpp @@ -98,18 +98,19 @@ bool BehaviourSystem::isFollowingPath(int spriteId) { } struct PathNodeInfo { - int cheapestPathCost = INT_MAX; - int estimatedRemainingCost = INT_MAX; + double cheapestPathCost = DBL_MAX; + double estimatedRemainingCost = DBL_MAX; vec2i previousPoint; Direction dirFromPreviousPoint; }; struct SearchNode { vec2i point; - int estimatedCost = INT_MAX; + Direction dirFromPreviousPoint; + double estimatedCost = DBL_MAX; int tiebreaker; // this actually counts downward. wow - SearchNode(vec2i point, int estimatedCost) : point(point), estimatedCost(estimatedCost) { + SearchNode(vec2i point, Direction dirFromPreviousPoint, double estimatedCost) : point(point), dirFromPreviousPoint(dirFromPreviousPoint), estimatedCost(estimatedCost) { static int tiebreakerCounter = 0; tiebreaker = tiebreakerCounter--; } @@ -119,12 +120,14 @@ struct SearchNode { } }; -int estimateRemainingCost(vec2i current, vec2i dest, int movementSpeed, bool cardinalDirectionsOnly) { +double estimateRemainingCost(vec2i current, vec2i dest, int movementSpeed, bool cardinalDirectionsOnly) { vec2i difference = dest - current; if (cardinalDirectionsOnly) { return (std::abs(difference.x()) + std::abs(difference.y())) / movementSpeed; } else { - return std::max(std::abs(difference.x()), std::abs(difference.y())) / movementSpeed; + int dx = std::abs(difference.x()) / movementSpeed; + int dy = std::abs(difference.y()) / movementSpeed; + return (dx + dy) + (1.4 - 2) * std::min(dx, dy); } } @@ -146,13 +149,13 @@ void BehaviourSystem::createPath(int spriteId) { } } - int initialCostGuess = estimateRemainingCost(sprite.loc, sprite.pathfindingDestination, sprite.movementSpeed, sprite.cardinalDirectionsOnly); + double initialCostGuess = estimateRemainingCost(sprite.loc, sprite.pathfindingDestination, sprite.movementSpeed, sprite.cardinalDirectionsOnly); - std::map pathNodes; - pathNodes[sprite.loc] = PathNodeInfo{.cheapestPathCost = 0, .estimatedRemainingCost = initialCostGuess}; + std::map> pathNodes; + pathNodes[sprite.loc][sprite.dir] = PathNodeInfo{.cheapestPathCost = 0, .estimatedRemainingCost = initialCostGuess}; std::priority_queue, std::greater> openSet; - openSet.emplace(sprite.loc, initialCostGuess); + openSet.emplace(sprite.loc, sprite.dir, initialCostGuess); while (!openSet.empty()) { SearchNode searchNode = openSet.top(); @@ -163,8 +166,7 @@ void BehaviourSystem::createPath(int spriteId) { break; } - PathNodeInfo& nodeInfo = pathNodes[searchNode.point]; - int newCost = nodeInfo.cheapestPathCost + 1; + PathNodeInfo& nodeInfo = pathNodes[searchNode.point][searchNode.dirFromPreviousPoint]; static const std::vector allDirections = { Direction::down, @@ -183,9 +185,17 @@ void BehaviourSystem::createPath(int spriteId) { Direction::right }; std::vector directionList = sprite.cardinalDirectionsOnly ? cardinalDirections : allDirections; - directionList.push_back(nodeInfo.dirFromPreviousPoint); - for (Direction dir : directionList) { + double newCost = nodeInfo.cheapestPathCost; + if (dir != searchNode.dirFromPreviousPoint) { + newCost += 0.1; + } + if (isCardinalDirection(dir)) { + newCost += 1; + } else { + newCost += 1.4; + } + vec2i newPos = searchNode.point + unitVecInDirection(dir) * sprite.movementSpeed; if (newPos.x() < 0 || newPos.y() < 0 || newPos.x() >= mapBounds.w() || newPos.y() >= mapBounds.h()) { @@ -193,7 +203,7 @@ void BehaviourSystem::createPath(int spriteId) { continue; } - PathNodeInfo& neighborInfo = pathNodes[newPos]; + PathNodeInfo& neighborInfo = pathNodes[newPos][dir]; if (neighborInfo.cheapestPathCost <= newCost) { // There is already a faster path through this neighbor. @@ -211,7 +221,7 @@ void BehaviourSystem::createPath(int spriteId) { neighborInfo.previousPoint = searchNode.point; neighborInfo.dirFromPreviousPoint = dir; - openSet.emplace(newPos, neighborInfo.cheapestPathCost + neighborInfo.estimatedRemainingCost); + openSet.emplace(newPos, dir, neighborInfo.cheapestPathCost + neighborInfo.estimatedRemainingCost); } } @@ -222,10 +232,15 @@ void BehaviourSystem::createPath(int spriteId) { vec2i curPos = sprite.pathfindingDestination; while (curPos != sprite.loc) { - PathNodeInfo& nodeInfo = pathNodes[curPos]; - if (sprite.path.empty() || sprite.path.front().dir != nodeInfo.dirFromPreviousPoint) { - sprite.path.push_front(PathfindingInstruction{.dir = nodeInfo.dirFromPreviousPoint, .endpoint = curPos}); + const PathNodeInfo* nodeInfo = nullptr; + for (const auto& pni : pathNodes[curPos]) { + if (nodeInfo == nullptr || pni.second.cheapestPathCost < nodeInfo->cheapestPathCost) { + nodeInfo = &pni.second; + } + } + if (sprite.path.empty() || sprite.path.front().dir != nodeInfo->dirFromPreviousPoint) { + sprite.path.push_front(PathfindingInstruction{.dir = nodeInfo->dirFromPreviousPoint, .endpoint = curPos}); } - curPos = nodeInfo.previousPoint; + curPos = nodeInfo->previousPoint; } } diff --git a/src/direction.h b/src/direction.h index 325bcaf..86eb31f 100644 --- a/src/direction.h +++ b/src/direction.h @@ -120,4 +120,8 @@ inline Direction cardinalDirectionFacingPoint(vec2i point) { } } +inline bool isCardinalDirection(Direction dir) { + return (dir == Direction::left || dir == Direction::right || dir == Direction::up || dir == Direction::down); +} + #endif /* end of include guard: DIRECTION_H_AB66A90E */ -- cgit 1.4.1