Click here to Skip to main content
15,861,125 members
Articles / Desktop Programming / WPF
Article

WPF Alien Sokoban

Rate me:
Please Sign up or sign in to vote.
4.88/5 (44 votes)
16 Jun 2008BSD9 min read 124.9K   3.4K   78   13
A fun implementation of the game Sokoban, written to showcase some features of WPF, C# 3.0, Expression Design, and Visual Studio 2008.
Screenshot - WpfSokoban.jpg

Contents

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:

XML
<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.

XML
<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:

XML
<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:

XML
<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:

C#
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

Sokoban project class diagram
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.

Cell Class Diagram
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.

Cell Contents Class Diagram
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.

Command Manager Class Diagram
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.

Move Class Diagram
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:

C#
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.

Expression Design Cell
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.

Expression Design Export
Figure: Exporting with Expression Design

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

XML
<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:

XML
<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.

C#
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

References

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


Written By
Engineer
Switzerland Switzerland
Daniel is a former senior engineer in Technology and Research at the Office of the CTO at Microsoft, working on next generation systems.

Previously Daniel was a nine-time Microsoft MVP and co-founder of Outcoder, a Swiss software and consulting company.

Daniel is the author of Windows Phone 8 Unleashed and Windows Phone 7.5 Unleashed, both published by SAMS.

Daniel is the developer behind several acclaimed mobile apps including Surfy Browser for Android and Windows Phone. Daniel is the creator of a number of popular open-source projects, most notably Codon.

Would you like Daniel to bring value to your organisation? Please contact

Blog | Twitter


Xamarin Experts
Windows 10 Experts

Comments and Discussions

 
QuestionXAML designer Pin
Sergey Arhipenko9-Jan-08 3:21
Sergey Arhipenko9-Jan-08 3:21 
GeneralRe: XAML designer Pin
Daniel Vaughan9-Jan-08 3:30
Daniel Vaughan9-Jan-08 3:30 
GeneralRe: XAML designer Pin
Sergey Arhipenko9-Jan-08 3:51
Sergey Arhipenko9-Jan-08 3:51 
GeneralRe: XAML designer Pin
Daniel Vaughan9-Jan-08 17:23
Daniel Vaughan9-Jan-08 17:23 
GeneralI say old sport Pin
Sacha Barber8-Nov-07 3:13
Sacha Barber8-Nov-07 3:13 
GeneralRe: I say old sport Pin
Daniel Vaughan8-Nov-07 13:57
Daniel Vaughan8-Nov-07 13:57 
GeneralRe: I say old sport Pin
Sergey Arhipenko8-Jan-08 22:25
Sergey Arhipenko8-Jan-08 22:25 
GeneralRe: I say old sport Pin
Daniel Vaughan8-Jan-08 23:13
Daniel Vaughan8-Jan-08 23:13 
GeneralRe: I say old sport Pin
Sergey Arhipenko9-Jan-08 0:52
Sergey Arhipenko9-Jan-08 0:52 
GeneralRe: I say old sport Pin
Daniel Vaughan9-Jan-08 2:41
Daniel Vaughan9-Jan-08 2:41 
Sergei,

Yes, I like what you’ve done. Don’t get me wrong, it’s good.
Your library does have a lot more features than the code I whipped up.
I like how you’ve added the convenient property changes. That’s cool.
I look forward to seeing more articles from you in the future. You’re obviously someone who is thinking deeply about the best implementation. I like that. Smile | :)

Daniel



Daniel Vaughan


LinkedIn Profile
ShelfSpy

GeneralI like this, but then I would Pin
Sacha Barber1-Nov-07 6:00
Sacha Barber1-Nov-07 6:00 
GeneralRe: I like this, but then I would Pin
Daniel Vaughan1-Nov-07 14:03
Daniel Vaughan1-Nov-07 14:03 
GeneralRe: I like this, but then I would Pin
Sacha Barber1-Nov-07 22:06
Sacha Barber1-Nov-07 22:06 

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

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