Struct GameBoard 

pub struct GameBoard { /* private fields */ }

Parsed game board for some Tessellation.

Encapsulates game board as 2D matrix of TileKind.

• coordinate system origin (0, 0) is at the top left of board
• X axis points from left to right
• Y axis points from top to down

GameBoard is end result of parsing and editing game puzzles. As such it is not optimized data structure playing the game, implementing game engines or game solvers. GameBoard is meant to be used only as input for these uses and will have to be converted into more suitable data structure.

GameBoard doesn’t place any restrictions on it’s width, height or on number of pushers, boxes and goals. When implementing game engines or game solvers, you’ll want to validate parsed GameBoard against concrete engine or solver requirements.

BoxID, GoalID, PusherID and PlusID ** do restrict** numeric IDs that they can represent. Having GameBoard with more pushers, boxes or goals than these can represent is possible, but you will not be able to represent ids of it’s pieces. Again and by design, there is no mechanism in GameBoard to prevent this situation.

GameBoard supports Index and IndexMut for (x, y), Point2D and linear usize.

GameBoard supports iter() yielding row-major ((x, y), TileKind) pairs.

Depending on Tessellation, a board position has related TileShape that can be calculated via Tessellation::tile_shape_from_pos(x, y) or via Point2D::tile_shape(tessellation)

Examples

use sokoban_elements::*;

let board_text = [
    "    #####",
    "    #   #",
    "    #$  #",
    "  ###  $##",
    "  #  $ $ #",
    "### # ## #   ######",
    "#   # ## #####  ..#",
    "# $  $          ..#",
    "##### ### #@##  ..#",
    "    #     #########",
    "    #######",
]
.join("\n");

let mut board = GameBoard::parsed(&board_text, Tessellation::Sokoban)?;

assert_eq!(board.width(), 19);
assert_eq!(board.height(), 11);

// tiles are read by (x, y)...
assert_eq!(board[(4, 0)], TileKind::Wall);

// ... or by linear board position: y * width + x
let position: usize = 4;
assert_eq!(board[position], TileKind::Wall);

// short rows are padded with floor tiles
assert_eq!(board[(18, 0)], TileKind::Floor);

// tiles are writable
board[(4, 0)] = TileKind::Floor;
assert_eq!(board[(4, 0)], TileKind::Floor);

// iteration is row major over ((x, y), tile) pairs
assert_eq!(board.iter().count(), board.width() * board.height());
assert_eq!(board.iter().next(), Some(((0, 0), TileKind::Floor)));

Board size

Board data is always width-normalized: all rows have exactly width() tiles. Rows shorter than board width are padded with TileKind::Floor. Parsing, resizing, rotation and mirroring ensure that this always holds. Index<(usize, usize)> and Index<Point2D> would’ve panicked for perfectly valid board coordinates, if the rows were ragged. Index<usize> wouldn’t even panic - in case of ragged rows it would silently return wrong board tile.

A board with no columns and or no rows is empty: width() is zero if and only if height() is zero. Constructing or editing a board in a way that would leave it with rows of zero length silently produces the empty board instead. There is no error for this.

These rules is what makes indexing board position well defined.

Resizing edits one edge at a time, so callers control operation order. Additions to a non-empty board apply count exactly, and methods return how many lines were applied.

Removals saturate. remove_rows(Top, 42) on a 11-row board removes 11, it is not an error. In that case we’d removed all the rows from the board, so there are no columns left either.

The result of chaining board edge edits depends on order of calls. Any individual step may collapse the board to size zero (because removals saturate).

Once edge editing empties a board, the one-edge-at-a-time methods cannot grow it back: there are no rows to add columns to, and rows added to a board with no columns are of zero length, which is the empty board again. Use grow() for that.

Top and Left resizing shifts existing content. To compensate what would otherwise be a break in tile geometry, GameBoard adds or removes one padding line in perpendicular axis. This means that Top and Left resizing may have side effect of changing both board dimensions. This depends on concrete Tessellation:

