Struct Graph

pub struct Graph<T>
where
    T: VertexDataProvider,
{
    pub vertices: Vec<T>,
    pub max_search_iterations: i32,
}

A collection of GraphVertices for pathfinding.

See module docs

Fields

vertices: Vec<T>

Vertices of the graph.

max_search_iterations: i32

The maximum iterations A* pathfinding will attempt before giving up and returning its best path.

Default: 1000

Notes

A* is inefficient when its desired destination is isolated or it must backtrack a substantial distance before it may reach the goal. Higher max iteration numbers will be required for huge graphs and graphs with many obstacles. Whereas, lower max iterations may be desired for smaller simple graphs.

Negative numbers disable max iterations

Implementations

impl<T: VertexDataProvider> Graph<T>

pub fn new() -> Self

Creates new empty graph.

pub fn set_vertices(&mut self, vertices: Vec<T>)

Sets active set of vertices. Links between vertices must contain valid indices (which are not out-of-bounds), otherwise path from/to such vertices won’t be built.

pub fn get_closest_vertex_to(&self, point: Vector3<f32>) -> Option<usize>

Tries to find a vertex closest to given point.

Notes

O(n) complexity.

pub fn link_bidirect(&mut self, a: usize, b: usize)

Creates bidirectional link between two vertices. Bidirectional means that point a can be reached from point b as well as point b can be reached from point a.

pub fn link_unidirect(&mut self, a: usize, b: usize)

Creates unidirectional link between vertex a and vertex b. Unidirectional means that there is no direct link between b to a, only from a to b.

pub fn vertex(&self, index: usize) -> Option<&T>

Returns shared reference to a path vertex at the given index.

pub fn vertex_mut(&mut self, index: usize) -> Option<&mut T>

Returns mutable reference to a path vertex at the given index.

pub fn vertices(&self) -> &[T]

Returns reference to the array of vertices.

pub fn vertices_mut(&mut self) -> &mut [T]

Returns mutable reference to the array of vertices.

pub fn add_vertex(&mut self, vertex: T) -> u32

Adds a new vertex to the path finder.

pub fn pop_vertex(&mut self) -> Option<T>

Removes last vertex from the graph. Automatically cleans “dangling” references to the deleted vertex from every other vertex in the graph and shifts indices of neighbour vertices, to preserve graph structure.

pub fn remove_vertex(&mut self, index: usize) -> T

Removes a vertex at the given index from the graph. Automatically cleans “dangling” references to the deleted vertex from every other vertex in the graph and shifts indices of neighbour vertices, to preserve graph structure.

pub fn insert_vertex(&mut self, index: u32, vertex: T)

Inserts the vertex at the given index. Automatically shifts neighbour indices of every other vertex in the graph to preserve graph structure.

pub fn build_indexed_path( &self, from: usize, to: usize, path: &mut Vec<usize>, ) -> Result<PathKind, PathError>

Tries to build path of vertex indices from beginning point to endpoint. Returns path kind:

• Full: Path vector is a direct path from beginning to end.
• Partial: Path vector is a path that ends closest to the desired end, because pathfinder could not find a full path.

See PathKind

Notes

This implementation is fast and allows for multiple searches in parallel, but does not attempt to find the optimal route

See Graph<T>.max_search_iterations to change the maximum amount of search iterations

pub fn build_positional_path( &self, from: usize, to: usize, path: &mut Vec<Vector3<f32>>, ) -> Result<PathKind, PathError>

Tries to build path of Vector3’s from beginning point to endpoint. Returns path kind:

• Full: Path vector is a direct path from beginning to end.
• Partial: Path vector is a path that ends closest to the desired end, because pathfinder could not find a full path.

See PathKind

Notes

This implementation is fast and allows for multiple searches in parallel, but does not attempt to find the optimal route

See Graph<T>.max_search_iterations to change the maximum amount of search iterations

pub fn build( &self, from: usize, to: usize, path: &mut Vec<Vector3<f32>>, ) -> Result<PathKind, PathError>

👎Deprecated: name is too ambiguous use build_positional_path instead

Deprecated use Graph<T>.build_positional_path() instead

Tries to build path of Vector3’s from beginning point to endpoint. Returns path kind:

• Full: Path vector is a direct path from beginning to end.
• Partial: Path vector is a path that ends closest to the desired end, because pathfinder could not find a full path.

See PathKind

Notes

This implementation is fast and allows for multiple searches in parallel, but does not attempt to find the optimal route

See Graph<T>.max_search_iterations to change the maximum amount of search iterations

Trait Implementations

impl<T> Clone for Graph<T>

where T: VertexDataProvider + Clone,

fn clone(&self) -> Graph<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Debug for Graph<T>

where T: VertexDataProvider + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: VertexDataProvider> Default for Graph<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T> PartialEq for Graph<T>

where T: VertexDataProvider + PartialEq,

fn eq(&self, other: &Graph<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T> Visit for Graph<T>

where T: VertexDataProvider, Vec<T>: Visit, i32: Visit,

fn visit(&mut self, name: &str, visitor: &mut Visitor) -> VisitResult

Read or write this value, depending on whether Visitor::is_reading() is true or false.

impl<T> StructuralPartialEq for Graph<T>

where T: VertexDataProvider,