Simple Sokoban

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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:

  •  Load cases.
  • Move the Sokoban to solve the puzzle,
  • Allow move undo and restart,
  • Track moves made and saving  winning move sequences
  • Reload and Replay move sequences..  
  • Only four cases are included in the download zip files, but two of them (Case3 and Case4) were ones that I had originally thought to be impossible to solve.

Additional cases will require encoding by what seems to a semi-standard for text version of puzzles; one line per puzzle row and one character in the line for each column in the puzzle.  The characters used are:

bullet      space (or _ or -) = blank (outside of walls) or floor {inside of walls}
bullet      # = Wall;
bullet     @ = Man on Floor
bullet      + = Man on Target
bullet      $ = Box on Floor
bullet      * = Target
bullet      . =  Box on Target

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 

Suggestions for Further Explorations

Images for Sokoban and boxes

"Solver" option?

 

Original Date: August 12, 2009

Modified: February 18, 2016

 

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.