Trait hierarchical_pathfinding::neighbors::Neighborhood

pub trait Neighborhood: Clone + Debug {
    fn get_all_neighbors(
        &self, 
        point: (usize, usize), 
        target: &mut Vec<(usize, usize)>
    );
    fn heuristic(&self, point: (usize, usize), goal: (usize, usize)) -> usize;
}

Defines how a Path can move along the Grid.

Different use cases may have different conditions for Paths. For example if movement is restricted to the 4 cardinal directions, any Paths generated should reflect that by only containing those steps.

This Trait is a generalized solution to that problem. It provides a function to query all neighboring Points of an existing Point and a Heuristic for how long it might take to reach a goal from a Point.

The most common implementations of this Trait are already provided by this Module:

• ManhattanNeighborhood for Agents that can move up, down, left or right
• MooreNeighborhood for Agents that can move up, down, left, right, as well as the 4 diagonals (up-right, …)

Required methods

fn get_all_neighbors(
    &self,
    point: (usize, usize),
    target: &mut Vec<(usize, usize)>
)

Provides all the Neighbors of a Point.

The Neighbors should be written into target

Note that it is not necessary to check weather the Tile at a Point is solid or not. That check is done later.

fn heuristic(&self, point: (usize, usize), goal: (usize, usize)) -> usize

Gives a Heuristic for how long it takes to reach goal from point.

This is usually the Distance between the two Points in the Metric of your Neighborhood.

The returned value must be less than or equal to the real cost of walking from point to goal. See A* for details.

If there is no proper way of calculation how long it takes, simply return 0. This will increase the time it takes to calculate the Path, but at least it will always be correct.

Implementors

impl Neighborhood for ManhattanNeighborhood

impl Neighborhood for MooreNeighborhood