Click here to Skip to main content
Click here to Skip to main content

Tackle complex puzzles with LP Sokoban#

, 16 Jan 2007
Rate this:
Please Sign up or sign in to vote.
A simple Sokoban implementation in C# with some extras

Sample Image (without logging listbox)

Sample Image (another puzzle, with logging listbox)

Introduction

This is my first article on CodeProject. I wanted to develop a simple Sokoban program with some added features; I needed this to solve some complex puzzles as can be found here (some of these need hundreds of moves). And I saw the opportunity to demonstrate some solutions to issues that seem popular on the CodeProject message boards.

The Sokoban game

Sokoban is a board game with one player, a number of boxes (yellow) and an equal number of squares the boxes must be moved to (the "goals", in pink). The first screen shot shows a game in progress. The second screen shot shows the initial state of another game; it also has the logging listbox visible.

The player (the red triangle) can move around on the board by using the arrow keys: he can move to an empty square, or he can move onto a square occupied by a box while pushing the box in the same direction, provided the square ahead of the box is empty. It is impossible to move two or more boxes at a time; the player is not strong enough to push two boxes at once, or to squash a box into the wall.

The challenge consists of finding which box goes to which goal, and in what order. As an additional challenge, the number of moves may be restricted.

The Program

The program is fairly simple. It does not include any algorithm, since it does not solve the puzzle. It merely shows a puzzle and processes the user's moves while he attempts to solve the puzzle.

There are four major classes: MainForm, Sokoban, History and Board.

MainForm

The main form holds the menus, and processes all user input (menu clicks and keyboard input). It was created with the Visual Studio Designer. There is not much special here, except for the way I added an instance of my Board class. Since this inherits from Panel, but was not built as a Component, I could not get the Designer to add an instance of it. So I just added a regular Panel, and then programmatically create a Board, gave it the same Bounds, removed the place holding Panel and added the Board to the Controls collection.

// create a Board panel and replace preliminary panel by it
board=new Board(this, new Logger(log), sokoban);
board.Bounds=prelimBoard.Bounds;
Controls.Remove(prelimBoard);
Controls.Add(board);

That took 4 lines of code and avoided an entire DLL file. It also allowed me to first create an instance of the Sokoban class, which is an input parameter to the Board constructor.

The MainForm, as well as the Board in it, are scalable: you can resize the form, and the board (and the scale of the drawing) will be adapted instantaneously. When printing a puzzle, a single page is generated containing a one line text header and the board, scaled to utilize most of the page area.

Sokoban

The Sokoban class reads puzzles from a file and implements the game rules.

An XML file is used to hold one or more puzzles. XMLDocument and XMLReader classes are used to get a structured representation of the file content in memory. The same file structure is used as in Sokoban Pro (see acknowledgements), so both programs can share puzzle definitions. As an added feature the number of moves can be limited: an optional MaxMoves field has been added to the XML file format; any moves beyond MaxMoves are still executed but get accompanied by a beep.

The game rules are implemented mainly by the TryMove(int dx, int dy) method, where dx and dy indicate the attempted move direction (either -1, 0 or +1). Since all four directions use the same code, it becomes rather easy to get them working correctly.

The Sokoban class does not rely on a two-dimensional array to represent the board; instead it uses a couple of ArrayLists to hold instances of the Item class, which represent boxes, goals or the player himself. This was considered beneficial for code simplicity and performance; it did require some additional functions though, such as:

    
// is there a goal at (x,y) ?
public bool IsOnGoal(int x, int y) {
   foreach (Item item in goals) 
      if (item.x==x && item.y==y) return true;
   return false;
}

History

The history class stores the moves in an ArrayList. It offers undo/redo functionality, in that it can return the previous move, or the next move that had been executed before. The History class itself is application independent, it keeps track of objects, in this case Move objects (Move is a little class that remembers a dx-dy direction and a pushed box).

Board

The Board class offers a Panel that displays the current state of the Sokoban game. I have chosen to keep the visualization separate from the game logic; in this way it should be easier to replace one or the other in future without compromising the other class.

The Board is a lightweight object: it does not use a collection of controls to aggregate the complete picture, it merely draws all the necessary parts by using GDI+ calls (i.e. the Graphics class). Aggregating Controls is great if you want user interaction with those controls, since the mouse (and other) events get dispatched for you; this program does not have mouse input (except for the menus), so controls within the board would not offer much advantage, if any.

Currently the Board does not use images, it merely draws lines and rectangles, which could easily be replaced by something more fancy, if that is required.

Some extra features

On top of the basic display and move functionality, some features got added that help exploring and hopefully also solving a puzzle; these include undo/redo, cut/paste and printing.

The Edit menu items "Undo" (CTRL/Z) and "Redo" (CTRL/Y) will undo or redo a move. A complete move history is maintained and one can backtrack on a path and try something else, without having to restart the puzzle from square one.

The solution attempt gets encoded as a string, using the characters UDLR for up/down/left/right. For example, the first screen shot was obtained after executing the moves "DDDLULLULLDDDUUURRDRRDDDLLLLL". Such a string can be copied and pasted with the Edit menu items "Copy" (CTRL/C) and "Paste" (CTRL/V), so a series of moves can be stored in, and retrieved from, a text document by using some external editor such as Notepad. While pasting a sequence of moves, a small delay makes sure intermediate board states are shown, resulting in an animation effect. Remark: you may want to perform a Level Restart before pasting a solution attempt.

