Struct pathfinding::grid::Grid
source · pub struct Grid {
pub width: usize,
pub height: usize,
/* private fields */
}
Expand description
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§
source§impl Grid
impl Grid
sourcepub fn new(width: usize, height: usize) -> Self
pub fn new(width: usize, height: usize) -> Self
Create a new empty grid object of the given dimensions, with diagonal mode disabled.
sourcepub fn is_inside(&self, vertex: (usize, usize)) -> bool
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.
sourcepub fn enable_diagonal_mode(&mut self)
pub fn enable_diagonal_mode(&mut self)
Enable diagonal mode. Diagonal edges will be created between adjacent vertices.
sourcepub fn disable_diagonal_mode(&mut self)
pub fn disable_diagonal_mode(&mut self)
Disable diagonal mode. Only horizontal and vertical edges will be created between adjacent vertices.
sourcepub fn resize(&mut self, width: usize, height: usize) -> bool
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.
sourcepub fn vertices_len(&self) -> usize
pub fn vertices_len(&self) -> usize
Return the number of vertices.
sourcepub fn add_vertex(&mut self, vertex: (usize, usize)) -> bool
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.
sourcepub fn remove_vertex(&mut self, vertex: (usize, usize)) -> bool
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.
sourcepub fn add_borders(&mut self) -> usize
pub fn add_borders(&mut self) -> usize
Add the borders of the grid. Return the number of added vertices.
sourcepub fn remove_borders(&mut self) -> usize
pub fn remove_borders(&mut self) -> usize
Remove the borders of the grid. Return the number of removed vertices.
sourcepub fn clear(&mut self) -> bool
pub fn clear(&mut self) -> bool
Remove all vertices from the grid. Return true
if the grid
previously contained at least one vertex.
sourcepub fn fill(&mut self) -> bool
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.
sourcepub fn is_full(&self) -> bool
pub fn is_full(&self) -> bool
Return true
if no additional vertices can be set
(because they are all already set).
sourcepub fn invert(&mut self)
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.
sourcepub fn has_vertex(&self, vertex: (usize, usize)) -> bool
pub fn has_vertex(&self, vertex: (usize, usize)) -> bool
Check if a vertex is present.
sourcepub fn has_edge(&self, v1: (usize, usize), v2: (usize, usize)) -> bool
pub fn has_edge(&self, v1: (usize, usize), v2: (usize, usize)) -> bool
Check if an edge is present.
sourcepub fn edges(&self) -> EdgesIterator<'_> ⓘ
pub fn edges(&self) -> EdgesIterator<'_> ⓘ
Iterate over edges.
sourcepub fn neighbours(&self, vertex: (usize, usize)) -> Vec<(usize, usize)>
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.
sourcepub fn bfs_reachable<P>(
&self,
start: (usize, usize),
predicate: P
) -> BTreeSet<(usize, usize)>
pub fn bfs_reachable<P>( &self, start: (usize, usize), predicate: P ) -> BTreeSet<(usize, usize)>
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.
sourcepub fn dfs_reachable<P>(
&self,
start: (usize, usize),
predicate: P
) -> BTreeSet<(usize, usize)>
pub fn dfs_reachable<P>( &self, start: (usize, usize), predicate: P ) -> BTreeSet<(usize, usize)>
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.
sourcepub fn iter(&self) -> GridIterator<'_> ⓘ
pub fn iter(&self) -> GridIterator<'_> ⓘ
Iterate over vertices.
sourcepub fn distance(&self, a: (usize, usize), b: (usize, usize)) -> usize
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.
sourcepub fn from_coordinates<T>(points: &[(T, T)]) -> Option<Self>
pub fn from_coordinates<T>(points: &[(T, T)]) -> Option<Self>
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<_>>());
sourcepub const fn constrain(&self, vertex: (isize, isize)) -> (usize, usize)
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§
source§impl<'a> IntoIterator for &'a Grid
impl<'a> IntoIterator for &'a Grid
source§impl IntoIterator for Grid
impl IntoIterator for Grid
source§impl PartialEq for Grid
impl PartialEq for Grid
impl Eq for Grid
Auto Trait Implementations§
impl Freeze for Grid
impl RefUnwindSafe for Grid
impl Send for Grid
impl Sync for Grid
impl Unpin for Grid
impl UnwindSafe for Grid
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
source§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
key
and return true
if they are equal.