summary refs log tree commit diff stats
path: root/src
diff options
context:
space:
mode:
authorStar Rauchenberger <fefferburbia@gmail.com>2021-07-06 13:31:37 -0400
committerStar Rauchenberger <fefferburbia@gmail.com>2021-07-06 13:31:37 -0400
commit23dbe100fb468c6268a94bcb3c448948fd686d62 (patch)
tree5c2f272b9e6aea9ee2874b65855819a09835d0a1 /src
parentcb1421b91b2f8ffa71f7ee009dad4e237ed36e2c (diff)
downloadtanetane-23dbe100fb468c6268a94bcb3c448948fd686d62.tar.gz
tanetane-23dbe100fb468c6268a94bcb3c448948fd686d62.tar.bz2
tanetane-23dbe100fb468c6268a94bcb3c448948fd686d62.zip
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.
Diffstat (limited to 'src')
-rw-r--r--src/behaviour_system.cpp55
-rw-r--r--src/direction.h4
2 files changed, 39 insertions, 20 deletions
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) {
98} 98}
99 99
100struct PathNodeInfo { 100struct PathNodeInfo {
101 int cheapestPathCost = INT_MAX; 101 double cheapestPathCost = DBL_MAX;
102 int estimatedRemainingCost = INT_MAX; 102 double estimatedRemainingCost = DBL_MAX;
103 vec2i previousPoint; 103 vec2i previousPoint;
104 Direction dirFromPreviousPoint; 104 Direction dirFromPreviousPoint;
105}; 105};
106 106
107struct SearchNode { 107struct SearchNode {
108 vec2i point; 108 vec2i point;
109 int estimatedCost = INT_MAX; 109 Direction dirFromPreviousPoint;
110 double estimatedCost = DBL_MAX;
110 int tiebreaker; // this actually counts downward. wow 111 int tiebreaker; // this actually counts downward. wow
111 112
112 SearchNode(vec2i point, int estimatedCost) : point(point), estimatedCost(estimatedCost) { 113 SearchNode(vec2i point, Direction dirFromPreviousPoint, double estimatedCost) : point(point), dirFromPreviousPoint(dirFromPreviousPoint), estimatedCost(estimatedCost) {
113 static int tiebreakerCounter = 0; 114 static int tiebreakerCounter = 0;
114 tiebreaker = tiebreakerCounter--; 115 tiebreaker = tiebreakerCounter--;
115 } 116 }
@@ -119,12 +120,14 @@ struct SearchNode {
119 } 120 }
120}; 121};
121 122
122int estimateRemainingCost(vec2i current, vec2i dest, int movementSpeed, bool cardinalDirectionsOnly) { 123double estimateRemainingCost(vec2i current, vec2i dest, int movementSpeed, bool cardinalDirectionsOnly) {
123 vec2i difference = dest - current; 124 vec2i difference = dest - current;
124 if (cardinalDirectionsOnly) { 125 if (cardinalDirectionsOnly) {
125 return (std::abs(difference.x()) + std::abs(difference.y())) / movementSpeed; 126 return (std::abs(difference.x()) + std::abs(difference.y())) / movementSpeed;
126 } else { 127 } else {
127 return std::max(std::abs(difference.x()), std::abs(difference.y())) / movementSpeed; 128 int dx = std::abs(difference.x()) / movementSpeed;
129 int dy = std::abs(difference.y()) / movementSpeed;
130 return (dx + dy) + (1.4 - 2) * std::min(dx, dy);
128 } 131 }
129} 132}
130 133
@@ -146,13 +149,13 @@ void BehaviourSystem::createPath(int spriteId) {
146 } 149 }
147 } 150 }
148 151
149 int initialCostGuess = estimateRemainingCost(sprite.loc, sprite.pathfindingDestination, sprite.movementSpeed, sprite.cardinalDirectionsOnly); 152 double initialCostGuess = estimateRemainingCost(sprite.loc, sprite.pathfindingDestination, sprite.movementSpeed, sprite.cardinalDirectionsOnly);
150 153
151 std::map<vec2i, PathNodeInfo> pathNodes; 154 std::map<vec2i, std::map<Direction, PathNodeInfo>> pathNodes;
152 pathNodes[sprite.loc] = PathNodeInfo{.cheapestPathCost = 0, .estimatedRemainingCost = initialCostGuess}; 155 pathNodes[sprite.loc][sprite.dir] = PathNodeInfo{.cheapestPathCost = 0, .estimatedRemainingCost = initialCostGuess};
153 156
154 std::priority_queue<SearchNode, std::vector<SearchNode>, std::greater<SearchNode>> openSet; 157 std::priority_queue<SearchNode, std::vector<SearchNode>, std::greater<SearchNode>> openSet;
155 openSet.emplace(sprite.loc, initialCostGuess); 158 openSet.emplace(sprite.loc, sprite.dir, initialCostGuess);
156 159
157 while (!openSet.empty()) { 160 while (!openSet.empty()) {
158 SearchNode searchNode = openSet.top(); 161 SearchNode searchNode = openSet.top();
@@ -163,8 +166,7 @@ void BehaviourSystem::createPath(int spriteId) {
163 break; 166 break;
164 } 167 }
165 168
166 PathNodeInfo& nodeInfo = pathNodes[searchNode.point]; 169 PathNodeInfo& nodeInfo = pathNodes[searchNode.point][searchNode.dirFromPreviousPoint];
167 int newCost = nodeInfo.cheapestPathCost + 1;
168 170
169 static const std::vector<Direction> allDirections = { 171 static const std::vector<Direction> allDirections = {
170 Direction::down, 172 Direction::down,
@@ -183,9 +185,17 @@ void BehaviourSystem::createPath(int spriteId) {
183 Direction::right }; 185 Direction::right };
184 186
185 std::vector<Direction> directionList = sprite.cardinalDirectionsOnly ? cardinalDirections : allDirections; 187 std::vector<Direction> directionList = sprite.cardinalDirectionsOnly ? cardinalDirections : allDirections;
186 directionList.push_back(nodeInfo.dirFromPreviousPoint);
187
188 for (Direction dir : directionList) { 188 for (Direction dir : directionList) {
189 double newCost = nodeInfo.cheapestPathCost;
190 if (dir != searchNode.dirFromPreviousPoint) {
191 newCost += 0.1;
192 }
193 if (isCardinalDirection(dir)) {
194 newCost += 1;
195 } else {
196 newCost += 1.4;
197 }
198
189 vec2i newPos = searchNode.point + unitVecInDirection(dir) * sprite.movementSpeed; 199 vec2i newPos = searchNode.point + unitVecInDirection(dir) * sprite.movementSpeed;
190 200
191 if (newPos.x() < 0 || newPos.y() < 0 || newPos.x() >= mapBounds.w() || newPos.y() >= mapBounds.h()) { 201 if (newPos.x() < 0 || newPos.y() < 0 || newPos.x() >= mapBounds.w() || newPos.y() >= mapBounds.h()) {
@@ -193,7 +203,7 @@ void BehaviourSystem::createPath(int spriteId) {
193 continue; 203 continue;
194 } 204 }
195 205
196 PathNodeInfo& neighborInfo = pathNodes[newPos]; 206 PathNodeInfo& neighborInfo = pathNodes[newPos][dir];
197 207
198 if (neighborInfo.cheapestPathCost <= newCost) { 208 if (neighborInfo.cheapestPathCost <= newCost) {
199 // There is already a faster path through this neighbor. 209 // There is already a faster path through this neighbor.
@@ -211,7 +221,7 @@ void BehaviourSystem::createPath(int spriteId) {
211 neighborInfo.previousPoint = searchNode.point; 221 neighborInfo.previousPoint = searchNode.point;
212 neighborInfo.dirFromPreviousPoint = dir; 222 neighborInfo.dirFromPreviousPoint = dir;
213 223
214 openSet.emplace(newPos, neighborInfo.cheapestPathCost + neighborInfo.estimatedRemainingCost); 224 openSet.emplace(newPos, dir, neighborInfo.cheapestPathCost + neighborInfo.estimatedRemainingCost);
215 } 225 }
216 } 226 }
217 227
@@ -222,10 +232,15 @@ void BehaviourSystem::createPath(int spriteId) {
222 232
223 vec2i curPos = sprite.pathfindingDestination; 233 vec2i curPos = sprite.pathfindingDestination;
224 while (curPos != sprite.loc) { 234 while (curPos != sprite.loc) {
225 PathNodeInfo& nodeInfo = pathNodes[curPos]; 235 const PathNodeInfo* nodeInfo = nullptr;
226 if (sprite.path.empty() || sprite.path.front().dir != nodeInfo.dirFromPreviousPoint) { 236 for (const auto& pni : pathNodes[curPos]) {
227 sprite.path.push_front(PathfindingInstruction{.dir = nodeInfo.dirFromPreviousPoint, .endpoint = curPos}); 237 if (nodeInfo == nullptr || pni.second.cheapestPathCost < nodeInfo->cheapestPathCost) {
238 nodeInfo = &pni.second;
239 }
240 }
241 if (sprite.path.empty() || sprite.path.front().dir != nodeInfo->dirFromPreviousPoint) {
242 sprite.path.push_front(PathfindingInstruction{.dir = nodeInfo->dirFromPreviousPoint, .endpoint = curPos});
228 } 243 }
229 curPos = nodeInfo.previousPoint; 244 curPos = nodeInfo->previousPoint;
230 } 245 }
231} 246}
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) {
120 } 120 }
121} 121}
122 122
123inline bool isCardinalDirection(Direction dir) {
124 return (dir == Direction::left || dir == Direction::right || dir == Direction::up || dir == Direction::down);
125}
126
123#endif /* end of include guard: DIRECTION_H_AB66A90E */ 127#endif /* end of include guard: DIRECTION_H_AB66A90E */