Project Examples: A Sudoku Solver Implementation

While on vacation in Florida, I got a bit restless during some downtime and broke out Visual Studio in order to see if there was anything I wanted to try and program. One of the ideas that came up was a Sudoku solver.

The project took a day or so to code. The goals of this implementation were, to establish a proof-of-concept:

1. Store a Sudoku puzzle in computer memory.

2. Access the Sudoku puzzle and display it on the screen.

3. Create and implement an algorithm to solve a Sudoku puzzle that a user inputs.

These goals were all met with the project. The implementation was written in C++ and uses a command-line interface to interact with the user.

In order to show off what this implementation can do, I took some screenshots. The puzzle used in this example is located here: http://www.sudoku.ws/extreme-20.htm

Here is what the user sees when the program is started. There is a blank Sudoku grid and a menu of options. The user can input a puzzle either 1 number at a time, or iterate through each spot and input the entire puzzle. I prefer option 1 to enter my puzzles.

When option 1 is selected, you are prompted to enter a value for each spot at (x, y) on the coordinate system. At any time, the user may stop entering new numbers, which will take him back to the main menu.

Here is my screen after I finished entering the puzzle. The puzzle values are displayed along with the main menu. From here, if we were trying to solve the puzzle manually, we can use option 4 to view a list of candidate numbers for a certain spot.

In this screen, I elected to view the candidate list for spot (1,1) on the Sudoku grid. The program calculates the valid candidates and returns the list for display. This information is helpful for those trying to manually solve the puzzle.

Finally, the option that is the backbone of the entire project, is the automated solver. I selected the automated solver and it returned 1 solution. This solution matches exactly with the posted solution on the web-site that provided the test puzzles. If there were more than 1 solution, the user has the option of viewing them 1 at a time in a slide-show format. At any time, the user may select the solution he wishes to do more work with  and that puzzle is then brought back to the main menu. This feature should be of help to Sudoku puzzle designers as they can see how removing numbers from the puzzle impacts the candidate lists for each spot.

The command line implementation utilizes a greedy algorithm and recursion to solve the puzzle. The first thing the solver does is scan the grid to determine which spot has the least amount of valid candidate numbers. From here, the solver simply inputs the first candidate and then repeats the process. When a puzzle becomes unsolvable, where an empty spot has no valid candidates, control is simply returned to a previous spot, and the next valid candidate is attempted. The algorithm has O(n ^ 2) time complexity due to the nested loops within each recursive call, but there is an upper limit since each Sudoku puzzle has, at maximum, 81 empty slots.

If you would like to try out the solver, I have uploaded it to Google Drive. Simply download the Sudoku solver and run it on your PC.

The next stage of this project is to implement the SudokuPuzzle class in a Windows form application that will allow us to create a GUI (graphical user interface) in order to allow easier puzzle input. I would also like the option to save and load puzzles for the application.

If you would like to see the source code for the SudokuPuzzle class, it is available here. The class contains the solver method.

Algorithms: Reverse a String when Given a Pointer to the First Character

First, my code. Then, the explanation.

void reverse(char* str)
{   
    if (str == NULL || *str == '\0') return;

    char *tail = str;

    while (*tail != '\0')
    {
        tail++;
    }

    char tempChar;
    tail--;

    while (str < tail)
    {
        tempChar = *tail;
        *tail = *str;
        *str = tempChar;
        str++;
        tail--;
    }

    return;
}

What does the above function do? Well, if you paid attention to the title, or if you can read C++, this should be fairly obvious.

The method in question is called reverse and passed to the method is the sole pointer to a string. This method assumes that the string in question will be a basic ASCII string that is null terminated. In fact, that what '\0' represents. The null terminator.

Where are the comments? Well, since the code is fairly simple, and after reading a blog essay by Steve Yegge, the comments were left out. The essay in question is here: Portrait of a N00b. I'll forgive the perceived insult because Steve Yegge is right: I'm a n00b. Besides, had I documented the method with enough comments to double the line-count, I wouldn't be able to write a descriptive blog post about my thought process going into the method, now, would I?

The original problem once again comes from McDowell (2012).

Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string.

 Now, that question seems pretty straightforward. The author's solution given in the book is a little different from mine in trivial items. The logic is exactly the same. That made me very proud, until Mr. Yegge reminded me that I am still a n00b at programming compared to a two-decade veteran who has worked for Amazon and Google. Again, not insulted, but now blissfully aware of how much harder I need to study outside of and in addition to my core classes at Baker College if I ever hope of landing an offer with one of the Big Four.

Had this been an actual interview question, I would have asked a few questions before coding this. Because these questions are from an interview preparation book, I can not unfortunately ask any questions, but only make assertions. From the problem, the string is known to be null-terminated. What I did not know was what encodings this method should handle. My assertion was the string would be a basic ASCII string and not Unicode. I would have also asked if I was allowed to declare additional pointers and variables within the method. My assertion was that I was allowed to. The reason I would have asked this question is that I've seen message board postings with a similar problem that gives the same method signature, but adds the qualifier that no additional pointers or variables may be declared. This solution came together in ten minutes, and was tested in two. Had this been an actual interview, I would have been able to write it, test it, and explain what I was doing within the confines of the interview. If I was not able to declare any local pointers or temporary variables, this would have taken much longer and probably would have overran the time constraints of said interview.

