Struct pathfinding::grid::Grid

pub struct Grid {
    pub width: usize,
    pub height: usize,
    /* private fields */
}

Representation of a rectangular grid in which vertices can be added or removed. Edges are automatically created between adjacent vertices. By default, only vertical and horizontal edges are created, unless diagonal mode is enabled.

The coordinate system is of the form (x, y), where x is the column and y is the row. (0, 0) corresponds to the top-left corner.

Internally, a Grid is represented either as a collection of vertices or as a collection of absent vertices, depending on the density of the grid. The switch between both representations is done automatically when vertices are added or removed, or when the grid is resized.

Grid implements Debug and represents the content using # and . characters. Alternate block characters ▓ and ░ can be selected by using the alternate debug format ({:#?}):

use pathfinding::prelude::Grid;

let mut g = Grid::new(3, 4);
g.add_borders();

assert_eq!(&format!("{g:?}"), "\
###
#.#
#.#
###");

assert_eq!(&format!("{g:#?}"), "\
▓▓▓
▓░▓
▓░▓
▓▓▓");

One of the ways to build a Grid is to start from an iterator of (usize, usize) representing the (x, y) coordinates:

use pathfinding::prelude::Grid;

let g = vec![(0, 0), (2, 2), (3, 2)].into_iter().collect::<Grid>();
assert_eq!(format!("{g:?}"), "\
#...
....
..##");

To be able to easily use the grid as a visualization tool for arbitrary types of coordinates, a from_coordinates method will build a grid and remap the top-left most coordinate as (0, 0):

use pathfinding::prelude::Grid;

let g = Grid::from_coordinates(&[(-16, -15), (-16, -16), (-15, -16)]).unwrap();
assert_eq!(format!("{g:#?}"), "\
▓▓
▓░");

Also, the order of lines can be inverted by using the - sign modifier while displaying:

assert_eq!(format!("{g:-#?}"), "\
▓░
▓▓");

Fields

width: usize

The grid width.

height: usize

The grid height.

Implementations

impl Grid

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

Create a new empty grid object of the given dimensions, with diagonal mode disabled.

pub fn is_inside(&self, vertex: (usize, usize)) -> bool

Check if a (possibly removed) vertex belongs to the grid or if it is located outside the grid.

pub fn enable_diagonal_mode(&mut self)

Enable diagonal mode. Diagonal edges will be created between adjacent vertices.

pub fn disable_diagonal_mode(&mut self)

Disable diagonal mode. Only horizontal and vertical edges will be created between adjacent vertices.

pub fn resize(&mut self, width: usize, height: usize) -> bool

Resize the grid to the given dimensions. Return true if this caused any existing vertex to be discarded.

pub fn size(&self) -> usize

Return the number of positions in this grid.

pub fn vertices_len(&self) -> usize

Return the number of vertices.

pub fn add_vertex(&mut self, vertex: (usize, usize)) -> bool

Add a new vertex. Return true if the vertex did not previously exist and has been added. Return false if the vertex exists already or would be outside the grid.

pub fn remove_vertex(&mut self, vertex: (usize, usize)) -> bool

Remove a vertex. Return true if the vertex did previously exist and has been removed.

pub fn add_borders(&mut self) -> usize

Add the borders of the grid. Return the number of added vertices.

pub fn remove_borders(&mut self) -> usize

Remove the borders of the grid. Return the number of removed vertices.

pub fn clear(&mut self) -> bool

Remove all vertices from the grid. Return true if the grid previously contained at least one vertex.

pub fn fill(&mut self) -> bool

Fill the grid with all possible vertices. Return true if this caused the addition of at least one vertex.

pub fn is_empty(&self) -> bool

Return true if the grid contains no vertices.

pub fn is_full(&self) -> bool

Return true if no additional vertices can be set (because they are all already set).

pub fn invert(&mut self)

Remove every existing vertex, and add all absent vertices. If you see the grid as a black and white array, imagine that the color are exchanged.

pub fn has_vertex(&self, vertex: (usize, usize)) -> bool

Check if a vertex is present.

pub fn has_edge(&self, v1: (usize, usize), v2: (usize, usize)) -> bool

Check if an edge is present.

pub fn edges(&self) -> EdgesIterator<'_>

Iterate over edges.

pub fn neighbours(&self, vertex: (usize, usize)) -> Vec<(usize, usize)>

Return the list of neighbours of a given vertex. If vertex is absent from the grid, an empty list is returned. Only existing vertices will be returned.

pub fn bfs_reachable<P>( &self, start: (usize, usize), predicate: P ) -> BTreeSet<(usize, usize)>

where P: FnMut((usize, usize)) -> bool,

Return a set of the indices reachable from a candidate starting point and for which the given predicate is valid using BFS. This can be used for example to implement a flood-filling algorithm. Since the indices are collected into a collection, they can later be used without keeping a reference on the matrix itself, e.g., to modify the grid.

The search is done using a breadth first search (BFS) algorithm.

See also

The dfs_reachable() method performs a DFS search instead.

pub fn dfs_reachable<P>( &self, start: (usize, usize), predicate: P ) -> BTreeSet<(usize, usize)>

where P: FnMut((usize, usize)) -> bool,

Return a set of the indices reachable from a candidate starting point and for which the given predicate is valid using BFS. This can be used for example to implement a flood-filling algorithm. Since the indices are collected into a collection, they can later be used without keeping a reference on the matrix itself, e.g., to modify the grid.

The search is done using a depth first search (DFS) algorithm.

See also

The bfs_reachable() method performs a BFS search instead.

pub fn iter(&self) -> GridIterator<'_>

Iterate over vertices.

pub fn distance(&self, a: (usize, usize), b: (usize, usize)) -> usize

Distance between two potential vertices. If diagonal mode is enabled, this is the maximum of both coordinates difference. If diagonal mode is disabled, this is the Manhattan distance.

pub fn from_coordinates<T>(points: &[(T, T)]) -> Option<Self>

where T: Ord + Sub<Output = T> + Copy + Default + ToPrimitive,

Build a grid from an arbitrary set of (x, y) coordinates. Coordinates will be adjusted so that the returned grid is the smallest one containing all the points while conserving horizontal and vertical distances between them.

This can be used for example to visualize data whose coordinates are expressed using a non-usize integer type, such as (isize, isize).

This method returns None if any axis of any coordinate cannot be represented as an usize once the minimum for this axis has been subtracted.

Example

use pathfinding::prelude::Grid;

let grid = Grid::from_coordinates(&[(2, 2), (3, 4)]).unwrap();
assert_eq!(vec![(0, 0), (1, 2)], grid.iter().collect::<Vec<_>>());

pub const fn constrain(&self, vertex: (isize, isize)) -> (usize, usize)

Constrain a wrapped-around index so that it falls inside the grid.

Examples

use pathfinding::grid::Grid;

let grid = Grid::new(3, 5);
assert_eq!(grid.constrain((1, 2)), (1, 2));
assert_eq!(grid.constrain((10, -53)), (1, 2));

Trait Implementations

impl Clone for Grid

fn clone(&self) -> Grid

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Grid

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

Formats the value using the given formatter.

impl From<&Matrix<bool>> for Grid

fn from(matrix: &Matrix<bool>) -> Self

Converts to this type from the input type.

impl From<Matrix<bool>> for Grid

fn from(matrix: Matrix<bool>) -> Self

Converts to this type from the input type.

impl FromIterator<(usize, usize)> for Grid

fn from_iter<T>(iter: T) -> Self

where T: IntoIterator<Item = (usize, usize)>,

Creates a value from an iterator.

impl<'a> IntoIterator for &'a Grid

type Item = (usize, usize)

The type of the elements being iterated over.

type IntoIter = GridIterator<'a>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl IntoIterator for Grid

type Item = (usize, usize)

The type of the elements being iterated over.

type IntoIter = GridIntoIterator

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl PartialEq for Grid

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl Eq for Grid