• add_rows(Top, 1) on a Trioban or Octoban board also adds a left column; add_columns(Left,1) also adds a top row.
• Hexoban needs it on odd Top counts when the retained board spans both row parities. Even counts need nothing

Bottom and Right resizing never adds perpendicular padding.

Each resizing count is one batched shift. Adding two Top rows to Trioban adds no padding, while two separate one-row calls each add a column.

If you need to tighten the resulting board after this padding, call trim() explicitly.

Transformations

rotate() applies one tessellation-specific step; see Tessellation::rotation_step_degrees(). A transform may add one row or column because its result must be re-anchored with a rigid motion of the tiling; integer translation periods are exposed by Tessellation::translation_period(). A full turn likewise takes four steps for Sokoban and Octoban, and six for Hexoban and Trioban. Rotation keeps its complete bounding box; call trim() separately when a tight board is wanted.

Mirroring twice restores the original content, but may retain padding added by re-anchoring.

Normalization and enclosing

grow() and enclose() are the two resizing methods that are not per-edge, because neither takes an edge to work on: grow() is told a size, and enclose() derives the edges it must grow from where the play area reaches.

enclose() walls the play area in, so it is the operation that makes a board “closed”.

normalize() does not produce a closed board. A play area that reaches the board edge is confined by the edge, not by a wall, and no wall is invented for it.

Edits invalidate emergent types and properties

Editing, resizing, mirroring and rotation invalidates everything keyed to position:

• BoxID, GoalID, and PusherID are reassigned by scanning the edited board in row-major order
• SokobanPlus is keyed to those IDs and is silently invalidated.
• SavedGame moves are directional and no longer describe the transformed board. In particular, Trioban direction changes depend on each triangle’s orientation and cannot be repaired by substituting direction characters.
• Zobrist hashes of boards (game engine feature) are position-keyed and do not survive editing.

Invalidation is natural consequences of how all of above types are defined: they need a stable board configuration to make any sense. Important thing to have in mind when editing the board: finish the design before assigning ie. Sokoban+ to it.

Serde

With the serde feature, GameBoard is a two field map of the printed board and the Tessellation needed to parse it back:

{ "tessellation": "Sokoban", "board": "#####\n#@$.#\n#####" }

Deserialization goes through parsed(), so a document can never produce a board that violates the width-normalization invariant. Unknown fields are rejected. The board text is accepted in any form parsed() accepts, run-length encoding included, but is always written out uncompressed with visible floors.

use sokoban_elements::*;

#[rustfmt::skip]
let board_text = [
    "#####",
    "#@$.#",
    "#####",
]
.join("\n");

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

let json = serde_json::to_string(&board)?;
assert_eq!(serde_json::from_str::<GameBoard>(&json)?, board);

Implementations

impl GameBoard

pub fn new(width: usize, height: usize, tessellation: Tessellation) -> Self

Constructs blank board of given size, all of it’s tiles being TileKind::Floor.

A board with no columns is the empty board: if either width or height is zero, both width() and height() of constructed board are zero.

Examples

use sokoban_elements::*;

let board = GameBoard::new(0, 5, Tessellation::Sokoban);

assert_eq!(board.width(), 0);
assert_eq!(board.height(), 0);

pub fn tessellation(&self) -> Tessellation

pub fn parsed( printed_board: &str, tessellation: Tessellation, ) -> Result<Self, BoardSyntaxError>

Parses board string in context of given Tessellation.

Examples

Constructing GameBoard from text:

use sokoban_elements::*;

let board_text = [
    "    #####",
    "    #   #",
    "    #$  #",
    "  ###  $##",
    "  #  $ $ #",
    "### # ## #   ######",
    "#   # ## #####  ..#",
    "# $  $          ..#",
    "##### ### #@##  ..#",
    "    #     #########",
    "    #######",
]
.join("\n");

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

Grammar

Game board strings use following characters:

tile	char
Wall	‘#’
Pusher	‘p’, ‘@’, ‘m’
Pusher on goal	‘P’, ‘+’, ‘M’
Box	‘b’, ‘$’
Goal	‘.’ , ‘o’
Floor	’ ’, ‘-’, ‘_’

