condor_grid/algorithms/

rectangular_symmetry_reduction.rs

//! Static-grid [`Pathfinder`]: Rectangular Symmetry Reduction (RSR).
//!
//! Each search builds a transient room decomposition, searches perimeter and macro
//! edges, and materializes a concrete path with the standard invalid/found/no-path
//! outcome. Its final cost recomputes per-cell [`traversal_cost`](crate::Grid::traversal_cost)
//! over path steps. Prefer [`super::astar::AStar`] as the general default; use RSR
//! only when the grid’s rectangular free space is the relevant structure.

use std::{cmp::Ordering, collections::BinaryHeap};

use super::dijkstra::Dijkstra;
use crate::{
    grid::Grid,
    path::Path,
    point::Point,
    search::{Pathfinder, SearchRequest, SearchResult},
};

/// Online [`Pathfinder`]: Rectangular Symmetry Reduction (RSR).
///
/// Per-search room decomposition (no durable preprocess); searches perimeter/macro
/// edges then materializes cardinal segments. Final path cost recomputes `traversal_cost`
/// over steps. Prefer on large rectangular free spaces; falls back to Dijkstra on
/// mismatched room-path costs.
#[derive(Debug, Default, Clone, Copy)]
pub struct RectangularSymmetryReduction;

impl Pathfinder for RectangularSymmetryReduction {
    fn name(&self) -> &'static str {
        "rectangular-symmetry-reduction"
    }

    fn search(&self, grid: &Grid, request: SearchRequest) -> SearchResult {
        crate::search::validate_request(grid, request)?;
        let Some(start_index) = grid.index_of(request.start) else {
            return crate::search::not_found(0);
        };
        let Some(goal_index) = grid.index_of(request.goal) else {
            return crate::search::not_found(0);
        };

        if !grid.is_walkable(request.start) || !grid.is_walkable(request.goal) {
            return crate::search::not_found(0);
        }

        if !grid.is_reachable(request.start, request.goal) {
            return crate::search::not_found(0);
        }

        if request.start == request.goal {
            return crate::search::found(
                Path::from_steps(vec![request.start]).expect("path contains at least one point"),
                1,
            );
        }

        let decomposition = RoomDecomposition::new(grid);
        let Some(start_room_id) = decomposition.room_id(start_index) else {
            return crate::search::not_found(0);
        };
        let Some(goal_room_id) = decomposition.room_id(goal_index) else {
            return crate::search::not_found(0);
        };
        let start_room = decomposition.room(start_room_id);
        let goal_room = decomposition.room(goal_room_id);

        if start_room_id == goal_room_id {
            let steps = direct_room_path(request.start, request.goal);
            let cost = weighted_path_cost(grid, &steps);
            if cost > manhattan_distance(request.start, request.goal) {
                return Dijkstra.search(grid, request);
            }
            return crate::search::found(
                Path::from_steps_with_cost(steps, cost).expect("path contains at least one point"),
                1,
            );
        }

        let start_is_inserted = !start_room.is_kept(request.start);
        let goal_is_inserted = !goal_room.is_kept(request.goal);
        let endpoints = SearchEndpoints {
            start: request.start,
            start_index,
            start_is_inserted,
            goal: request.goal,
            goal_index,
            goal_is_inserted,
        };
        let start_adapter = SpecialAdapter::new(
            grid,
            &decomposition,
            endpoints.start,
            endpoints.start_index,
            endpoints.start_is_inserted,
        );
        let goal_adapter = SpecialAdapter::new(
            grid,
            &decomposition,
            endpoints.goal,
            endpoints.goal_index,
            endpoints.goal_is_inserted,
        );
        let adapters = EndpointAdapters {
            start: start_adapter.as_ref(),
            goal: goal_adapter.as_ref(),
        };
        let mut frontier = BinaryHeap::from([FrontierEntry {
            estimated_total_cost: manhattan_distance(request.start, request.goal),
            cost_so_far: 0,
            index: start_index,
        }]);
        let mut best_costs = vec![usize::MAX; grid.cell_count()];
        let mut parents = std::iter::repeat_with(|| None)
            .take(grid.cell_count())
            .collect::<Vec<Option<usize>>>();
        let mut visited_nodes = 0;
        let watch = crate::search::BudgetWatch::start(request.budget);

        best_costs[start_index] = 0;

        while let Some(entry) = frontier.pop() {
            if entry.cost_so_far != best_costs[entry.index] {
                continue;
            }

            visited_nodes += 1;
            if entry.index == goal_index {
                break;
            }

            if let Err(reason) = watch.check(visited_nodes) {
                return Err(crate::search::budget_error(reason));
            }

            let current = grid.point_from_index(entry.index);
            for_each_successor(
                grid,
                &decomposition,
                current,
                entry.index,
                endpoints,
                adapters,
                |target_index, edge_cost| {
                    let next_cost = entry.cost_so_far + edge_cost;
                    if next_cost >= best_costs[target_index] {
                        return;
                    }

                    best_costs[target_index] = next_cost;
                    parents[target_index] = Some(entry.index);

                    let target = grid.point_from_index(target_index);
                    frontier.push(FrontierEntry {
                        estimated_total_cost: next_cost + manhattan_distance(target, request.goal),
                        cost_so_far: next_cost,
                        index: target_index,
                    });
                },
            );
        }

        if best_costs[goal_index] == usize::MAX {
            return crate::search::not_found(visited_nodes);
        }

        crate::search::found(
            reconstruct_path(grid, request.start, goal_index, &parents),
            visited_nodes,
        )
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct FrontierEntry {
    estimated_total_cost: usize,
    cost_so_far: usize,
    index: usize,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SearchEndpoints {
    start: Point,
    start_index: usize,
    start_is_inserted: bool,
    goal: Point,
    goal_index: usize,
    goal_is_inserted: bool,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct EndpointAdapters<'a> {
    start: Option<&'a SpecialAdapter>,
    goal: Option<&'a SpecialAdapter>,
}

#[derive(Debug, Clone, PartialEq, Eq)]
struct SpecialAdapter {
    room_id: usize,
    special: Point,
    special_index: usize,
    forward_targets: [(usize, usize); 4],
    forward_len: usize,
    back_connectors: [usize; 4],
    back_len: usize,
}

impl SpecialAdapter {
    fn new(
        grid: &Grid,
        decomposition: &RoomDecomposition,
        special: Point,
        special_index: usize,
        is_inserted: bool,
    ) -> Option<Self> {
        if !is_inserted {
            return None;
        }

        let room_id = decomposition
            .room_id(special_index)
            .expect("inserted special nodes must belong to a room");
        let room = decomposition.room(room_id);
        let mut forward_targets = [(0usize, 0usize); 4];
        let mut back_connectors = [0usize; 4];
        let mut forward_len = 0usize;
        let mut back_len = 0usize;

        room.for_each_connection_point(special, |target| {
            let target_index = grid
                .index_of(target)
                .expect("room connection points must exist inside the grid");
            forward_targets[forward_len] = (target_index, manhattan_distance(special, target));
            back_connectors[back_len] = target_index;
            forward_len += 1;
            back_len += 1;
        });

        Some(Self {
            room_id,
            special,
            special_index,
            forward_targets,
            forward_len,
            back_connectors,
            back_len,
        })
    }

    fn for_each_forward_edge(&self, mut f: impl FnMut(usize, usize)) {
        for (target_index, edge_cost) in self.forward_targets[..self.forward_len].iter().copied() {
            f(target_index, edge_cost);
        }
    }

    fn maybe_emit_back_edge(
        &self,
        current_room_id: usize,
        current_index: usize,
        current: Point,
        mut f: impl FnMut(usize, usize),
    ) {
        if current_room_id != self.room_id {
            return;
        }

        if self.back_connectors[..self.back_len]
            .iter()
            .all(|connector| *connector != current_index)
        {
            return;
        }

        f(
            self.special_index,
            manhattan_distance(current, self.special),
        );
    }
}

impl Ord for FrontierEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .estimated_total_cost
            .cmp(&self.estimated_total_cost)
            .then_with(|| other.cost_so_far.cmp(&self.cost_so_far))
            .then_with(|| other.index.cmp(&self.index))
    }
}

