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 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:
- It is not space-efficient, using one letter for every move.
- 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” ??
- 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.
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.
§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.
(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:
Shorter and easier to understand, wouldn’t you agree?
(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.
Consider Aruba 9, number 6:
The P-format string can be read “push 1st block north, twice west and north”
Consider Aruba 10, number 91:
Mixed M & P: SPA9bwe8bw
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.