sokoban_elements/game_board/

transform.rs

//! Rigid transformations of board coordinates.
//!
//! Raw tessellation maps may produce negative coordinates. Re-anchoring starts with the tight
//! bounding box, then considers adding zero or one column and row. Of the anchors that are rigid
//! translations, this module chooses the smallest resulting area, with candidate order as the
//! deterministic tie-breaker.
//!
//! Hexoban could sometimes save a padding column by reindexing odd and even rows independently.
//! The shared engine deliberately uses integer translations only; the simpler rule is sufficient
//! for every transform and keeps anchoring uniform across tessellations.
//!
//! See also: `board-geometry-and-transformations.md` in `doc/dev-notes/`.

use super::parser::{ParsedBoard, assert_width_normalized};
use crate::{Tessellation, TileKind};

/// Axis reflected across by [`GameBoard::mirror()`](crate::GameBoard::mirror).
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum MirrorAxis {
    /// Reflect across a horizontal axis, exchanging the top and bottom edges.
    Horizontal,

    /// Reflect across a vertical axis, exchanging the left and right edges.
    Vertical,
}

/// Direction of one tessellation-specific [`GameBoard::rotate()`](crate::GameBoard::rotate) step.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum Rotation {
    Clockwise,
    CounterClockwise,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub(crate) enum BoardTransform {
    MirrorHorizontal,
    MirrorVertical,
    RotateClockwise,
    RotateCounterClockwise,
}

fn to_i64(value: usize) -> i64 {
    // Boards are orders of magnitude smaller than this bound; saturation is unreachable.
    i64::try_from(value).unwrap_or(i64::MAX)
}

fn to_usize(value: i64) -> usize {
    // Anchoring makes every coordinate non-negative and real boards fit comfortably in `usize`.
    usize::try_from(value).unwrap_or(0)
}

fn raw_bounds(
    body: &ParsedBoard, tessellation: Tessellation, transform: BoardTransform,
) -> (i64, i64, i64, i64) {
    let mut min_x = i64::MAX;
    let mut min_y = i64::MAX;
    let mut max_x = i64::MIN;
    let mut max_y = i64::MIN;

    for (y, row) in body.iter().enumerate() {
        for x in 0..row.len() {
            let (mapped_x, mapped_y) =
                tessellation.transformed_raw(transform, to_i64(x), to_i64(y));
            min_x = min_x.min(mapped_x);
            min_y = min_y.min(mapped_y);
            max_x = max_x.max(mapped_x);
            max_y = max_y.max(mapped_y);
        }
    }

    (min_x, min_y, max_x, max_y)
}

fn anchored_size(max_x: i64, max_y: i64, dx: i64, dy: i64) -> (usize, usize) {
    (to_usize(max_x + dx + 1), to_usize(max_y + dy + 1))
}

fn best_anchor(
    tessellation: Tessellation, min_x: i64, min_y: i64, max_x: i64, max_y: i64,
) -> (i64, i64, usize, usize) {
    let tight_dx = -min_x;
    let tight_dy = -min_y;
    let mut best: Option<(i64, i64, usize, usize, usize)> = None;

    for (extra_x, extra_y) in [(0_i64, 0_i64), (1, 0), (0, 1), (1, 1)] {
        let dx = tight_dx + extra_x;
        let dy = tight_dy + extra_y;
        if !tessellation.is_rigid_translation(dx, dy) {
            continue;
        }

        let (width, height) = anchored_size(max_x, max_y, dx, dy);
        let area = width.saturating_mul(height);
        if best.is_none_or(|(_, _, _, _, best_area)| area < best_area) {
            best = Some((dx, dy, width, height, area));
        }
    }

    // Every supported translation lattice has period at most two on each axis, so one of the
    // four candidates above is always rigid.
    best.map_or((tight_dx, tight_dy, 0, 0), |(dx, dy, width, height, _)| {
        (dx, dy, width, height)
    })
}