Starting off, the first line of code is just basic optimization. If we were given a pointer that points to NOTHING, or to a null-terminator character itself, it means we have no string to work with. Nothing more is needed, so we return the control to the calling method. The method signature also states we return nothing, hence no error code such as "return 1;".

Yes, Mr. Yegge, I am a two-year old explaining how this big scary programming world works so that I know I understand it. At least I'm following one of your blogging rules, which is write a blog. :D

The next line declares a new pointer called tail and sets it to the address of the same starting character pointed to by str. So far, the time complexity of the method is O(1).

From here, we need to increment the tail pointer in order to find the null-terminator character. After that, we decrement the tail pointer so that it points to the last non-terminator character in the string. This loop changes the method time complexity to O(n) where n is the number of characters in our string. I saw no reason to limit how large the string can be that is passed. If I had, I would have kept track of how many times we incremented the tail pointer and then checked to see if the string fell into the confines of our arbitrary limit.

Now that the tail is found, we simply switch the first character, pointed to by str, and the last character, pointed to by tail. Now, we increment str and decrement tail, so that they both move toward the middle of the string, and swap each character again. We keep doing this until str and tail are at the same memory address or have passed each other. This means that the entire string is now reversed.

The overall time complexity of the method reduces to O(n). This means it scales linearly as the number of characters in the string gets larger. I see no way to make this O(1) constant time. If any industry veteran out there is reading this and knows a trick to do so, please feel free to share. I love it when n00bs like me are mentored.

The code I provided is my own code. It is not elegant, but simply straightforward. I chose to implement a "quick and dirty" solution rather than trying to hack the compiler to achieve the fastest possible run time. Depending on the project, "quick and dirty" may have saved the company some money by not devoting days to optimizing something that shouldn't break the overall project.

If this does break the project, then methinks I'm doomed...

Reference:

McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions (5th ed.). Career Cup: Palo Alto.

Algorithms: Design an Algorithm to Determine if there are Repeating Characters in a String

Lately, I've been practicing coding techniques by taking a look at different coding problems available for those preparing for computer science positions. The practice problem I worked on today involves both algorithm design and coding. The problem comes from Gayle Laakmann McDowell's Cracking the Coding Interview.

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

The  first thing I did was start thinking about possible ways to solve this. For the example, I am using C++. C and C++ recognize a string as an array of characters. If I was given this problem as part of an interview, I would ask if the string would be passed in ASCII or in another format. For this example I am assuming that all characters are ASCII.

My first algorithm is a straightforward, brute force approach. Basically, we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop.

bool noRepeatingCharacters(string myString)
{
    for (int x = 0; x < myString.length(); x++)
    {
        for (int y = 0; y < myString.length(); y++)
        {
            if (myString[x] == myString[y] && x != y) return false;
        }
    }
    return true;
}
 
This code is very simple, but there are some problems. First, comparisons are repeated. Let's say we have a string of five characters, and the string is "ABCDE". On the first iteration, we will compare A to B, then to C, then to D, then to E. On the second iteration, we will compare B to A, then to C, then to D, then to D. Do you see how the comparison between A and B is repeated on the second iteration?

We can optimize this code a bit by altering the loops so that each character is only compared to every character AFTER it. This would mean that once A is compared to all the other characters, the other characters never compare themselves to A again.

bool noRepeatingCharacters(string myString)
{
    for (int x = 0; x < myString.length() - 1; x++)
    {
        for (int y = x + 1; y < myString.length(); y++)
        {
            if (myString[x] == myString[y]) return false;
        }
    }
    return true;
}

This code is a bit better than the previous code since we avoid repeated comparisons. The number of comparisons made with a string with n characters is (n - 1) + (n - 2) + (n - 3) + ... + (1). With a string of 5 characters, this would mean 10 comparisons, or 4 + 3 + 2 + 1. This algorithm works if I am not allowed to use any additional data structures.

I came up with another solution that is even faster, but it is only faster at the expense of memory. By using an additional data structure, we can speed up comparisons. How? By using a hash table. Each character can be cast to an integer in order to determine its ASCII value. We can use that integer as a hash key inside an array that serves as a hash table. The array itself can be made up of boolean values for quick comparisons.

bool noRepeatingCharacters(string myString)
{
    /*
    This is a hash table algorithm. This will speed up comparison times by 
    using a 128 slot hash table based on the ASCII encoding of each char
    in the string. The index number matches the ASCII decimal value. If a
    character is in the string, then its ASCII slot is marked true. If
    another character collides with that slot, then the function returns
    false. If no collisions are detected, the function returns true.
   
    The hash table uses more memory than the brute force algorithm, but
    comparison time is drastically improved.
    */

    bool myHashTable[256] = {false};
    int myIndex;

    for (int x = 0; x < myString.length(); x++)
    {
        myIndex = int(myString[x]);
        if (myHashTable[myIndex]) return false;
        else myHashTable[myIndex] = true;
    }
    return true;
}

This is much better than the brute force algorithm. The time complexity for comparisons becomes O(n). The memory requirements for the hash table is constant. As long as memory is not a concern, this algorithm will give us a much better comparison time.

In order to validate that both algorithms work correctly, I wrote a short testing method that will take in a user-defined string, determine if there are repeating characters in the string, and then pause to show the results. Here is the full code for the exercise:

//Cracking the Coding Interview
//Chapter 1: Problem 1
//
//Design an algorithm to determine if a string has all unique characters.
//What if you cannot use additional data structures?
//
//Solution by Brandon Theolet
//December 20, 2012

#include <iostream>
#include <string>

using namespace std;

bool noRepeatingCharacters(string myString);

void main()
{
    //Method to test the algorithm.

    string myString;
    cout << "Please enter any phrase: ";
    cin >> myString;
    cout << "\n";
    if (noRepeatingCharacters(myString)) cout << "There are no repeating characters in this string.\n\n";
    else cout << "There are repeating characters in this string.\n\n";
    system("pause");
}

bool noRepeatingCharacters(string myString)
{
    /*
    This is a hash table algorithm. This will speed up comparison times by
    using a 256 slot hash table based on the ASCII encoding of each char
    in the string. The index number matches the ASCII decimal value. If a
    character is in the string, then its ASCII slot is marked true. If
    another character collides with that slot, then the function returns
    false. If no collisions are detected, the function returns true.
   
    The hash table uses more memory than the brute force algorithm, but
    comparison time is drastically improved.
    */

    bool myHashTable[256] = {false};
    int myIndex;

    for (int x = 0; x < myString.length(); x++)
    {
        myIndex = int(myString[x]);
        if (myHashTable[myIndex]) return false;
        else myHashTable[myIndex] = true;
    }
    return true;
}

/*

bool noRepeatingCharacters(string myString)
{
    //This is a brute force implementation that uses no additional data structures.
    //Instead, two loops will iterate through the string and compare all chars
    //to every other char in the string AFTER the starting char. This is to avoid
    //repeating comparisons. If a match is found, the function returns false. If
    //the entire string is compared and no matches were found, the function returns
    //true.

    for (int x = 0; x < myString.length() - 1; x++)
    {
        for (int y = x + 1; y < myString.length(); y++)
        {
            if (myString[x] == myString[y]) return false;
        }
    }
    return true;
}

*/

Update: The author of the text proposed another solution that I had not considered with this problem. The solution involved first sorting the string. A well-implemented quicksort algorithm would sort the string in O(n log n) time on average. For comparisons of unique characters, the ordering of the string does not need to be preserved. Once the string is sorted, we can simple iterate through the sorted string, starting at the first character, and comparing this character to the character in the next index. If any neighboring characters are equal, we have non-unique characters in the string.

Another point the author made that I did not consider in my solution involved optimization. If we assume that the ASCII encoding was used to pass the string, then at most there can be 256 characters, which is one unique character for every possibly ASCII character. Thus, if we pass in a string with more than 256 characters, we can assume that at least one is repeated and then return an appropriate value from the function. This optimization would involve O(1) time, or constant time, for strings that were longer than 256 characters. Improving on this idea, I imagine we could also involve error checking where we would throw an error if we received an empty string.

Game Design: Static vs. Random Content

Looking through GameFAQS.com today got me thinking about static content and random content. In terms of game design, what are they?

Static content never changes in a game, no matter how many times it is played. It can be a level design, enemy placement, or a puzzle. Most games released in the past typically use static content. Static content still makes up a large majority of games released today.

Random content is procedurally generated based on some input seed. Computers cannot generate truly random numbers, but can come close enough by taking an input value that is hard to control, such as the time of day down to the second, and using it to generate a predictable value based on a random number generation algorithm. This means a game can change the content it presents based on any number of input values. Level designs can change, enemy placement can change, and even the starting state of a puzzle can change.

Both methodologies have advantages and disadvantages. Replay value of a game is one area that is affected by the choice of using static content or random content. For illustration purposes, let's take a look at Resident Evil, originally released on the PSX in 1997. The game state is the same each time it is played. Each item and enemy is in the same spot each time it is played. Each time the game is played, it becomes easier for the player to plan and map out his approach since he knows what to expect. When using randomized content, such as the case in Diablo, released for the PC in 1996, this is not the case. Diablo features randomized dungeon layout, randomized enemy locations, and randomized item placement and drops. Each time the player plays through this game, he is limited in planning his approach. He can set up his character for different possibilities, but does not know the absolute layout of the dungeon or the absolute enemy positioning. Even though games like Diablo feature randomized level layouts and enemy positioning, the game still gets easier each time it is played. The player does not know the absolute enemy positions, but he should get a general idea of the general enemies he will face in each area of the game. The Butcher, for example, is a boss character that is always found on the second level of the Cathedral. As we discussed earlier, randomized content is not truly randomized but rather procedurally generated by a computer in order to appear random.

Some games attempted to blur the line between static content and random content. Resident Evil 3 was the first Resident Evil game to feature variable enemy placement and item placement in a static world. Some puzzles could also have different starting states, requiring game guides to determine multiple solutions for the player seeking assistance. Unfortunately, Resident Evil 3 only included two or three states or locations for puzzles and items that featured random placement. After two or three plays, the player would likely see all configurations for each design.

Some independent games, such as Dwarf Fortress, like to be as random as possible. Upon setting up a game in Dwarf Fortress, the game prompts the player to generate a new world. Dwarf Fortress uses various algorithms to model terrain and then flesh out multiple generations of history for this world. Races rise and fall, erosion and weather changes the landscape, and characters end up migrating to end up in a different area of the world than when they started. Once this world generation is completed, it is open for the player to explore however he wishes. There is very little guidance and limitless options about where to travel, where to build, and who to talk to. The downside of this level of randomness is the lack of structure to the game. Many players are put off by the lack of guidance and abandon the game due to this. Imagine spending five hours building a character in Adventure Mode and then running across an enemy that is far too strong. The character is now dead, and in Dwarf Fortress, death is permanent. This level of freedom and unpredictability appeals to a niche genre of gamers, but is not for everybody.

