condor_grid/grid/

mod.rs

//! Rectangular 4-connected map substrate shared by all discrete grid lanes.
//!
//! [`Grid`] owns walkability ([`Cell`]), positive per-cell
//! [`Grid::traversal_cost`], and an optional [`reachability::GridReachabilityIndex`]
//! for early same-component checks. Walkability edits invalidate that index; rebuild
//! it with [`Grid::index_reachability`]. Prefer [`GridBuilder`] / [`Grid::builder`]
//! for bulk construction, or [`Grid::try_from_rows`] / [`grid!`](crate::grid!) for
//! small textual fixtures.

use std::{error::Error, fmt};

use crate::point::Point;

/// Optional same-component reachability index for early no-path rejection.
pub mod reachability;

/// Walkability state of a single grid cell.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Cell {
    /// Passable; participates in 4-connected search and may carry a traversal cost.
    Open,
    /// Impassable; excluded from neighbors and path validation.
    Blocked,
}

/// Storage buffer that could not be allocated while constructing a grid.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum GridStorage {
    /// Walkability cell array.
    Cells,
    /// Per-cell `traversal_cost` array.
    TraversalCosts,
}

impl fmt::Display for GridStorage {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Cells => formatter.write_str("cells"),
            Self::TraversalCosts => formatter.write_str("traversal costs"),
        }
    }
}

/// Error returned when a grid cannot be constructed.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum GridBuildError {
    /// Width must be positive.
    ZeroWidth,
    /// Height must be positive.
    ZeroHeight,
    /// `width * height` overflowed `usize`.
    CellCountOverflow { width: usize, height: usize },
    /// Backing vector reserve failed for the named buffer.
    CapacityExceeded { storage: GridStorage },
    /// Textual row input was empty.
    EmptyRows,
    /// A textual row had zero characters.
    ZeroWidthRow,
    /// A textual row did not match the first row's width.
    RaggedRow {
        row: usize,
        expected_width: usize,
        actual_width: usize,
    },
    /// Unsupported character in textual row input.
    InvalidRowCharacter {
        row: usize,
        column: usize,
        character: char,
    },
    /// A queued builder edit failed validation.
    Edit(GridEditError),
}

impl fmt::Display for GridBuildError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::ZeroWidth => formatter.write_str("grid width must be greater than zero"),
            Self::ZeroHeight => formatter.write_str("grid height must be greater than zero"),
            Self::CellCountOverflow { width, height } => {
                write!(formatter, "grid dimensions {width}x{height} overflow usize")
            }
            Self::CapacityExceeded { storage } => {
                write!(formatter, "grid {storage} exceed available capacity")
            }
            Self::EmptyRows => formatter.write_str("grid rows must not be empty"),
            Self::ZeroWidthRow => formatter.write_str("grid rows must not be zero-width"),
            Self::RaggedRow {
                row,
                expected_width,
                actual_width,
            } => write!(
                formatter,
                "grid row {row} has width {actual_width}, expected {expected_width}"
            ),
            Self::InvalidRowCharacter {
                row,
                column,
                character,
            } => write!(
                formatter,
                "grid row {row}, column {column} contains unsupported character {character:?}"
            ),
            Self::Edit(error) => write!(formatter, "grid edit failed: {error}"),
        }
    }
}

impl Error for GridBuildError {
    fn source(&self) -> Option<&(dyn Error + 'static)> {
        match self {
            Self::Edit(error) => Some(error),
            _ => None,
        }
    }
}

impl From<GridEditError> for GridBuildError {
    fn from(error: GridEditError) -> Self {
        Self::Edit(error)
    }
}

/// Error returned when a requested grid edit violates grid invariants.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum GridEditError {
    /// Target cell lies outside `0..width` × `0..height`.
    OutOfBounds {
        point: Point,
        width: usize,
        height: usize,
    },
    /// Traversal cost cannot be set on a blocked cell.
    BlockedCell { point: Point },
    /// Traversal cost must be strictly positive.
    ZeroTraversalCost { point: Point },
}

