CodeProject: WPF Alien Sokoban. Free source code and programming help

Report Article

Discuss

Send to a friend

35 votes for this Article.

Popularity: 6.67 Rating: 4.32 out of 5

Download demo and source - 386.66 KB

Introduction
Background
How to Play the Game
Extending Playability
- Map File Format
XAML and Data Binding
Sokoban Project
Expression Design and Resource Dictionaries
Points of Interest
Asynchronous Property Changes
Level Codes
Future Enhancements
Conclusion
Credits
References
History

Introduction

The downloadable WPF Sokoban project is intended to be an instructional yet fun introduction to creating WPF applications, and an introduction to some of the new features of .NET 3.5. It is inspired by Sacha Barber's excellent article WPF: The Classic Snakes WPF'ed. This article provides an overview of data binding with WPF: styling and templating of controls. In a later article I intend to port this application to Silverlight, in order to explore some of the differences between the two technologies.

Background

If you must play, decide on three things at the start: the rules of the game, the stakes, and the quitting time.
-Chinese proverb

Sokoban, like many other brain teasing and time consuming puzzles, can be enjoyable to play but difficult to quit. It has few rules, and can, at times, be challenging. The game was invented by Hiroyuki Imabayashi in 1980. It is somewhat ubiquitous, and can be found on game consoles, mobile phones, and according to the Wikipedia entry, Canon power shots digital cameras.

How to Play the Game

Push the blue power cubes (treasures) onto the yellow power stations. When all cubes are seated in the power stations, our alien friend will be transported to the next level. Only one power cube may be pushed at a time, and they cannot be pulled.
Once a new level has been attained, make note of the level code. This may be used to later return to that level.

Controls

Either the arrow keys or the mouse can be used to control the actor. If the arrow keys are used, then the actor is able to move up, down, left, or right. If the mouse is used, then the actor will attempt to traverse the level grid to a point clicked by the user. The mouse can be used to move a power cube by positioning the actor adjacent to the power cube and then by single clicking on it.

Undo and Redo

Use Ctrl+Z and Ctrl+Y to undo and redo moves and jumps.

Level Items

Power cubes are to be moved to the goal cells (power stations)
The actor is controlled by the user
Wall cells cannot be entered by the actor, nor have content placed in the cell
Floor cells are where the actor may move, or place power cubes
Space cells are normally outside of the walled enclosure of the level grid. They can't contain content

Moving Around

The actor may move either in a single step to an adjacent floor cell, or with a jump to any reachable floor cell on the level grid. In the case of a jump, the application will calculate the best path i.e. that which is comprised of the fewest number of moves.

Extending Playability

Alien Sokoban's playability may be extended by creating or modifying the map files located in the Levels directory.

Map File Format

The following characters are used within the map files to signify the structure of a level:

"#" Wall
" " Empty floor cell
"$" Power cell in a power station (or goal)
"." Power station (or goal)
"@" Actor in a floor cell
"!" Space cell

XAML and Data Binding

This application displays a game level using a System.Windows.Controls.Grid populated with buttons. That is, each cell on the grid contains a button. We use a Style for each button in conjunction with Style triggers to display the cell and any cell contents.
The following excerpt from MainWindow.xaml shows how this is accomplished:

<Style x:Key="Cell" TargetType="{x:Type Button}">
    <Setter Property="Template">
        <Setter.Value>
            <ControlTemplate TargetType="{x:Type Button}">
                <Grid>
                    <!-- The cell, -->
                    <Rectangle Width="40" Height="40" 
                        Style="{DynamicResource CellStyle}" />
                    <!-- and its content. -->
                    <Rectangle Style="{DynamicResource CellContentStyle}"/>
                </Grid>
            </ControlTemplate>
        </Setter.Value>
    </Setter>
</Style>

Style triggers change the way the cell is displayed when the Cell or CellContents, which is databound to the button, changes. The following excerpt shows how the Actor is set to display when the CellContents.Name property changes to Actor.