impl PartialOrd for FrontierEntry {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
struct Room {
    x1: usize,
    y1: usize,
    x2: usize,
    y2: usize,
    trivial: bool,
    left_side: Vec<SideEntry>,
    right_side: Vec<SideEntry>,
    top_side: Vec<SideEntry>,
    bottom_side: Vec<SideEntry>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SideEntry {
    index: usize,
    coordinate: usize,
}

impl Room {
    fn width(&self) -> usize {
        self.x2 - self.x1 + 1
    }

    fn height(&self) -> usize {
        self.y2 - self.y1 + 1
    }

    fn is_trivial(&self) -> bool {
        self.trivial
    }

    fn is_perimeter(&self, point: Point) -> bool {
        point.x == self.x1 || point.x == self.x2 || point.y == self.y1 || point.y == self.y2
    }

    fn is_kept(&self, point: Point) -> bool {
        self.is_trivial() || self.is_perimeter(point)
    }

    fn for_each_connection_point(&self, point: Point, mut f: impl FnMut(Point)) {
        let mut seen = [None; 4];
        let mut seen_len = 0usize;

        for candidate in [
            Point::new(self.x1, point.y),
            Point::new(self.x2, point.y),
            Point::new(point.x, self.y1),
            Point::new(point.x, self.y2),
        ] {
            if seen[..seen_len]
                .iter()
                .flatten()
                .any(|prior| *prior == candidate)
            {
                continue;
            }

            seen[seen_len] = Some(candidate);
            seen_len += 1;
            f(candidate);
        }
    }

