Crate sokoban_elements 

sokoban-elements

sokoban-elements crate implements reading and writing various Sokoban file formats.

• it supports representation of Sokoban, Hexoban, Trioban and Octoban game variants
• it supports Classic, Sokoban+ and Multiban variants of game rules
• it supports reading and writing of common Sokoban file formats like SokobanYASC .sok, Sokoban for Windows .slc and traditional XSokoban .xsb
• it can read and write whole collections as .json, with the json feature

Intended use is for any kind of sokoban program that needs to be able to read game files, have a nice API for representing objects it had read, edit game boards and write edits back to files. Crate provides many elements needed to build puzzle editor for any of supported game variants. And, even game engines can benefit from static board features (corners, walls, initial piece positions, …) detected and represented by this crate:

• single crate that reads many sokoban file formats with all their quirks and gotchas implemented and tested
• static board analysis already detects important game board features like walls, playable area, piece positions and identification, …
• all game board editing primitives and transformations (mirroring/rotation) are implemented here: for all supported tessellations

This crate is neither a game engine nor a solver, and does not aim to become one: it will not play Sokoban for you, it does not validate moves against the rules, and it does not search for solutions. What it does cover is everything around that - reading and writing the files, editing the board and reporting what is on it - so that an engine or a solver has somewhere to start.

About Sokoban

From Wikipedia Sokoban rules, classic game rules are:

The game is played on a board of squares, where each square is a floor or a wall. Some floor squares contain boxes, and some floor squares are marked as storage locations.

The player is confined to the board, and may move horizontally or vertically onto empty squares (never through walls or boxes). The player can also move into a box, which pushes it into the square beyond. Boxes may not be pushed into other boxes or walls, and they cannot be pulled. The number of boxes is equal to the number of storage locations. The puzzle is solved when all boxes are at storage locations.

Game variants

Along classic, square grid Sokoban, there exists few more variants having different game grid (plane tessellation):

1. Sokoban - game is played on grid of squares
2. Trioban - game is played on grid of alternating triangles (▽ and △) where bottom left tile is triangle pointing up (△)
3. Hexoban - game is played on grid of hexagons
4. Octoban - game is played on grid of alternating squares and octagons with bottom left tile being octagon

Sokoban rules variants

For each variant of game grid, there are three variants of game rules:

1. Classic Sokoban rules

   There is only one pusher on game board.

2. Multiban rules

   More than one pusher is present on game board. Classic rules of game apply to each of the pushers on board with additional rule that pusher can’t move through another pusher

3. Sokoban+ rules

   Boxes and goals are tagged with numbers or colors. Game is considered solved when all boxes are on goals and when tags of each box and goal match

Sokoban game solving mode

Any combination of game rules and game grid can also be played in two different modes:

1. Forward solving

   Pusher can’t pull box and can’t move through boxes, walls or other pushers.

2. Reverse solving

   Reversed Solving reverses the game, working from the solution back to the original puzzle. Pusher no longer pushes boxes, but pulls them instead. This method completely eliminates the need for box deadlock detection and prevention, as undesired states related to the position of the boxes can never be reached.

   When game is started, positions of boxes and goals are switched and game starts in solved state.

   Pusher can only pull boxes, not push them. If position allows a pull, that pull is optional (pusher is allowed to move without pull even if pull is possible).

   Pusher is allowed to jump over boxes, walls and other pushers. Jumps are allowed only before first box had been pulled.

   When game is started in reverse solving mode, pusher may end up standing “on top” of a box. In that case first move for that pusher must be jump.

   Jumping after first pull can be optionally enabled if that helps searching for board solution.

   A reverse solution is a forward solution played backwards, so it can be converted into the forward solution of the same puzzle - but this is out of scope for this crate.

Examples

Puzzles and collections of puzzles

sokoban_elements implements Puzzle type which stores game board and it’s meta data ( author, title, …). It also provides Collection type to group multiple puzzles.

Game board and pieces

Boards for any game variant are managed by GameBoard type. Boards can be read from strings in memory using traditional board encoding schemes and characters. For example:

use sokoban_elements::*;

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

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

assert!(board[(5, 2)] == TileKind::Box);

Each kind of game piece is implemented by it’s own type: Boxbox, Goal and Pusher.

All individual game pieces on single game board have unique integer identifier: BoxID, GoalID and PusherID. Continuing example from before,

let boxes = board.boxes(None)?;
println!("{:?}", &boxes[0]);
// Boxbox { id: BoxID(0), x: 5, y: 2, plus_id: None }

Boxes and goals optionally also have PlusID which comes from representation of Sokoban+ rules in SokobanPlus type. SokobanPlus is optional because not every Puzzle even has Sokoban+ rules, and the ones that have them can be played with or without enabling Sokoban+:

let sokoban_plus = SokobanPlus::parsed("1 1 1 2 2 3", "0 3 2 2 1 1 1").unwrap();

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

println!("{:?}", &boxes_without_plus[3]);
// Boxbox { id: BoxID(3), x: 7, y: 4, plus_id: None }

println!("{:?}", &boxes_with_plus[3]);
// Boxbox { id: BoxID(3), x: 7, y: 4, plus_id: Some(PlusID(2)) }