impl fmt::Display for GridEditError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::OutOfBounds {
                point,
                width,
                height,
            } => write!(
                formatter,
                "point ({}, {}) is outside grid bounds {width}x{height}",
                point.x, point.y
            ),
            Self::BlockedCell { point } => write!(
                formatter,
                "cannot set traversal cost for blocked cell ({}, {})",
                point.x, point.y
            ),
            Self::ZeroTraversalCost { point } => write!(
                formatter,
                "traversal cost at ({}, {}) must be greater than zero",
                point.x, point.y
            ),
        }
    }
}

impl Error for GridEditError {}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum GridBuilderEdit {
    Cell { point: Point, cell: Cell },
    Cost { point: Point, cost: usize },
}

/// Builder for applying validated bulk edits to a new [`Grid`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct GridBuilder {
    width: usize,
    height: usize,
    edits: Vec<GridBuilderEdit>,
    index_reachability: bool,
}

impl GridBuilder {
    /// Queues edits for a `width`×`height` grid; dimensions are validated on [`Self::build`].
    ///
    /// Starts fully open with unit traversal costs. Call [`Self::index_reachability`]
    /// if the built grid should short-circuit disconnected start/goal pairs.
    #[must_use]
    pub const fn new(width: usize, height: usize) -> Self {
        Self {
            width,
            height,
            edits: Vec::new(),
            index_reachability: false,
        }
    }

    /// Marks all supplied cells as blocked.
    #[must_use]
    pub fn blocked<I, P>(mut self, points: I) -> Self
    where
        I: IntoIterator<Item = P>,
        P: Into<Point>,
    {
        self.edits
            .extend(points.into_iter().map(|point| GridBuilderEdit::Cell {
                point: point.into(),
                cell: Cell::Blocked,
            }));
        self
    }

    /// Marks all supplied cells as open.
    #[must_use]
    pub fn open<I, P>(mut self, points: I) -> Self
    where
        I: IntoIterator<Item = P>,
        P: Into<Point>,
    {
        self.edits
            .extend(points.into_iter().map(|point| GridBuilderEdit::Cell {
                point: point.into(),
                cell: Cell::Open,
            }));
        self
    }

    /// Sets traversal costs from `(point, cost)` pairs.
    #[must_use]
    pub fn costs<I, P>(mut self, costs: I) -> Self
    where
        I: IntoIterator<Item = (P, usize)>,
        P: Into<Point>,
    {
        self.edits.extend(
            costs
                .into_iter()
                .map(|(point, cost)| GridBuilderEdit::Cost {
                    point: point.into(),
                    cost,
                }),
        );
        self
    }

    /// Builds a reachability index after all edits have been applied.
    #[must_use]
    pub const fn index_reachability(mut self) -> Self {
        self.index_reachability = true;
        self
    }

    /// Builds the grid and validates every queued edit in insertion order.
    ///
    /// # Errors
    ///
    /// Returns [`GridBuildError`] for invalid dimensions, allocation failure,
    /// or an invalid queued edit.
    pub fn build(self) -> Result<Grid, GridBuildError> {
        let mut grid = Grid::new(self.width, self.height)?;
        for edit in self.edits {
            match edit {
                GridBuilderEdit::Cell { point, cell } => grid.set_cell(point, cell)?,
                GridBuilderEdit::Cost { point, cost } => {
                    grid.set_traversal_cost(point, cost)?;
                }
            }
        }
        if self.index_reachability {
            grid.index_reachability();
        }
        Ok(grid)
    }
}

/// Dense row-major rectangular map: walkability, `traversal_cost`, optional reachability.
///
/// Shared substrate for online [`crate::Pathfinder`] algorithms (4-connected). Open cells
/// default to unit cost; blocked cells are excluded from neighbors. Cached
/// [`reachability::GridReachabilityIndex`] is optional and cleared on walkability edits.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Grid {
    width: usize,
    height: usize,
    cells: Vec<Cell>,
    traversal_costs: Vec<usize>,
    reachability: Option<reachability::GridReachabilityIndex>,
}

