sokoban_elements/

static_board_analysis.rs

use std::collections::{HashMap, VecDeque};

use crate::{
    BoardArea, BoardSyntaxError, BoardSyntaxErrorKind, BoxID, Boxbox, Direction, Goal, GoalID,
    Point2D, Pusher, PusherID, Size2D, SokobanPlus, Tessellation, TileKind, TileShape,
};

/// Static analysis of game boards (outer walls, corners, play area...)
///
/// Static board features are categories of board positions that don't change semantics
/// even after pushers and boxes had been moved around board. For example:
///
/// - positions of outer walls
/// - position of "corners"
/// - active playable area
/// - pusher, box and goal IDs in starting position
/// - ...
///
/// This kind of analysis only makes sense when applied to finalized board designs, ie. a
/// [`GameBoard`](crate::GameBoard) that is no longer being edited.
///
/// # Todo
///
/// - construct and test more pathological cases for Trioban / Hexoban / Octoban (play area,
///   significant walls, corners, ...)
/// - wall surrounded by walls in play area?
/// - in Sokoban this wall should not be marked as playable, neither should floors in same position
pub struct StaticBoardAnalysis {
    tessellation: Tessellation,
    size:         Size2D,

    walls_positions:   BoardArea,
    pushers_positions: BoardArea,
    boxes_positions:   BoardArea,
    goals_positions:   BoardArea,

    boxes:   Box<[Boxbox]>,
    goals:   Box<[Goal]>,
    pushers: Box<[Pusher]>,
}

impl StaticBoardAnalysis {
    /// Builds a new [`StaticBoardAnalysis`] from a board scan.
    ///
    /// That way it is decoupled from [`GameBoard`](crate::GameBoard), with no loss of
    /// functionality.
    pub fn new<I>(
        board: I, size: Size2D, tessellation: Tessellation, sokoban_plus: Option<&SokobanPlus>,
    ) -> Result<Self, BoardSyntaxError>
    where
        I: Iterator<Item = TileKind>,
    {
        let expected_len = size.size();

        let mut walls_pos = BoardArea::new(size);
        let mut pushers_pos = BoardArea::new(size);
        let mut boxes_pos = BoardArea::new(size);
        let mut goals_pos = BoardArea::new(size);

        let mut boxes: Vec<Boxbox> = Vec::default();
        let mut pushers: Vec<Pusher> = Vec::default();
        let mut goals: Vec<Goal> = Vec::default();

        for (idx, tile) in board.enumerate() {
            if idx >= expected_len {
                return Err(BoardSyntaxError::new(
                    BoardSyntaxErrorKind::InputSizeNotMatchedByDeclaredSize {
                        input:           idx.checked_add(1).unwrap_or(idx),
                        declared_width:  size.width,
                        declared_height: size.height,
                    },
                ));
            }

            let pos = Point2D::new_from_idx(idx, &size);

            if tile.is_wall() {
                walls_pos.add_point(pos);
            }

            if tile.has_pusher() {
                let p = Self::build_pusher(pushers.len(), pos.x, pos.y)?;
                pushers_pos.add_point(pos);
                pushers.push(p);
            }

            if tile.has_box() {
                let b = Self::build_box(boxes.len(), pos.x, pos.y, sokoban_plus)?;
                boxes_pos.add_point(pos);
                boxes.push(b);
            }

            if tile.has_goal() {
                let g = Self::build_goal(goals.len(), pos.x, pos.y, sokoban_plus)?;
                goals_pos.add_point(pos);
                goals.push(g);
            }
        }

        Ok(Self {
            tessellation,
            walls_positions: walls_pos,
            pushers_positions: pushers_pos,
            boxes_positions: boxes_pos,
            goals_positions: goals_pos,
            size,
            boxes: boxes.into_boxed_slice(),
            goals: goals.into_boxed_slice(),
            pushers: pushers.into_boxed_slice(),
        })
    }

