Building a puzzle game using Generics

• Download demo project - 15 Kb
• Download source - 32 Kb

Introduction

The first place that I needed to construct a doubly linked list, I was programming in assembly from Intel. To be honest, in the occasion I had some difficulty in understanding how this type of structure worked. With the time, I had to make the same thing in C and C++. Despite the C# language to be more soft than these others and also to have an excellent library of classes that gives a good support for the user, I believe that some developers can still have some difficulty to understand the functioning of a doubly linked list. Based in this, I decided to create this small game using Windows Form and C# to show, visually, the functionalities offered by classes of Namespace Generic when programming a doubly linked list with generic use. To understand these concepts becomes much more simple its use in the implementation of programs using the C# or other .Net platform language. To run this program you will have to make use of the Visual Studio C# Express or then the Visual Studio 2005 Beta1. You can make download both at http://lab.msdn.microsoft.com

Background

Is there any background to this article that may be useful such as an introduction to the basic ideas presented?

How the game works

To learn with this game is very simple. The Figure 1 shows the initial game form that has two panels and a set of buttons.

The head panel or source pane stores the pieces that will have to be moved to the low panel or target panel, where they must be positioned correctly and, in this in case, to form a word. The source panel represents the shuffled items list and the target panel represents the list where the solution of the game will be mounted. The pieces can be put into motion freely, from a panel to the other, obviously following the existing rules in the use of a linked list. The set of buttons is used to put into motion the pieces. See that the buttons have headings that represent the methods of the generic lists that are used in the program. This way, visually it is easy for who manipulates the game and to know how each method works because each method is being represented visually when a button is pressed. Another interesting point is that, because the program is manipulating lists, some rules have to be followed for the program to run correctly. For example, if the button Add After (It adds Later) is clicked and if there is no pieces in the target panel, the user will receive an error message saying that the program cannot add a piece after another piece, once that still does not exist piece in the target panel. It seems obvious? Yes, but people use not to attempt against these small details.

About the program

Although this project is only to demonstrate some functionalities of the namespace Generic, I decided to make use of some new features existing in the Visual Studio .Net 2005 as the Refactoring to accelerate and standardize the code generation, partial to divide great classes and FxCop to analyze the code and to find points to be corrected. The objective was to have adherence to best practices in programming. The diagram of Figure 2, generated by Visual Studio, shows the architecture diagram used in the program.

As you can see in the diagram, the program uses the class GameForm, GameItems, Item, LinkedItems<T>, and LinkedList<T>.

GameForm Class

The game form is generated by the GameForm class that encapsulates all the functionalities that will allow the user to interact with the game. In the used architecture, this class abstracts the way how the lists that contain the items are managed. This way, when a button is clicked, the control is passed to the GameItems class in the logic layer, which has the function to manipulate the lists adequately. When it is desired to move a piece, the GameForm class needs to know in which of the two panels is the piece in question. For this, the class makes use of the boolean variable named sourcePanelSelectedthat This variable changes according the MouseEnter event that is fired when mouse enters in the region of the panel, as showed in the code below:

Blocks of code should be wrapped in <pre> tags like this:

 
private void sourcePn_MouseEnter(object sender, EventArgs e)
{
         sourcePanelSelected = true;
}
 
private void targetPn_MouseEnter(object sender, EventArgs e)
{
         sourcePanelSelected = false;
}
 

Item Class

This class stores each of the items functionalities like, for instance, the initial position of each piece in the panel, if selected or not, and so on. We will speak more about item selection later on.

LinkedItem<T> Class

This class is derived from LinkedList<T>, as showed in the code:

 
public class LinkedItems<T> : LinkedList<T>
{
         // some code
}
 

This way, we create a generic doubly linked list that can be used to store different types of objects, without the necessity to modify its code. That is why we call a generic list. With the use of Generic Namespace we can build a strongly typed safe list increasing the performance and getting a cleaner code and easy to do maintenance. Despite the LinkedItems class to inherit methods from the base class, I decided to add some functionality to facilitate the pieces manipulation in the game. Also sees that, although some methods accepts parameters overload, these methods work with the node list and, because the GameItems class manipulates only the pieces in lists and not its node, I had to implement methods that accepted only list items and, internally, to call the base class methods that uses node list as parameters. See, for example, the methods AddAfterItem and AddBeforeItem below:

 
public LinkedListNode<T> AddAfterItem(T newItem, T item)
{
        LinkedListNode<T> node = Find(newItem);
        return base.AddAfter(node, item);
}
 
public LinkedListNode<T> AddBeforeItem(T newItem, T item)
{
        LinkedListNode<T> node = Find(newItem);
        return base.AddBefore(node, item);
}
 

The base class methods AddAfter and AddBefore only accept the first parameter as an object of type LinkedListNode. Then it was necessary first to find the node node relate to the item and, only then, to call the base class method. Another method also added to LinkedItems class is the GetSiblingItem method that returns the sibling item relate to the last item, as a reference. This method also has as a second parameter a boolean that indicates if the item to be found is the sibling before or after the reference. You can see in the code below:

 
public T GetSiblingItem(T item, bool forward)
{
        // because the list is doubly linked, we can
        // search the entire list forward and backward, easily
        LinkedListNode<T> node = null;
        
        node = Find(item);
        if (node == null)
           return default(T);
        else
        {
            // look forward
            if (forward)
            {
                node = node.Next;
            }
            // look backward
            else
            {
                node = node.Previous;
            }
        }
        // if not found, return null 
        if (node == null)
            return default(T);
        else
            return node.Value;
}
 