impl Grid {
    /// Creates a grid with non-zero dimensions.
    ///
    /// # Errors
    ///
    /// Returns [`GridBuildError`] when either dimension is zero, the cell count
    /// overflows, or backing storage cannot be reserved.
    pub fn new(width: usize, height: usize) -> Result<Self, GridBuildError> {
        if width == 0 {
            return Err(GridBuildError::ZeroWidth);
        }
        if height == 0 {
            return Err(GridBuildError::ZeroHeight);
        }
        let Some(cell_count) = width.checked_mul(height) else {
            return Err(GridBuildError::CellCountOverflow { width, height });
        };

        let mut cells = Vec::new();
        cells
            .try_reserve_exact(cell_count)
            .map_err(|_| GridBuildError::CapacityExceeded {
                storage: GridStorage::Cells,
            })?;
        cells.resize(cell_count, Cell::Open);

        let mut traversal_costs = Vec::new();
        traversal_costs.try_reserve_exact(cell_count).map_err(|_| {
            GridBuildError::CapacityExceeded {
                storage: GridStorage::TraversalCosts,
            }
        })?;
        traversal_costs.resize(cell_count, 1);

        Ok(Self {
            width,
            height,
            cells,
            traversal_costs,
            reachability: None,
        })
    }

    /// Starts a builder for a grid with the supplied dimensions.
    #[must_use]
    pub const fn builder(width: usize, height: usize) -> GridBuilder {
        GridBuilder::new(width, height)
    }

    /// Parses a rectangular grid from textual rows.
    ///
    /// `.` creates an open cell with cost 1, `#` creates a blocked cell, and
    /// `1` through `9` create open cells with the corresponding traversal cost.
    ///
    /// # Errors
    ///
    /// Returns [`GridBuildError`] for empty, zero-width, ragged, or invalid
    /// input, or when the resulting grid cannot be allocated.
    pub fn try_from_rows<I, S>(rows: I) -> Result<Self, GridBuildError>
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        let rows: Vec<S> = rows.into_iter().collect();
        let Some(first) = rows.first() else {
            return Err(GridBuildError::EmptyRows);
        };
        let width = first.as_ref().chars().count();
        if width == 0 {
            return Err(GridBuildError::ZeroWidthRow);
        }