The following code snippet shows the paste handler creating the background thread, the method running on that thread, and the method pasteOneMove() that uses a delegate to Invoke itself on the UI thread. Rather than using input parameters, the pasteSequencer() method uses an instance field (pasteString) to get its data. This is safe since the Paste menu item is disabled while the background thread is running.

private void menuPaste_Click(object sender, System.EventArgs e) {
    IDataObject data=Clipboard.GetDataObject();
    if (data.GetDataPresent(DataFormats.Text)) {
        pasteString=data.GetData(DataFormats.Text).ToString();
        menuPaste.Enabled=false; // prevent multiple execution
        log("Pasting "+pasteString);
        Thread thread=new Thread(new ThreadStart(pasteSequencer));
        thread.IsBackground=true;
        thread.Start();
    }
}

private void pasteSequencer() {
    string s=pasteString.ToUpper();
    foreach (char c in s) {
        pasteOneMove(c);
        Thread.Sleep(100);    // slow down for animation
    }
    pasteOneMove(char.MaxValue);    // last paste action (reenable menu)
}

private delegate void MovePaster(char c);

private void pasteOneMove(char c) {
    if (this.InvokeRequired) {
        Invoke(new MovePaster(pasteOneMove), new object[]{c});
    } else {
        if (c==char.MaxValue) {
            menuPaste.Enabled=true;
        } else {
            Move move=null;
            if (c=='U') move=sokoban.TryMove(0,-1,true);
            else if (c=='D') move=sokoban.TryMove(0,1,true);
            else if (c=='L') move=sokoban.TryMove(-1,0,true);
            else if (c=='R') move=sokoban.TryMove(1,0,true);
            else log("*** bad character in paste: "+c);
            if (move!=null) postProcessMove(move);
        }
    }
}

As a last extra feature the Board can be printed, fitting neatly on one page. So you can even try to solve a puzzle on paper, or keep a printout of an intermediate state.

Points of interest

Some of the following items relate to recent topics on one of the CodeProject message boards:

  • the Board panel uses graphical primitives to make up a drawing
  • the Board panel is double-buffered to avoiding screen flickering
  • the Board panel is scalable, so one can accommodate the program's view to the available screen area.
  • the MainForm has built-in logging; it uses a listbox to display the log. The view menu controls the visibility of that listbox, and the listbox keeps scrolling down to keep the most recent messages visible. A delegate is used to make the log method available to the other major classes too.
  • the MainForm uses a background thread to paste a sequence of moves; this thread invokes the UI thread for each individual move, so UI Controls are handled correctly.
  • the MainForm uses about five strings in the Windows Registry to remember the most recent program settings. They are stored under HKEY_CURRENT_USER/Software/LP/Sokoban.

This program runs on both .NET Framework 1.1 and 2.0

Although this program supports printing, and accesses the Clipboard, an XML file and the Windows Registry, and uses delegates and even PInvoke to call a native method (MessageBeep), it consists of fewer than 1600 lines of source code.

Acknowledgements

Thanks to:

History

  • LP Sokoban# 1.0 (first release).

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Luc Pattyn
Software Developer (Senior) Perceler
Belgium Belgium
I am an engineer with a background in electronics, software and mathematics.
 
I develop technical software, both for embedded systems and for desktop equipment. This includes operating systems, communication software, local networks, image processing, machine control, automation, etc.
 
I have been using all kinds of microcontrollers and microprocessors (Intel 4004/8080/8051/80386/Pentium, Motorola 680x/680x0/ColdFire/PowerPC, Microchip PIC, Altera NIOS, and many more), lots of programming languages (all relevant assemblers, Fortran, Basic, C, Java, C#, and many more), and different operating systems (both proprietary and commercial).
 
For desktop applications and general development tools I have been using both UNIX systems and Mac/MacOS for many years, but I have switched to x86-based PCs with Windows, Visual Studio and the .NET Framework several years ago.
 
I specialize in:
- cross-platform development (making software that runs on diverse hardware/OS combinations)
- instruction set simulation
- improving software performance, i.e. making sure the software runs the job at hand in as short a time as possible on the given hardware. This entails algorithm selection, implementation design, accurate measurements, code optimisation, and sometimes implementing virtual machines, applying SIMD technology (such as MMX/SSE), and more.

Comments and Discussions

 
GeneralMy vote of 5 PinmvpS Mewara11-Jun-11 5:03 
GeneralGot to love Sokoban PinmvpDaniel Vaughan24-Mar-10 12:15 
AnswerRe: Got to love Sokoban PinmvpLuc Pattyn24-Mar-10 12:25 
GeneralRe: Got to love Sokoban PinmvpDaniel Vaughan24-Mar-10 13:06 
AnswerRe: Got to love Sokoban PinmvpLuc Pattyn24-Mar-10 13:44 
I meant from me posting the link to you reading and replying, but you knew that.
 
Thumbs Up | :thumbsup:

GeneralOutstanding!! [modified] PinmemberAreJay25-Jan-07 6:43 
GeneralRe: Outstanding!! PinmemberLuc Pattyn25-Jan-07 7:52 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 17 Jan 2007
Article Copyright 2007 by Luc Pattyn
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid