# sokoban-elements
[](https://github.com/tadams42/sokoban-elements/actions/workflows/ci.yml)
[](https://crates.io/crates/sokoban-elements)
[](https://docs.rs/sokoban-elements)
[](https://github.com/tadams42/sokoban-elements)
`sokoban-elements` crate implements reading and writing various
[Sokoban](https://en.wikipedia.org/wiki/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:
```rust
use sokoban_elements::*;
# fn main() -> Result<(), BoardSyntaxError> {
let board_text = [
" #####",
" # #",
" #$ #",
" ### $##",
" # $ $ #",
"### # ## # ######",
"# # ## ##### ..#",
"# $ $ ..#",
"##### ### #@## ..#",
" # #########",
" #######",
]
.join("\n");
let board = GameBoard::parsed(&board_text, Tessellation::Sokoban)?;
assert!(board[(5, 2)] == TileKind::Box);
# Ok(())
# }
```
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,
```rust
# use sokoban_elements::*;
#
# fn main() -> Result<(), BoardSyntaxError> {
# let board_text = [
# " #####",
# " # #",
# " #$ #",
# " ### $##",
# " # $ $ #",
# "### # ## # ######",
# "# # ## ##### ..#",
# "# $ $ ..#",
# "##### ### #@## ..#",
# " # #########",
# " #######",
# ]
# .join("\n");
#
# let board = GameBoard::parsed(&board_text, Tessellation::Sokoban)?;
let boxes = board.boxes(None)?;
println!("{:?}", &boxes[0]);
// Boxbox { id: BoxID(0), x: 5, y: 2, plus_id: None }
# Ok(())
# }
```
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+`:
```rust
# use sokoban_elements::*;
#
# fn main() -> Result<(), BoardSyntaxError> {
# let board_text = [
# " #####",
# " # #",
# " #$ #",
# " ### $##",
# " # $ $ #",
# "### # ## # ######",
# "# # ## ##### ..#",
# "# $ $ ..#",
# "##### ### #@## ..#",
# " # #########",
# " #######",
# ]
# .join("\n");
#
# let board = GameBoard::parsed(&board_text, Tessellation::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)) }
# Ok(())
# }
```
### Saved games
Each `Puzzle` can have zero or more associated `SavedGame`s. `SavedGame` is a sequence
of pusher `Step`s. 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 `SolvingMode`s.
```rust
# use sokoban_elements::*;
#
# fn main() -> Result<(), SavedGameSyntaxError> {
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
# Ok(())
# }
```
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
| `serde` | no | `Serialize` / `Deserialize` for the public types |
| `json` | no | `.json` file format (`FileFormat::Json`). Implies `serde` |
```toml
[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:
| `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.
[SokobanYASC]: https://sourceforge.net/projects/sokobanyasc/
[Wikipedia Sokoban rules]: https://en.wikipedia.org/wiki/Sokoban#Rules
[Sokoban for Windows]: https://www.sourcecode.se/sokoban/
[XSokoban]: https://www.cs.cornell.edu/andru/xsokoban.html