    /// Flood fill with generic bordering predicate.
    ///
    /// `None` if `root` is off-board.
    ///
    /// # Todo
    ///
    /// It should probably return top-left position of found area, as an optimization
    pub fn flood_fill<F>(
        root: Point2D, is_obstacle: F, size: Size2D, tessellation: Tessellation,
    ) -> Option<BoardArea>
    where
        F: Fn(Point2D) -> bool,
    {
        let mut retv = BoardArea::new(size);
        let mut visited = BoardArea::new(size);
        let mut to_inspect: VecDeque<Point2D> = VecDeque::new();
        to_inspect.push_back(root);

        while !to_inspect.is_empty() {
            let current_position = to_inspect.pop_front()?;
            retv.add_point(current_position);

            for (_, neighbor) in current_position.neighbors(tessellation, size)? {
                if !visited.contains(neighbor) {
                    if !is_obstacle(neighbor) {
                        to_inspect.push_back(neighbor);
                    }
                    visited.add_point(neighbor);
                }
            }
        }

        Some(retv)
    }

    /// Dimensions of the board this analysis was built from.
    pub fn size(&self) -> Size2D { self.size }

    /// [`Tessellation`] of the board this analysis was built from.
    pub fn tessellation(&self) -> Tessellation { self.tessellation }

    /// Positions of walls on the board this analysis was built from.
    pub fn walls_positions(&self) -> &BoardArea { &self.walls_positions }

    /// Positions of boxes on the board this analysis was built from.
    pub fn boxes_positions(&self) -> &BoardArea { &self.boxes_positions }

    /// Positions of goals on the board this analysis was built from.
    pub fn goals_positions(&self) -> &BoardArea { &self.goals_positions }

    /// Positions of pushers on the board this analysis was built from.
    pub fn pushers_positions(&self) -> &BoardArea { &self.pushers_positions }

    /// See also: [`GameBoard::boxes()`](crate::GameBoard::boxes())
    pub fn boxes(&self) -> &[Boxbox] { &self.boxes }

    /// See also: [`GameBoard::goals()`](crate::GameBoard::goals())
    pub fn goals(&self) -> &[Goal] { &self.goals }

    /// See also: [`GameBoard::pushers()`](crate::GameBoard::pushers())
    pub fn pushers(&self) -> &[Pusher] { &self.pushers }

    /// All board positions that are not part of playable area and are not significant walls.
    pub fn outer_area(&self) -> BoardArea {
        let play_area = self.playable_area();
        let significant_walls = self.significant_walls();

        let is_candidate =
            |pos: Point2D| -> bool { !significant_walls.contains(pos) && !play_area.contains(pos) };

        let mut candidates: Vec<Point2D> = Vec::with_capacity(
            self.size
                .width
                .saturating_mul(2)
                .saturating_add(self.size.height.saturating_mul(2)),
        );
        for x in 0..self.size.width {
            let pos = Point2D::new(x, 0);
            if is_candidate(pos) {
                candidates.push(pos);
            }
            let pos = Point2D::new(x, self.size.height - 1);
            if is_candidate(pos) {
                candidates.push(pos);
            }
        }
        for y in 0..self.size.height {
            let pos = Point2D::new(0, y);
            if is_candidate(pos) {
                candidates.push(pos);
            }
            let pos = Point2D::new(self.size.width - 1, y);
            if is_candidate(pos) {
                candidates.push(pos);
            }
        }

        let is_border = |pos: Point2D| -> bool { significant_walls.contains(pos) };

        let mut retv = BoardArea::new(self.size);

        for candidate in candidates {
            if !retv.contains(candidate)
                && let Some(neighbor_outers) =
                    Self::flood_fill(candidate, is_border, self.size, self.tessellation)
            {
                neighbor_outers.into_iter().for_each(|pos| {
                    retv.add_point(pos);
                });
            }
        }

        retv
    }

