Sok format

From Sokoban Wiki

(Difference between revisions)
Jump to: navigation, search
m (Implementation of the Sok Format)
m (Implementation of the Sok Format)
Line 386: Line 386:
     if the current text line contains board rows and
     if the current text line contains board rows and
       the first of these rows isn't empty then
       the first of these rows isn't empty then
-
       collect text lines until finding a text line that doesn't contain board rows
+
       collect text lines until encountering:
-
   
+
        1. a text line that doesn't contain board rows
-
       while the last collected board row is empty
+
        2. the end of the file
 +
 
 +
       while the last found board row is empty
         discard the board rows found in the last collected text line
         discard the board rows found in the last collected text line
         put the last collected text line back on the queue (treat it as a notes text line)
         put the last collected text line back on the queue (treat it as a notes text line)
Line 402: Line 404:
* '''Puzzle board rows:'''  Run-length decoding is essential to accurately determine the content of individual rows due to the potential for compressed data within a single line.
* '''Puzzle board rows:'''  Run-length decoding is essential to accurately determine the content of individual rows due to the potential for compressed data within a single line.
-
* '''Snapshot moves:'''  Finding snapshot moves is simpler and doesn't require run-length decoding initially. However, when we perform run-length decoding at a later stage, it's important to note that it can span multiple lines. This is in contrast to board rows, which are always decoded one line at a time. This flexibility allows for cleaner snapshot storage with a straight right margin in the text file.
+
* '''Snapshot moves:'''  Finding snapshot moves is simpler and doesn't require run-length decoding initially. However, when we perform run-length decoding at a later stage, it's important to note that it can span multiple lines. This is in contrast to board text lines, which are always decoded one line at a time. This flexibility allows for cleaner snapshot storage with a straight right margin in the text file.
'''Function Implementation:'''
'''Function Implementation:'''

Revision as of 07:33, 22 May 2024


Contents

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

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
::         Sokoban (c) by Falcon Co., Ltd., Japan         ::
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
::                    File Format 0.18                    ::
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
::                                                        ::
:: 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:        ::
::   "[]Urrd".                                            ::
::                                                        ::
::   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 Sokoban puzzle file format is designed with user-friendliness in mind. Unlike stricter formats like HTML or XML, it allows puzzles to be written in a way that's easy for people to share and understand. This simplicity comes at a cost, though. While the files are plain text, the logic behind reading them can get tricky for the programmer if not handled correctly.

This guide will demonstrate how to create a program that effectively parses these files. To complement the guide, a fully functional and efficient reference implementation of both a puzzle file reader and writer, written in Common Lisp, is available here. The Common Lisp code can easily be converted to other programming languages, and this process can even be partially automated.

Main Procedure

Key Observation:

One crucial concept to remember is that the program will encounter notes until it stumbles upon a puzzle board, a snapshot (an unsolved state of the puzzle), or a solution (a snapshot representing a completed puzzle). This observation forms the core of our program's structure, as reflected in the following pseudocode:

 function readPuzzleFile()
   file.notes := readNotes()
   while found-puzzle-board? or found-snapshot?
     ... (more to come)

Prioritizing Notes:

At first glance, focusing on notes might seem strange since puzzle boards are the heart of the file. However, this approach has a significant advantage. Not only does the file begin with notes, but each puzzle and snapshot can have their own set of notes as well. This means that whenever we encounter a puzzle board or a snapshot, we need to grab any associated notes before moving on.

 function readPuzzleFile()
   file.notes := readNotes()
   while found-puzzle-board? or found-snapshot?
     if found-puzzle-board? then
       puzzle := makePuzzle(puzzle-board)
       file.puzzles += puzzle
       puzzle.notes := readNotes()
       ... (more to come)
     else
       (found an orphaned snapshot)
       puzzle := makePuzzle(no board)
       file.puzzles += puzzle
       puzzle.snapshots += snapshot
       snapshot.notes := readNotes()

"Orphaned" Snapshots:

The reason we handle "orphaned snapshots" is because it's sometimes useful to load snapshots and solutions separately for further processing. A common scenario would be loading a file containing solutions (perhaps from the clipboard) to pair them with existing puzzles.

Recurring Pattern:

