Tackle complex puzzles with LP Sokoban#

• Download demo project - 19 KB
• Download source - 29 KB

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.

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:

• Jasper van den Bergh who wrote the article on Sokoban Pro and shared code and problem files.
• Marc Clifton who wrote the article on an Undo/Redo Buffer Framework

History

• LP Sokoban# 1.0 (first release).

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