        let mut grid = Self::new(width, rows.len())?;
        for (row, source) in rows.iter().enumerate() {
            let actual_width = source.as_ref().chars().count();
            if actual_width != width {
                return Err(GridBuildError::RaggedRow {
                    row,
                    expected_width: width,
                    actual_width,
                });
            }
            for (column, character) in source.as_ref().chars().enumerate() {
                let point = Point::new(column, row);
                match character {
                    '.' | '1' => {}
                    '#' => grid.set_cell(point, Cell::Blocked)?,
                    '2'..='9' => {
                        let cost = character.to_digit(10).expect("matched an ASCII digit") as usize;
                        grid.set_traversal_cost(point, cost)?;
                    }
                    character => {
                        return Err(GridBuildError::InvalidRowCharacter {
                            row,
                            column,
                            character,
                        });
                    }
                }
            }
        }
        Ok(grid)
    }

    /// Builds or rebuilds the cached reachability index from the current cells.
    pub fn index_reachability(&mut self) {
        self.reachability = Some(reachability::GridReachabilityIndex::from_grid(self));
    }

    /// Returns whether `start` and `goal` share a walkable 4-way component.
    ///
    /// Without a prior [`Self::index_reachability`] call, always returns `true`
    /// so search is not short-circuited.
    #[must_use]
    pub fn is_reachable(&self, start: Point, goal: Point) -> bool {
        if let Some(reachability) = &self.reachability {
            reachability.is_reachable(start, goal)
        } else {
            true
        }
    }

    /// Column count (cells along x).
    #[must_use]
    pub const fn width(&self) -> usize {
        self.width
    }

    /// Row count (cells along y).
    #[must_use]
    pub const fn height(&self) -> usize {
        self.height
    }

    /// Total cells (`width * height`).
    #[must_use]
    pub fn cell_count(&self) -> usize {
        self.cells.len()
    }

    /// Whether `point` lies inside the grid bounds (walkability is separate).
    #[must_use]
    pub fn contains(&self, point: Point) -> bool {
        self.index_of(point).is_some()
    }

    /// Cell state at `point`, or `None` when out of bounds.
    #[must_use]
    pub fn cell(&self, point: Point) -> Option<Cell> {
        self.index_of(point).map(|index| self.cells[index])
    }

    /// Sets walkability; clears the cached reachability index when the value changes.
    ///
    /// Blocking an open cell hides its traversal cost from queries but retains the
    /// stored cost so reopening restores it.
    ///
    /// # Errors
    ///
    /// Returns [`GridEditError::OutOfBounds`] if `point` is outside the grid.
    pub fn set_cell(&mut self, point: Point, cell: Cell) -> Result<(), GridEditError> {
        let Some(index) = self.index_of(point) else {
            return Err(GridEditError::OutOfBounds {
                point,
                width: self.width,
                height: self.height,
            });
        };

        if self.cells[index] != cell {
            self.cells[index] = cell;
            self.reachability = None;
        }
        Ok(())
    }

    /// In-bounds and [`Cell::Open`]; out-of-bounds and blocked cells are not walkable.
    #[must_use]
    pub fn is_walkable(&self, point: Point) -> bool {
        matches!(self.cell(point), Some(Cell::Open))
    }

    /// Checks that every point is open and every consecutive pair is an orthogonal unit step.
    #[must_use]
    pub fn path_is_walkable(&self, points: &[Point]) -> bool {
        points.iter().all(|&p| self.is_walkable(p))
            && points
                .windows(2)
                .all(|pair| self.segment_is_walkable(pair[0], pair[1]))
    }

    /// Returns whether `start` and `end` form a single orthogonal unit edge between open cells.
    #[must_use]
    pub fn segment_is_walkable(&self, start: Point, end: Point) -> bool {
        if start == end {
            return self.is_walkable(start);
        }

        let dx = (start.x as i64 - end.x as i64).abs();
        let dy = (start.y as i64 - end.y as i64).abs();

        if (dx == 1 && dy == 0) || (dx == 0 && dy == 1) {
            self.is_walkable(start) && self.is_walkable(end)
        } else {
            false
        }
    }

    /// Returns the traversal cost for an open cell, or `None` if blocked or out of bounds.
    #[must_use]
    pub fn traversal_cost(&self, point: Point) -> Option<usize> {
        let index = self.index_of(point)?;
        self.is_walkable(point)
            .then_some(self.traversal_costs[index])
    }

    /// Sets a positive traversal cost for a walkable cell.
    ///
    /// # Errors
    ///
    /// Returns [`GridEditError`] if the cost is zero, the point is outside the
    /// grid, or the cell is blocked.
    pub fn set_traversal_cost(&mut self, point: Point, cost: usize) -> Result<(), GridEditError> {
        if cost == 0 {
            return Err(GridEditError::ZeroTraversalCost { point });
        }

        let Some(index) = self.index_of(point) else {
            return Err(GridEditError::OutOfBounds {
                point,
                width: self.width,
                height: self.height,
            });
        };
        if !matches!(self.cells[index], Cell::Open) {
            return Err(GridEditError::BlockedCell { point });
        }

        self.traversal_costs[index] = cost;
        Ok(())
    }

    /// Walkable 4-connected neighbors of `point`, in fixed axis order.
    #[must_use]
    pub fn neighbors4(&self, point: Point) -> Vec<Point> {
        let mut neighbors = Vec::with_capacity(4);

        if point.x > 0 {
            let candidate = Point::new(point.x - 1, point.y);
            if self.is_walkable(candidate) {
                neighbors.push(candidate);
            }
        }

        if point.x + 1 < self.width {
            let candidate = Point::new(point.x + 1, point.y);
            if self.is_walkable(candidate) {
                neighbors.push(candidate);
            }
        }

        if point.y > 0 {
            let candidate = Point::new(point.x, point.y - 1);
            if self.is_walkable(candidate) {
                neighbors.push(candidate);
            }
        }

        if point.y + 1 < self.height {
            let candidate = Point::new(point.x, point.y + 1);
            if self.is_walkable(candidate) {
                neighbors.push(candidate);
            }
        }

        neighbors
    }

    /// Dense row-major cell index (`y * width + x`), or `None` when out of bounds.
    #[must_use]
    #[doc(hidden)]
    pub fn index_of(&self, point: Point) -> Option<usize> {
        if point.x >= self.width || point.y >= self.height {
            return None;
        }

        Some((point.y * self.width) + point.x)
    }

    /// Inverse of [`Self::index_of`]: reconstructs `(x, y)` from a dense row-major index.
    #[must_use]
    #[doc(hidden)]
    pub fn point_from_index(&self, index: usize) -> Point {
        let x = index % self.width;
        let y = index / self.width;
        Point::new(x, y)
    }
}