<MultiDataTrigger>
    <MultiDataTrigger.Conditions>
        <!-- If the cell contains the Actor. -->
        <Condition Binding="{Binding Path=CellContents.Name}" Value="Actor" />
    </MultiDataTrigger.Conditions>
    <Setter Property="Fill" Value="{StaticResource PlayerCellContentBrush}"/>
</MultiDataTrigger>

Evaluation of the trigger occurs when the PropertyChanged event of the CellContent class is raised. The DataContext of the button is set to an Orpius.Sokoban.Cell when the level is first initialized in the InitialiseLevel method of the MainWindow codebehind. In this case, the databinding is one way only. That is, the UI does not change the Cell instance. The DataContext of, in this case, a button, is merely some object instance that has implemented the INotifyPropertyChanged interface. When a property changes in the DataContext, it is reflected in the UI. For a more detailed explanation of WPF data binding see Data Binding on MSDN. Please note that implementing the INotifyPropertyChanged interface is not required for data binding, but this allows changes to a DataContext to be reflected in the UI. A single Orpius.Sokoban.Game instance is used for the life of the application. It is specified in XAML as the following excerpt shows:

<Sokoban:Game x:Key="sokobanGame"/>

When the MainWindow is initialized, an instance of the Game class is created and made available as a window resource. We are then able to arbitrarily bind data to the instance, as shown in the following excerpt:

<Label Name="label_Moves" Style="{StaticResource CenterLabels}" 
    Content="{Binding Level.Actor.MoveCount}"/>

Here, the Level is a property of the Game Window.Resource just mentioned. The Game instance is also used in the codebehind, and is privately exposed as a property like so:

Game Game
{
    get
    {
        return (Game)TryFindResource("sokobanGame");
    }
}

Sokoban Project

All game logic is contained within the Orpius.Sokoban project. This approach was chosen to provide clear separation of game logic and presentation logic, so that we may easily reuse the game logic for a technology other than WPF.

Game Logic Overview

Figure: Class diagram providing an overview of the relationships between the main Sokoban project classes

Cells

As the previous diagram shows, a Game has, at most, one Level at any time. Each Level has a collection of Cells, with each Cell having zero or one CellContents instances.

The Cell is the base implementation for all cells used in the game.

Figure: Cell class and concrete implementations

Cell contents

A Cell may hold a single instance of the CellContents class. That is, an Actor or a Treasure may be present in a cell at any one time. Not both.

Figure: CellContents base class and its two concrete implementations: Treasure and Actor

Command Manager

Each modification of the Game instance in the presentation layer project is done via a CommandBase instance passed to the CommandManager, and is an implementation of the Command Pattern. This allows us to undo and redo moves that the actor has performed. A Jump is considered a single command, and thus is undone in a single step. The CommandManager maintains a Stack of undoable and redoable commands.

Figure: Class diagram of the CommandManager and related classes

Moves

Moves are delivered to the Actor instance. The actor knows how to perform a move, whether it is a move to an adjacent cell, or a jump to a non-adjacent cell somewhere on the level.

The number of moves is accumulated by the Actor instance. A jump is considered to be a set of moves, and therefore a jump will increase the number of moves by one or greater. Undoing a move or jump decreases the move count accordingly.

Figure: MoveBase class and associated concrete classes

Jumping and Path Searching

A Jump is executed by the Actor instance with the help of a PathSearch instance. The PathSearch attempts to recursively locate the shortest path to the Jump.Destination location. The recursive path search method is presented here:

bool Step(Location location, int steps)
{
    bool found = false;
    steps++;

    if (location.Equals(destination))
    {
        if (minSteps == 0 || steps < minSteps)
        {
            route = new Move[steps];
            minSteps = steps;
            foundPath = true;
            arrayIndex = minSteps - 1;
        }
        else
        {
            return false;
        }
    }
    else
    {
        for (int i = 0; i < 4; i++)
        {
            Direction direction = GetDirection(i);
            Location neighbour = location.GetAdjacentLocation(direction);

            int traversedLength = traversed.Count;

            if (level[neighbour].CanEnter
                && IsNewLocation(neighbour)
                && Step(neighbour, steps)) /* Recursive call. */
            {
                route[arrayIndex--] = new Move(direction);
                found = true;
            }
            traversed.RemoveRange(traversedLength, 
                traversed.Count - traversedLength);
        }
        return found;
    }
    return foundPath;
}