When designing a game, you need to be aware of your audience. You also need to be aware of your game genre. Some genres do not require any sort of randomized content. Sports games should have schedules and rosters that mimic the real world. They should not be jumbled up as this can lead to clustering of star players on few teams, lending those teams an unfair advantage, and an unrealistic schedule. This may put off a large number of fans that would prefer to play a game this is closer to their actual sport. RPGs on the other hand lend themselves well to randomly generated content. Many RPG fans enjoy games that offer a high degree of replayability. This does not mean that RPGs should all be randomized, though. Replayability can still be offered through branching storylines that requires many playthroughs before the player is able to see all options.

The real challenge for determining whether to use static content or randomized content comes in determining what your target audience wants and striking a balance between fun and difficulty. Games that are randomized to a high degree are usually more difficult than games that feature static content. The player is not able to plan a specific approach since level design and enemy placement is not static. The player also has no ideas which item he will find or need for specific areas, or if his character is even strong enough to survive an area. Guides written for randomized content will be vague when compared to guides written for games with static content.


Static content versus random content is an important design decision. It affects many facets of game, from replayability to difficulty to target audience. The choice needs to be made at the design stage in order to get the team on the same page. Static content is easier to develop and implement, but may be harder to change. Once the static content is implemented into a game, changing it would mean a new design for the entire area. Randomized content is harder to develop, but once fully implemented can be easily changed by changing specific inputs. Games that use both need to be designed very carefully in order to prevent static events from being broken by randomized content.

In terms of game design, I believe a mix is best for most games that have the option to implement either. Good games feature guidance that is appropriate for the target audience. If the target audience is sandbox gamers, then very little guidance is needed. If the target audience is young children, then a high level of guidance needs to be implemented.

The only area of game design where I like to seen purely randomized content is concerning game puzzles. Most RPGs, shooters, and action and adventure titles feature them. Most of them are static, and are easily solved with the assistance of a game guide. I believe puzzles should be designed better than bring key A to lock B. A puzzle should be self-contained and started in a randomized initial state. Take the example of the "Lights-Out!" inspired door lock from Resident Evil. The puzzle has the player hit buttons on a 3 by 3 keypad. Each time a button is hit, its state is switched from lit to blacked out or vice versa. All surrounding buttons are also switched, similar to the children's puzzle game "Lights-Out!". The puzzle is solved the same way each time. If the player found a note earlier in the game, the key code to solve the puzzle is given. This puzzle can be initialized to a random starting state each time the game is played, and the note can be generated to give a solution to each generated puzzle. This would prevent players from being able to breeze through the puzzle without finding the note or at least taking time to think about their moves before touching the key pad. Guides would also be unable to assist the player by providing the definitive answer. Instead, guides would need to switch to teaching the players  how to think and solve the puzzle for themselves. If this turns off too many players, then the game designer may need to revisit including puzzles in the game in the first place.

Project Examples: SWF Illustrating the Star, Starfield, and MessageBoxManager Classes

Here is an extremely early build for the game engine for Salvager: A Dredger's Tale. This build uses the Star, Starfield, and MessageBoxManager classes discussed and shared in previous posts. This build merely moves the game camera down and then creates a new message on the screen every few seconds. This is a build illustrating how to use the MessageBoxManager to show the main title and how to use the Star and Starfield classes to create a simple animated background.


 

Related posts:

• Flash Game Programming: Adding objects to the main stage from a child object.
• Code Examples: Starfield and Star Classes
• Flash Game Programming: Treating Game Messages Similarly to Particles with a Life Timer
• Code Examples: MessageBoxManager Class

Code Examples: MessageBoxManager Class

This example code for Actionscript 3.0 is the class I wrote titled MessageBoxManager. The description for this example is in this post: Flash Game Programming: Treating Game Messages Similarly to Particles with a Life Timer .

If you would like to see this class used in a small project, go here:  Project Examples: SWF Illustrating the Star, Starfield, and MessageBoxManager Classes.