Saved games

Each Puzzle can have zero or more associated SavedGames. SavedGame is a sequence of pusher Steps. Each step records direction and kind of movement (move, push, pull, jump and pusher change in Multiban games). SavedGame records movement history for both game SolvingModes.

let saved_game = SavedGame::parsed("llRRddsssSSSnNN", Tessellation::Hexoban)?;
println!("{:?}", &saved_game[3]);
// PushOrPull(Right)

let reverse_saved_game: SavedGame = SavedGame::parsed("lurd[]", Tessellation::Sokoban)?;
println!("{:?}", reverse_saved_game.solving_mode());
// Reverse

Replaying a saved game against its board - to check that it solves the puzzle, to count its solution metrics, or to turn a reverse solution into the forward one it mirrors - is out of scope for this crate. This crate parses and prints saved games; it does not play them.

Feature flags

Feature	Default	Description
serde	no	Serialize / Deserialize for the public types
json	no	.json file format (FileFormat::Json). Implies serde

[dependencies]
sokoban-elements = { version = "0.2.1", features = ["json"] }

serde alone pulls in no JSON parser, so it stays useful for compact formats like bincode or MessagePack. A .json file is exactly the Collection wire format below, pretty printed; like .sok it is lossless and may mix tessellations, and unlike .sok any JSON library can read it.

Most types serialize the obvious way. Three do not, because their invariants live in their constructors rather than in their fields, and deserialization is routed back through those constructors:

Type	Wire format
GameBoard	{ "tessellation": .., "board": .. } - the printed board plus its tessellation
SavedGame	{ "tessellation": .., "moves": .., .. } - printed steps plus metadata
SokobanPlus	{ "boxorder": [..], "goalorder": [..] } - one dense slot per piece, null when a piece has no Sokoban+ ID

SavedGame has no solving_mode field: reverse mode is already encoded in the moves text as a leading jump section, so the text is the single source of truth. SokobanPlus deliberately does not reuse its textual boxorder / goalorder form: that form encodes “no Sokoban+ ID” as a marker value, so reading it back depends on which marker convention the reader picks, whereas the array form has no marker at all. A client in another language therefore decodes one Sokoban+ ID or null per piece directly, instead of reimplementing those marker rules. All three reject unknown fields.

These formats are part of the public API - changing them is a breaking change. Compact, non self-describing formats (bincode, MessagePack) are supported by construction, but only JSON is covered by tests.

Structs

BoardArea

Set of Point2D with small(ish) memory footprint.

BoardAreaIntoIter

Owning iterator over Point2D in BoardArea.

BoardAreaIter

Iterator over Point2D in BoardArea.

BoardSyntaxError

std::Error when parsing GameBoard.

BoxID

Box identifier.

Boxbox

Box (crate, container) on game board.

Collection

Collection of Sokoban puzzles and accompanying metadata.

DirectionsSet

Immutable Set of Direction with small memory footprint.

DirectionsSetIter

Iterator over Direction in DirectionsSet in clockwise order.

GameBoard

Parsed game board for some Tessellation.

GameBoardIter

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

Goal

Goal on game board.

GoalID

Goal identifier.

IoReadError

std::Error when reading FileFormat.

IoWriteError

std::Error when writing FileFormat.

PieceIdError

Errors when working with BoxID, GoalID and PusherID.

PlusID

Sokoban+ identifier for box and goal.

Point2D

1D / 2D coordinate for GameBoard positions.

Pusher

Pusher on game board.

PusherID

Pusher identifier.

Puzzle

Sokoban puzzle that consists of GameBoard and accompanying metadata.

ReaderSettings

Settings for FileFormat reader.

SavedGame

Sequence of pusher steps with accompanying metadata (ie. title, author, etc..).

SavedGameSyntaxError

std::Error when parsing SavedGame.

Size2D

2D size of game boards.

SokobanPlus

Data for Sokoban+ variant of game rules.

SokobanPlusSyntaxError

std::Error when parsing SokobanPlus.

StaticBoardAnalysis

Static analysis of game boards (outer walls, corners, play area…)

WriterSettings

Settings for FileFormat writer.

Enums

BoardSyntaxErrorKind

Variants of BoardSyntaxError.

Direction

Direction of movement.

FileFormat

All supported Sokoban file formats.

HorizontalEdge

Horizontal edge of a GameBoard: the edge rows are added to and removed from.

IoReadErrorKind

Variants of IoReadError.

MirrorAxis

Axis reflected across by GameBoard::mirror().

PieceIdErrorKind

Variants of PieceIdError.

Rotation

Direction of one tessellation-specific GameBoard::rotate() step.

SavedGameSyntaxErrorKind

Variants of SavedGameSyntaxError.

SokobanPlusSyntaxErrorKind

Variants of input for SokobanPlusSyntaxError

SolvingMode

Game solving mode.

Step

Single step of a pusher.

Tessellation

Sokoban game variants.

TileKind

What kind of game board element is one tile of that board.

TileShape

Shape of single game board tile.

VerticalEdge

Vertical edge of a GameBoard: the edge columns are added to and removed from.