Quick grid graph implementation for searching square map with Rust.

grid_graph.rs

/// Coordinate on 2D plane, which `+X` is right and `+Y` is down.
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Coordinate {
    pub x: usize,
    pub y: usize,
}

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct GridGraph<T> {
    grid: Vec<Vec<T>>,
    blocked: Vec<Vec<bool>>,
    width: usize,
    height: usize,
}

impl<T> GridGraph<T> {
    pub fn new(width: usize, height: usize) -> Self
    where
        T: Default,
    {
        Self {
            grid: (0..height)
                .map(|_| (0..width).map(|_| T::default()).collect())
                .collect(),
            blocked: vec![vec![false; width]; height],
            width,
            height,
        }
    }

    pub fn area(&self) -> usize {
        self.height * self.width
    }

    pub fn contains(&self, on: Coordinate) -> bool {
        on.x < self.width && on.y < self.height && !self.blocked[on.y][on.x]
    }

    pub fn is_blocked(&self, on: Coordinate) -> bool {
        self.blocked[on.y][on.x]
    }

    pub fn block(&mut self, on: Coordinate) -> bool {
        self.set_blocked(on, true)
    }

    pub fn unblock(&mut self, on: Coordinate) -> bool {
        self.set_blocked(on, false)
    }

    pub fn set_blocked(&mut self, on: Coordinate, value: bool) -> bool {
        std::mem::replace(&mut self.blocked[on.y][on.x], value)
    }

    pub fn coordinates(&self) -> impl Iterator<Item = Coordinate> {
        let width = self.width;
        let height = self.height;
        (0..height).flat_map(move |y| (0..width).map(move |x| Coordinate { x, y }))
    }

    pub fn iter(&self) -> impl Iterator<Item = &T> {
        self.grid.iter().flatten()
    }

    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut T> {
        self.grid.iter_mut().flatten()
    }

    pub fn entries(&self) -> impl Iterator<Item = (Coordinate, &T)> {
        self.coordinates().zip(self.iter())
    }

    pub fn entries_mut(&mut self) -> impl Iterator<Item = (Coordinate, &mut T)> {
        self.coordinates().zip(self.iter_mut())
    }

    /// Makes the neighbor coordinates from `on` with `(diff_x, diff_y)` from `on`.
    pub fn neighbors(&self, on: Coordinate) -> Vec<(Coordinate, (isize, isize))> {
        [(-1, 0), (1, 0), (0, -1), (0, 1)]
            .into_iter()
            .flat_map(|(dy, dx)| {
                let new_x =
                    on.x.checked_add_signed(dx)
                        .filter(|&new_x| new_x < self.width)?;
                let new_y =
                    on.y.checked_add_signed(dy)
                        .filter(|&new_y| new_y < self.height)?;
                let coordinate = Coordinate { x: new_x, y: new_y };
                (!self.blocked[new_y][new_x]).then(|| (coordinate, (dx, dy)))
            })
            .collect()
    }

    pub fn get(&self, pos: Coordinate) -> Option<&T> {
        self.contains(pos)
            .then(|| self.grid.get(pos.y).and_then(|row| row.get(pos.x)))?
    }

    pub fn get_mut(&mut self, pos: Coordinate) -> Option<&mut T> {
        self.contains(pos)
            .then(|| self.grid.get_mut(pos.y).and_then(|row| row.get_mut(pos.x)))?
    }
}

impl<T> std::ops::Index<Coordinate> for GridGraph<T> {
    type Output = T;

    fn index(&self, index: Coordinate) -> &Self::Output {
        self.get(index).unwrap()
    }
}

impl<T> std::ops::IndexMut<Coordinate> for GridGraph<T> {
    fn index_mut(&mut self, index: Coordinate) -> &mut Self::Output {
        self.get_mut(index).unwrap()
    }
}