Game board strings mostly follow SokobanYASC specification:

::::::::::::::::::::::::::: Board ::::::::::::::::::::::::::
::                                                        ::
:: Remarks:                                               ::
::                                                        ::
::   The first and the last non-empty square in each row  ::
::   must be a wall or a box on a goal. An empty interior ::
::   row is written with at least one "-" or "_".         ::
::                                                        ::
::   Boards may be run-length encoded (RLE), e.g.,        ::
::   "###----p.#" may be encoded as "3#4-p.#", and        ::
::   "#-#-#-##-#-#-#" may be encoded as "2(3(#-)#)".      ::
::   A row cannot be split over multiple lines.           ::
::                                                        ::
::   Rows may be combined on a single line by using "|"   ::
::   as a row separator, e.g., "--3#|3#-#|#pb.#|5#".      ::
::   A "|" at the end of a line is optional and may be    ::
::   omitted.                                             ::

• RLE grammar

pub fn parsed_from_tiles( data: &[TileKind], width: usize, height: usize, tessellation: Tessellation, ) -> Result<Self, BoardSyntaxError>

Constructs board from row major slice of TileKind.

A board with no columns is the empty board: if either width or height is zero, data must be empty and constructed board is the empty board.

Errors

InputSizeNotMatchedByDeclaredSize when length of data is not exactly width * height. Sizes too large to be represented are reported the same way.

pub fn printed(&self, visible_floor: bool) -> String

pub fn width(&self) -> usize

Number of board columns.

Returns 0 for empty board. Board width and height() are either both zero or both greater than zero.

pub fn height(&self) -> usize

Number of board rows.

Returns 0 for empty board. Board height and width() are either both zero or both greater than zero.

pub fn size(&self) -> Size2D

pub fn pushers_count(&self) -> usize

pub fn boxes_count(&self) -> usize

pub fn goals_count(&self) -> usize

pub fn is_blank(&self) -> bool

pub fn pushers(&self) -> Result<Vec<Pusher>, BoardSyntaxError>

All Pusher pieces on this board, in row major order.

PusherID of each piece is assigned by scanning board top to bottom and each row left to right, starting from 0. See PusherID docs.

Tile with pusher standing on goal (TileKind::PusherOnGoal) yields both a Pusher here and a Goal in goals().

Errors

TooManyPushers when board has more pushers than PusherID can represent.

Examples

use sokoban_elements::*;

#[rustfmt::skip]
let board_text = [
    "#####",
    "#@$.#",
    "#####",
]
.join("\n");

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

let pushers = board.pushers()?;

assert_eq!(pushers.len(), board.pushers_count());
assert_eq!(pushers[0].id, PusherID::from(0_u8));
assert_eq!((pushers[0].x, pushers[0].y), (1, 1));

pub fn boxes( &self, sokoban_plus: Option<&SokobanPlus>, ) -> Result<Vec<Boxbox>, BoardSyntaxError>

All Boxbox pieces on this board, in row major order.

BoxID of each piece is assigned by scanning board top to bottom and each row left to right, starting from 0. See BoxID docs.

Tile with box standing on goal (TileKind::BoxOnGoal) yields both a Boxbox here and a Goal in goals().

Sokoban+ ID of each piece is looked up in sokoban_plus by assigned BoxID. Without sokoban_plus, no box gets Sokoban+ ID. See SokobanPlus.

Errors

TooManyBoxes when board has more boxes than BoxID can represent.

Examples

use sokoban_elements::*;

#[rustfmt::skip]
let board_text = [
    "#####",
    "#@$*#",
    "#####",
]
.join("\n");

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

let boxes = board.boxes(None)?;

assert_eq!(boxes.len(), board.boxes_count());
assert_eq!(boxes[0].id, BoxID::from(0_u8));
assert_eq!((boxes[0].x, boxes[0].y), (2, 1));
assert_eq!(boxes[0].plus_id, None);

// box standing on goal is both a box and a goal
assert_eq!((boxes[1].x, boxes[1].y), (3, 1));
assert_eq!(board.goals(None)?.len(), 1);

Reading Sokoban+ IDs:

use sokoban_elements::*;

#[rustfmt::skip]
let board_text = [
    "#####",
    "#@$*#",
    "#####",
]
.join("\n");

let board = GameBoard::parsed(&board_text, Tessellation::Sokoban)?;
let sokoban_plus = SokobanPlus::parsed("0 42", "42 0")?;

let boxes = board.boxes(Some(&sokoban_plus))?;

assert_eq!(boxes[0].plus_id, None);
assert_eq!(boxes[1].plus_id, Some(PlusID::new(42)?));

pub fn goals( &self, sokoban_plus: Option<&SokobanPlus>, ) -> Result<Vec<Goal>, BoardSyntaxError>

All Goal pieces on this board, in row major order.

GoalID of each piece is assigned by scanning board top to bottom and each row left to right, starting from 0. See GoalID docs.

Tiles with box or pusher standing on goal (TileKind::BoxOnGoal, TileKind::PusherOnGoal) yield a Goal here in addition to the piece standing on it.

Sokoban+ ID of each piece is looked up in sokoban_plus by assigned GoalID. Without sokoban_plus, no goal gets Sokoban+ ID. See SokobanPlus.

Errors

TooManyGoals when board has more goals than GoalID can represent.

Examples

use sokoban_elements::*;

#[rustfmt::skip]
let board_text = [
    "#####",
    "#+$.#",
    "#####",
]
.join("\n");

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

let goals = board.goals(None)?;

assert_eq!(goals.len(), board.goals_count());

// pusher standing on goal is both a pusher and a goal
assert_eq!(goals[0].id, GoalID::from(0_u8));
assert_eq!((goals[0].x, goals[0].y), (1, 1));
assert_eq!((goals[1].x, goals[1].y), (3, 1));

pub fn iter(&self) -> GameBoardIter<'_>

Row major iterator over ((x, y), tile) pairs of this board.

Examples

use sokoban_elements::*;

let board = GameBoard::new(3, 2, Tessellation::Sokoban);

let positions: Vec<(usize, usize)> = board.iter().map(|(position, _)| position).collect();

assert_eq!(positions, vec![(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1)]);

pub fn mirror(&mut self, axis: MirrorAxis)

Mirrors the board across axis as a rigid motion of its tessellation.

MirrorAxis::Horizontal exchanges the top and bottom edges; MirrorAxis::Vertical exchanges the left and right edges. Re-anchoring may add one row or column to keep tile geometry intact.

Examples

use sokoban_elements::*;

let mut board = GameBoard::parsed("@$.", Tessellation::Sokoban)?;
board.mirror(MirrorAxis::Vertical);
assert_eq!(board.printed(false), ".$@");

pub fn rotate(&mut self, rotation: Rotation)

Rotates the board by one natural step of its tessellation.

The step is 90 degrees for Sokoban and Octoban, and 60 degrees for Hexoban and Trioban; see Tessellation::rotation_step_degrees(). Rotation keeps the complete rotated bounding box and does not trim floor-only edges.

Examples

use sokoban_elements::*;

#[rustfmt::skip]
let board_text = [
    "@",
    "$",
    ".",
]
.join("\n");
let mut board = GameBoard::parsed(&board_text, Tessellation::Sokoban)?;
board.rotate(Rotation::Clockwise);
assert_eq!(board.printed(false), ".$@");

pub fn grow(&mut self, width: NonZeroU16, height: NonZeroU16)

Grows the board to at least width columns and height rows, filling with TileKind::Floor.

Each axis is grown independently to the larger of its current and its wanted size, so a board is never shrunk: an axis already at or past its wanted size is left alone, and a call asking for no growth on either axis is a no-op.

Growth is added to the Bottom and Right edges only. Existing tiles therefore keep their (x, y), and no perpendicular padding line is ever added, whatever the Tessellation.

This is also the way back from the empty board, which the one-edge-at-a-time methods cannot grow.

Examples

use std::num::NonZeroU16;

use sokoban_elements::*;

let mut board = GameBoard::new(3, 2, Tessellation::Sokoban);