package  {
  
    import flash.display.*;
    import flash.text.*;
    import flash.events.*;
  
  
    public class MessageBoxManager extends MovieClip {
      
        //This variable keeps track of how long the message is displayed.
        private var displayTimer: int;
        //This variable keeps track of how long since the message was created.
        private var timeSinceCreated: int;
        //A text field container to hold the messages.
        private var thisTextField:TextField;
        //A TextFormat object to alter the appearance of the text as needed.
        private var thisTextFormat:TextFormat;
        //A Boolean variable to notate if the message should not dissapear in a few seconds.
        private var permaDisplay: Boolean;
      
        public function MessageBoxManager() {
          
            //Constructor function to initialize the variables.
            thisTextField = new TextField();
            thisTextFormat = new TextFormat();
            permaDisplay = false;
            thisTextField.border = true;
            thisTextField.borderColor = 0x00FF00;
            thisTextField.width = 630;
            thisTextField.height = 100;
            thisTextField.alpha = 0;
            thisTextField.textColor = 0x00FF00;
            thisTextField.embedFonts = true;
            displayTimer = 0;
            thisTextField.x = 5;
            thisTextField.y = 10;
            thisTextField.alpha = 0;
          
            //When this object is added to the stage by the parent class, call the function
            //that draws the text box on the screen.
            this.addEventListener(Event.ADDED_TO_STAGE, DrawMessageBox);
          
        }
      
        public function DrawMessageBox(event:Event){
          
            //This object has been added to the stage by the parent.
          
            //Remove the event listener.
            this.removeEventListener(Event.ADDED_TO_STAGE, DrawMessageBox);
          
            //Draw the message box on the stage.
            parent.addChild(thisTextField);
        }
      
        public function addNewMessage(myMessage:String, size:int, font:String, seconds:int, alignment:String, permaDisplay:Boolean) {
          
            //Add a new message to the text box.
          
            //Set the display timer for the number of frames to show the message.
            this.displayTimer = 60 * seconds;
            this.timeSinceCreated = 0;
          
            //Determine which alignment to use. The parent class uses string constants to pass this
            //information quickly and easily.
            switch (alignment) {
                case "center": thisTextFormat.align = TextFormatAlign.CENTER; break;
                case "left": thisTextFormat.align = TextFormatAlign.LEFT; break;
                case "right": thisTextFormat.align = TextFormatAlign.RIGHT; break;
                case "justify": thisTextFormat.align = TextFormatAlign.JUSTIFY; break;
            }
          
            //Set the permanent display option if the message needs to stay on the screen.
            this.permaDisplay = permaDisplay;
          
            //Set the font. The parent class uses string constants to pass in the embedded font
            //quickly and easily.
            thisTextFormat.font = font;
          
            //Set the size.
            thisTextFormat.size = size;
          
            //Set the format properties to the text.
            thisTextField.defaultTextFormat = thisTextFormat;
          
            //Add the text to the text box and end the line with a newline character.
            thisTextField.appendText(myMessage + "\n");
        }
      
        public function clearMessages() {
            //Clear the text box.
            thisTextField.text = "";
            this.permaDisplay = false;
        }
      
        public function updateMessages() {
          
            //This function is called every frame.
          
            //Decrement the displayTimer variable.
            displayTimer--;
            timeSinceCreated++;
          
            //Set the limits for each timer variable.
            if (displayTimer < 0) {displayTimer = 0;}
            if (timeSinceCreated > 60) {timeSinceCreated = 60;}
          
            //If permaDisplay is true, give 1 second of life.
            if (permaDisplay == true) {displayTimer = 60;}
          
            //Determine the visibility of the text box. If the text box has less than 1 second
            //to live, gradully fade it out.
            if (timeSinceCreated < 60) {thisTextField.alpha = timeSinceCreated / 60;}
            else {thisTextField.alpha = displayTimer / 60;}
        }
    }
  
}

Code Examples: Starfield and Star Classes

 This code example contains the full Actionscript 3.0 code for the Starfield and Star classes discussed in this post: Flash Game Programming: Adding objects to the main stage from a child object.

If you would like to see these classes used in a small project, go here: Project Examples: SWF Illustrating the Star, Starfield, and MessageBoxManager Classes.

The Starfield class:

package
{

    import flash.display.*;
    import flash.events.*;

    public class Starfield extends MovieClip
    {
        //This class manages all of the Star objects displayed on the game screen.
       
        //Array to hold the Star objects.
        private var myStarfield:Array = new Array;
        //Integer to notate the number of Star objects to create.
        private var numberOfStars:int;
       
        public function Starfield(numberOfStars: int)
        {
            //Constructor initializes the class and waits for the object to be drawn on the main stage.
            this.numberOfStars = numberOfStars;
            this.addEventListener(Event.ADDED_TO_STAGE, DrawStarfield);
        }
       
        public function DrawStarfield(myEvent: Event): void
        {
            //The Starfield object has been added to the stage by its parent. We now create and draw
            //the Star objects.
           
            //Remove the event listener.
            this.removeEventListener(Event.ADDED_TO_STAGE, DrawStarfield);
           
            //Temporary variables to create and display the Star objects.
            var thisIndex:int;
            var thisStar:Star;

            //Loop to iterate the creation and display of each Star object.
            for (thisIndex = 0; thisIndex < numberOfStars; thisIndex++)
            {
                //Create a new Star object.
                thisStar = new Star(Math.random() * 640,Math.random() * 480, Math.random() * 3 + 1);
               
                //Add the Star object to the parent's stage.
                parent.addChild(thisStar);
               
                //Add the Star object to the reference array for the Starfield object.
                myStarfield.push(thisStar);
            }
        }
       
        public function UpdateStarField(cameraX:int, cameraY:int) {
           
            //Update all stars being managed by the object based on the change in game camera position.
           
            //Temporary variables to point to each Star object and update it.
            var thisIndex:int;
            var thisStar:Star;
           
            //Loop to access each Star object in the reference array.
            for (thisIndex = 0; thisIndex < myStarfield.length; thisIndex++)
            {
                //Point to the Star object in the reference array indicated by thisIndex.
                thisStar = myStarfield[thisIndex];
               
                //Update the Star object's position based on the change in the game camera and the Star object's layer.
                thisStar.x = thisStar.x - (cameraX / thisStar.getZDistance);
                thisStar.y = thisStar.y - (cameraY / thisStar.getZDistance);
               
                //If the Star object goes off screen, recycle it by wrapping it on the screen.
                if (thisStar.x > 640) {thisStar.x = 0;}
                if (thisStar.x < 0) {thisStar.x = 640;}
                if (thisStar.y > 480) {thisStar.y = 0;}
                if (thisStar.y < 0) {thisStar.y = 480;}
            }
        }
    }

}