pub(super) fn transformed(
    body: &ParsedBoard, tessellation: Tessellation, transform: BoardTransform,
) -> ParsedBoard {
    assert_width_normalized(body);
    if body.is_empty() {
        return ParsedBoard::new();
    }

    let (min_x, min_y, max_x, max_y) = raw_bounds(body, tessellation, transform);
    let (dx, dy, width, height) = best_anchor(tessellation, min_x, min_y, max_x, max_y);
    let mut transformed = vec![vec![TileKind::Floor; width]; height];

    for (y, row) in body.iter().enumerate() {
        for (x, tile) in row.iter().enumerate() {
            let (mapped_x, mapped_y) =
                tessellation.transformed_raw(transform, to_i64(x), to_i64(y));
            transformed[to_usize(mapped_y + dy)][to_usize(mapped_x + dx)] = *tile;
        }
    }

    transformed
}

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

    use super::*;

    const TESSELLATIONS: [Tessellation; 4] = [
        Tessellation::Sokoban,
        Tessellation::Hexoban,
        Tessellation::Trioban,
        Tessellation::Octoban,
    ];
    const TRANSFORMS: [BoardTransform; 4] = [
        BoardTransform::MirrorHorizontal,
        BoardTransform::MirrorVertical,
        BoardTransform::RotateClockwise,
        BoardTransform::RotateCounterClockwise,
    ];
    const SIZES: [(usize, usize); 6] = [(4, 4), (4, 5), (5, 4), (5, 5), (7, 3), (1, 5)];

    type Position = (usize, usize);
    type PositionMap = HashMap<Position, Position>;

    fn mapping(
        tessellation: Tessellation, transform: BoardTransform, width: usize, height: usize,
    ) -> (Position, PositionMap) {
        let body = vec![vec![TileKind::Floor; width]; height];
        let (min_x, min_y, max_x, max_y) = raw_bounds(&body, tessellation, transform);
        let (dx, dy, transformed_width, transformed_height) =
            best_anchor(tessellation, min_x, min_y, max_x, max_y);
        let positions = (0..height)
            .flat_map(|y| {
                (0..width).map(move |x| {
                    let (mapped_x, mapped_y) =
                        tessellation.transformed_raw(transform, to_i64(x), to_i64(y));
                    ((x, y), (to_usize(mapped_x + dx), to_usize(mapped_y + dy)))
                })
            })
            .collect();
        ((transformed_width, transformed_height), positions)
    }

    fn neighbors(
        tessellation: Tessellation, position: (usize, usize), width: usize, height: usize,
    ) -> HashSet<(usize, usize)> {
        tessellation
            .known_directions()
            .iter()
            .filter_map(|direction| {
                tessellation.neighbor(position.0, position.1, *direction, width, height)
            })
            .collect()
    }

    /// The re-anchoring rule of section 5 of
    /// `doc/dev-notes/board-geometry-and-transformations.md`, which that document calls "the only
    /// free choice in the whole design" - and which nothing pinned until now.
    ///
    /// Expected sizes are computed from the section 4 maps plus the documented rule (smallest area
    /// over the four candidate offsets, first found wins), cross-checked against an independent
    /// implementation. Deliberately *not* taken from the probe run recorded in section 11: that
    /// probe takes the first valid candidate rather than the smallest-area one, so its figures are
    /// not the engine's.
    mod test_anchoring {
        use super::*;

        /// A source size and the size it anchors to under each of `TRANSFORMS`, in that order.
        type SizeExpectation = (Tessellation, Position, [Position; 4]);

        #[rustfmt::skip]
        #[test]
        fn it_anchors_to_the_smallest_area() {
            // (tessellation, source, [MirrorH, MirrorV, RotateCW, RotateCCW])
            let expectations: [SizeExpectation; 8] = [
                (Tessellation::Sokoban, (5, 4), [(5, 4), (5, 4), (4, 5), (4, 5)]),
                (Tessellation::Sokoban, (4, 3), [(4, 3), (4, 3), (3, 4), (3, 4)]),
                (Tessellation::Hexoban, (4, 4), [(4, 5), (5, 4), (4, 6), (5, 6)]),
                (Tessellation::Hexoban, (4, 3), [(4, 3), (5, 3), (4, 5), (4, 6)]),
                (Tessellation::Trioban, (4, 4), [(4, 4), (5, 4), (7, 4), (7, 4)]),
                (Tessellation::Trioban, (5, 5), [(6, 5), (5, 5), (10, 5), (10, 5)]),
                (Tessellation::Octoban, (5, 4), [(6, 4), (5, 4), (4, 6), (4, 5)]),
                (Tessellation::Octoban, (4, 3), [(4, 3), (5, 3), (3, 4), (3, 5)]),
            ];

            for (tessellation, (width, height), wanted) in expectations {
                for (transform, want) in TRANSFORMS.iter().zip(wanted) {
                    let (size, _) = mapping(tessellation, *transform, width, height);
                    assert_eq!(
                        size, want,
                        "{tessellation:?} {width}x{height} under {transform:?}"
                    );
                }
            }
        }

        /// When the column-adding and row-adding candidates have *exactly* the same area, the
        /// column wins - decided only by the candidate order `[(0,0), (1,0), (0,1), (1,1)]` and by
        /// the comparison being strictly `<`. Relaxing either flips precisely these cases and
        /// nothing else in the suite notices.
        #[test]
        fn it_breaks_an_exact_area_tie_by_adding_a_column() {
            let ties = [
                (
                    Tessellation::Octoban,
                    (2, 2),
                    BoardTransform::MirrorHorizontal,
                    (3, 2),
                ),
                (Tessellation::Octoban, (2, 2), BoardTransform::RotateClockwise, (3, 2)),
                (
                    Tessellation::Octoban,
                    (4, 4),
                    BoardTransform::MirrorHorizontal,
                    (5, 4),
                ),
                (
                    Tessellation::Trioban,
                    (3, 3),
                    BoardTransform::MirrorHorizontal,
                    (4, 3),
                ),
                (
                    Tessellation::Trioban,
                    (5, 5),
                    BoardTransform::MirrorHorizontal,
                    (6, 5),
                ),
                (Tessellation::Trioban, (4, 4), BoardTransform::MirrorVertical, (5, 4)),
            ];

            for (tessellation, (width, height), transform, wanted) in ties {
                let (size, _) = mapping(tessellation, transform, width, height);
                assert_eq!(size, wanted, "{tessellation:?} {width}x{height} under {transform:?}");

                // The row-adding alternative really is available and really does tie, so the
                // choice above is the tie-break and not just the smaller option.
                let body = vec![vec![TileKind::Floor; width]; height];
                let (min_x, min_y, max_x, max_y) = raw_bounds(&body, tessellation, transform);
                let column = anchored_size(max_x, max_y, -min_x + 1, -min_y);
                let row = anchored_size(max_x, max_y, -min_x, -min_y + 1);

                assert!(tessellation.is_rigid_translation(-min_x + 1, -min_y));
                assert!(tessellation.is_rigid_translation(-min_x, -min_y + 1));
                assert_eq!(column, wanted);
                assert_eq!(
                    column.0 * column.1,
                    row.0 * row.1,
                    "{tessellation:?} {width}x{height} {transform:?}: {column:?} vs {row:?} \
                     should tie on area"
                );
            }
        }

        /// A transform may leave destination cells with no source cell mapping onto them. Section 5
        /// says this "is not a bug" - the anchored bounding box is what the tiling admits, not a
        /// tight fit - so pin it rather than leave it to be "fixed" later.
        #[test]
        fn it_leaves_padding_cells_with_no_preimage() {
            let expectations = [
                // A whole column, because Trioban's horizontal mirror shifts every row.
                (
                    Tessellation::Trioban,
                    (4, 3),
                    BoardTransform::MirrorHorizontal,
                    vec![(0, 0), (0, 1), (0, 2)],
                ),
                // Hexoban's row parities mirror to different columns, so the holes alternate
                // between the two edges. Listed row-major, as the scan below yields them.
                (
                    Tessellation::Hexoban,
                    (4, 3),
                    BoardTransform::MirrorVertical,
                    vec![(0, 0), (4, 1), (0, 2)],
                ),
            ];

            for (tessellation, (width, height), transform, wanted) in expectations {
                let ((transformed_width, transformed_height), positions) =
                    mapping(tessellation, transform, width, height);
                let covered: HashSet<Position> = positions.values().copied().collect();

                let holes: Vec<Position> = (0..transformed_height)
                    .flat_map(|y| (0..transformed_width).map(move |x| (x, y)))
                    .filter(|position| !covered.contains(position))
                    .collect();

                assert_eq!(holes, wanted, "{tessellation:?} {width}x{height} under {transform:?}");
            }
        }
    }

    #[test]
    fn every_transform_is_injective_and_preserves_adjacency() {
        for tessellation in TESSELLATIONS {
            for (width, height) in SIZES {
                for transform in TRANSFORMS {
                    let ((new_width, new_height), positions) =
                        mapping(tessellation, transform, width, height);
                    let image: HashSet<_> = positions.values().copied().collect();
                    assert_eq!(
                        image.len(),
                        width * height,
                        "{tessellation:?} {width}x{height} {transform:?} is not injective"
                    );

                    for (source, destination) in &positions {
                        let mapped_neighbors: HashSet<_> =
                            neighbors(tessellation, *source, width, height)
                                .iter()
                                .map(|neighbor| positions[neighbor])
                                .collect();
                        let destination_neighbors: HashSet<_> =
                            neighbors(tessellation, *destination, new_width, new_height)
                                .intersection(&image)
                                .copied()
                                .collect();

                        assert_eq!(
                            mapped_neighbors, destination_neighbors,
                            "{tessellation:?} {width}x{height} {transform:?}: {source:?} -> \
                             {destination:?}"
                        );
                    }
                }
            }
        }
    }

    #[test]
    fn every_transform_preserves_the_multiset_of_non_floor_tiles() {
        const MARKERS: [TileKind; 6] = [
            TileKind::Wall,
            TileKind::Pusher,
            TileKind::Box,
            TileKind::Goal,
            TileKind::BoxOnGoal,
            TileKind::PusherOnGoal,
        ];

        for tessellation in TESSELLATIONS {
            for (width, height) in SIZES {
                let body: ParsedBoard = (0..height)
                    .map(|y| {
                        (0..width)
                            .map(|x| MARKERS[(y * width + x) % MARKERS.len()])
                            .collect()
                    })
                    .collect();
                for transform in TRANSFORMS {
                    let result = transformed(&body, tessellation, transform);
                    let actual = MARKERS.map(|marker| {
                        result
                            .iter()
                            .flatten()
                            .filter(|&&tile| tile == marker)
                            .count()
                    });
                    let expected = MARKERS.map(|marker| {
                        body.iter()
                            .flatten()
                            .filter(|&&tile| tile == marker)
                            .count()
                    });
                    assert_eq!(actual, expected, "{tessellation:?} {width}x{height} {transform:?}");
                }
            }
        }
    }

    #[test]
    fn empty_boards_are_unchanged_by_every_transform() {
        for tessellation in TESSELLATIONS {
            for transform in TRANSFORMS {
                assert!(transformed(&ParsedBoard::new(), tessellation, transform).is_empty());
            }
        }
    }
}