/// Constructs a [`Grid`] from textual rows using [`Grid::try_from_rows`].
#[macro_export]
macro_rules! grid {
    () => {
        $crate::Grid::try_from_rows(::core::iter::empty::<&str>())
    };
    ($($row:expr),+ $(,)?) => {
        $crate::Grid::try_from_rows([$($row),+])
    };
}

#[cfg(test)]
mod tests {
    use super::{Cell, Grid, GridBuildError, GridEditError, Point};

    #[test]
    fn blocking_and_reopening_preserves_custom_traversal_cost() {
        let mut grid = Grid::new(3, 1).expect("grid dimensions are valid");
        let point = Point::new(1, 0);

        assert_eq!(grid.set_traversal_cost(point, 5), Ok(()));
        assert_eq!(grid.traversal_cost(point), Some(5));

        assert_eq!(grid.set_cell(point, Cell::Blocked), Ok(()));
        assert_eq!(grid.traversal_cost(point), None);

        assert_eq!(grid.set_cell(point, Cell::Open), Ok(()));
        assert_eq!(grid.traversal_cost(point), Some(5));
    }

    #[test]
    fn builder_applies_bulk_edits_and_indexes_reachability() {
        let grid = Grid::builder(3, 2)
            .blocked([(1, 0), (1, 1), (0, 1)])
            .open([(0, 1)])
            .costs([((2, 1), 4)])
            .index_reachability()
            .build()
            .expect("builder input is valid");

        assert_eq!(grid.cell(Point::new(1, 0)), Some(Cell::Blocked));
        assert_eq!(grid.cell(Point::new(0, 1)), Some(Cell::Open));
        assert_eq!(grid.cell(Point::new(1, 1)), Some(Cell::Blocked));
        assert_eq!(grid.traversal_cost(Point::new(2, 1)), Some(4));
        assert!(!grid.is_reachable(Point::new(0, 0), Point::new(2, 0)));
    }

    #[test]
    fn builder_reports_invalid_edits_with_context() {
        let error = Grid::builder(2, 2)
            .blocked([(2, 0)])
            .build()
            .expect_err("point is out of bounds");

        assert_eq!(
            error,
            GridBuildError::Edit(GridEditError::OutOfBounds {
                point: Point::new(2, 0),
                width: 2,
                height: 2,
            })
        );
    }

    #[test]
    fn rows_parse_cells_and_costs() {
        let grid = Grid::try_from_rows([".#1", ".29"]).expect("rows are valid");

        assert_eq!(grid.cell(Point::new(1, 0)), Some(Cell::Blocked));
        assert_eq!(grid.traversal_cost(Point::new(2, 0)), Some(1));
        assert_eq!(grid.traversal_cost(Point::new(1, 1)), Some(2));
        assert_eq!(grid.traversal_cost(Point::new(2, 1)), Some(9));
    }

