Struct PathingGrid 

pub struct PathingGrid {
    pub grid: BoolGrid,
    pub neighbours: SimpleValueGrid<u8>,
    pub jump_point: SimpleValueGrid<u8>,
    pub components: UnionFind<usize>,
    pub components_dirty: bool,
    pub heuristic_factor: f32,
    pub improved_pruning: bool,
    pub allow_diagonal_move: bool,
    /* private fields */
}

PathingGrid maintains information about components using a UnionFind structure in addition to the raw bool grid values in the BoolGrid that determine whether a space is occupied (true) or empty (false). It also records neighbours in u8 format for fast lookups during search. Implements [Grid] by building on BoolGrid.

Fields

grid: BoolGrid

neighbours: SimpleValueGrid<u8>

jump_point: SimpleValueGrid<u8>

components: UnionFind<usize>

components_dirty: bool

heuristic_factor: f32

improved_pruning: bool

allow_diagonal_move: bool

Implementations

impl PathingGrid

pub fn heuristic(&self, p1: &Point, p2: &Point) -> i32

Uses C as cost for cardinal (straight) moves and D for diagonal moves.

pub fn get_component(&self, point: &Point) -> usize

Retrieves the component id a given Point belongs to.

pub fn reachable(&self, start: &Point, goal: &Point) -> bool

Checks if start and goal are on the same component.

pub fn unreachable(&self, start: &Point, goal: &Point) -> bool

Checks if start and goal are not on the same component.

pub fn neighbours_reachable(&self, start: &Point, goal: &Point) -> bool

Checks if any neighbour of the goal is on the same component as the start.

pub fn neighbours_unreachable(&self, start: &Point, goal: &Point) -> bool

Checks if every neighbour of the goal is on a different component as the start.

pub fn get_path_single_goal( &self, start: Point, goal: Point, approximate: bool, ) -> Option<Vec<Point>>

Computes a path from start to goal using JPS. If approximate is true, then it will path to one of the neighbours of the goal, which is useful if the goal itself is blocked. If diagonals are allowed, the heuristic used computes the path cost of taking the maximal number of diagonal moves before continuing straight. If diagonals are not allowed, the Manhattan distance is used instead (see heuristic). This can be specified by setting allow_diagonal_move. The heuristic will be scaled by heuristic_factor which can be used to trade optimality for faster solving for many practical problems, a technique called Weighted A*. In pathfinding language, a factor greater than 1.0 will make the heuristic inadmissible, a requirement for solution optimality. By default, the heuristic_factor is 1.0 which gives optimal solutions.

pub fn get_path_multiple_goals( &self, start: Point, goals: Vec<&Point>, ) -> Option<(Point, Vec<Point>)>

Computes a path from the start to one of the given goals and returns the selected goal in addition to the found path. Otherwise behaves similar to get_path_single_goal.

pub fn get_waypoints_multiple_goals( &self, start: Point, goals: Vec<&Point>, ) -> Option<(Point, Vec<Point>)>

The raw waypoints (jump points) from which get_path_multiple_goals makes a path.

pub fn get_waypoints_single_goal( &self, start: Point, goal: Point, approximate: bool, ) -> Option<Vec<Point>>

The raw waypoints (jump points) from which get_path_single_goal makes a path.

pub fn update(&mut self)

Regenerates the components if they are marked as dirty.

pub fn update_all_neighbours(&mut self)

pub fn set_jumppoints(&mut self, point: Point)

pub fn fix_jumppoints(&mut self, point: Point)

pub fn set_all_jumppoints(&mut self)

Performs the full jump point precomputation

pub fn initialize(&mut self)

pub fn generate_components(&mut self)

Generates a new UnionFind structure and links up grid neighbours to the same components.

Trait Implementations

impl Clone for PathingGrid

fn clone(&self) -> PathingGrid

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for PathingGrid

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

Formats the value using the given formatter.

impl Default for PathingGrid

fn default() -> PathingGrid

Returns the “default value” for a type.

impl Display for PathingGrid

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

Formats the value using the given formatter.

impl ValueGrid<bool> for PathingGrid

fn set(&mut self, x: i32, y: i32, blocked: bool)

Updates a position on the grid. Joins newly connected components and flags the components as dirty if components are (potentially) broken apart into multiple.

fn new(width: usize, height: usize, default_value: bool) -> Self

fn get(&self, x: i32, y: i32) -> bool

fn width(&self) -> usize

fn height(&self) -> usize

fn get_point(&self, point: Point) -> T

fn get_ix(&self, ix: usize) -> T

fn get_ix_point(&self, point: &Point) -> usize

fn compute_ix(&self, x: i32, y: i32) -> usize

Gets the index corresponding to a coordinate, which is row-wise.

fn set_point(&mut self, point: Point, value: T)

fn set_ix(&mut self, ix: usize, value: T)

fn point_in_bounds(&self, point: Point) -> bool

Tests whether a point is in bounds.

fn index_in_bounds(&self, x: i32, y: i32) -> bool

Tests whether an index is in bounds.

fn set_rect(&mut self, rect: Rect, value: T)

Sets a given rectangle on the grid to the value.

fn rect(&self) -> Rect

Retrieves the rectangle corresponding to the grid dimensions at the origin.

fn get_rect(&self, rect: Rect) -> Vec<T>

Retrieves a column-wise vector of grid values in the given rectangle.