    fn emit_materialized_macro_edges(
        &self,
        point: Point,
        point_index: usize,
        side_mask: u8,
        mut f: impl FnMut(usize, usize),
    ) {
        if self.is_trivial() || side_mask == 0 {
            return;
        }

        if side_mask & SIDE_LEFT != 0 {
            let base_cost = self.width() - 1;
            for entry in &self.right_side {
                if entry.index != point_index {
                    f(entry.index, base_cost + point.y.abs_diff(entry.coordinate));
                }
            }
        }

        if side_mask & SIDE_RIGHT != 0 {
            let base_cost = self.width() - 1;
            for entry in &self.left_side {
                if entry.index != point_index {
                    f(entry.index, base_cost + point.y.abs_diff(entry.coordinate));
                }
            }
        }

        if side_mask & SIDE_TOP != 0 {
            let skipped_coordinate = if side_mask & SIDE_LEFT != 0 {
                Some(self.x2)
            } else if side_mask & SIDE_RIGHT != 0 {
                Some(self.x1)
            } else {
                None
            };
            let base_cost = self.height() - 1;
            for entry in &self.bottom_side {
                if Some(entry.coordinate) == skipped_coordinate || entry.index == point_index {
                    continue;
                }
                f(entry.index, base_cost + point.x.abs_diff(entry.coordinate));
            }
        }

        if side_mask & SIDE_BOTTOM != 0 {
            let skipped_coordinate = if side_mask & SIDE_LEFT != 0 {
                Some(self.x2)
            } else if side_mask & SIDE_RIGHT != 0 {
                Some(self.x1)
            } else {
                None
            };
            let base_cost = self.height() - 1;
            for entry in &self.top_side {
                if Some(entry.coordinate) == skipped_coordinate || entry.index == point_index {
                    continue;
                }
                f(entry.index, base_cost + point.x.abs_diff(entry.coordinate));
            }
        }
    }
}

const SIDE_LEFT: u8 = 1;
const SIDE_RIGHT: u8 = 1 << 1;
const SIDE_TOP: u8 = 1 << 2;
const SIDE_BOTTOM: u8 = 1 << 3;

#[derive(Debug, Clone, PartialEq, Eq)]
struct RoomDecomposition {
    rooms: Vec<Room>,
    room_by_index: Vec<Option<usize>>,
    search_node_by_index: Vec<bool>,
    side_mask_by_index: Vec<u8>,
}

impl RoomDecomposition {
    fn new(grid: &Grid) -> Self {
        let mut assigned = vec![false; grid.cell_count()];
        let mut room_by_index = vec![None; grid.cell_count()];
        let mut search_node_by_index = vec![false; grid.cell_count()];
        let mut side_mask_by_index = vec![0u8; grid.cell_count()];
        let mut rooms = Vec::new();

        for y in 0..grid.height() {
            for x in 0..grid.width() {
                let point = Point::new(x, y);
                let Some(index) = grid.index_of(point) else {
                    continue;
                };

                if assigned[index] || !grid.is_walkable(point) {
                    continue;
                }

                let (width, height) = best_room_from(grid, &assigned, point);
                let x2 = x + width - 1;
                let y2 = y + height - 1;
                let trivial = width <= 2 || height <= 2;
                let mut left_side = Vec::new();
                let mut right_side = Vec::new();
                let mut top_side = Vec::new();
                let mut bottom_side = Vec::new();
                let room = Room {
                    x1: x,
                    y1: y,
                    x2,
                    y2,
                    trivial,
                    left_side: Vec::new(),
                    right_side: Vec::new(),
                    top_side: Vec::new(),
                    bottom_side: Vec::new(),
                };
                let room_id = rooms.len();

                for yy in room.y1..=room.y2 {
                    for xx in room.x1..=room.x2 {
                        let member = Point::new(xx, yy);
                        let member_index = grid
                            .index_of(member)
                            .expect("room members must exist inside the grid");
                        assigned[member_index] = true;
                        room_by_index[member_index] = Some(room_id);

                        let mut side_mask = 0u8;
                        if xx == room.x1 {
                            side_mask |= SIDE_LEFT;
                        }
                        if xx == room.x2 {
                            side_mask |= SIDE_RIGHT;
                        }
                        if yy == room.y1 {
                            side_mask |= SIDE_TOP;
                        }
                        if yy == room.y2 {
                            side_mask |= SIDE_BOTTOM;
                        }

                        if trivial || side_mask != 0 {
                            search_node_by_index[member_index] = true;
                        }
                        side_mask_by_index[member_index] = side_mask;

                        if !trivial {
                            if side_mask & SIDE_LEFT != 0 {
                                left_side.push(SideEntry {
                                    index: member_index,
                                    coordinate: yy,
                                });
                            }
                            if side_mask & SIDE_RIGHT != 0 {
                                right_side.push(SideEntry {
                                    index: member_index,
                                    coordinate: yy,
                                });
                            }
                            if side_mask & SIDE_TOP != 0 {
                                top_side.push(SideEntry {
                                    index: member_index,
                                    coordinate: xx,
                                });
                            }
                            if side_mask & SIDE_BOTTOM != 0 {
                                bottom_side.push(SideEntry {
                                    index: member_index,
                                    coordinate: xx,
                                });
                            }
                        }
                    }
                }

                rooms.push(Room {
                    left_side,
                    right_side,
                    top_side,
                    bottom_side,
                    ..room
                });
            }
        }

        Self {
            rooms,
            room_by_index,
            search_node_by_index,
            side_mask_by_index,
        }
    }

