Struct positioning::pathfinding::AllPairsShortestPaths

pub struct AllPairsShortestPaths(_);

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.

This heuristic is extremely valuable for the use case described in this module. Imagine the following scenario:

____________
|e X   start|
|n X        |
|d X        |
|  XXXXXXX  |
|           |
-------------

The HammingDistance heuristic will send you looking all throughout the top right region before you realize you’re meant to go around, whereas the all pairs metric will immediately be able to bypass this obstacle. In the presence of dynamically but not statically blocked tiles, we can run into these problems again easily, but we avoid them in many cases even then.

Correctness: When you use this heuristic, you should be careful to ensure that the dynamically open positions are a subset of the statically open positions.

Implementations

impl AllPairsShortestPaths

pub fn distance_between(
    &self,
    position: Position,
    other_position: Position
) -> Option<WithInfinity<u64>>

Trait Implementations

impl Heuristic for AllPairsShortestPaths

fn heuristic_distance(&self, start: Position, end: Position) -> WithInfinity<u64>

fn find_shortest_path(
    &self,
    open_positions: &BTreeSet<Position>,
    start: Position,
    end: Position
) -> Option<VecDeque<Position>>