    /// All board positions which are part of "active" board area.
    ///
    /// Active board area contains any position that is reachable by any of pushers as if there were
    /// no boxes and no other pushers on board.
    ///
    /// Any tile not included in this area may be replaced by wall. Resulting
    /// [`GameBoard`](crate::GameBoard) would no longer look exactly the same but will still have
    /// exact same solution.
    ///
    /// In following image, greyed out squares are the ones that will not be in set returned by this
    /// method:
    ///
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/playable_area1.png)
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/hexoban_play_area.png)
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/trioban_play_area.png)
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/octoban_play_area.png)
    pub fn playable_area(&self) -> BoardArea {
        let is_obstacle = |pos: Point2D| -> bool { self.walls_positions.contains(pos) };

        let mut retv = BoardArea::new(self.size);

        let pushers = self.pushers_positions.clone();

        for pos in pushers {
            if let Some(rp) = Self::flood_fill(pos, is_obstacle, self.size, self.tessellation) {
                for pos in rp {
                    retv.add_point(pos);
                }
            }
        }

        retv
    }

    /// Is the [`playable_area()`](Self::playable_area()) confined by walls alone?
    ///
    /// `true` when no playable position lies on the board's outer edge. This is what "closed board"
    /// means, and it is the only thing it can mean: [`flood_fill()`](Self::flood_fill()) stops at
    /// walls and at the board edge, so the play area is *always* confined by walls together with
    /// the edge. A board is closed exactly when the edge is not doing any of that work.
    ///
    /// A board with no [`Pusher`] has no play area at all and is vacuously confined, as is the
    /// empty board.
    ///
    /// See also: [`GameBoard::enclose()`](crate::GameBoard::enclose())
    pub fn is_playable_area_confined(&self) -> bool {
        let Some((top_left, bottom_right)) = self.playable_area().bounds() else {
            return true;
        };

        top_left.x > 0
            && top_left.y > 0
            && bottom_right.x.saturating_add(1) < self.size.width
            && bottom_right.y.saturating_add(1) < self.size.height
    }

    /// Breadth first search for the shortest path from `from` to `to`, with generic bordering
    /// predicate.
    ///
    /// The path-shaped counterpart of [`flood_fill()`](Self::flood_fill()), and deliberately the
    /// same shape: both take the obstacle predicate, the board size and the [`Tessellation`] as
    /// arguments rather than reading them off `self`, so a caller is free to define "obstacle"
    /// however its rules require.
    ///
    /// Returns [`Some`] empty path when `from == to`, and [`None`] when either endpoint is
    /// off-board or `to` cannot be reached.
    pub fn flood_path<F>(
        from: Point2D, to: Point2D, is_obstacle: F, size: Size2D, tessellation: Tessellation,
    ) -> Option<Vec<Direction>>
    where
        F: Fn(Point2D) -> bool,
    {
        if !from.is_on_board(size) || !to.is_on_board(size) {
            return None;
        }

        if from == to {
            return Some(Vec::new());
        }

        // Unlike `flood_fill`, `from` is marked visited before the search rather than not at all.
        // A predecessor map whose root can be overwritten by a later visit describes a cycle, and
        // the unwind below would never reach `from`.
        let mut visited = BoardArea::new(size);
        visited.add_point(from);

        let mut came_from: HashMap<Point2D, (Direction, Point2D)> = HashMap::new();
        let mut to_inspect: VecDeque<Point2D> = VecDeque::new();
        to_inspect.push_back(from);

        while let Some(current_position) = to_inspect.pop_front() {
            for (direction, neighbor) in current_position.neighbors(tessellation, size)? {
                if visited.contains(neighbor) || is_obstacle(neighbor) {
                    continue;
                }

                visited.add_point(neighbor);
                came_from.insert(neighbor, (direction, current_position));

                if neighbor == to {
                    let mut path = Vec::new();
                    let mut position = to;

                    while position != from {
                        let (direction, previous) = came_from.get(&position)?;
                        path.push(*direction);
                        position = *previous;
                    }

                    path.reverse();
                    return Some(path);
                }

                to_inspect.push_back(neighbor);
            }
        }

        None
    }

    /// Corners in playable area.
    ///
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/corners_in_playable_area.png)
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/hexoban_corners.png)
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/trioban_corners.png)
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/octoban_corners.png)
    pub fn corners(&self) -> BoardArea {
        let mut retv = BoardArea::new(self.size);

        for pos in self.playable_area() {
            if !self.walls_positions.contains(pos) && self.is_corner(pos) {
                retv.add_point(pos);
            }
        }

        retv
    }

    /// Helper for [`GameBoard`](crate::GameBoard) scanners. Builds a [Boxbox] for the `maybe_id`-th
    /// box of a scan, tagged from `sokoban_plus`.
    pub fn build_box(
        maybe_id: usize, x: usize, y: usize, sokoban_plus: Option<&SokobanPlus>,
    ) -> Result<Boxbox, BoardSyntaxError> {
        let box_id = BoxID::try_from(maybe_id).map_err(|e| {
            BoardSyntaxError::new_with_source(BoardSyntaxErrorKind::TooManyBoxes, Some(e))
        })?;

        Ok(Boxbox {
            id: box_id,
            plus_id: sokoban_plus.and_then(|sp| sp.get_box_plus_id(box_id)),
            x,
            y,
        })
    }

    /// Helper for [`GameBoard`](crate::GameBoard) scanners. Builds a [Goal] for the `maybe_id`-th
    /// goal of a scan, tagged from `sokoban_plus`.
    pub fn build_goal(
        maybe_id: usize, x: usize, y: usize, sokoban_plus: Option<&SokobanPlus>,
    ) -> Result<Goal, BoardSyntaxError> {
        let goal_id = GoalID::try_from(maybe_id).map_err(|e| {
            BoardSyntaxError::new_with_source(BoardSyntaxErrorKind::TooManyGoals, Some(e))
        })?;

        Ok(Goal {
            id: goal_id,
            plus_id: sokoban_plus.and_then(|sp| sp.get_goal_plus_id(goal_id)),
            x,
            y,
        })
    }

    /// Helper for [`GameBoard`](crate::GameBoard) scanners. Builds a [Pusher] for the `maybe_id`-th
    /// pusher of a scan.
    pub fn build_pusher(maybe_id: usize, x: usize, y: usize) -> Result<Pusher, BoardSyntaxError> {
        let pusher_id = PusherID::try_from(maybe_id).map_err(|e| {
            BoardSyntaxError::new_with_source(BoardSyntaxErrorKind::TooManyPushers, Some(e))
        })?;
        Ok(Pusher {
            id: pusher_id,
            x,
            y,
        })
    }

    /// Is the given position a corner, ie. is it adjacent to walls in such a way that a box placed
    /// there would be stuck?
    fn is_corner(&self, at: Point2D) -> bool {
        let is_wall =
            |p: Option<Point2D>| -> bool { p.is_some_and(|pp| self.walls_positions.contains(pp)) };

        match self.tessellation {
            Tessellation::Sokoban => {
                let l = at.neighbor(self.tessellation, Direction::Left, self.size);
                let u = at.neighbor(self.tessellation, Direction::Up, self.size);
                let r = at.neighbor(self.tessellation, Direction::Right, self.size);
                let d = at.neighbor(self.tessellation, Direction::Down, self.size);

                (is_wall(l) && is_wall(u))
                    || (is_wall(u) && is_wall(r))
                    || (is_wall(r) && is_wall(d))
                    || (is_wall(d) && is_wall(l))
            }

            Tessellation::Hexoban => {
                let l = at.neighbor(self.tessellation, Direction::Left, self.size);
                let r = at.neighbor(self.tessellation, Direction::Right, self.size);
                let nw = at.neighbor(self.tessellation, Direction::NorthWest, self.size);
                let ne = at.neighbor(self.tessellation, Direction::NorthEast, self.size);
                let sw = at.neighbor(self.tessellation, Direction::SouthWest, self.size);
                let se = at.neighbor(self.tessellation, Direction::SouthEast, self.size);

                (is_wall(l) && is_wall(nw) && is_wall(ne))
                    || (is_wall(nw) && is_wall(ne) && is_wall(r))
                    || (is_wall(ne) && is_wall(r) && is_wall(se))
                    || (is_wall(r) && is_wall(se) && is_wall(sw))
                    || (is_wall(se) && is_wall(sw) && is_wall(l))
                    || (is_wall(sw) && is_wall(l) && is_wall(nw))
            }

            Tessellation::Trioban => {
                at.neighbors(self.tessellation, self.size)
                    .map_or(0, |iter_neighbors| {
                        iter_neighbors.filter(|(_d, p)| is_wall(Some(*p))).count()
                    })
                    >= 4
            }

            Tessellation::Octoban => {
                if self.tessellation.tile_shape_from_pos(at.x, at.y) == TileShape::Octagon {
                    let l = at.neighbor(self.tessellation, Direction::Left, self.size);
                    let u = at.neighbor(self.tessellation, Direction::Up, self.size);
                    let r = at.neighbor(self.tessellation, Direction::Right, self.size);
                    let d = at.neighbor(self.tessellation, Direction::Down, self.size);
                    let nw = at.neighbor(self.tessellation, Direction::NorthWest, self.size);
                    let ne = at.neighbor(self.tessellation, Direction::NorthEast, self.size);
                    let sw = at.neighbor(self.tessellation, Direction::SouthWest, self.size);
                    let se = at.neighbor(self.tessellation, Direction::SouthEast, self.size);

                    (is_wall(l) && is_wall(nw) && is_wall(u))
                        || (is_wall(u) && is_wall(ne) && is_wall(r))
                        || (is_wall(r) && is_wall(se) && is_wall(d))
                        || (is_wall(d) && is_wall(sw) && is_wall(l))
                } else {
                    // if at.tile_shape() == TileShape::Square {
                    let l = at.neighbor(self.tessellation, Direction::Left, self.size);
                    let u = at.neighbor(self.tessellation, Direction::Up, self.size);
                    let r = at.neighbor(self.tessellation, Direction::Right, self.size);
                    let d = at.neighbor(self.tessellation, Direction::Down, self.size);

                    (is_wall(l) && is_wall(u))
                        || (is_wall(u) && is_wall(r))
                        || (is_wall(r) && is_wall(d))
                        || (is_wall(d) && is_wall(l))
                }
            }
        }
    }

    /// All board positions that are touching active [`playable_area()`](Self::playable_area()).
    ///
    /// In following image, tiles that are not greyed out are positions returned by this method.
    /// Notice how it also correctly detects a missing wall tile (circled in red).
    ///
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/significant_walls.png)
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/hexoban_significant_walls.png)
    /// ![](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/trioban_significant_walls.png)
    pub fn significant_walls(&self) -> BoardArea {
        let mut playable_area = self.playable_area();

        let mut non_area = BoardArea::new(self.size);
        for y in 0..self.size.height {
            for x in 0..self.size.width {
                let pos = Point2D::new(x, y);
                if !playable_area.contains(pos) {
                    non_area.add_point(pos);
                }
            }
        }

        // Add any position that directly touches area
        let mut retv = BoardArea::new(self.size);
        let mut remainder = BoardArea::new(self.size);
        for pos in non_area {
            if pos
                .neighbors(self.tessellation, self.size)
                .is_some_and(|mut iter_neigh| iter_neigh.any(|(_d, p)| playable_area.contains(p)))
            {
                retv.add_point(pos);
            } else {
                remainder.add_point(pos);
            }
        }

        for pos in &retv {
            playable_area.add_point(pos);
        }

        if self.tessellation == Tessellation::Sokoban {
            for pos in self.additional_sig_walls_squares(&playable_area, &remainder) {
                retv.add_point(pos);
            }
        }
        if self.tessellation == Tessellation::Trioban {
            for pos in self.additional_sig_walls_triangles(&playable_area, &remainder) {
                retv.add_point(pos);
            }
        }

        retv
    }

    /// Additional significant walls for Trioban tessellation.
    fn additional_sig_walls_triangles(
        &self, found_so_far: &BoardArea, to_check: &BoardArea,
    ) -> BoardArea {
        let mut retv = BoardArea::new(self.size);

        for pos in to_check {
            if pos
                .neighbors(self.tessellation, self.size)
                .map_or(0, |nps| nps.filter(|(_d, p)| found_so_far.contains(*p)).count())
                > 1
            {
                retv.add_point(pos);
            }
        }

        retv
    }

    /// Additional significant walls for Sokoban tessellation.
    fn additional_sig_walls_squares(
        &self, found_so_far: &BoardArea, to_check: &BoardArea,
    ) -> BoardArea {
        let mut retv = BoardArea::new(self.size);

        let neighbor = |p: Option<Point2D>, d: Direction| -> Option<Point2D> {
            if let Some(p1) = p {
                p1.neighbor(self.tessellation, d, self.size)
            } else {
                None
            }
        };

        let is_in_area =
            |p: Option<Point2D>| -> bool { p.is_some_and(|pp| found_so_far.contains(pp)) };

        let is_wall =
            |p: Option<Point2D>| -> bool { p.is_some_and(|pp| self.walls_positions.contains(pp)) };

        // If `pos` is corner wall position and it has two neighbor walls that are already in play
        // area and if between those 2 walls there is no  wall, then this corner should also be
        // marked as belonging to significant walls

        for pos in to_check {
            let l = pos.neighbor(self.tessellation, Direction::Left, self.size);
            let u = pos.neighbor(self.tessellation, Direction::Up, self.size);
            let r = pos.neighbor(self.tessellation, Direction::Right, self.size);
            let d = pos.neighbor(self.tessellation, Direction::Down, self.size);

            let ne = neighbor(u, Direction::Right);
            let se = neighbor(d, Direction::Right);
            let sw = neighbor(d, Direction::Left);
            let nw = neighbor(u, Direction::Left);

            if (is_wall(u) && is_wall(r) && is_in_area(u) && is_in_area(r) && !is_wall(ne))
                || (is_wall(r) && is_wall(d) && is_in_area(r) && is_in_area(d) && !is_wall(se))
                || (is_wall(d) && is_wall(l) && is_in_area(d) && is_in_area(l) && !is_wall(sw))
                || (is_wall(l) && is_wall(u) && is_in_area(l) && is_in_area(u) && !is_wall(nw))
            {
                retv.add_point(pos);
            }
        }

        retv
    }
}

