sokoban_elements/

tessellation.rs

mod errors;
mod hexoban;
mod octoban;
mod sokoban;
mod trioban;

use std::fmt::Debug;
use std::hash::Hash;

use errors::{TessellationError, validate_and_apply_delta};

use crate::game_board::BoardTransform;
use crate::{Direction, DirectionsSet, Size2D, TileShape};

/// Sokoban game variants.
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum Tessellation {
    /// Classic Sokoban game variant.
    ///
    /// Game board is grid of squares.
    ///
    /// [`Direction`](crate::Direction) <-> character mapping:
    ///
    /// | Direction          | Characters |
    /// | ------------------ | ---------- |
    /// | `Direction::Left`  | `l`, `L`   |
    /// | `Direction::Right` | `r`, `R`   |
    /// | `Direction::Up`    | `u`, `U`   |
    /// | `Direction::Down`  | `d`, `D`   |
    ///
    /// Example board
    ///
    /// ![Classic sokoban board](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/classic_sokoban_board.png)
    #[default]
    Sokoban,

    /// Hexoban game variant.
    ///
    /// Game board is grid of vertical, equilateral hexagons with following coordinate system:
    ///
    /// ![Hexoban coordinates](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/hexoban_coordinates.png)
    ///
    /// Textual representation uses two characters for each hexagon. This allows different encoding
    /// schemes.
    ///
    /// | Scheme 1             | Scheme 2             |
    /// | -------------------- | -------------------- |
    /// | ![][hexoban_scheme1] | ![][hexoban_scheme2] |
    ///
    /// [hexoban_scheme1]: https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/hexoban_scheme1.png
    /// [hexoban_scheme2]: https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/hexoban_scheme2.png
    ///
    /// As long as encoding of single board is consistent, all methods handle any scheme
    /// transparently - parsing of board strings 'Just Works ™'.
    ///
    /// [`Direction`](crate::Direction) <-> character mapping:
    ///
    /// | Direction              | Characters |
    /// | ---------------------- | ---------- |
    /// | `Direction::Left`      | `l`, `L`   |
    /// | `Direction::Right`     | `r`, `R`   |
    /// | `Direction::NorthWest` | `u`, `U`   |
    /// | `Direction::SouthWest` | `d`, `D`   |
    /// | `Direction::NorthEast` | `n`, `N`   |
    /// | `Direction::SouthEast` | `s`, `S`   |
    ///
    /// Example board
    ///
    /// ![Hexoban puzzle](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/hexoban_example_board.png)
    Hexoban,

    /// Trioban game variant.
    ///
    /// Game board is grid of alternating triangles with origin triangle pointing down.
    ///
    /// Depending on pusher position, not all move directions are allowed on all board positions:
    ///
    /// ![Trioban movement](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/trioban_am.png)
    ///
    /// [`Direction`](crate::Direction) <-> character mapping:
    ///
    /// | Direction              | Characters |
    /// | ---------------------- | ---------- |
    /// | `Direction::Left`      | `l`, `L`   |
    /// | `Direction::Right`     | `r`, `R`   |
    /// | `Direction::NorthWest` | `u`, `U`   |
    /// | `Direction::SouthWest` | `s`, `S`   |
    /// | `Direction::NorthEast` | `n`, `N`   |
    /// | `Direction::SouthEast` | `d`, `D`   |
    ///
    /// Example board
    ///
    /// ![Trioban puzzle](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/trioban_example_board.png)
    Trioban,

    /// Octoban game variant.
    ///
    /// Game board is grid of alternating squares and octagons with origin of coordinate system
    /// being octagon.
    ///
    /// ![Octoban coordinates](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/octoban_coordinates.png)
    ///
    /// This game variant allows usage of all 8 directions of movement from
    /// [`Direction`](crate::Direction). Depending on current pusher position, some of these
    /// directions may not result in successful move or may even be invalid (ie. trying to move
    /// north-west while standing on square tile).
    ///
    /// [`Direction`](crate::Direction) <-> character mapping:
    ///
    /// | Direction              | Characters |
    /// | ---------------------- | ---------- |
    /// | `Direction::Up`        | `u`, `U`   |
    /// | `Direction::NorthEast` | `n`, `N`   |
    /// | `Direction::Right`     | `r`, `R`   |
    /// | `Direction::SouthEast` | `e`, `E`   |
    /// | `Direction::Down`      | `d`, `D`   |
    /// | `Direction::SouthWest` | `s`, `S`   |
    /// | `Direction::Left`      | `l`, `L`   |
    /// | `Direction::NorthWest` | `w`, `W`   |
    ///
    /// Example board
    ///
    /// ![Octoban puzzle](https://raw.githubusercontent.com/tadams42/sokoban-elements/main/crates/sokoban-elements/doc/img/octoban_example_board.png)
    Octoban,
}

