use std::{cmp::Ordering, collections::BinaryHeap};
use super::dijkstra::Dijkstra;
use crate::{
grid::Grid,
path::Path,
point::Point,
search::{Pathfinder, SearchRequest, SearchResult},
};
#[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]);
}
}
}
}