Struct de_pathing::finder::PathFinder

pub struct PathFinder {
    triangles: RTree<GraphTriangle>,
    exclusions: RTree<GraphExclusion>,
    graph: VisibilityGraph,
}

A struct used for path finding.

Fields

triangles: RTree<GraphTriangle>

Spatial index of triangles. It is used to find edges neighboring start and end pints of a path to be found.

exclusions: RTree<GraphExclusion>

All mutually exclusive exclusion areas which are not covered by triangles. It is used to find way out of unreachable area.

graph: VisibilityGraph

Implementations

impl PathFinder

pub(crate) fn new(bounds: &MapBounds) -> Self

Creates a new path finder. It is assumed that there are no obstacles within bounds.

pub(crate) fn from_triangles( triangles: Vec<Triangle>, exclusions: Vec<ExclusionArea> ) -> Self

Creates a new path finder based on a triangulated accessible area.

Arguments

• triangles - the triangulation of the map. It must a) fully cover area where objects (their centroids so there needs to be padding) can freely move, b) contain not triangle-to-triangle intersections, c) cover any of the area where object cannot freely move.

• exclusions - mutually exclusive areas which fully cover area not covered by triangles. There is no intersection between the exclusions and triangles.

pub fn find_path<P: Into<Point<f32>>>( &self, from: P, target: PathTarget ) -> Option<Path>

Returns a shortest path between two points.

Returns None if there is no path between the two points.

fn locate_triangle_edges(&self, point: Point<f32>) -> Vec<Step>

fn locate_exclusion_edges(&self, point: Point<f32>) -> Vec<Step>