The Star class:

package
{

    import flash.display.*;

    public class Star extends MovieClip
    {
        //This class defines the properties of a Star object used to make the scrolling background
        //on the main stage.
       
        //Integer to determine which layer of the background the Star object is in.
        private var zDistance:int;
       
        public function Star(xPos: int, yPos: int, zDistance: int)
        {
            //Constructor to initialize the Star object.
           
            this.x = xPos;
            this.y = yPos;
            this.alpha = .25 * (4 - zDistance);
            this.zDistance = zDistance;
        }
       
        public function get getZDistance():int {
           
            //This get function returns the integer variable zDistance. We use it to determine
            //which layer the Star object is in. The layer determines the brightness of the star
            //and how fast it will scroll as the game camera changes positions.
           
            return this.zDistance;
        }
    }

}

Flash Game Programming: Treating Game Messages Similarly to Particles with a Life Timer

I love particle engines. We can accomplish so many interesting graphical effects using particles with relatively minimal code. This is because the class definition for the behavior of a particle is minimal but we leverage the power of object oriented design principles to create a complex system. The behavior of any one particle is easy to predict, but the behavior of hundreds of these objects acting at the same time is difficult to predict.

On the other hand, we can also use design patterns similar to particle engines to create a remarkably simple device to manage lots of data.One element that is present in most particle designs is a timer that keeps track of how long a particle has to live before it is released from memory. I will use this design technique in order to simplify the adding and removing of game messages in the game engine for Salvager: A Dredger's Tale.

In the game, one of my classes that I created manages in-game messages. The title of the class is MessageBoxManager. The class holds a standard text-box, a TextFormat object alter the appearance of the text, a variable to keep track of how long the message should be displayed if on a timer, a variable to keep track of how long since the message was created, and a Boolean flag that marks whether or not the message box should acknowledge the timer and just stay visible until the player wishes to close the messages.

What use is this class? In order to script in-game events, one of the issues that needs to be dealt with is to create a mechanism to easily display game messages. These messages can be hints, data from the game engine such as damage dealt on each successful hit, or even dialogue from a non-player character. This mechanism will accept strings that need to be displayed to the player and put them in the game environment on the stage.

The last post outlined how to add display objects to the main stage from a class that is a child of the class that directly references the stage. I have used a similar technique here. The constructor initializes the variables and sets an event listener to execute a method as soon as the object is added to the stage. The main class adds the object to the stage, and the method within the child class executes to add all relevant display objects to the stage by referencing its parent. I know that sounds confusing, so check out my previous post for clarification on how to do this and why we have to do this: Flash Game Programming: Adding objects to the main stage from a child object.

The class creates a text box and edits the display attributes in order to make it match the game content. The visual style is simple retro-style vector graphics. Everything is typically green or white on a black background. A method is created in order to accept a string and then append this string to the text box. We also accept various arguments to this method. One such argument is the number of seconds that the message box should be displayed for. For most quick messages, 3 seconds is the standard time. Since the project is set to run in the Flash environment at 60 fps, we simply assign the timer variable the argument value multiplied by 60.

How do we get the message box to go away without losing any data contained within? The Flash environment makes this very easy. Every display object has an alpha property which determines transparency. This value can be any value from 0 to 1. 0 means the object is entirely transparent and 1 means the object is entirely opaque. I treat the message box like one big particle here. On every frame, when the method that handles updating the message box is called, we set the alpha property of the message box itself. I use a simple formula.


          displayTimer--;

          thisTextField.alpha = displayTimer / 60;

What happens here? We set the alpha property of the text box based on how long the display timer has left. Remember, when we created a message, we passed in a value that told the manager how long we wanted it to be visible by. If the value passed was 3 seconds, then timeToLive was set to 180. Since 180 divided by 60 is 3, the alpha property of the box is set to 1. That means it is opaque. Every frame, that variable is decreased by 1. For two seconds, the box is completely opaque. Then, during the last second that it's to be shown, the box slowly fades until it becomes invisible on the main stage. For example, let's say that timeToLive is equal to 30 frames. It has half a second to live. It will also be at half transparency, since 30 divided by 60 is one half. The alpha property will always be set to 1 if the value of timeToLive divided by 60 is 1 or greater than 1. Once we get below 1 second of life left, it will start to fade as the alpha property is set to the appropriate decimal between 0 and 1.

Notice how easy this technique is. We don't add a new text box each time we create a message. We also don't have to worry about removing old text boxes from the stage and deallocating the memory. The text box inside the manager class is added once and only once. It is never removed. We simple remove it from sight, but the other display properties such as the text inside that container as well as the on-screen position do not change.

When we have an event, such as the player pressing the console key to bring up a history of recent messages, we can set the Boolean flag to display the message box constantly to true. Here, we simply have to add an additional line of code.

            if (permaDisplay) {displayTimer = 60;}

