Struct grid_pathfinding::PathingGrid

pub struct PathingGrid {
    pub grid: BoolGrid,
    pub neighbours: SimpleGrid<u8>,
    pub components: UnionFind<usize>,
    pub components_dirty: bool,
}

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: SimpleGrid<u8>

components: UnionFind<usize>

components_dirty: bool

Implementations

impl PathingGrid

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

Retrieves the component id a given Point belongs to.

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

Checks if start and goal are on the same component.

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

Checks if any neighbour of the goal is on the same 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 goal itself is blocked. The heuristic used is the Chebyshev distance.

Examples found in repository

examples/simple.rs (line 24)

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(3, 3, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let end = Point::new(2, 2);
    let path = pathing_grid
        .get_path_single_goal(start, end, false)
        .unwrap();
    println!("Path:");
    for p in path {
        println!("{:?}", p);
    }
}

examples/paths_and_waypoints.rs (line 41)

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(5, 5, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let end = Point::new(4, 4);
    if let Some(path) = pathing_grid.get_waypoints_single_goal(start, end, false) {
        println!("Waypoints:");
        for p in &path {
            println!("{:?}", p);
        }
        println!("\nPath generated from waypoints:");
        for p in waypoints_to_path(path) {
            println!("{:?}", p);
        }
    }
    println!("\nDirectly computed path");
    let expanded_path = pathing_grid
        .get_path_single_goal(start, end, false)
        .unwrap();
    for p in expanded_path {
        println!("{:?}", p);
    }
}

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

Computes a path from start to one of the given goals. This is done by taking the Chebyshev distance to the closest goal as heuristic value.

Examples found in repository

examples/multiple_goals.rs (line 26)

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(3, 3, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let goal_1 = Point::new(2, 0);
    let goal_2 = Point::new(2, 2);
    let goals = vec![&goal_1, &goal_2];
    let (selected_goal, path) = pathing_grid.get_path_multiple_goals(start, goals).unwrap();
    println!("Selected goal: {:?}\n", selected_goal);
    println!("Path:");
    for p in path {
        println!("{:?}", p);
    }
}

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.

Examples found in repository

examples/paths_and_waypoints.rs (line 29)

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(5, 5, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let end = Point::new(4, 4);
    if let Some(path) = pathing_grid.get_waypoints_single_goal(start, end, false) {
        println!("Waypoints:");
        for p in &path {
            println!("{:?}", p);
        }
        println!("\nPath generated from waypoints:");
        for p in waypoints_to_path(path) {
            println!("{:?}", p);
        }
    }
    println!("\nDirectly computed path");
    let expanded_path = pathing_grid
        .get_path_single_goal(start, end, false)
        .unwrap();
    for p in expanded_path {
        println!("{:?}", p);
    }
}

pub fn update(&mut self)

Regenerates the components if they are marked as dirty.

pub fn generate_components(&mut self)

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

Examples found in repository

examples/simple.rs (line 19)

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(3, 3, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let end = Point::new(2, 2);
    let path = pathing_grid
        .get_path_single_goal(start, end, false)
        .unwrap();
    println!("Path:");
    for p in path {
        println!("{:?}", p);
    }
}

examples/multiple_goals.rs (line 20)

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(3, 3, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let goal_1 = Point::new(2, 0);
    let goal_2 = Point::new(2, 2);
    let goals = vec![&goal_1, &goal_2];
    let (selected_goal, path) = pathing_grid.get_path_multiple_goals(start, goals).unwrap();
    println!("Selected goal: {:?}\n", selected_goal);
    println!("Path:");
    for p in path {
        println!("{:?}", p);
    }
}

examples/paths_and_waypoints.rs (line 25)

fn main() {
    let mut pathing_grid: PathingGrid = PathingGrid::new(5, 5, false);
    pathing_grid.set(1, 1, true);
    pathing_grid.generate_components();
    println!("{}", pathing_grid);
    let start = Point::new(0, 0);
    let end = Point::new(4, 4);
    if let Some(path) = pathing_grid.get_waypoints_single_goal(start, end, false) {
        println!("Waypoints:");
        for p in &path {
            println!("{:?}", p);
        }
        println!("\nPath generated from waypoints:");
        for p in waypoints_to_path(path) {
            println!("{:?}", p);
        }
    }
    println!("\nDirectly computed path");
    let expanded_path = pathing_grid
        .get_path_single_goal(start, end, false)
        .unwrap();
    for p in expanded_path {
        println!("{:?}", p);
    }
}

Trait Implementations

impl Clone for PathingGrid

fn clone(&self) -> PathingGrid

Returns a copy 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 Grid<bool> for PathingGrid

fn set(&mut self, x: usize, y: usize, 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: usize, y: usize) -> bool

fn width(&self) -> usize

fn height(&self) -> usize

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

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

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

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

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

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

Tests whether a point is in bounds.

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

Tests whether an index is in bounds.

fn set_rectangle(&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.