    fn room_id(&self, index: usize) -> Option<usize> {
        self.room_by_index[index]
    }

    fn room(&self, room_id: usize) -> &Room {
        &self.rooms[room_id]
    }

    fn is_search_node(&self, index: usize, start_index: usize, goal_index: usize) -> bool {
        index == start_index || index == goal_index || self.search_node_by_index[index]
    }

    fn side_mask(&self, index: usize) -> u8 {
        self.side_mask_by_index[index]
    }
}

fn best_room_from(grid: &Grid, assigned: &[bool], origin: Point) -> (usize, usize) {
    let mut best_width = 1;
    let mut best_height = 1;
    let mut best_interior = 0usize;
    let mut best_area = 1usize;
    let mut min_width = usize::MAX;

    for y in origin.y..grid.height() {
        let row_width = contiguous_unassigned_width(grid, assigned, origin.x, y);
        if row_width == 0 {
            break;
        }

        min_width = min_width.min(row_width);
        let height = y - origin.y + 1;
        let area = min_width * height;
        let interior = interior_node_count(min_width, height);

        if (interior, area) > (best_interior, best_area) {
            best_interior = interior;
            best_area = area;
            best_width = min_width;
            best_height = height;
        }
    }

    (best_width, best_height)
}

fn contiguous_unassigned_width(grid: &Grid, assigned: &[bool], start_x: usize, y: usize) -> usize {
    let mut width = 0;
    for x in start_x..grid.width() {
        let point = Point::new(x, y);
        if !grid.is_walkable(point) {
            break;
        }

        let index = grid
            .index_of(point)
            .expect("walkable points must exist inside the grid");
        if assigned[index] {
            break;
        }

        width += 1;
    }
    width
}

fn interior_node_count(width: usize, height: usize) -> usize {
    width.saturating_sub(2) * height.saturating_sub(2)
}

fn for_each_successor(
    grid: &Grid,
    decomposition: &RoomDecomposition,
    current: Point,
    current_index: usize,
    endpoints: SearchEndpoints,
    adapters: EndpointAdapters<'_>,
    mut f: impl FnMut(usize, usize),
) {
    let room_id = decomposition
        .room_id(current_index)
        .expect("walkable search nodes must belong to a room");
    let room = decomposition.room(room_id);

    for_each_cardinal_successor(
        grid,
        decomposition,
        current,
        current_index,
        endpoints,
        &mut f,
    );

    if room.is_trivial() {
        return;
    }

    if current_index == endpoints.start_index
        && let Some(adapter) = adapters.start
    {
        adapter.for_each_forward_edge(&mut f);
    }

    if current_index == endpoints.goal_index
        && let Some(adapter) = adapters.goal
    {
        adapter.for_each_forward_edge(&mut f);
    }

    let side_mask = decomposition.side_mask(current_index);
    if side_mask != 0 {
        room.emit_materialized_macro_edges(current, current_index, side_mask, &mut f);

        if let Some(adapter) = adapters.start {
            adapter.maybe_emit_back_edge(room_id, current_index, current, &mut f);
        }

        if let Some(adapter) = adapters.goal {
            adapter.maybe_emit_back_edge(room_id, current_index, current, &mut f);
        }
    }
}

fn for_each_cardinal_successor(
    grid: &Grid,
    decomposition: &RoomDecomposition,
    current: Point,
    current_index: usize,
    endpoints: SearchEndpoints,
    mut f: impl FnMut(usize, usize),
) {
    if current.x > 0 {
        let target_index = current_index - 1;
        if decomposition.is_search_node(target_index, endpoints.start_index, endpoints.goal_index) {
            f(target_index, 1);
        }
    }

    if current.x + 1 < grid.width() {
        let target_index = current_index + 1;
        if decomposition.is_search_node(target_index, endpoints.start_index, endpoints.goal_index) {
            f(target_index, 1);
        }
    }

    if current.y > 0 {
        let target_index = current_index - grid.width();
        if decomposition.is_search_node(target_index, endpoints.start_index, endpoints.goal_index) {
            f(target_index, 1);
        }
    }

    if current.y + 1 < grid.height() {
        let target_index = current_index + grid.width();
        if decomposition.is_search_node(target_index, endpoints.start_index, endpoints.goal_index) {
            f(target_index, 1);
        }
    }
}

fn straight_segment(from: Point, to: Point) -> Vec<Point> {
    let mut points = Vec::with_capacity(manhattan_distance(from, to));
    let mut current = from;

    while current.x != to.x {
        current = if current.x < to.x {
            Point::new(current.x + 1, current.y)
        } else {
            Point::new(current.x - 1, current.y)
        };
        points.push(current);
    }

    while current.y != to.y {
        current = if current.y < to.y {
            Point::new(current.x, current.y + 1)
        } else {
            Point::new(current.x, current.y - 1)
        };
        points.push(current);
    }

    points
}

fn direct_room_path(start: Point, goal: Point) -> Vec<Point> {
    let mut steps = vec![start];
    steps.extend(straight_segment(start, goal));
    steps
}

fn reconstruct_path(
    grid: &Grid,
    start: Point,
    goal_index: usize,
    parents: &[Option<usize>],
) -> Path {
    let mut segments = Vec::new();
    let mut current_index = goal_index;

    while let Some(parent_index) = parents[current_index] {
        let parent = grid.point_from_index(parent_index);
        let current = grid.point_from_index(current_index);
        segments.push(straight_segment(parent, current));
        current_index = parent_index;
    }

    let mut steps = vec![start];
    for segment in segments.iter().rev() {
        steps.extend(segment.iter().copied());
    }

    let cost = weighted_path_cost(grid, &steps);
    Path::from_steps_with_cost(steps, cost).expect("path contains at least one point")
}

fn weighted_path_cost(grid: &Grid, steps: &[Point]) -> usize {
    steps.iter().skip(1).fold(0usize, |total, point| {
        total.saturating_add(grid.traversal_cost(*point).unwrap_or(1))
    })
}

fn manhattan_distance(from: Point, to: Point) -> usize {
    from.x.abs_diff(to.x) + from.y.abs_diff(to.y)
}

#[cfg(test)]
mod tests {
    use crate::{
        algorithms::rectangular_symmetry_reduction::RectangularSymmetryReduction,
        grid::{Cell, Grid},
        point::Point,
        search::{Pathfinder, SearchRequest},
    };