As you can see, one of the great advantages of a doubly linked list is that it can easily be covered forward and backward. In this case, it becomes a great head hatch when in a low-level language, where the programmer must be worried about update all internal pointers correctly, once that it points to forward and backward simultaneously. Any error in the incorrect use of these pointers and your program will be in a wrong way. In C# language, that generates a managed code, you do not have to be aware about these details. Another interesting point of this method is the use of the Nullable<T> class:

 
return default(T);  
 

You can see that, if the item that will be used as a reference can’t be found in the list, the method must return null. The question now is: how to return null for a generic object of type T? If in the code I force the return null, the compiler shows an error message saying that it cannot convert a null type to the type T to be returned. The solution is to use the default value of the type or, default (T). The default value also is known as null value of the type nullable. Here occurs an implicit conversion between the null literal, for any type and, this conversion produces the null value for the desired type.

GemeItems Class

To have a cleaner code in this class, I used some new features from VS.Net 2005 like partial keyword that allows breaking a big class, structure or interface in many files. This class has a fundamental importance about how the program works. The reason is that it will make use of methods exposed by linked list approach. When instantiated, the GameItems class creates two LinketItems<T> lists, that will receive as parameter the Item class, as showed the code:

 
public GameItems(GameForm frm)
{
            //savedItemsLocation = new List<Item>();
            // creates a target linked list
            targetListItems = new LinkedItems<Item>();
            // creates a source linked list
            sourceListItems = new LinkedItems<Item>();
 
            // save the initial appearance of the game
            SaveSourceLocationAndItems(frm);
}
 

You can see that created lists targetListItems and sourceListItems are strongly typed because the parameter is a predefined type. This turns its use much easier because it does not have to use "cast" when getting an element from the list, once that the list only accept a unique list type item. The GameItems class also receives, in its constructor, a reference to the form, that it is passed to the SaveSourceLocationAndItems method, allowing to save the initial positions of all existing parts in the source panel. Another interesting point is that the GameItems class manipulates the game pieces exchanging the pieces between the lists and updating its position, while the GameForm class manipulates the pieces in the panels.

Adding and deleting an item

The procedure to add an item at the beginning or end of a list isl simple and the code is intuitive in this direction. You can see that, to add or delete an element from list, it is necessity to update list pointers, what is done internally by .Net Framework. In a lower level language like C++, C or assembly, this has to be done manually by the programmer. Lets take a look about how to add an item BEFORE another item, as showed the code:

 
public PictureBox AddPieceBefore()
{
            Item selectedSrcItem = null;
            Item selectedTgtItem = null;
 
            // get the selected item in source list
            selectedSrcItem = GetSelectedItem(sourceListItems);
            // get the selected item in target list
            selectedTgtItem = GetSelectedItem(targetListItems);
 
            // if null, needs to select one item
            if (selectedSrcItem != null && selectedTgtItem != null)
            {
                // add item to end list
                targetListItems.AddBeforeItem(selectedTgtItem, selectedSrcItem);
                // remove item from source list
                sourceListItems.Remove(selectedSrcItem);
                // unselect the item
                selectedSrcItem.IsSelected = false;
                selectedTgtItem.IsSelected = false;
 
                // try to shift all items to acomodate the added item 
                Point nextPosition = solutionPosition;
                // update the list
                UpdatePositionForEntireList(targetListItems, nextPosition);
            }
            else
                return null;
            return selectedSrcItem.PicItem;
}
 

When adding an item before another, some conditions have to be satisfied as showed in the code below:

 
if (selectedSrcItem != null && selectedTgtItem != null)
 

The code verifies if exists a selected item to be removed from the source list and if exists a selected item in target list to be used as a reference, as seen in AddBeforeItem method that takes two parameters. If the insert operation success, the item is removed from the source list and the pieces are turned not selected. After the insert, it has still to update the items positions, which is equivalent to update its pointers, as commented above. The UpdatePositionForEntireList method makes this update, accommodating each item in its correct place. The AddAfterItem method has a similar behavior, changing only the place where the insertion will take place, that is, it adds later. See that for the removal methods, a RemoveBefore or RemoveAfter does not exist. Once that the user chooses a piece to be moved, it does not make sense, at least in this program, to have a method that removes the piece from before or after the referenced piece. Of course that, if it was necessary, this could be easily implemented.

Selecting an item

As already commented above, depending on the operation to be executed in the game, it is necessity to select one or two pieces. This selection order is made in theGameForm class by PieceItem_Click method that, in its turn, forward the order to SelectPicItem method in GemeItems class. The change from selected item status is made by IsSelected property in Item class, as showed in the code below:

 
public bool IsSelected
{
            get{ return selected;}
 
            set
            {
                selected = value;
                // if the item is selected, change its appearence
                // to notify the user
                if (selected)
                    item.BorderStyle = BorderStyle.FixedSingle;
                else
                    item.BorderStyle = BorderStyle.None;
            }
}
 

Points of Interest

The project shows in a visual way and by code how is very simple to deal with a doubly linked list using the namespace Generic. The use of a strongly typed list enables a better way to program a system. As the main target was to show in a visual way these concepts, is clear that some improvements could be made if the target was to create a real game. See that, the buttons could simply be removed and the pieces movement could be done exclusively using the mouse. Of course that this sample can be a starting point to a real puzzle game. Enjoy!