Each frame, the timer will be given 1 second to live. This will keep the alpha property of the text box at 1. We have to make sure that this line comes after the line that decrements the displayTimer variable so that the alpha property of the text box is always set to 1. One the flag is set back to false, the message box will fade out over the course of 1 second.

The full code to the MessageBoxManager class is posted here: Code Examples: MessageBoxManager Class.

Flash Game Programming: Adding objects to the main stage from a child object.

When it comes to object oriented design principles, Flash and Actionscript 3.0 do things a little differently. My current project, Salvager: A Dredger's Tale, ran into an early hurdle. While trying to keep true to the object oriented design principle of encapsulation, I discovered that adding items to the stage became a bit convoluted when trying to do so from a child of the parent class where the stage was instantiated.

Most of the rendering is being done through Actionscript classes rather than animated MovieClip objects. I still use MovieClip objects as the containers for my classes, but most of them have no graphics. The reason is that MovieClips are easily linked to ActionScript classes and provide easy access from within the Flash IDE.

In the IDE, the stage is linked to its own ActionScript 3.0 file. This main class instantiates the other classes I've written. From the main class, adding a display object to the stage is as easy as using the addChild function. Trying to add an object from a child class was a bit of a challenge.

For this example, I will use my classes Star and Starfield. Star is a MovieClip that contains a 1 frame graphic of a star. The MovieClip is linked to an ActionScript file. The Star definition includes the x position of the object, the y position of the object, and an integer from 1 through 3 to notate the depth layer. Starfield is a class that was designed to manage all the Star objects on the main stage that will make up the background. There are 300 Star objects on the main stage, and using Starfield as a manager class to update all of them during gameplay keeps the main class neat and tidy.

When Starfield is instantiated, it creates 300 Star objects. Their position on the screen is set. Their brightness is determined by their depth layer. A depth layer of 1 will be closer to the camera than depth layer 3, and thus brighter. When the game camera moves during gameplay, the Star objects in depth layer 1 will also scroll faster than those in depth layer 3. The objects were originally created in the constructor method for Starfield. I then tried to add them to main stage by using this line.

        parent.addChild(thisStar);

It seemed simple. Starfield is a child of the main class. In the line of code, "parent" references the main class and the addChild() method should push the object pointed to by thisStar onto the stage to display it. The compiler did not like the code.

It turns out that one of the peculiarities of Flash is that an object does not know it has a parent until the object itself has been added to the stage as a display object. Starfield is a manager class and is not a display object by itself, but it is the container for which all the Star objects are held, and those Star objects are display objects.

The workaround for this hurdle is actually quite simple. From the main class, we instantiate the Starfield class and then add that class to the stage.

This is the variable declaration in the main class.

        private var gameStarField:Starfield;

And this is where we instantiate it and add it to the stage.

            gameStarField = new Starfield(300);
            addChild(gameStarField);

But that means we cannot create and draw the Star objects in the Starfield constructor because the constructor must finish executing before Starfield is added to the stage from the main class. To solve this problem, we need to take out all the code from the Starfield constructor and replace it with an event.

        public function Starfield(numberOfStars: int)
        {
            //Constructor initializes the class and waits for the object to be drawn on the main stage.
            this.numberOfStars = numberOfStars;
            this.addEventListener(Event.ADDED_TO_STAGE, DrawStarfield);
        }

The event listener waits until the Starfield object myStarfield is added to the stage in the main program. Once it has been added to the stage, the function CreateStarfield() is called from within the Starfield object. This enables us to now create the number of Star objects we need and then push them onto the main stage so that they are now displayed.

        public function DrawStarfield(myEvent: Event): void
        {
            //The Starfield object has been added to the stage by its parent. We now create and draw
            //the Star objects.
          
            //Remove the event listener.
            this.removeEventListener(Event.ADDED_TO_STAGE, DrawStarfield);
          
            //Temporary variables to create and display the Star objects.
            var thisIndex:int;
            var thisStar:Star;

            //Loop to iterate the creation and display of each Star object.
            for (thisIndex = 0; thisIndex < numberOfStars; thisIndex++)
            {
                //Create a new Star object.
                thisStar = new Star(Math.random() * 640,Math.random() * 480, Math.random() * 3 + 1);
              
                //Add the Star object to the parent's stage.
                parent.addChild(thisStar);
              
                //Add the Star object to the reference array for the Starfield object.
                myStarfield.push(thisStar);
            }
        }

Presto! We can now instantiate the Starfield object myStarfield, add it the stage, and immediately have a method executed that creates all the Star objects and pushes them to the main stage from inside a child object of the main class. Don't forget to remove the event listener once the appropriate method is called. Also don't forget to import the proper package in order to use the ADDED_TO_STAGE event.

If you would like to see the full Actionscript 3.0 code for both the Starfield and the Star classes, they are available here: Code Examples: Starfield and Star Classes.

Prototypes and RetroVector Games

I keep coming across game development pieces and advice columns that state students need to be creating prototypes for games. A writer writes, a developer develops. I have not been following this advice as closely as I should have been.

I am in my senior year of my undergraduate career. Soon I will have the choice of continuing my education or trying to secure a job. If securing a job is anything like securing an internship, then I have a lot of competition from highly regarded universities and experienced developers who have been laid off. In order to be able to compete, I need a portfolio of projects.