    #[test]
    fn charges_per_cell_traversal_cost_matching_dijkstra() {
        let mut grid = Grid::new(8, 1).expect("grid dimensions are valid");
        assert_eq!(grid.set_traversal_cost(Point::new(4, 0), 5), Ok(()));

        let request = SearchRequest::new(Point::new(0, 0), Point::new(7, 0));
        let result = RectangularSymmetryReduction.search(&grid, request);

        assert!(result.as_ref().expect("valid search request").is_found());
        assert_eq!(
            result.as_ref().expect("valid search request").cost(),
            Some(11)
        );

        let path = result
            .as_ref()
            .expect("valid search request")
            .path()
            .expect("path should exist");
        let manual: usize = path
            .steps()
            .iter()
            .skip(1)
            .map(|p| grid.traversal_cost(*p).expect("walkable cell has cost"))
            .sum();
        assert_eq!(
            Some(manual),
            result.as_ref().expect("valid search request").cost()
        );

        let dijkstra_cost = crate::Dijkstra
            .search(&grid, request)
            .as_ref()
            .expect("valid search request")
            .cost();
        assert_eq!(
            result.as_ref().expect("valid search request").cost(),
            dijkstra_cost
        );
    }

    #[test]
    fn finds_a_shortest_path_through_the_only_gap() {
        let mut grid = Grid::new(5, 5).expect("grid dimensions are valid");
        for y in 0..5 {
            if y != 2 {
                grid.set_cell(Point::new(2, y), Cell::Blocked)
                    .expect("valid grid edit");
            }
        }

        let rsr = RectangularSymmetryReduction;
        let result = rsr.search(
            &grid,
            SearchRequest::new(Point::new(0, 0), Point::new(4, 4)),
        );

        assert!(result.as_ref().expect("valid search request").is_found());
        assert_eq!(
            result.as_ref().expect("valid search request").cost(),
            Some(8)
        );

        let path = result
            .as_ref()
            .expect("valid search request")
            .path()
            .expect("path should exist");
        assert_eq!(path.start(), Point::new(0, 0));
        assert_eq!(path.goal(), Point::new(4, 4));
        assert!(path.steps().contains(&Point::new(2, 2)));
    }

