SokoPath: Sokoban Solution Format

QUICK INFO

The SokoPath-format is a readable and efficient way of managing sokoban solutions.

A sokoban solution is a description of the steps the player has to take to solve a certain Sokoban level.

There are several existing methods to describe those steps, but I needed a more flexible system for my solver, so I created SokoPath.

THE PROBLEM

The problem with the current options:

Sokoban solutions are often described using the LURD-format, which is a string of the characters l, u, r and d, meaning left, up, right and down.
Let’s take an extreme example, Microban level 154:

The solution in LURD-format:

ruuuuuuuuuuuurrrrrrrrrrrrrrrrrrrrrddddddddddllllllllllllllllluuuuuurrrrrrrrrrrrrddlllllllllllddrrrrrrrrrrr rruuuuuulllllllllllllllllddddddddddrrrrrrrrrrrrrrrrrrrrruuuuuuuuuuuuuulllllllllllllllllllllllllddddddddd dddduuuuuuuuuuuuurrrrrrrrrrrrrrrrrrrrrrrrrddddddddddddddllllllllllllllllllllluuuuuuuuuurrrrrrrrrr rrrrrrrddddddllllllllllllluurrrrrrrrrrruulllllllllllllddddddrrrrrrrrrrrrrrrrruuuuuuuuuullllllllllllllllllllldddd ddddddddll

This format is less than ideal for the following reasons:

  1. It is not space-efficient, using one letter for every move.
  2. It is hard to read, especially when using a non-fixed font which makes the letter l thinner than the other letters. Exactly how many l’s are there in “lllllllllllllllllllllllllll” ??
  3. The player is not moving up and down, he is a warehouse keeper moving on the floor, it would be more logical to use the cardinal direction system from classic text-adventures: (n)orth, (e)ast, (s)outh, (w)est.

There are some other formats, including a binary format with the moves encoded into bits and then uuencoded. The result is a fairly small solution file but you lose readability, there is no way for a human to manually enter the data into a sokoban game without decoding it first.

With SokoPath I wanted a high level of readability and as low space requirements as possible.

CHANGES

2012-11-11: Removed Jumps from the specification due to technical issues. Using coordinates made the path string depend not on the players position but the position of the level on the “grid”. Cleaned up the specification a bit. Added versioning.

2008-12-11: I finally decided upon the name SokoPath. “Soko” as all my Sokoban-related classes have that prefix, and “Path” as it describes a path, not necessarily a solution, or even part of a solution.

SokoPath, General

§1 A SokoPath is a string of characters. It can consist of one or more formats, freely mixed.

$2 The string is prefixed by the letters SP and a version letter. Current version is A.

§3 The string is case-independant.

MOVES

(Previously called M-format)

Moves is the classic way of describing movement in Sokoban.

§11 Moves are described by a series of n,e,s,w characters, although optionally run-length (also called byterun) encoded. nn becomes 2n, eeeee becomes 5e and ssssssssssss becomes 12s.

§12 Encoded and non-encodes moves can be freely mixed.

Here is the exact same solution of the above Microban 154 level using this system:

SPAe12n21e10s17w6n13e2s11w2s13e6n17w10s21e14n25w13s13n25e14s21w10n17e6s13w2n11e2n13w6s17e10n21w12s2w

Shorter and easier to understand, wouldn’t you agree?

PUSHES

(Previously called P-format)

My solver thinks only in pushes. The exact path the player takes is not that interesting. It is thus pointless to store movements to certain positions when there is no pushing being done there anyway. You also lose data (alternative routes) when you specify the exact route.

Using the P-format you can describe the pushes and not have to concern yourself with the exact route to the block.

§30 The format: <block no>b<direction(s)>

§31 block no for the format is the number of the block being pushed, according to its starting position, going from left to right, top-down. The first block is number 1.

§32 direction(s) for the pushes is one or more directions that you push that block. Optionally encoded as M-format above.

EXAMPLES

Consider Aruba 9, number 6:

M-format: SPAe2nen2we3s2w3n

P-format: SPA1bn2wn

The P-format string can be read “push 1st block north, twice west and north”

Consider Aruba 10, number 91:

M-format: SPA2nw2nw2n5ese7s7w4ne2w

Mixed M & P: SPA9bwe8bw

NOTES

I might make available reference routines in C++ and/or C# for parsing this format as well as converting from other formats. What I will not make available this way is routines for converting FROM the format to other formats, although you will be able to do that with jeSokobanLibrary.

 

Leave a Reply

Your email address will not be published. Required fields are marked *