Thus far, I have two working projects. One is an XNA project called KLAX'D and is outlined below. The second is a Flash project and is an Asteroids clone. I named it Salvager as the goal of the game is not just survival, but also to break down space debris and collect the pieces once it is safe to do so. This project was a three week part-time endeavor, and I am not happy with the results. If you would like to play this rushed prototype version, you can find it at Kongregate.com: http://www.kongregate.com/games/theo20185/salvager

Since I am not happy with the results of Salvager, I have decided to start fresh on that same project. It will remain a Flash project. I am changing the art style to mimic old school vector arcade platforms. These were the games that drew everything out in monochrome lines. There were even some 3D titles that displayed everything in wireframe.

Why the choice of vector graphics? The reasoning is simple. I am studying to be a game programmer. I am not studying to be a game artist. Using vector graphics will allow me to quickly create needed assets for prototype projects and use them as placeholders. It will also allow me to draw sprites or object wire frame models without embarrassing myself among the artistic side of the industry. My pixel art and textures leave a lot to be desired. Since I have opted to go lean on graphics and focus on programming, I have decided to brand my games using the name RetroVector Games.

What plans do I have for the full version of Salvager? First, I am programming a 2D engine in Flash that will allow me to script enemy behavior and add events and objects to certain spots in the game world. The player will no longer be confined to a small box, but will be able to travel the galaxy in an open-world environment. The new working title for this project is "Salvager: A Dredger's Tale". Yes, this is an homage to classic games such as A Bard's Tale. I want an adventure-style shooter that keeps the mechanics shown in the Salvager prototype and adds new features such as NPC interactions, an upgradeable player ship, and scripted enemies. You can only shoot so many pieces of non-sentient space debris before you go looking for something more challenging.

I've already started on the game engine. In Flash, I've grouped my files into three main folders. Thus far, we have fonts that are embedded into the project, graphics, and classes. I've created blank movie clips and stuck them into the classes folder for easy access to the ActionScript definitions of these objects through the Flash IDE.

Thus far, I have a definition for a game camera, a star, a star field manager, and a message manager. Later in this week, I will make posts concerning these game components and how I've implemented them.

Here's to an official brand for my student game projects! Salvager: A Dredger's Tale will be the first project from RetroVector games. All RetroVector branded games will be projects that are not academic assignments.

Project Examples: Klax'D

It's been more than a month since my last post. I have been extremely busy with college assignments. I thought today was a great day to update my blog. I am pleased to announce my first XNA Game Studio project was turned in for grading, and I would like to share it with all of you as well. The link to the file is included at the end of this post.

Klax was released in 1989 by Dave Akers and Mark Stephen Pierce. It is an action-puzzle game. My first XNA Game Studio project is a version of this game and I titled it Klax'D in homage to the original.

The game world consists of a conveyor belt, a paddle at the end of this belt, and a drop zone. The conveyor belt has five lanes. Bricks spawn at one end of the belt and move towards the end. The player can choose to catch these on his paddle or let them fall into the drop zone. The paddle can stack up to five bricks. The player can either drop the bottom brick or put the bottom brick at the top of the stack. If he drops the brick, it falls into an appropriate lane in the drop zone. The drop zone is able to hold 5 stacks of bricks. Each stack can hold 5 bricks. If a brick falls onto a stack that is full, it's game over. The player can remove bricks from the drop zone by matching like-colors. If three or more bricks with the same color form a line in any direction (vertical, horizontal, or diagonal) then those bricks are removed from the drop zone.

It's a simple game and a good one to code for a starter project. I will not share the source code for this project since I can get in trouble with the school for that, but I will be more than happy to share the finished compiled project. This game requires the appropriate .NET and XNA frameworks, which are included in the file if you don't already have them. The game will run on any Windows computer with a graphics card that is capable of rendering DX9 or higher. Please note this project is not digitally signed, so you should see a message asking if you trust the content of the file during the installation. If you are not comfortable with this, then do not install the game. There is no malware included in this file.

If you have an XNA Creator's Club membership, you can also run this project on your Xbox 360 through XNA Connect. If you want the Xbox version to try on your own console, send me an email and I will send you the .ccgame file to unpack to your Xbox.

Some of the features we focused on for this assignment were using the XNA framework to access the GPU, inclusion of very simple shaders, basic game loop architecture within the XNA framework, and using an established code base and building a game on top of that (for this project, we were given the Game State Management Sample code from the Microsoft Developer Network and used that as the starting framework). I built this game using one 3D model and added additional methods to the Screen class in the GSMS from MSDN.

Please download Klax'D from this link.

What is Dreamer of Worlds?

This is the first post for my blog, "Dreamer of Worlds." This blog will chronicle my journey as I study the art of game design and development.

I am a student at Baker College in Michigan. Baker is the state's largest private college. I am a BCS candidate with a concentration in Game Software Development. I am in my junior year as of this post. I have 100 credit hours completed of the 181 credit hour program with a cumulative GPA of 3.96 on a 4.0 scale.

I've found college to be a challenge. I juggle my classwork with a full time job at North American Bancard and with my two-month old daughter Amelia. I've learned a lot during these past two years, both in and out of the classroom. I hope that I am honing my time management skills to an extent where they will be useful outside of school.

This blog is meant to be an outlet for my thoughts on game design and game development as well as a platform to show off some of my work as I progress through the last two years of my undergraduate degree.

If you are a game designer/developer, or a student planning on entering the game industry, please feel free to send me an email or follow the blog. I'll be sure to return the favor.

-Theo20185