impl Tessellation {
    /// Number of all possible [`Tessellation`]s.
    pub const COUNT: usize = 4;

    /// All possible [`Tessellation`]s in order of their discriminant values.
    pub const ALL: [Tessellation; Tessellation::COUNT] = [
        Tessellation::Sokoban,
        Tessellation::Hexoban,
        Tessellation::Trioban,
        Tessellation::Octoban,
    ];

    /// Angle of one call to [`GameBoard::rotate()`](crate::GameBoard::rotate), in degrees.
    pub fn rotation_step_degrees(&self) -> u16 {
        match self {
            Tessellation::Sokoban => sokoban::ROTATION_STEP_DEGREES,
            Tessellation::Hexoban => hexoban::ROTATION_STEP_DEGREES,
            Tessellation::Trioban => trioban::ROTATION_STEP_DEGREES,
            Tessellation::Octoban => octoban::ROTATION_STEP_DEGREES,
        }
    }

    /// Smallest axis-aligned integer translation that preserves the tiling.
    ///
    /// Board resizing may apply a smaller shift by adding perpendicular padding or, for Hexoban,
    /// reindexing alternating rows.
    pub fn translation_period(&self) -> Size2D {
        match self {
            Tessellation::Sokoban => Size2D::new(1, 1),
            Tessellation::Hexoban => Size2D::new(1, 2),
            Tessellation::Trioban | Tessellation::Octoban => Size2D::new(2, 2),
        }
    }

    /// `true` if translation by `(dx, dy)` preserves the tiling.
    pub(crate) fn is_rigid_translation(self, dx: i64, dy: i64) -> bool {
        match self {
            Tessellation::Sokoban => sokoban::is_rigid_translation(dx, dy),
            Tessellation::Hexoban => hexoban::is_rigid_translation(dx, dy),
            Tessellation::Trioban => trioban::is_rigid_translation(dx, dy),
            Tessellation::Octoban => octoban::is_rigid_translation(dx, dy),
        }
    }

    /// Result of applying `transform` to `(x, y)`.
    pub(crate) fn transformed_raw(self, transform: BoardTransform, x: i64, y: i64) -> (i64, i64) {
        match self {
            Tessellation::Sokoban => sokoban::transformed_raw(transform, x, y),
            Tessellation::Hexoban => hexoban::transformed_raw(transform, x, y),
            Tessellation::Trioban => trioban::transformed_raw(transform, x, y),
            Tessellation::Octoban => octoban::transformed_raw(transform, x, y),
        }
    }