    #[test]
    fn reports_when_no_path_exists() {
        let mut grid = Grid::new(3, 3).expect("grid dimensions are valid");
        for x in 0..3 {
            grid.set_cell(Point::new(x, 1), Cell::Blocked)
                .expect("valid grid edit");
        }

        let rsr = RectangularSymmetryReduction;
        let result = rsr.search(
            &grid,
            SearchRequest::new(Point::new(0, 0), Point::new(2, 2)),
        );

        assert!(!result.as_ref().expect("valid search request").is_found());
        assert_eq!(result.as_ref().expect("valid search request").cost(), None);
        assert!(
            result
                .as_ref()
                .expect("valid search request")
                .stats()
                .visited_nodes
                > 0
        );
    }

    #[test]
    fn directly_connects_points_inside_the_same_empty_room() {
        let grid = Grid::new(6, 5).expect("grid dimensions are valid");
        let rsr = RectangularSymmetryReduction;
        let result = rsr.search(
            &grid,
            SearchRequest::new(Point::new(1, 1), Point::new(4, 3)),
        );

        assert!(result.as_ref().expect("valid search request").is_found());
        assert_eq!(
            result.as_ref().expect("valid search request").cost(),
            Some(5)
        );
        assert_eq!(
            result
                .as_ref()
                .expect("valid search request")
                .stats()
                .visited_nodes,
            1
        );
    }

