Introduction
This article shows how to create a causal (easy, simple, and fun) puzzle game in managed code for Windows Mobile devices. This example was developed with Visual Studio 2008, in C#. The resulting executable is targeted for Windows Mobile 5 devices or later with the .NET Compact Framework 3.5 installed. With minor changes, it should be backward compatible with earlier Windows Mobile devices. As the SoundPlayer
class is new to the .NET Compact Framework 3.5, the sound routines will need to be rewritten using another method.
What you can expect to learn from this article:
- Puzzle algorithms
- Integer array to screen coordinate to control coordinate mapping
- Using
Point
and Stack<>
classes
- A little graphics and sound programming
I read an article on CNN about the game Trism and its developer, Steve Demeter, who made a quarter of a million dollars within a few months of releasing this iPhone based game. Wow. Nice work Steve! With all of the press his game received at the time, he probably made another quarter million.
As you can see, developers are making hundreds of thousands of dollars for software like Trism, Jawbreaker, and Bejeweled. Whether the game has sliding triangles, colored balls, flashy jewels, or other graphical objects, when all the bells and whistles are removed, these games are really just a handful of common algorithms acting upon a matrix of integers!
Soon after reading the article about Trism, I received a Microsoft Mobile email mentioning CodeProject's Microsoft Mobile Developers Contest. I figured I'd give developing a casual puzzle game a try. The following game, Fruit Drop, is the fruit (pun intended) of my labors.
Fruit Drop
Fruit Drop is a Jawbreaker, Bubble Breaker, and/or Bubblet type game.
Game Play
The randomly generated game board is made up of a matrix of images of various fruits. There are five different fruit images: cherries, bananas, grapes, oranges, and strawberries. The player clicks on the fruit images where two or more fruits of the same type are adjacent in either a vertical or horizontal pattern. The more fruit images removed at the same time, the more points that are earned.
The game ends when there are no more like fruit images adjacent to one another.
Scoring
The points awarded are expressed in the formula: points awarded = (Images Removed)2. Hence, the more like fruit images removed at the same time, the higher the resulting score will be. For example:
The Code
Generating the Game Board
There are many ways to generate a pseudo-random game board. Here are three simple methods to do it.
The first basic method is to loop through each game board position, one position after another, generating a pseudo-random number between one and the number of fruit images inclusive. This method is relatively fast, but may generate a game board where there are many more of one fruit image than another. In fact, it is possible, but not very probable, to generate a game board of all one fruit image.
public void InitializeGrid()
{
for(int x=0; x < MAX_X; ++x)
{
for(int y=0; y < MAX_Y; ++y)
{
m_PuzzleGrid[x, y] = m_Random.Next(1, 6);
}
}
}
The second basic method is to calculate the number of positions in the matrix and divide that number by the number of fruit images. Then, loop through each fruit image, putting the correct number of that fruit image in pseudo-random, unoccupied positions on the game board. This method will put an equal amount (or close to it, depending on if the number of cells divided by the number of fruit images is a whole number) of each fruit image on the game board, but may take a while to generate the game board, trying to find random, unoccupied positions for each fruit image.
A colleague of mine, Sam Domenico, brought up a third method of randomly generating a game structure. While not used in this game, it also provides for a balanced game data structure, and in the best-case, compared against method two above, it will execute much faster. It requires a little more setup, so in the worst-case, it would execute slightly slower than method two.
When comparing method three against method two, the best case for method three would be if method two goes into an almost endless loop trying to locate an unoccupied position for any remaining values. The worst case for method three would be if method two simply finds an unoccupied position for each value on the first try.
This method requires unwrapping the two dimensional game data structures into a one dimensional collection of objects, where each object contains an x, y, and a value member. Initialize this collection so that each object has an x and y value that corresponds to a position in the game data structure. Then, loop through the collection, picking a random index from the remaining objects in the list, update the object at that position, then move the object at that position to the end of the list, and decrement the count of available objects to choose from. Each object can only be randomly chosen once. Once the loop is complete, map the collection back into the game data structure.
Consider the following console code and output:
class Program
{
public class CCell
{
public int X;
public int Y;
public int Value;
}
private static readonly int MAX_X = 8;
private static readonly int MAX_Y = 8;
private static Random m_random = new Random();
static void Main(string[] args)
{
int[] aValueArray = new int[MAX_X * MAX_Y];
for (int x = 0; x < aValueArray.Length; ++x)
{
aValueArray[x] = (x % 4) + 1;
}
List<CCell> aPlacementList = new List<CCell>();
for (int x = 0; x < MAX_X; ++x)
{
for (int y = 0; y < MAX_Y; ++y)
{
CCell aCell = new CCell();
aCell.X = x;
aCell.Y = y;
aCell.Value = 0;
aPlacementList.Add(aCell);
}
}
int aPlacementListCount = aPlacementList.Count;
int aValueArrayIndex = 0;
while (aPlacementListCount > 0)
{
int aSelectedIndex = m_random.Next(0, aPlacementListCount);
CCell aCell = aPlacementList[aSelectedIndex];
aPlacementList.RemoveAt(aSelectedIndex);
aCell.Value = aValueArray[aValueArrayIndex];
aPlacementList.Add(aCell);
aValueArrayIndex++;
--aPlacementListCount;
}
int[,] aGameStructure = new int[MAX_X, MAX_Y];
for (int x = 0; x < aPlacementList.Count; ++x)
{
CCell aCell = aPlacementList[x];
aGameStructure[aCell.X, aCell.Y] = aCell.Value;
}
for (int y = 0; y < MAX_Y; ++y)
{
for (int x = 0; x < MAX_X; ++x)
{
Console.Write(aGameStructure[x, y].ToString() + " ");
}
Console.WriteLine();
}
}
}
For simplicity and speed, Fruit Drop uses the first method discussed above, though the second or third method would probably be better choices for a more balanced game.
Rendering the Screen
The game board is rendered by looping through each cell in the puzzle matrix, determining the correct image to display by inspecting the cell value. Each image is then mapped to its correct position and drawn on the screen.
pbGameBox.Image = m_Bitmap;
Image aGameBoxImage = this.pbGameBox.Image;
using (Graphics g = Graphics.FromImage(aGameBoxImage))
{
for (int aRow = 0; aRow < BOARD_MAX_HEIGHT; ++aRow)
{
for (int aColumn = 0; aColumn < BOARD_MAX_WIDTH; ++aColumn)
{
switch (m_PuzzleGrid[aColumn, aRow])
{
case 0:
g.DrawImage(pbZero.Image,
new Rectangle(aColumn * IMAGE_MAX_WIDTH, aRow *
IMAGE_MAX_HEIGHT, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
new Rectangle(0, 0, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
GraphicsUnit.Pixel);
break;
case 1:
g.DrawImage(pbOne.Image,
new Rectangle(aColumn * IMAGE_MAX_WIDTH, aRow *
IMAGE_MAX_HEIGHT, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
new Rectangle(0, 0, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
GraphicsUnit.Pixel);
break;
case 2:
g.DrawImage(pbTwo.Image,
new Rectangle(aColumn * IMAGE_MAX_WIDTH, aRow *
IMAGE_MAX_HEIGHT, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
new Rectangle(0, 0, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
GraphicsUnit.Pixel);
break;
case 3:
g.DrawImage(pbThree.Image,
new Rectangle(aColumn * IMAGE_MAX_WIDTH, aRow *
IMAGE_MAX_HEIGHT, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
new Rectangle(0, 0, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
GraphicsUnit.Pixel);
break;
case 4:
g.DrawImage(pbFour.Image,
new Rectangle(aColumn * IMAGE_MAX_WIDTH, aRow *
IMAGE_MAX_HEIGHT, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
new Rectangle(0, 0, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
GraphicsUnit.Pixel);
break;
case 5:
g.DrawImage(pbFive.Image,
new Rectangle(aColumn * IMAGE_MAX_WIDTH, aRow *
IMAGE_MAX_HEIGHT, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
new Rectangle(0, 0, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
GraphicsUnit.Pixel);
break;
case 9:
g.DrawImage(pbPop.Image,
new Rectangle(aColumn * IMAGE_MAX_WIDTH, aRow *
IMAGE_MAX_HEIGHT, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
new Rectangle(0, 0, IMAGE_MAX_WIDTH, IMAGE_MAX_HEIGHT),
GraphicsUnit.Pixel);
break;
}
}
}
}
Sound
As the .NET Compact Framework version 3.5 supports the SoundPlayer
class, this method is used for generating the game sounds. One issue I ran into is that the first time a sound is played, there is a noticeable pause in the screen rendering. To mitigate this annoyance, I used GoldWave to create a WAV file with two seconds of silence, which is loaded and played during the form load event. This 'primes the pump' for future sounds.
The game sounds are embedded in the Resources.resx file. These resources are then converted to MemoryStream
s, and played as needed.
if (m_IsSoundOn)
{
try
{
m_SoundPlayer.Stop();
m_SoundPlayer.Stream = new MemoryStream
(com.langesite.fruitdrop.Properties.Resources.Quiet);
m_SoundPlayer.Load();
m_SoundPlayer.Play();
}
catch (Exception e)
{
MessageBox.Show(e.Message);
}
}
Adjacency Search Algorithm
The most interesting algorithm in this game is the 'Adjacency Search Algorithm.' This algorithm looks at the player selected fruit image and all of the necessary adjacent fruit images, to determine which fruit images should be removed.
The 'Adjacency Search Algorithm' follows the following pattern:
A Stack<>
of Point
objects is used to implement the 'Adjacency Search Algorithm'. Once the player clicks on an image, the cell location of that image is pushed onto the stack by using a Point
object to hold the coordinates of the cell. Once the first point is pushed onto the stack, a loop is executed that tests and updates points in the stack until the stack is empty.
The pseudo-code looks something like:
- The player clicks on cell (3,3)
- Cell (3,3) is pushed on the stack
- The cell (3,2) to the NORTH of cell (3,3) is tested for extreme bounds and passes
- The cell (3,2) to the NORTH of cell (3,3) is tested for image type and passes
- The cell (3,2) to the NORTH of cell (3,3) is tested for non-visited and passes
- The last checked direction for cell (3,3) is saved, and cell (3,2) is marked as visited and pushed on the stack
- The cell (3,1) to the NORTH of cell (3,2) is tested for extreme bounds and passes
- The cell (3,1) to the NORTH of cell (3,2) is tested for image type and fails
- The direction of inspection for cell (3,2) is changed to EAST
- The cell (4,2) to the EAST of cell (3,2) is tested for extreme bounds and passes
- The cell (4,2) to the EAST of cell (3,2) is tested for image type and passes
- The cell (4,2) to the EAST of cell (3,2) is tested for non-visited and passes
- The last checked direction for cell (3,2) is saved, and cell (4,2) is marked as visited and pushed on the stack
- The cell (4,1) to the NORTH of cell (4,2) is tested for extreme bounds and passes
- The cell (4,1) to the NORTH of cell (4,2) is tested for image type and passes
- The cell (4,1) to the NORTH of cell (4,2) is tested for non-visited and passes
- The last checked direction for cell (4,2) is saved, and cell (4,1) is marked as visited and pushed on the stack
- The cell (undefined) to the NORTH of cell (4,1) is tested for extreme bounds and fails
- The direction of inspection for cell (4,1) is changed to EAST
- The cell (5,1) to the EAST of cell (4,1) is tested for extreme bounds and passes
- The cell (5,1) to the EAST of cell (4,1) is tested for image type and fails
- The direction of inspection for cell (4,1) is changed to SOUTH
- The cell (4,2) to the SOUTH of cell (4,1) is tested for extreme bounds and passes
- The cell (4,2) to the SOUTH of cell (4,1) is tested for image type and passes
- The cell (4,2) to the SOUTH of cell (4,1) is tested for non-visited and fails
- The direction of inspection for cell (4,1) is changed to WEST
- The cell (3,1) to the WEST of cell (4,1) is tested for extreme bounds and passes
- The cell (3,1) to the WEST of cell (4,1) is tested for image type and fails
- All directions for cell (4,1) have been tested, so pop it from the stack and continue testing the next cell on the stack
- Cell (4,2) is now at the top of the stack, and its last checked direction is NORTH
- The direction of inspection for cell (4,2) is changed to EAST
- The cell (5,2) to the EAST of cell (4,2) is tested for extreme bounds and passes
- The cell (5,2) to the EAST of cell (4,2) is tested for image type and passes
- The cell (5,2) to the EAST of cell (4,2) is tested for non-visited and passes
- The last checked direction for cell (4,2) is saved, and cell (5,2) is marked as visited and pushed on the stack
- The cell (5,1) to the NORTH of cell (5,2) is tested for extreme bounds and passes
- The cell (5,1) to the NORTH of cell (5,2) is tested for image type and fails
- The direction of inspection for cell (5,2) is changed to EAST
- The cell (undefined) to the EAST of cell (5,2) is tested for extreme bounds and fails
- The direction of inspection for cell (5,2) is changed to SOUTH
- The cell (5,3) to the SOUTH of cell (5,2) is tested for extreme bounds and passes
- The cell (5,3) to the SOUTH of cell (5,2) is tested for image type and fails
- The direction of inspection for cell (5,2) is changed to WEST
- The cell (4,2) to the WEST of cell (5,2) is tested for extreme bounds and passes
- The cell (4,2) to the WEST of cell (5,2) is tested for image type and passes
- The cell (4,2) to the WEST of cell (5,2) is tested for non-visited and fails
- All directions for cell (5,2) have been tested, so pop it from the stack, and continue testing the next cell on the stack
- Cell (4,2) is now at the top of the stack again, and its last checked direction is EAST
- The direction of inspection for cell (4,2) is changed to SOUTH
- The cell (4,3) to the SOUTH of cell (4,2) is tested for extreme bounds and passes
- The cell (4,3) to the SOUTH of cell (4,2) is tested for image type and fails
- The direction of inspection for cell (4,2) is changed to WEST
- The cell (3,2) to the WEST of cell (4,2) is tested for extreme bounds and passes
- The cell (3,2) to the WEST of cell (4,2) is tested for image type and passes
- The cell (3,2) to the WEST of cell (4,2) is tested for non-visited and fails
- All directions for cell (4,2) have been tested, so pop it from the stack, and continue testing the next cell on the stack
- Cell (3,2) is now at the top of the stack again, and its last checked direction is EAST
- The direction of inspection for cell (3,2) is changed to SOUTH
- The cell (3,3) to the SOUTH of cell (3,2) is tested for extreme bounds and passes
- The cell (3,3) to the SOUTH of cell (3,2) is tested for image type and passes
- The cell (3,3) to the SOUTH of cell (3,2) is tested for non-visited and fails
- The direction of inspection for cell (3,2) is changed to WEST
- The cell (2,2) to the WEST of cell (3,2) is tested for extreme bounds and passes
- The cell (2,2) to the WEST of cell (3,2) is tested for image type and passes
- The cell (2,2) to the WEST of cell (3,2) is tested for non-visited and passes
- The last checked direction for cell (3,2) is saved, and the cell (2,2) is marked as visited and pushed on the stack
- The cell (2,1) to the NORTH of cell (2,2) is tested for extreme bounds and passes
- The cell (2,1) to the NORTH of cell (2,2) is tested for image type and fails
- The direction of inspection for cell (2,2) is changed to EAST
- The cell (3,2) to the EAST of cell (2,2) is tested for extreme bounds and passes
- The cell (3,2) to the EAST of cell (2,2) is tested for image type and passes
- The cell (3,2) to the EAST of cell (2,2) is tested for non-visited and fails
- The direction of inspection for cell (2,2) is changed to SOUTH
- The cell (2,3) to the SOUTH of cell (2,2) is tested for extreme bounds and passes
- The cell (2,3) to the SOUTH of cell (2,2) is tested for image type and fails
- The direction of inspection for cell (2,2) is changed to WEST
- The cell (1,2) to the WEST of cell (2,2) is tested for extreme bounds and passes
- The cell (1,2) to the WEST of cell (2,2) is tested for image type and fails
- All directions for cell (2,2) have been tested, so pop it from the stack, and continue testing the next cell on the stack
- All directions for cell (3,2) have been tested, so pop it from the stack, and continue testing the next cell on the stack
- Cell (3,3) is now at the top of the stack again, and its last checked direction is NORTH
- The direction of inspection for cell (3,3) is changed to EAST
- The cell (4,3) to the EAST of cell (3,3) is tested for extreme bounds and passes
- The cell (4,3) to the EAST of cell (3,3) is tested for image type and fails
- The direction of inspection for cell (3,3) is changed to SOUTH
- The cell (3,4) to the SOUTH of cell (3,3) is tested for extreme bounds and passes
- The cell (3,4) to the SOUTH of cell (3,3) is tested for image type and fails
- The direction of inspection for cell (3,3) is changed to WEST
- The cell (2,3) to the WEST of cell (3,3) is tested for extreme bounds and passes
- The cell (2,3) to the WEST of cell (3,3) is tested for image type and fails
- All directions for cell (3,3) have been tested, so pop it from the stack
- The stack is now empty
Updating the Game Board
Once the 'Adjacency Search Algorithm' completes, if any cell other than the initial cell is marked as 'visited', then the initial cell is marked as 'visited' as well. All cells marked as 'visited' are removed, if there are any.
Dropping the Fruit
Any fruit images that now have empty cells below them 'drops' through the empty cells, according to the PerformDrop
algorithm:
for (int aRow = BOARD_MAX_HEIGHT - 1; aRow > 0; --aRow)
{
for (int aColumn = 0; aColumn < BOARD_MAX_WIDTH; ++aColumn)
{
while (m_PuzzleGrid[aColumn, aRow] == 9)
{
for (int aMoveRow = aRow; aMoveRow >= 0; --aMoveRow)
{
if (aMoveRow > 0)
{
m_PuzzleGrid[aColumn, aMoveRow] =
m_PuzzleGrid[aColumn, aMoveRow - 1];
}
else
{
m_PuzzleGrid[aColumn, aMoveRow] = 0;
}
}
}
}
}
for (int aColumn = 0; aColumn < BOARD_MAX_WIDTH; ++aColumn)
{
if (m_PuzzleGrid[aColumn, 0] == 9)
{
m_PuzzleGrid[aColumn, 0] = 0;
}
}
Removing Empty Columns
In the case where a full column of cells has been emptied, all columns to the left of the empty column will move to the right one (or more) columns, creating one (or more) empty columns at the extreme left of the game board.
while (aCurrentColumn > aZeroColumnInsertedCounter)
{
for (int aCurrentRow = 0; aCurrentRow < BOARD_MAX_HEIGHT; aCurrentRow++)
{
if (tGrid[aCurrentColumn, aCurrentRow] > 0)
{
aNonzeroCounter++;
}
}
if (aNonzeroCounter > 0)
{
aCurrentColumn--;
aNonzeroCounter = 0;
}
else
{
for (int aMoveColumn = aCurrentColumn; aMoveColumn > 0; aMoveColumn--)
{
for (int aMoveRow = 0; aMoveRow < BOARD_MAX_HEIGHT; aMoveRow++)
{
tGrid[aMoveColumn, aMoveRow] = tGrid[aMoveColumn - 1, aMoveRow];
}
}
for (int aZeroRow = 0; aZeroRow < BOARD_MAX_HEIGHT; aZeroRow++)
{
tGrid[0, aZeroRow] = 0;
}
aZeroColumnInsertedCounter++;
}
}
Checking for the Game Over State
After each move, the code must check to see if the game is over, that is, check if there are anymore adjacent like fruit images. This is rather simple to implement in a couple of loops.
First, check for horizontal matches by looping through each row of the matrix, checking to see if the row contains two like fruit images adjacent to each other in a horizontal pattern. If any two like fruit images are adjacent in a horizontal pattern, then the algorithm is done, and the vertical pattern does not need to be checked.
for (int aImageType = 1; aImageType <= 6; ++aImageType)
{
for (int aRow = 0; aRow < BOARD_MAX_HEIGHT; ++aRow)
{
int aMatchCount = 0;
for (int aColumn = 0; aColumn < BOARD_MAX_WIDTH; ++aColumn)
{
if (m_PuzzleGrid[aColumn, aRow] == aImageType)
{
++aMatchCount;
}
else
{
aMatchCount = 0;
}
if (aMatchCount > 1)
{
aReturnVal = true;
}
}
}
}
Second, if needed, check for vertical matches by looping through each column of the matrix, checking to see if the column contains two like fruit images adjacent to each other in a vertical pattern. The vertical check algorithm is very similar to the horizontal check.
As soon as either condition is true, the algorithm is short-circuited, and the game continues. If both conditions are false, then there are no more available moves, and the game is over. These algorithms need only check for two adjacent like fruit images, and not 'two or more', as two adjacent like fruit images satisfies the definition of a move.
Game Resources
The graphics for this game were downloaded from molotov.nu, specifically the Town tiles of the Angband Graphics set. The author of this graphics collection seems to be unknown, and according to the site, are in the public domain. The downloaded graphics were than manipulated with Paint.Net, Microsoft Paint, and/or Microsoft Visio.
The sounds for this game were created with GoldWave, and download from freesound.org.
Additional Notes
Fruit Drop was developed in Visual Studio 2008, in C#. Even though it was intended for Windows Mobile, it started as a full .NET Framework application as, in my opinion, it is much easier and faster to develop and test a Windows application due to screen real estate and the lack of the need to deploy to a device or emulator during testing. Once I was satisfied with the major game algorithms, I simply added a Windows Mobile project to the solution and copied the code over.
Once the code was copied to a Windows Mobile project and tweaked to compile in the .NET Compact Framework, I was surprised at how slow it ran. It now took two to three seconds to remove adjacent like fruit images when clicked. Ugh! This made the game unplayable.
To speed up the game play, I first tried to shrink the size of the playing field by going from 12 columns and 12 rows of dynamically generated colored balls to 8 columns and 8 rows of dynamically generated colored balls, thinking that this would increase the speed of all game algorithms, which are mostly loops with a Big-O of N2. This change did not have much of an effect, it was still unplayable.
My next change was to switch from using dynamically generated colored balls to using five preloaded (picture boxes) images of fruits. This achieved the speed of game play that I was looking for.
Conclusion
This game was obviously based on Jawbreaker. Fruit Drop was simply a vehicle to demonstrate some puzzle game algorithms in managed code.
With an original idea, or by recycling an existing idea and adding some new interesting features, a creative developer can craft a fun casual puzzle game with acceptable playability in managed code for the Windows, Windows Mobile, mobile phones, or other platforms.
References
Revision History
- 12-02-2008
- Added third game board generation method and code snippet.
- 11-29-2008