    /// Slice of all directions that are supported by this tessellation.
    pub fn known_directions(&self) -> &'static [Direction] {
        match self {
            Tessellation::Sokoban => &sokoban::KNOWN_DIRECTIONS,
            Tessellation::Trioban => &trioban::KNOWN_DIRECTIONS,
            Tessellation::Octoban => &octoban::KNOWN_DIRECTIONS,
            Tessellation::Hexoban => &hexoban::KNOWN_DIRECTIONS,
        }
    }

    /// Slice of all tile shapes that are supported by this tessellation.
    pub fn tile_shapes(&self) -> &'static [TileShape] {
        match self {
            Tessellation::Sokoban => &sokoban::TILE_SHAPES,
            Tessellation::Trioban => &trioban::TILE_SHAPES,
            Tessellation::Octoban => &octoban::TILE_SHAPES,
            Tessellation::Hexoban => &hexoban::TILE_SHAPES,
        }
    }

    /// [`TileShape`] for given game board position.
    ///
    /// Doesn't check if `(x, y)` is off board position because planar tiling applies to whole 2D
    /// plane, not just to some part of it enclosed by some game board.
    pub const fn tile_shape_from_pos(&self, x: usize, y: usize) -> TileShape {
        match self {
            Tessellation::Sokoban => sokoban::tile_shape_from_pos(),
            Tessellation::Hexoban => hexoban::tile_shape_from_pos(),
            Tessellation::Octoban => octoban::tile_shape_from_pos(x, y),
            Tessellation::Trioban => trioban::tile_shape_from_pos(x, y),
        }
    }

    /// Calculates neighbor position in part of plane enclosed by some game board.
    ///
    /// It returns `None` if:
    ///
    /// - input coordinate `(x, y)` is off-board coordinate
    /// - output coordinate in direction `to` would've been off-board coordinate
    /// - `to` is not supported direction of movement for underlying [`Tessellation`] (for example,
    ///   trying to move north-west in [`Tessellation::Sokoban`] from any position)
    /// - `to` is supported direction of movement for underlying [`Tessellation`] but is not allowed
    ///   for `from` (for example, trying to move north-west in [`Tessellation::Octoban`] from
    ///   position of square tile)
    pub fn neighbor(
        &self, x: usize, y: usize, to: Direction, width: usize, height: usize,
    ) -> Option<(usize, usize)> {
        match self {
            Tessellation::Sokoban => sokoban::neighbor_checked(x, y, to, width, height).ok(),
            Tessellation::Hexoban => hexoban::neighbor_checked(x, y, to, width, height).ok(),
            Tessellation::Octoban => octoban::neighbor_checked(x, y, to, width, height).ok(),
            Tessellation::Trioban => trioban::neighbor_checked(x, y, to, width, height).ok(),
        }
    }

    /// Calculates set of directions where all directions in output set lead to valid
    /// [`Self::neighbor()`] positions.
    ///
    /// If input coordinate `(x, y)` is off board position, returns `None`.
    pub fn neighbor_directions(
        &self, x: usize, y: usize, width: usize, height: usize,
    ) -> Option<DirectionsSet> {
        (x < width && y < height).then(|| {
            DirectionsSet::from_iter(
                self.known_directions()
                    .iter()
                    .filter_map(|d| self.neighbor(x, y, *d, width, height).map(|_| *d)),
            )
        })
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Board size used by all dispatch tests.
    ///
    /// Chosen so that positions `(2, 2)` and `(3, 2)` have every one of their neighbors on-board in
    /// every tessellation, which keeps `None` in the expectations below meaning "this direction is
    /// not legal here" rather than "we walked off the edge".
    const WIDTH: usize = 5;
    const HEIGHT: usize = 5;

    /// `(x, y, tile shape, neighbor)` in each of [`Direction::ALL`]
    type PositionExpectation =
        (usize, usize, TileShape, [Option<(usize, usize)>; Direction::COUNT]);

    /// Hand-computed expectations, one row per position, derived from the coordinate systems
    /// documented on the [`Tessellation`] variants rather than from the implementation modules.
    ///
    /// Every row covers all eight directions, so directions a tessellation does not support are
    /// pinned as `None` and cannot silently start working.
    #[rustfmt::skip]
    const EXPECTATIONS: [(Tessellation, [PositionExpectation; 2]); 4] = [
        //                                   Up            NorthEast     Right         SouthEast     Down          SouthWest     Left          NorthWest
        (Tessellation::Sokoban, [
            (2, 2, TileShape::Square,       [Some((2, 1)), None,         Some((3, 2)), None,         Some((2, 3)), None,         Some((1, 2)), None]),
            (3, 2, TileShape::Square,       [Some((3, 1)), None,         Some((4, 2)), None,         Some((3, 3)), None,         Some((2, 2)), None]),
        ]),
        (Tessellation::Hexoban, [
            (2, 2, TileShape::Hexagon,      [None,         Some((2, 1)), Some((3, 2)), Some((2, 3)), None,         Some((1, 3)), Some((1, 2)), Some((1, 1))]),
            (3, 2, TileShape::Hexagon,      [None,         Some((3, 1)), Some((4, 2)), Some((3, 3)), None,         Some((2, 3)), Some((2, 2)), Some((2, 1))]),
        ]),
        (Tessellation::Trioban, [
            (2, 2, TileShape::TriangleDown, [None,         Some((2, 1)), Some((3, 2)), Some((3, 2)), None,         Some((1, 2)), Some((1, 2)), Some((2, 1))]),
            (3, 2, TileShape::TriangleUp,   [None,         Some((4, 2)), Some((4, 2)), Some((3, 3)), None,         Some((3, 3)), Some((2, 2)), Some((2, 2))]),
        ]),
        (Tessellation::Octoban, [
            (2, 2, TileShape::Octagon,      [Some((2, 1)), Some((3, 1)), Some((3, 2)), Some((3, 3)), Some((2, 3)), Some((1, 3)), Some((1, 2)), Some((1, 1))]),
            (3, 2, TileShape::Square,       [Some((3, 1)), None,         Some((4, 2)), None,         Some((3, 3)), None,         Some((2, 2)), None]),
        ]),
    ];

    /// The four `match self` blocks in [`Tessellation`] are the only place a variant is bound to
    /// its implementation module, and every arm has the same shape — mixing two of them up
    /// compiles cleanly and is invisible on a read-through. This pins each variant to
    /// hand-computed behavior that no two tessellations share.
    #[test]
    fn it_dispatches_to_the_behavior_of_its_own_tessellation() {
        for (tessellation, positions) in EXPECTATIONS {
            for (x, y, tile_shape, neighbors) in positions {
                assert_eq!(
                    tessellation.tile_shape_from_pos(x, y),
                    tile_shape,
                    "{tessellation:?} tile shape at ({x}, {y})"
                );

                for (direction, expected) in Direction::ALL.into_iter().zip(neighbors) {
                    assert_eq!(
                        tessellation.neighbor(x, y, direction, WIDTH, HEIGHT),
                        expected,
                        "{tessellation:?} neighbor of ({x}, {y}) to {direction}"
                    );
                }
            }
        }
    }

    #[test]
    fn it_dispatches_transform_geometry_to_its_own_tessellation() {
        #[rustfmt::skip]
        let expectations = [
            (Tessellation::Sokoban, 90, Size2D::new(1, 1), true,  [(2, -1), (-2, 1), (-1, 2), (1, -2)]),
            (Tessellation::Hexoban, 60, Size2D::new(1, 2), false, [(2, -1), (-3, 1), (0, 3),  (2, -2)]),
            (Tessellation::Trioban, 60, Size2D::new(2, 2), true,  [(2, -2), (-4, 1), (-2, 2), (3, -1)]),
            (Tessellation::Octoban, 90, Size2D::new(2, 2), true,  [(2, -1), (-2, 1), (-1, 2), (1, -2)]),
        ];
        let transforms = [
            BoardTransform::MirrorHorizontal,
            BoardTransform::MirrorVertical,
            BoardTransform::RotateClockwise,
            BoardTransform::RotateCounterClockwise,
        ];

        for (tessellation, degrees, period, diagonal_is_rigid, transformed) in expectations {
            assert_eq!(tessellation.rotation_step_degrees(), degrees);
            assert_eq!(tessellation.translation_period(), period);
            assert_eq!(tessellation.is_rigid_translation(1, 1), diagonal_is_rigid);
            for (transform, expected) in transforms.into_iter().zip(transformed) {
                assert_eq!(tessellation.transformed_raw(transform, 2, 1), expected);
            }
        }
    }

    /// [`Tessellation::neighbor_directions()`] is derived state: a direction belongs in the set
    /// exactly when [`Tessellation::neighbor()`] yields a position for it, so the same
    /// hand-computed rows pin it too.
    ///
    /// This says little about [`Tessellation::known_directions()`] on its own. A *shorter* list
    /// than the tessellation needs does show up here, as directions missing from the set. A
    /// longer one does not — the surplus directions are filtered out by
    /// [`Tessellation::neighbor()`] anyway.
    /// [`Self::it_agrees_with_its_implementation_module_over_the_whole_board`] is what checks the
    /// list itself.
    #[test]
    fn its_neighbor_directions_are_the_directions_that_have_a_neighbor() {
        for (tessellation, positions) in EXPECTATIONS {
            for (x, y, _, neighbors) in positions {
                let expected = DirectionsSet::from_iter(
                    Direction::ALL
                        .into_iter()
                        .zip(neighbors)
                        .filter_map(|(direction, neighbor)| neighbor.map(|_| direction)),
                );

                assert_eq!(
                    tessellation.neighbor_directions(x, y, WIDTH, HEIGHT),
                    Some(expected),
                    "{tessellation:?} neighbor directions at ({x}, {y})"
                );
            }
        }
    }

    type TileShapeFn = fn(usize, usize) -> TileShape;
    type NeighborFn =
        fn(usize, usize, Direction, usize, usize) -> Result<(usize, usize), TessellationError>;

    /// The implementation module a [`Tessellation`] variant is supposed to dispatch to.
    struct Module {
        tessellation:        Tessellation,
        known_directions:    &'static [Direction],
        tile_shapes:         &'static [TileShape],
        tile_shape_from_pos: TileShapeFn,
        neighbor_checked:    NeighborFn,
    }

    /// Broader than the hand-computed rows above: sweeps the whole board and asserts that each
    /// variant agrees with its module everywhere, not just at the two anchor positions. Also the
    /// only coverage of [`Tessellation::known_directions()`] and [`Tessellation::tile_shapes()`].
    ///
    /// On its own this table could be miswired the same way the dispatch is; it is
    /// [`Self::it_dispatches_to_the_behavior_of_its_own_tessellation`] that anchors which module
    /// belongs to which variant.
    #[test]
    fn it_agrees_with_its_implementation_module_over_the_whole_board() {
        let modules: [Module; 4] = [
            Module {
                tessellation:        Tessellation::Sokoban,
                known_directions:    &sokoban::KNOWN_DIRECTIONS,
                tile_shapes:         &sokoban::TILE_SHAPES,
                tile_shape_from_pos: |_x, _y| sokoban::tile_shape_from_pos(),
                neighbor_checked:    sokoban::neighbor_checked,
            },
            Module {
                tessellation:        Tessellation::Hexoban,
                known_directions:    &hexoban::KNOWN_DIRECTIONS,
                tile_shapes:         &hexoban::TILE_SHAPES,
                tile_shape_from_pos: |_x, _y| hexoban::tile_shape_from_pos(),
                neighbor_checked:    hexoban::neighbor_checked,
            },
            Module {
                tessellation:        Tessellation::Trioban,
                known_directions:    &trioban::KNOWN_DIRECTIONS,
                tile_shapes:         &trioban::TILE_SHAPES,
                tile_shape_from_pos: trioban::tile_shape_from_pos,
                neighbor_checked:    trioban::neighbor_checked,
            },
            Module {
                tessellation:        Tessellation::Octoban,
                known_directions:    &octoban::KNOWN_DIRECTIONS,
                tile_shapes:         &octoban::TILE_SHAPES,
                tile_shape_from_pos: octoban::tile_shape_from_pos,
                neighbor_checked:    octoban::neighbor_checked,
            },
        ];

        for module in modules {
            let tessellation = module.tessellation;

            assert_eq!(
                tessellation.known_directions(),
                module.known_directions,
                "{tessellation:?}"
            );
            assert_eq!(tessellation.tile_shapes(), module.tile_shapes, "{tessellation:?}");

            for y in 0..HEIGHT {
                for x in 0..WIDTH {
                    assert_eq!(
                        tessellation.tile_shape_from_pos(x, y),
                        (module.tile_shape_from_pos)(x, y),
                        "{tessellation:?} tile shape at ({x}, {y})"
                    );

                    for direction in Direction::ALL {
                        assert_eq!(
                            tessellation.neighbor(x, y, direction, WIDTH, HEIGHT),
                            (module.neighbor_checked)(x, y, direction, WIDTH, HEIGHT).ok(),
                            "{tessellation:?} neighbor of ({x}, {y}) to {direction}"
                        );
                    }
                }
            }
        }
    }

    /// Load-bearing for any game engine using our [`Tessellation`] and [`Direction`]
    /// implementations.
    ///
    /// For example, inverting a reverse mode game's steps flips every direction with
    /// [`Direction::opposite()`]. That is sound only if stepping back that way lands exactly where
    /// the step came from. Breaking this test silently breaks any engine that depends on that
    /// guarantee.
    ///
    /// Nothing in the geometry modules enforces it. Each tessellation writes its own delta per
    /// direction, Hexoban's depend on row parity and Trioban's on tile shape, and Trioban's six
    /// direction names alias onto three real neighbors per triangle - so the property is pinned
    /// here rather than assumed.
    #[test]
    fn opposite_is_the_geometric_inverse_of_neighbor() {
        for (tessellation, _) in EXPECTATIONS {
            for y in 0..HEIGHT {
                for x in 0..WIDTH {
                    // Illegal directions yield `None` and are skipped, so this covers every
                    // position/direction pair the tessellation actually admits.
                    for direction in Direction::ALL {
                        let Some((neighbor_x, neighbor_y)) =
                            tessellation.neighbor(x, y, direction, WIDTH, HEIGHT)
                        else {
                            continue;
                        };

                        assert_eq!(
                            tessellation.neighbor(
                                neighbor_x,
                                neighbor_y,
                                direction.opposite(),
                                WIDTH,
                                HEIGHT
                            ),
                            Some((x, y)),
                            "{tessellation:?}: ({x}, {y}) to {direction} lands on \
                            ({neighbor_x}, {neighbor_y}), which does not step back to it"
                        );
                    }
                }
            }
        }
    }

    /// The other half of what inverting a step sequence needs: a flipped direction has to be one
    /// the tessellation still accepts, or
    /// [`SavedGame::from_steps()`](crate::SavedGame::from_steps()) would reject the converted
    /// game.
    #[test]
    fn known_directions_are_closed_under_opposite() {
        for (tessellation, _) in EXPECTATIONS {
            for direction in tessellation.known_directions() {
                assert!(
                    tessellation
                        .known_directions()
                        .contains(&direction.opposite()),
                    "{:?} knows {} but not its opposite {}",
                    tessellation,
                    direction,
                    direction.opposite()
                );
            }
        }
    }

    #[test]
    fn it_has_no_neighbor_directions_off_board() {
        for (tessellation, _) in EXPECTATIONS {
            assert!(
                tessellation
                    .neighbor_directions(WIDTH, 0, WIDTH, HEIGHT)
                    .is_none()
            );
            assert!(
                tessellation
                    .neighbor_directions(0, HEIGHT, WIDTH, HEIGHT)
                    .is_none()
            );

            for direction in Direction::ALL {
                assert!(
                    tessellation
                        .neighbor(WIDTH, 0, direction, WIDTH, HEIGHT)
                        .is_none()
                );
                assert!(
                    tessellation
                        .neighbor(0, HEIGHT, direction, WIDTH, HEIGHT)
                        .is_none()
                );
            }
        }
    }
}