    #[test]
    fn same_room_weighted_route_matches_dijkstra() {
        let mut grid = Grid::new(3, 3).expect("grid dimensions are valid");
        assert_eq!(grid.set_traversal_cost(Point::new(1, 1), 100), Ok(()));

        let request = SearchRequest::new(Point::new(0, 1), Point::new(2, 1));
        let result = RectangularSymmetryReduction.search(&grid, request);
        let dijkstra = crate::Dijkstra.search(&grid, request);

        assert!(result.as_ref().expect("valid search request").is_found());
        assert_eq!(
            result.as_ref().expect("valid search request").cost(),
            Some(4)
        );
        assert_eq!(
            result.as_ref().expect("valid search request").cost(),
            dijkstra.as_ref().expect("valid search request").cost()
        );
        assert!(
            !result
                .as_ref()
                .expect("valid search request")
                .path()
                .expect("path should exist")
                .steps()
                .contains(&Point::new(1, 1))
        );
    }

    #[test]
    fn connects_inserted_room_endpoints_through_a_doorway() {
        let mut grid = Grid::new(8, 5).expect("grid dimensions are valid");
        for y in 0..5 {
            if y != 2 {
                grid.set_cell(Point::new(4, y), Cell::Blocked)
                    .expect("valid grid edit");
            }
        }

        let rsr = RectangularSymmetryReduction;
        let result = rsr.search(
            &grid,
            SearchRequest::new(Point::new(1, 1), Point::new(6, 3)),
        );

        assert!(result.as_ref().expect("valid search request").is_found());
        assert_eq!(
            result.as_ref().expect("valid search request").cost(),
            Some(7)
        );

        let path = result
            .as_ref()
            .expect("valid search request")
            .path()
            .expect("path should exist");
        assert_eq!(path.start(), Point::new(1, 1));
        assert_eq!(path.goal(), Point::new(6, 3));
        assert!(path.steps().contains(&Point::new(4, 2)));
    }

    #[test]
    fn materializes_non_trivial_room_perimeter_metadata() {
        let grid = Grid::new(4, 4).expect("grid dimensions are valid");
        let decomposition = super::RoomDecomposition::new(&grid);
        let room = decomposition.room(0);

        assert!(!room.is_trivial());
        assert_eq!(room.left_side.len(), 4);
        assert_eq!(room.right_side.len(), 4);
        assert_eq!(room.top_side.len(), 4);
        assert_eq!(room.bottom_side.len(), 4);

        let top_left = grid
            .index_of(Point::new(0, 0))
            .expect("top-left should exist");
        let center = grid
            .index_of(Point::new(1, 1))
            .expect("center should exist");

        assert_eq!(
            decomposition.side_mask(top_left),
            super::SIDE_LEFT | super::SIDE_TOP
        );
        assert!(decomposition.search_node_by_index[top_left]);
        assert!(!decomposition.search_node_by_index[center]);
    }

    #[test]
    fn materializes_trivial_rooms_as_search_nodes_without_macro_sides() {
        let grid = Grid::new(2, 2).expect("grid dimensions are valid");
        let decomposition = super::RoomDecomposition::new(&grid);
        let room = decomposition.room(0);

        assert!(room.is_trivial());
        assert!(room.left_side.is_empty());
        assert!(room.right_side.is_empty());
        assert!(room.top_side.is_empty());
        assert!(room.bottom_side.is_empty());

        for y in 0..grid.height() {
            for x in 0..grid.width() {
                let index = grid
                    .index_of(Point::new(x, y))
                    .expect("grid point should exist");
                assert!(decomposition.search_node_by_index[index]);
            }
        }
    }
}