#[cfg(test)]
mod tests {
    use std::collections::HashSet;

    use indoc::indoc;

    use super::*;
    use crate::{GameBoard, Tessellation};

    #[test]
    fn it_calculates_playable_areas() -> Result<(), BoardSyntaxError> {
        // Test data generated after visually inspecting it works. Probably should be
        // split into multiple tests that each presents one pathological case
        // from the following
        //
        // - corner wall in non playable area
        // - missing corner wall is detected
        // - walls fully surrounded by other walls should not be included

        let src = indoc! {"#####   ###########
                           #@  ######       ##
                           #$  #   # . * $   #
                           #. *#$  ##        #
                           #####  $###  ######
                            ##  $ $  #      ##
                           ### # ##   # ######
                           #   # ##  ##### ..#
                           # $  $          ..#
                           ##### ### #@    .+#
                           #  ##     #########
                           #   ####  ##  ### #
                           ########  #   ### #
                           #    ###  ####### #
                           # ##              #
                           ###################"};

        let board = GameBoard::parsed(src, Tessellation::Sokoban)?;

        let expected_playable: HashSet<usize> = HashSet::from_iter([
            20, 21, 22, 39, 40, 41, 43, 44, 45, 58, 59, 60, 62, 63, 64, 81, 82, 83, 98, 99, 100,
            101, 102, 103, 104, 117, 119, 122, 123, 124, 134, 135, 136, 138, 141, 142, 148, 149,
            150, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168,
            169, 176, 180, 182, 183, 184, 185, 186, 187, 188, 195, 196, 197, 198, 199, 217, 218,
            226, 236, 237, 245, 248, 249, 250, 251, 255, 256, 264, 267, 270, 271, 272, 273, 274,
            275, 276, 277, 278, 279, 280, 281, 282, 283,
        ]);

        assert_eq!(
            HashSet::from_iter(
                StaticBoardAnalysis::new(
                    board.iter().map(|(_, t)| t),
                    board.size(),
                    board.tessellation(),
                    None
                )?
                .playable_area()
                .iter()
                .map(|p| p.idx(board.size()))
            ),
            expected_playable
        );

        let expected_walls: HashSet<usize> = HashSet::from_iter([
            0, 1, 2, 3, 4, 19, 23, 24, 25, 26, 27, 38, 42, 46, 57, 61, 65, 76, 77, 78, 79, 80, 84,
            85, 86, 97, 105, 106, 114, 115, 116, 118, 120, 121, 125, 128, 129, 130, 131, 132, 133,
            137, 139, 140, 143, 144, 145, 146, 147, 151, 152, 170, 171, 172, 173, 174, 175, 177,
            178, 179, 181, 189, 194, 200, 201, 202, 203, 204, 205, 206, 207, 208, 213, 214, 215,
            216, 219, 225, 227, 228, 229, 230, 231, 232, 233, 235, 238, 244, 246, 247, 252, 253,
            254, 257, 258, 259, 260, 261, 262, 263, 265, 266, 268, 269, 284, 285, 286, 287, 288,
            289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303,
        ]);
        assert_eq!(
            HashSet::from_iter(
                StaticBoardAnalysis::new(
                    board.iter().map(|(_, t)| t),
                    board.size(),
                    board.tessellation(),
                    None
                )?
                .significant_walls()
                .iter()
                .map(|p| p.idx(board.size()))
            ),
            expected_walls
        );

        Ok(())
    }

    #[test]
    fn it_calculates_hexoban_outer_cells() -> Result<(), BoardSyntaxError> {
        let src = indoc! {"-----------#-#-#---
                           ----------#-----#--
                           ---------#-$-.---#-
                           ----#-#-#---*---#--
                           ---#-#---$-.-$-#---
                           --#-@-.-*-.-.---#--
                           ---#---$---$-*-$-#-
                           ----#-#-#-#---.---#
                           -----------#-----#-
                           ------------#-#-#--"};

        let board = GameBoard::parsed(src, Tessellation::Hexoban)?;

        let expected: HashSet<usize> = HashSet::from_iter([
            0, 1, 2, 3, 4, 8, 9, 10, 11, 12, 17, 18, 19, 20, 21, 27, 28, 35, 36, 44, 53, 54, 63,
            72, 73, 74, 75, 76, 81, 82, 83, 84, 85, 89,
        ]);
        assert_eq!(
            HashSet::from_iter(
                StaticBoardAnalysis::new(
                    board.iter().map(|(_, t)| t),
                    board.size(),
                    board.tessellation(),
                    None
                )?
                .outer_area()
                .iter()
                .map(|p| p.idx(board.size()))
            ),
            expected
        );

        Ok(())
    }
}