Problem Description
Sokoban is a Japanese word for "warehouseman" and is the name of a puzzle
played on a grid of squares representing a warehouse with a Sokoban, some
boxes (or other objects) to be moved and specified target locations for the
boxes. The man can only move vertically or horizontally
and can only push boxes into empty squares, i.e. not walls or other boxes.
<===== Simple example
Background & Techniques
The game was invented by Thinking Rabbit Inc, a
Japanese company and copyrighted in the 1980's. I believe it
originally appeared on Nintendo Gameboy machines. Since then dozens of
versions have appeared on the web and thousands of puzzles are available.
It is one of the few puzzle games that I have found somewhat addictive,
mainly because so many small ones seem to be unsolvable. I started
been thinking about writing a solver on these occasions just to prove that
someone had posted an unsolvable puzzle. Let me add that I have not
yet written the solver, but have not yet found a puzzle that was really
unsolvable - they usually just require some counter-intuitive moves.
In any event, I decided to write a user play
version as a test bed for the future solver, if I ever write it.
This is not a fancy version and will not be the best version to play if you
get serious about solving Sokoban puzzles, but might be a good one Delphians
waning to learn more about the techniques and considerations.
Here are other Sokoban sites that I have found to
be fun and/or useful in this investigation:
LetsLogic.com
Online game play with thousands of levels and comprehensive statistics about
the players and the puzzles. I am a user here with user-id of garyd if
you want to check me out. I am currently (August 2009) ranked 23rd
with a few hundred points, but a long way from the leader with 15,000+
points. Multiple points are awarded per solved puzzle depending on the
number of moves taken. "Different strokes for different folks"
definitely applies to your level of participation in this activity!
http://www.sourcecode.se/sokoban/index.php has a downloadable shareware
version of the game, but also has free access to the text version of many
puzzles which are in the format that my program reads.
http://www.joriswit.nl/sokoban/ provides a sophisticated freeware
version and access to many puzzles.
You will even find a number of Delphi versions if
you Google or Bing "Delphi Sokoban", but I have not investigated any of
them.
I won't spend much time describing the mechanics of
playing my version. In does provide the basic functions:
More sophisticated versions of Sokoban typically
include many puzzles (referred to as levels) in a single file. This
version reads a single puzzle per file.
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.
Notes for programmers
I had originally intended to post several versions of the program, each
showing further development toward the final project. That didn't
happen , mainly because things happen in stage 2 that require stage 1 to be
modified. The steps I envisioned, and the way that program evolved was
like this:
Stage 1: Define the board and the Load-case logic to display a puzzle.
Procedure LoadCase handles this, reading the selected file
according to the above format. One of the early decisions was how to
encode the characteristics of each cell in a StringGrid board to reflect its
characteristics. I chose a two character encoding: The 1st
character represent the background content of the cell (background
color for outside of the puzzle walls, wall color for wall
segments, floor color for floor segments which are not target, and
target color for target cells). The 2nd character of each
cell reflect the movable object, blank for none. A TCodes type
of each of types (Wall, Floor, Box, etc.) is used to index a Colors
array of type colors used to render the cells and an StrCodes array
of the characters used to fill the text values of cells.
One of the interesting problems arose because the encoding uses the
"space" character to represent both the area outside of the walls and the
floor area inside the walls which must be rendered differently. I
ended up by pre-scanning each line to find the first and last positions of
wall segments. Any space characters between these two values are Floor
cells.
I put a primitive face on the man just to identify him, but didn't
try to scale him. Cells dimensions are adjusted based on the number of
horizontal and vertical cells in the puzzle. I save the original grid
dimensions in the FormActivate exit and use those value to determine
the largest cell that will fit in the grid and then reduce grid dimension to
minimize the unused space around the cells.
Stage 2: Define the move logic to recognize arrow keys and allow legal
moves around the board.
Most of this is performed in the OnKeyDown exit for the main form.
By setting the KeyPreview property for the form to True, it sees all
keystrokes before they get passed on the control which has the focus.
This works well since, from the user's point of view, it doesn't matter
where I clicked last when I press a key. Arrow keys do not
generate KeyPress events, put the do generate KeyDown and KeyUp events.
I chose to check and act on KeyDown events. These event receive
virtual key codes which are word values which have predefined constant names
like VK_Left, Vl_Right, Vk_Up, and Vk_Down. Originally i had unique
code for the checking and changing cell values but later changed to the
current method. I set X and Y offset values, dx and dy
based on the key pressed, so for example, the left arrow sets dx to -1 and
dy to 0. Global variable ManLoc contains the current column and
row location of the man which together with the dx and dy values is enough
for function ValidMove to return True or False and for procedure
MovePieces to make the move if it is valid.
If the new location for the man already contains a box, additional
checking is required to make sure that the next cell in the same direction
is available to receive the box. MovePieces calls procedure
MovePiece twice in this case, once for the box and once for the man.
Stage 3: Track the number of boxes on targets to recognize the
winning position. Allow Undo. Everything else that i didn't think
about initially.
The implementation of undo is more complex than need be but I
didn't bother to change it. A TUndo record type contains the move
number and the from and to column and row values. I later found
another of those de facto standards that uses letters l,r,u,d for
direction that the man moved and capitalizes these letter if the move
included moving a box. Much simpler and I use this format to display
move sequences to the used and to save them. Undo is requested
by the "U", "Z", or BackSpace keys. The undo logic still uses
the "from" and "to" cell information to undo a move but ManLoc field and
direction letter would work just as well and probably will be is in the next
update.
I defined a "Sokoban.Ini" file using the TIniFile control
to save solution paths with fields Solution and
SolutionPathLength defined in a section indentified by the file name of
the puzzle. The Replay button simply reloads the
puzzle file and simulates arrow clicks by reading the Solution string with a
1/2 second delay between moves.
Running/Exploring the Program