board.grow(NonZeroU16::try_from(5)?, NonZeroU16::try_from(1)?);

// width grew, height was already past the wanted one and stayed
assert_eq!(board.width(), 5);
assert_eq!(board.height(), 2);

// editing can empty a board, and growing is the way back
board.remove_columns(VerticalEdge::Left, 42);
assert_eq!(board.size(), Size2D::new(0, 0));

board.grow(NonZeroU16::try_from(4)?, NonZeroU16::try_from(3)?);
assert_eq!(board.size(), Size2D::new(4, 3));

pub fn add_rows(&mut self, edge: HorizontalEdge, count: usize) -> usize

Adds count rows of TileKind::Floor to given board edge.

Returns count when the board is non-empty. A Top addition may also add one left padding column to preserve tile geometry.

Does nothing to the empty board: a board with no columns can only grow rows of zero length, and a board with no columns is the empty board. Grow the empty board with grow() instead.

Examples

use sokoban_elements::*;

let mut board = GameBoard::new(3, 2, Tessellation::Sokoban);

board.add_rows(HorizontalEdge::Top, 2);

assert_eq!(board.width(), 3);
assert_eq!(board.height(), 4);

pub fn remove_rows(&mut self, edge: HorizontalEdge, count: usize) -> usize

Removes up to count rows from given board edge and returns the number removed.

Removal saturates at the board height. A Top removal that retains rows may also add one left padding column to preserve tile geometry.

Examples

use sokoban_elements::*;

let mut board = GameBoard::new(3, 2, Tessellation::Sokoban);

board.remove_rows(HorizontalEdge::Bottom, 1);
assert_eq!(board.height(), 1);

// removing more rows than there are empties the board
board.remove_rows(HorizontalEdge::Bottom, 42);
assert_eq!(board.width(), 0);
assert_eq!(board.height(), 0);

pub fn add_columns(&mut self, edge: VerticalEdge, count: usize) -> usize

Adds count columns of TileKind::Floor to given board edge.

Returns count when the board is non-empty. An odd Left addition on Trioban or Octoban also adds one top padding row to preserve tile geometry.

Does nothing to the empty board, which has no rows to add columns to. Grow the empty board with grow() instead.

Examples

use sokoban_elements::*;

let mut board = GameBoard::new(3, 2, Tessellation::Sokoban);

board.add_columns(VerticalEdge::Right, 4);

assert_eq!(board.width(), 7);
assert_eq!(board.height(), 2);

pub fn remove_columns(&mut self, edge: VerticalEdge, count: usize) -> usize

Removes up to count columns from given board edge and returns the number removed.

Removal saturates at the board width. An odd Left removal that retains columns on Trioban or Octoban also adds one top padding row to preserve tile geometry. Removing all columns also removes the rows, because a board with no columns is the empty board.

Examples

use sokoban_elements::*;

let mut board = GameBoard::new(3, 2, Tessellation::Sokoban);

board.remove_columns(VerticalEdge::Left, 1);
assert_eq!(board.width(), 2);

board.remove_columns(VerticalEdge::Left, 2);
assert_eq!(board.width(), 0);
assert_eq!(board.height(), 0);

pub fn trim(&mut self)

Removes “outer” floor-only rows and columns in one geometry-preserving crop.

A tile is retained when it is not empty floor - walls, boxes, goals and pushers all count, so a goal-only or pusher-only edge line survives trimming.

The result is the smallest rigidly anchored rectangle. It may retain one padding row or column when the tight rectangle would change tile geometry.

Trimming leaves the empty board exactly when there is nothing to retain, which is what is_blank() reports.

pub fn enclose(&mut self) -> Result<(), BoardSyntaxError>

Surrounds the play area with walls, growing the board where there is no room for them.

StaticBoardAnalysis::flood_fill() stops at walls and at the board edge, so the play area is always confined by the two together. A board is “closed” exactly when the edge is not doing any of that work, which is what StaticBoardAnalysis::is_playable_area_confined() reports and what this method establishes. There is no need to reconstruct anything inward: every on-board position next to the play area and not in it is already a wall, because that is why the flood stopped there.

