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.

1 files changed, 4 insertions, 0 deletions

@@ -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 */