The efficiency of this method should be improved. For levels with large open areas, it is too slow. It has been listed as a future enhancement.

Expression Design and Resource Dictionaries

Expression Design was used to create all of the images seen in the game.

Figure: Expression Design

Rather than mocking up the whole game board in Photoshop, I chose to experiment with the design within Expression Design and export it as I went. It was certainly less efficient doing it this way, as time was wasted exporting and viewing repeatedly. The process was somewhat streamlined though: by exporting as a Resource Dictionary one is able to create a brush for each layer in the document.

Figure: Exporting with Expression Design

Within the App.xaml file, a ResourceDictionary element was created for each Expression Design exported document.

<Application.Resources>
    <ResourceDictionary>
        <ResourceDictionary.MergedDictionaries>
            <ResourceDictionary Source="ResourceDictionaries/Cell.xaml" />
            <ResourceDictionary Source="ResourceDictionaries/Banner.xaml" />
        </ResourceDictionary.MergedDictionaries>
    </ResourceDictionary>
</Application.Resources>

Then a cell could be styled within a trigger, like so:

<Setter Property="Fill" Value="{StaticResource WallCellBrush}"/>

Points of Interest

Asynchronous Property Changes

There are two actions that take place within the application that occur asynchronously. The first is level loading. In order to compensate for slow loading of map file data, such as in a web application, loading of level data is done asynchronously. The second is that in order to simulate the actor walking across a level, when a Jump occurs, the executing thread needs to be put to sleep for a specific duration. This is also done asynchronously. As with Windows Forms programming, WPF uses a single thread of execution with thread affinity. The base class for Cell and CellContents is LevelContentBase. This class provides for the raising of the PropertyChanged event asynchronously; not using the main UI thread. This is done by initialising a SynchronizationContext instance with the SynchronizationContext.Current property during instantiation, and sending calls to the main UI thread as shown in the following excerpt from LevelContentBase.cs.

context.Send(delegate
{
    OnPropertyChanged(new PropertyChangedEventArgs(property));
}, null);

Level Codes

Level codes are used to jump to a level after it has been successfully completed. The LevelCode class has 500 pregenerated level codes available. Although there are only 51 levels, if more level files are added (*.skbn files in the Levels directory), the level codes will open up. There are some static methods in the LevelCode class to regenerate the level codes if necessary.

Future Enhancements

Improve efficiency of search path algorithm. It doesn't work well with large open areas
Add some animation to actor/cubes etc.
Create a level editor

Conclusion

The aim of this project was to explore WPF, and to employ some of the new language features of C# 3.5 including extension methods, and automatic properties, and object initialisers. WPF makes it remarkably easy to rapidly create complex GUI interfaces, without having to write lots of plumbing code. In my next article, I intend to port "Alien Sokoban" to Silverlight.

I hope you find this project useful. If so, then you may like to rate it and/or leave feedback below.

Credits

FlashKit for some royalty free sound effects clips:
- Movement from NEO Sounds
- Dull Clapping

References

Sacha Barber, 24 October 2007, WPF: The Classic Snakes WPF'ed
Retrieved on 30 October 2007 from The Code Project
Microsoft, 2007, Data Binding Overview
Retrieved on 28 October 2007 from MSDN
Microsoft, 2007, Data Templating Overview
Retrieved on 28 October 2007 from MSDN

History

November 2007: First release
15 June 2008: Improved path search algorithm and graphics.

License

This article, along with any associated source code and files, is licensed under The BSD License

About the Author

Daniel Vaughan

Mvp

Daniel has been developing software professionally for nine years, and is based in Geneva Switzerland and Prague in the Czech Republic.

Daniel is currently seeking expressions of interest from prospective employers in either Geneva/Lausanne (CH) or Prague (CZ).

Daniel's Blog

Occupation:	Software Developer (Senior)
Location:	Australia

WPF Alien Sokoban

Contents