One row or column is added to each edge the play area reaches, and then every empty floor tile on the resulting outer edge becomes a Wall. Edges are grown Bottom, Right, Top, Left, because only Top and Left shift content and may add a perpendicular padding line. Those padding lines are floor too, so walling the outer edge afterwards seals them without tracking where they landed.

Nothing is overwritten but floor, so no piece, goal or wall is ever lost. Two consequences:

• Dead floor on an edge that was not grown becomes wall as well. It lies outside the play area, so the puzzle is unchanged, and it only happens on a board that was leaking somewhere - an already closed board is left exactly as it is, which makes this method idempotent.
• The result is not tightened. Follow with trim() or normalize() when a tight board is wanted.

A board with no Pusher has no play area to enclose and is left untouched, as is the empty board.

Examples

use sokoban_elements::*;

// The pusher can walk off the top of this board, so the top is not a wall's job yet.
#[rustfmt::skip]
let board_text = [
    "#-@-#",
    "#####",
]
.join("\n");

let mut board = GameBoard::parsed(&board_text, Tessellation::Sokoban)?;
board.enclose()?;

#[rustfmt::skip]
let enclosed = [
    "#####",
    "#-@-#",
    "#####",
]
.join("\n");

assert_eq!(board.printed(true), enclosed);

// Enclosing an already closed board changes nothing.
board.enclose()?;
assert_eq!(board.printed(true), enclosed);

pub fn normalize(&mut self) -> Result<(), BoardSyntaxError>

All non-playable tiles are replaced by floors and missing walls around play area are reconstructed.

The reconstructed board is cropped once using the same smallest rigid anchor as trim(). The crop is the bounding box of everything this method keeps: the play area plus the reconstructed walls confining it.

This does not make a board closed. A play area that reaches the board edge is confined there by the edge itself rather than by a wall, and those edge tiles are kept as they are - no wall is invented around them. enclose() is the operation that makes room and walls them, and the two compose: board.enclose()?; board.normalize()?;.

A board with no Pusher has no play area to normalize around, and is left untouched.

becomes

Todo

Following is the stuff that SokobanYASC does, see what we can implement too

• fill jagged (i.e., “stair-case” like) wall edges
• remove redundant walls and floors,
• remove unused boxes and goals
• change immovable boxes on non goal squares to walls
• change immovable boxes on goal squares to walls
• fill unnecessary illegal box squares

Trait Implementations

impl Clone for GameBoard

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for GameBoard

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for GameBoard

fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error>

Deserialize this value from the given Serde deserializer.

impl Eq for GameBoard

impl Index<(usize, usize)> for GameBoard

fn index(&self, index: (usize, usize)) -> &Self::Output

index is (x, y)

Panics

Panics if index is outside of board.

type Output = TileKind

The returned type after indexing.

impl Index<Point2D> for GameBoard

fn index(&self, index: Point2D) -> &Self::Output

index is Point2D of the tile.

Panics

Panics if index is outside of board.

type Output = TileKind

The returned type after indexing.

impl Index<usize> for GameBoard

fn index(&self, index: usize) -> &Self::Output

index is linear board position: y * width + x

Panics

Panics if index is outside of board.

type Output = TileKind

The returned type after indexing.

impl IndexMut<(usize, usize)> for GameBoard

fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output

index is (x, y)

Panics

Panics if index is outside of board.

impl IndexMut<Point2D> for GameBoard

fn index_mut(&mut self, index: Point2D) -> &mut Self::Output

index is Point2D of the tile.

Panics

Panics if index is outside of board.

impl IndexMut<usize> for GameBoard

fn index_mut(&mut self, index: usize) -> &mut Self::Output

index is linear board position: y * width + x

Panics

Panics if index is outside of board.

impl<'a> IntoIterator for &'a GameBoard

type IntoIter = GameBoardIter<'a>

Which kind of iterator are we turning this into?

type Item = ((usize, usize), TileKind)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl PartialEq for GameBoard

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl Serialize for GameBoard

fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>

Serialize this value into the given Serde serializer.

impl StructuralPartialEq for GameBoard