    #[test]
    fn rows_report_shape_and_character_errors() {
        assert_eq!(
            Grid::try_from_rows(Vec::<String>::new()),
            Err(GridBuildError::EmptyRows)
        );
        assert_eq!(Grid::try_from_rows([""]), Err(GridBuildError::ZeroWidthRow));
        assert_eq!(
            Grid::try_from_rows(["..", "."]),
            Err(GridBuildError::RaggedRow {
                row: 1,
                expected_width: 2,
                actual_width: 1,
            })
        );
        assert_eq!(
            Grid::try_from_rows([".x"]),
            Err(GridBuildError::InvalidRowCharacter {
                row: 0,
                column: 1,
                character: 'x',
            })
        );
    }

    #[test]
    fn macro_delegates_to_row_parser() {
        let from_macro = crate::grid![".#", ".3"].expect("rows are valid");
        let from_parser = Grid::try_from_rows([".#", ".3"]).expect("rows are valid");
        assert_eq!(from_macro, from_parser);
        assert_eq!(crate::grid!(), Err(GridBuildError::EmptyRows));
    }

    #[test]
    fn builder_accepts_tuple_coordinates_and_builds_index() {
        let grid = Grid::builder(3, 2)
            .blocked([(1, 0), (1, 1), (0, 1)])
            .open([(0, 1)])
            .costs([((2, 1), 7)])
            .index_reachability()
            .build()
            .expect("builder input is valid");

        assert_eq!(grid.cell(Point::new(1, 0)), Some(Cell::Blocked));
        assert_eq!(grid.traversal_cost(Point::new(2, 1)), Some(7));
        assert!(!grid.is_reachable(Point::new(0, 0), Point::new(2, 0)));
    }

    #[test]
    fn setters_report_why_an_edit_failed() {
        let mut grid = Grid::new(2, 2).expect("dimensions are valid");

        assert_eq!(
            grid.set_cell(Point::new(2, 0), Cell::Blocked),
            Err(GridEditError::OutOfBounds {
                point: Point::new(2, 0),
                width: 2,
                height: 2,
            })
        );
        grid.set_cell(Point::new(1, 1), Cell::Blocked)
            .expect("point is in bounds");
        assert_eq!(
            grid.set_traversal_cost(Point::new(1, 1), 4),
            Err(GridEditError::BlockedCell {
                point: Point::new(1, 1),
            })
        );
        assert_eq!(
            grid.set_traversal_cost(Point::new(0, 0), 0),
            Err(GridEditError::ZeroTraversalCost {
                point: Point::new(0, 0),
            })
        );
    }

    #[test]
    fn row_parser_and_macro_share_the_same_result() {
        let parsed = Grid::try_from_rows([".#.", ".39"]).expect("rows are valid");
        let expanded = crate::grid![".#.", ".39"].expect("rows are valid");

        assert_eq!(expanded, parsed);
        assert_eq!(parsed.cell(Point::new(1, 0)), Some(Cell::Blocked));
        assert_eq!(parsed.traversal_cost(Point::new(1, 1)), Some(3));
        assert_eq!(parsed.traversal_cost(Point::new(2, 1)), Some(9));
    }

    #[test]
    fn row_parser_reports_precise_shape_and_character_errors() {
        assert_eq!(
            Grid::try_from_rows(Vec::<String>::new()),
            Err(GridBuildError::EmptyRows)
        );
        assert_eq!(Grid::try_from_rows([""]), Err(GridBuildError::ZeroWidthRow));
        assert_eq!(
            Grid::try_from_rows(["..", "."]),
            Err(GridBuildError::RaggedRow {
                row: 1,
                expected_width: 2,
                actual_width: 1,
            })
        );
        assert_eq!(
            Grid::try_from_rows([".x"]),
            Err(GridBuildError::InvalidRowCharacter {
                row: 0,
                column: 1,
                character: 'x',
            })
        );
    }
}