Sok format

From Sokoban Wiki

Jump to: navigation, search


Contents

Header added to the level files by the program "Sokoban YASC"

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
::         Sokoban (c) by Falcon Co., Ltd., Japan         ::
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
::                    File Format 0.17                    ::
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
::                                                        ::
:: File Notes                                  Optional   ::
:: Puzzle 1                                    Required   ::
::    Title                                    Optional*  ::
::    Board                                    See legend ::
::    Puzzle Notes                             Optional   ::
::    Saved Game or Solution 1                 Optional   ::
::      Title                                  Optional*  ::
::      Moves                                  See legend ::
::      Notes                                  Optional   ::
::    Saved Game or Solution 2                 Optional   ::
::    ... (more saved games and solutions)                ::
:: Puzzle 2                                    Optional   ::
:: ... (more puzzles)                                     ::
::                                                        ::
:: Remarks:                                               ::
::                                                        ::
:: File Notes                                             ::
::   File notes consist of unstructured text and          ::
::   key/value properties, such as "Author: Name". Lines  ::
::   beginning with "::" are comments meant to be read    ::
::   only by a person examining the file in a text        ::
::   editor, and should not be displayed by the Sokoban   ::
::   program.                                             ::
::                                                        ::
::   The optional but recommended property                ::
::   "Collection: Name" assigns a name to the puzzle      ::
::   collection. When a collection is copied from the     ::
::   internet, for example, and pasted into a Sokoban     ::
::   program, this information allows the collection to   ::
::   be saved with the proper name.                       ::
::                                                        ::
:: Titles                                                 ::
::   A title line is the last non-blank text line before  ::
::   a board, a saved game, or a solution, provided the   ::
::   line is preceded  by a blank line or it is the only  ::
::   text line at this position in the file.              ::
::                                                        ::
::   Title lines are optional unless a single or a last   ::
::   text line from a preceding puzzle, saved game,       ::
::   solution, or file header can be mistaken for a title ::
::   line.                                                ::
::                                                        ::
:: Puzzle Notes                                           ::
::   Two special key/value pairs are supported in puzzle  ::
::   notes: "Title" and "Author", hence, titles can       ::
::   either come from a title line or from a key/value    ::
::   pair.                                                ::
::                                                        ::
::::::::::::::::::::::::::: Board ::::::::::::::::::::::::::
:: Legend.................:      :.................Legend ::
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: Wall...................: #  # :...................Wall ::
:: Pusher.................: p  @ :.................Pusher ::
:: Pusher on goal square..: P  + :..Pusher on goal square ::
:: Box....................: b  $ :....................Box ::
:: Box on goal square.....: B  * :.....Box on goal square ::
:: Goal square............: .  . :............Goal square ::
:: Floor..................:      :..................Floor ::
:: Floor..................: -  _ :..................Floor ::
::                                                        ::
:: 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.                                             ::
::                                                        ::
::::::::::::::::::::::::::: Moves ::::::::::::::::::::::::::
:: Legend.................:      :.................Legend ::
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:: Move pusher up.........: u  U :.......Push/pull box up ::
:: Move pusher down.......: d  D :.....Push/pull box down ::
:: Move pusher left.......: l  L :.....Push/pull box left ::
:: Move pusher right......: r  R :....Push/pull box right ::
:: Begin jump.............: [  ] :...............End jump ::
:: Begin pusher change....: {  } :......End pusher change ::
:: Current position.......: *  * :.......Current position ::
::                                                        ::
:: Remarks:                                               ::
::                                                        ::
::   Moves may be run-length encoded, e.g., "3r4U" means  ::
::   "rrrUUUU", and "2(3(dr)R)" means "drdrdrRdrdrdrR".   ::
::   Each line must, however, have at least one proper    ::
::   non-digit character. Spaces between moves are        ::
::   allowed.                                             ::
::                                                        ::
::   Jumps and pulls: Only in reverse mode saved games    ::
::   and solutions.                                       ::
::                                                        ::
::   Reverse mode saved games and solutions must begin    ::
::   with a jump, even if it is empty. An example:        ::
::   "[]U[rr]d".                                          ::
::                                                        ::
::   Pusher changes: Only in puzzles with multiple        ::
::   pushers, e.g., Multiban. Moves inside the braces     ::
::   depict the relative movement to get from the         ::
::   currently active pusher to the next active pusher.   ::
::   At game start, a "{...}" sequence activates the      ::
::   pusher relative to the top-left pusher. An example:  ::
::   "{rddd}Urr{uul}uLU". If the top-left pusher is the   ::
::   first active pusher, then the empty "{}" can be      ::
::   omitted.                                             ::
::                                                        ::
::   The current position is optional and defaults to the ::
::   position after the last move.                        ::
::                                                        ::
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

An example file:

----------------------------------------------------------------------
Collection: YASGen
Author: YASGen & Brian Damgaard
Copyright (c) 2003 by Brian Damgaard
These levels may be freely distributed provided they are credited with
the author's name.

Chaos

  #####
###p .#
# b #.#
#  bb #
#.  # #
#   b.#
#######