It's worth noting the repeated use of the "readNotes()" function right before the "while" loop restarts. We'll see this pattern again as we complete the main function by adding the logic to load snapshots associated with a specific puzzle.

 function readPuzzleFile()
   file.notes := readNotes()
   while found-puzzle-board? or found-snapshot?
     if found-puzzle-board? then
       puzzle := makePuzzle(puzzle-board, optional-title)
       file.puzzles += puzzle
       puzzle.notes := readNotes()
       while found-snapshot?
         puzzle.snapshots += snapshot
         snapshot.title := optional-title
         snapshot.notes := readNotes()
     else
       (found an orphaned snapshot)
       puzzle := makePuzzle(no board)
       file.puzzles += puzzle
       puzzle.snapshots += snapshot
       snapshot.title := optional-title
       snapshot.notes := readNotes()
   post-processing, e.g., make titles unique and resistant to misinterpretation

Wrapping Up:

With these additions, our main function is complete! It's both straightforward and robust. We've also introduced the concept of optional titles for puzzles and snapshots. These titles are essentially header lines from the text file, and the "readNotes()" function is responsible for differentiating them from regular notes belonging to the preceding element.

As you can see, the "readNotes()" function carries a significant responsibility. However, this modular approach keeps the code well-organized and easy to manage.

Notes Text Lines

Now, let's take a closer look at the "readNotes()" function.

 function readNotes()
   ... (initialize return values)
   collect notes text lines until encountering:
     1. a puzzle board
     2. a snapshot
     3. the end of the file
 
   ... (more to come)

As you can see, the function accumulates text lines until it encounters one of three conditions: a puzzle board, a snapshot, or the end of the file.

Title Line Detection:

The slightly tricky part for "readNotes()" is identifying a potential title line preceding the next puzzle board or snapshot. Here's the key: we discard trailing blank lines, but at first, we need to keep initial blank lines. This distinction plays a role in determining whether a line is interpreted as a title or simply part of the notes.

Imagine these two scenarios:

  • Scenario 1 (No Title Line):
 I am a notes text line
 I am a notes text line too
  • Scenario 2 (With Title Line):
 I am a notes text line
 [blank line]
 I am the title of the next puzzle or snapshot, if any

In the second scenario, the blank line separates the notes from the title line.

Complete Implementation:

The complete implementation of "readNotes()" is shown below. The description includes all the necessary details, allowing for a straightforward translation into your preferred programming language.

 function readNotes()
   initialize return values:
     notes, puzzle-board, snapshot, run-length-encoded-snapshot?, and optional-title
 
   collect notes text lines until encountering:
     1. a puzzle board
     2. a snapshot
     3. the end of the file
   
   trim notes text lines by removing:
     - leading ">" characters followed by a space (email-style quoting)
     - trailing spaces, tabs, and other control characters
 
   discard trailing blank lines (empty lines at the end)
 
   if a puzzle board or snapshot is found:
     if there are notes lines:
       and (only one line exists in the notes
           or the second-to-last line in the notes is blank)
       then
         optional-title := the last line in notes
         discard the last line in notes
         discard trailing blank lines
   
   discard leading blank lines (empty lines at the beginning)

Board Text Lines

Several key points need to be considered when finding puzzle boards:

  1. Run-length encoding: A single line can represent multiple board rows.
  2. Validation criteria: To distinguish actual puzzle boards from notes that resemble them, the program checks for specific characteristics:
  • Structure: The first non-empty column in each row must contain a wall or a box on a goal. This ensures a minimum level of structure, making puzzle boards easier to locate, especially in large files.
  • Minimum size: The board must have at least three rows and three columns.
  • Empty rows: Empty rows are used for decoration and should only appear within the board, not at the beginning or end.

Here's the process the program follows:

  • Tentative collection: When encountering a line that might contain puzzle rows, the program initially collects that line along with all subsequent lines that also seem like puzzle rows.
  • Validation: The program then analyzes the collected lines to determine if they actually form a valid puzzle board. If not, or if the "tail" ends with an empty row (which is invalid), the program puts as many of the collected lines back on the queue as necessary, so they will be treated as notes.

It's important to note that this validation focuses solely on the structure of the board. Whether the puzzle is well-formed (e.g., has a player, matching boxes and goals) is only checked when a user attempts to solve it.

Function Implementation:

The "boardLines?()" function, despite its name, actually returns the identified puzzle rows rather than a simple true/false value. Here's the pseudocode:

 function boardLines?()
   if the current text line contains board rows and
      the first of these rows isn't empty then
     collect text lines until encountering:
       1. a text line that doesn't contain board rows
       2. the end of the file
 
     while the last found board row is empty
       discard the board rows found in the last collected text line
       put the last collected text line back on the queue (treat it as a notes text line)
   
     if the collected board rows live up to the minimum size criteria then
       return the collected board rows, left-justified
     else
       put all collected text lines back on the queue (treat them as notes)

