Module positioning::pathfinding
source · [−]Expand description
Contains an implementation of A* and all-pairs-shortest paths with fun a twist where the latter performs well as a heuristic in a specific context.
Pathfinding
Imagine we have a fixed 3D grid world with some set of blocked and non-blocked tiles that we know of statically. Dynamically, as the game or whatever other system is running, those tiles may be blocked by other things, but the statically known blocked tiles will never be open in any circumstance.
Then, we can compute all-pairs shortest paths on the statically known paths and use that information in order to inform a clever heuristic for the A* algorithm. That is the strategy taken in this module.
Structs
The all-pairs shortest paths on the static graph described above will always be an admissible heuristic for the dynamic graph as long as the statically closed tiles are never unblocked.
The 3D hamming distance metric is always fine to use.
Enums
Traits
An admissible heuristic for the A* pathfinding algorithm is one which always returns an optimistic result. Oftentimes, a good heuristic can make a big performance difference. The more tight the heuristic is to the real distance, the better.
Functions
Computes a data structure caching the distances between all open positions