Solution/Moves
dDuurrddLLrrddLLUlluuRDRddrruuLLrruullDlldddRRuULrrruullDldRddlUruuurr
ddddLLuuRlddrruUUdlldlldRRuuulDrddlluRurrrddLLUluRRlddrruUlldlldRRRllu
uulD
----------------------------------------------------------------------

More level examples:

Demo Level 01

########
#      #
#@ $   #
#   $  #
# . .  #
########

This demo level is trivial, but it suffices to demonstrate
the file-format.
A Sokoban program can add key/value pairs within the notes,
such as:
Author: nn
Website: http://www.nn.net

Solution/Moves
rurrdDuLulDD

The title of a snapshot does not bear any special meaning.
This snapshot just happens to be the best solution found
(so far). The demo-program automatically saves best solutions.

Snapshot 7/0
urrrrdd

This is an example of a snapshot saved by the user.
Later he/she can continue work on this path.

Snapshot 9/2
urrrrddLL*ruulDD

Another snapshot saved by the user. The '*' indicates
current position, i.e., the last moves were taken back,
but are still available for the "redo" function.


Demo Level 02

########
#     .#
#@ $   #
#   $  #
# . *  #
########

Just another trivial demo level. The number of levels in a
file is limited by available memory only.

Solution/Moves
rRRRdrUdlLLulD

Reverse Mode Snapshot 13/6
[rrrd]UUrLLLdrD

This is an example of a reverse mode snapshot.

Reverse mode snapshots always have a leading jump-sequence,
even if it is empty. An example: "[]Ulld...".


Demo Level 03

########
#      #
#  $   #
#   $  #
# + .  #
########

Solution/Moves
rrruulLrDuullDD

Implementation of the sok format

The advantage of the free formatted .sok file format is that it doesn't depend on keywords or specific tags (like xml based formats do). Therefore it's rather easy to manipulate and edit the files manually.
From Brian Damgaard on yahoo group:

It only requires a few extra code lines and can easily be implemented with a normal and efficient one-pass parser. The only special thing the program must do is to take into account that:

  • At the time the parser reads level notes, it's not known whether 1) the last text line belongs to the notes for the current level, or 2) it's the title line for the next level.
  • Resolving that question can first take place when the parser sees the next level (its board).
  • At that point, a non-fool-proof-but-in-practice-more-than-good-enough separation can be made. If the last text line in the notes from the preceding level is a single line (not part of a multi-line paragraph) then it's a title.

Some refinements can be implemented. For instance, in YASC, the line isn't considered a title if the line contains ":" because it typically signals a key-value pair. Again, it's not fool-proof, but in practice it's perfectly all right. There won't be more than, say, 1 in 50,000 true levels. where this logic fails.

The easiest way to describe a .sok file parser is with pseudo-code, concentrating on file-header, boards, titles, and notes, but omitting snapshots:

 ..set state to fileHeader
 ..while more lines do
 .....case state of
 .......fileHeader......if...next line is a board-line then
 ............................change state to newLevel
 ............................check whether the file-header
 ............................contains a title for the first level
 .......................else add next line to file-header
 ............................and advance
 .......................(break, for C-programmers)
 .......newLevel........create new level
 .......................set level-title to the stored title, if any
 .......................repeat
 .........................add next line to board-lines and advance
 .......................until eof or the next line isn't a board-line
 .......................set state to levelNotes
 .......................(break, for C-programmers)
 .......levelNotes......if...next line is a board-line then
 ............................change state to newLevel
 ............................check whether the level-notes
 ............................contain a title for the next level
 .......................else add next line to level-notes and advance
 .....endcase
 ..endwhile
 Adding snapshots/solutions to the parser is straightforward. 
 It involves 2 more parser states, "NewSnapshot" and "SnapshotNotes", 
 which work more or less like "newLevel" and "levelNotes".


Note: Some programs like Sokoban YASC resctrict the level titles to valid Windows file names. This means characters like these ": \ * ? [ ] ; < > | / " are ignored in the level title. This however it not part of the sok-file format.

Answer from Eric Sunshine in yahoo group:

If you would like to support other cases, such as when much or all of the meta-data appears before the puzzle, then you likely will need to implement a more complex heuristic for determining which non-puzzle data belongs to each puzzle. SokoSave Mobile takes this approach, trying very hard to intuit which information belongs with which puzzle, since many older collections are formatted in ways not compatible with the .sok format. To do this, SokoSave Mobile implements heuristics based directly on the SokoSplit utility (with a few small bug fixes): http://www.high-speed-software.com/sokosave/sokosavedesktop/sokosplit/

Here is a brief description of the heuristic. For each puzzle, perform the following steps in order:

1. If there is a blank line immediately before the puzzle, assign it to the puzzle.

2. Assign all following unassigned non-blank lines to the puzzle.

3. Assign all preceding unassigned non-blank lines to the puzzle. These lines precede the blank line (if present) assigned to the puzzle in step 1.

4. Assign all following unassigned lines (blank or not) to the puzzle.

5. Optional: Clean up by trimming leading and trailing blank lines from the collected meta-data. (Internal blank lines are retained.)

This heuristic works correctly with all of the old puzzle collections I have sitting around which were downloaded years ago, as well as with modern collections available for download. The heuristic also is a superset of the YASC .sok parsing, so it works properly with those collections, as well.

Personal tools