Snapshot Moves Text Lines

There's a key distinction between identifying puzzle board rows and snapshot moves:

  • Puzzle board rows: Run-length decoding is essential to accurately determine the content of individual rows due to the potential for compressed data within a single line.
  • Snapshot moves: Finding snapshot moves is simpler and doesn't require run-length decoding initially. However, when we perform run-length decoding at a later stage, it's important to note that it can span multiple lines. This is in contrast to board text lines, which are always decoded one line at a time. This flexibility allows for cleaner snapshot storage with a straight right margin in the text file.

Function Implementation:

The "snapshotLines?()" function, similar to "boardLines?()", returns the actual snapshot lines rather than a simple true/false value. Here's the pseudocode:

 function snapshotLines?()
   collect text lines with moves until encountering:
     1. a line that doesn't contain moves
     2. the end of the file

We're nearing the completion of these functions! We've defined the "plural" functions ("boardLines?()" and "snapshotLines?()") that handle collections of lines. Now, let's explore their corresponding "singular" counterparts, which examine a single line at a time.

Board Text Line

The "boardLine?()" function has two key distinctions:

  1. Arguments: Unlike prior functions, it can accept an argument beyond just the current text line. This allows us to call the function recursively.
  2. Return Value: Upon successful decoding, it returns a list containing multiple board rows, not just a single row.

Function Implementation:

Here's the pseudocode for "boardLine?()":

 function boardLine?( text )
   trim leading ">" characters (email-style quoting)
   if the text contains only legal board characters then
     if the text is run-length encoded then
       decode the text
       trim one trailing "|" and then split on "|"
       for each text section:
         call boardLine?( text-section )
       if all text sections pass the test then
         return the decoded text sections as board rows
     else
       (the text isn't run-length encoded)
       return a list with the trimmed text as one board row

Explanation:

The function first checks if the line contains only valid board characters. If so, it then determines if the data is run-length encoded. If it is, the function decodes it, splits it into sections (representing individual board rows), and recursively calls itself on each section for further validation. Finally, if all sections pass the test, the decoded text sections are returned as a list of board rows.

Snapshot Moves Text Line

The "snapshotLine?()" function should not perform run-length decoding. Instead, it has another speciality: it returns two values:

  1. Snapshot moves: These moves might be run-length encoded.
  2. A "run-length encoded?" flag: This indicates whether the returned moves are indeed run-length encoded.

If a snapshot contains one or more run-length encoded lines, the "snapshotLines?()" function (which calls "snapshotLine?()") can then optionally perform a decoding of the entire snapshot.

Function Implementation:

Here's the pseudocode for "snapshotLine?()":

 function snapshotLine?( text )
   trim leading ">" characters (email-style quoting)
   if the text contains only legal snapshot characters and
      the text contains at least one move (a direction character) then
     return two values:
       1. the trimmed text as snapshot moves
       2. run-length encoded moves?

Explanation:

The function verifies that the line represents a valid sequence of snapshot moves. If the line is valid, the function returns two values:

  1. Snapshot moves: This is the trimmed text representing the actual moves within the snapshot.
  2. A "run-length encoded?" flag: This value indicates whether the returned moves are run-length encoded.

The flag value can be used later by "snapshotLines?()" to determine if any decoding is necessary. In other words, "snapshotLines?()" can use this flag to decide whether to decode the entire snapshot, in case some of the lines within the snapshot contain run-length encoded moves.

Utility Functions

Here's a final noteworthy utility function:

make-interpretation-resistant-title( title ): This function addresses a potential issue where a title line preceding a puzzle or snapshot could be mistakenly interpreted as part of a puzzle or snapshot itself. For example, titles like "Dull" or "Rud" might cause confusion.

The function ensures clarity by enclosing such titles in quotation marks. Here's the pseudocode:

 function make-interpretation-resistant-title( title )
   if boardLine?( title ) or snapshotLine?( title ) then
     return the title enclosed by quotation marks
   else
     return the title

Conclusion

With this, we've reached the end of our guide! The functions for run-length decoding and its counterpart for run-length encoding are implemented in the accompanying Common Lisp program and won't be covered here.


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.

Note from Eric Sunshine on the Yahoo Sokoban 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