The Game (Part 4)

I have implemented the mask and view capabilities.  I’m calling this version 2.  Here’s a sample screenshot of how it looks in action:

The first thing you’ll notice about this map is that unexplored areas are colored in black.  These will uncover as allied units are moved around the map.  The darker areas are areas that are not visible but have been explored.  These areas could have enemy units hiding there.  Every time an allied unit is moved the view map is recomputed in JavaScript (and a duplicate array is maintained in C# in case the player refreshes their browser).  The unexplored areas are initialized at the beginning of the game and are cleared as units are moved.  Both the JavaScript and C# code have functions/methods to deal with this mask.  The difference is that the JavaScript doesn’t maintain an array of cells that are explored because they are just set to hide the mask whenever a unit passes by and they are never set back during the game.
The two masks are identical and use the same image to paint over top of the entire board.  I set the opacity to 0.3 for the view hex pictures so the player can see the terrain under it.  I also manually set the display value of each enemy unit to match the value of the view mask.
Here’s the code: Battlefield One Code V2
You can go directly to my website to play the game as is: (temporarily down).
I’ve played the game a few times and it is a bit more challenging than the first version without the masks.  I think my next enhancement will be adding a variety of different unit types.  I might have to enlarge the playing board to allow more playing pieces.
Stay tuned…
Note: I have recently upgraded my website to use MVC4 and .NET 4.5. I have refactored my code to make the game work on MVC4.  Click here to try it out.

 

Linked Lists – Adding and Deleting

Getting Started

In my last blog post I showed how I setup a basic board game with an array of linked lists.  Now I’m going to show you some straight C code to add a unit to the board.  I used a standard WIN32 console application, just to get past the complex interface code.  My purpose is to show the linked list part. 

First, we’ll need a structure:
 
struct Unit
{
 int Offense;
 int Defense;
 (Unit *) Next;
};

This structure will store the variables that represent the unit offense and defense numbers.  The “Next” variable is a pointer to the next unit node in the linked list.

The game board

The game board is nothing more than a 4×4 array of Unit structure pointers that I declared globally:

Unit * PlayingBoard[4][4];

The problem with this array is that each cell has an unknown value in it.  So we’ll need a function to make sure all cells contain a NULL value to begin with.  I called that function “InitializeBoard()”:

void InitializeBoard()
{
    for (int i=0;i<4;i++)
    {
        for (int j=0;j<4;j++)
        {
            PlayingBoard[i][j] = NULL;
        }
    }
}

Add a Unit

Now, we’ll need a way to add a unit to the board.  I want to set this up so the whole “pointer” arrangement is hidden from the game designer.  I just want to use pointers inside the lowest level functions.  This will prevent someone else from having to do all the allocation and de-allocation when they can just call the low-level functions that create pieces and delete pieces.  So I’m going to use the malloc command in this function to get enough memory to use as my structure.  To make sure I have the exact amount of memory that I need, I used the “sizeof” command with the structure name.

void AddUnit(int pUnitType,int pX,int pY)
{
    int liOffense = 1; // default to soldier
    int liDefense = 1;


    if (pUnitType == 1) // tank
    {
        liOffense = 3;
        liDefense = 5;
    }


    if (pX < 4 && pX > -1 && pY < 4 && pY > -1)
    {
        Unit * p = (Unit *)malloc(sizeof Unit);
        if (p)
        {
            p->Next = PlayingBoard[pX][pY];
            PlayingBoard[pX][pY] = p;
        }
    }
}

Notice how I checked to make sure that the x and y coordinates that were passed in as parameters are within the range of the board.  Don’t assume anything!  I also made sure that the malloc command returned a valid pointer.  If not, then the playing piece will not be added to the board.  There should be a warning message recorded someplace so that it can be checked after testing the game to see if any memory problems had occurred during the game.  If this type of memory problem occurs, then the playing piece won’t show up, but the game will continue to work without crashing.

Delete a Unit

Now, it’s time to delete a unit:

void DeleteUnit(int pX, int pY)
{
    if (pX < 4 && pX > -1 && pY < 4 && pY > -1)
    {
        if (PlayingBoard[pX][pY])
        {
            Unit * p = PlayingBoard[pX][pY];
            PlayingBoard[pX][pY] = p->Next;
            free(p);
        }
    }
}

Again, I checked to make sure that the x and y parameters are inside the actual board.  Then I check to make sure that the element at that grid location is not NULL.  Don’t forget this step, because there might not be a unit at the location that the function wants to delete.  Now for the tricky part.  First we have to assign the top unit (the one linked to the board) to a temporary pointer, that I called “p”.  Then we can assign the board position to the “Next” pointer of that Unit.  This will cause the stack to shift up one.  If “Next” is equal to NULL, then that will just get assigned to the board and no unit is sitting on that board position.  If there is another unit attached to next, then it will get assigned to the board.

The last line will free the temporary pointer to the Unit we’re trying to actually get rid of.  This returns the memory back to the operating system.

Tying it Together
Now, we need to actually write a program that uses all the above pieces.  You’ll need to add a stdlib.h header declaration at the top.  That is where the malloc and free commands reside.  You’ll also need to add any function declarations at the top of your file to make sure they can be called:

#include <stdlib.h>

// function declarations
void InitializeBoard();
void AddUnit(int pUnitType, int pX,int pY);
void DeleteUnit(int pX, int pY);

Then, make sure you call the InitializeBoard() function first.  After this, you can call AddUnit and DeleteUnit for any square on the board.

To download the complete CPP file click here: linked list source code file.

What’s Next?

If you typed in the code above (or copied and pasted), you’ll notice that this is not really a “game” yet.  What it would take to make this into something useful is a few more low level functions.  One function that will be necessary is a complete board clear.  You’ll have to do a while loop on a board cell and call Delete unit until a NULL is detected.  Then do that for every cell.  You could change the DeleteUnit function to return a true/false depending on if the “Next” unit was NULL or not.  That could signify if there are any additional units at that cell.  Then just created a function that calls DeleteUnit until false for each cell.

Other functions needed are a function to render the units on the screen.  This, of course, depends on what you want to be displayed.  If you just want to work on the game engine first and ignore the graphical front end, you can just setup a dumb and dirty text based interface to use symbols to represent each unit on the playing board.  Or you can go for the cool graphics first and get it to look right before you start working on the game AI. 

You’ll need functions to read and write the offense and defense numbers.  Since the top unit is the only unit fighting at a time, then only the top defense and offense matter.  Remember the goal is to keep all the pointer code inside the lowest level units.  Make these units perform the minimum task they need to perform, then do the complicated stuff by calling these functions.

I hope this blog post helps you to learn pointers better. 

 

 

Linked Lists

Basic Unordered Linked Lists

So my last blog posts was about pointers.  I gave a little historical context to the fact that I’m a self-taught pointer maniac.  The past 6 years is the longest stretch I’ve gone without using a pointer.  That is due to the fact that I now program using C# instead of C/C++.  Sometimes I miss pointers.  They’re so powerful.  What I don’t miss about pointers and what I love about C# is the memory management aspect of it all.  That’s why I’m so methodical about assigning nulls and checking before allocating and de-allocating memory.  There are other tests that should be performed as well, and I’m going to talk about it right now.

What happens if your application runs out of memory?  It could happen.  It does happen.  So the C/C++ malloc command has a flag for that, it’s called null.  Yup, you guessed it, when you attempt to allocate a pointer and there is no memory available, the malloc command returns a null pointer.  So always check to make sure the pointer is not null before using it.  Here’s an example from the sample code used in my previous blog post:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer = NULL;
 
    if (!mypointer)

    {
        mypointer = (char *)malloc(1);

        if (!mypointer)
        {
            // perform some sort of error reporting here
            return -1;
        }
    }

    *mypointer=’a’;

    if (mypointer)
    {
        free(mypointer);
        mypointer=NULL;
    }
}


I returned a “-1”, that’s just my return for an error code in this sample.  Your method might not return anything and you might have to exit out of the program entirely.  Anyway, it’s on to linked lists.

What is a Linked List and Why Use them?

So I used to program games as a hobby.  Nothing serious, just a hobby.  I liked to play Avalon board games, mostly World War II style strategy games and I made an attempt at writing a C++ war game with a similar board design.  Here’s what Panzer Blitz looks like:

One of the things I noticed about the hex shaped board locations is that it is really just an array where the odd numbered columns are shifted half way up or down.  Here’s what I’m talking about:


As you can see by the cell numbers the hex board on the left is the same as the shifted square board in the middle and the same as the 4×4 array on the right.  So I used an array to represent the map positions of each piece.

Now, it’s on to the playing pieces.  One of the fun aspects of these types of games is that you can stack pieces.  Here’s a sample picture I found using Google (I’m just trying to avoid dragging out the game and taking photos myself):


This is where pointers become fun.  Yes, I said fun.  But first, it’s time for a little diversion, let me explain what a linked list looks like in an abstract diagram form.

First, I’m going to use structures to store information about each playing piece.  Each tank and soldier (I’m really trying to keep this simple) will have one structure allocated in memory and then I’m going to link them together into little stacks.  Like this:

This is a list of three pieces, two tanks and a soldier.  Inside each structure (not shown) is a variable that is the pointer to the next structure and the last structure points to null.  The variable “P” here is the pointer to the first playing piece in the list.  What I’m going to do here is setup a playing board that has an array of pointers.  Each cell in the array is nothing more than a pointer, then I’ll initialize them all to null.  When I place one or more pieces on the board, I just set one of the array cells to point to the top of the list or stack.  Like this:

Now the basic game structures are setup.  The rendering engine can run through the array and paint the associated background image (which can be stored in a separate array) and if the pointer in this array is not null, then render the top piece offset by the number of pieces in the stack so the height is different depending on the number of pieces. 

When the user drags a stack of pieces, the pointer at the array cell containing the stack can be copied to the new grid location and the old pointer in the array can be set to null.  This will have the effect of moving an entire stack of playing pieces without moving a bunch of data.  Just re-adjusting the cell location of the pointer to the stack.

One of the rules of the game is that the top piece is attacked first.  Once eliminated, then the next piece in the stack is under attack.  So if the top tank in the sample game board above becomes destroyed in game play, then the top tank can be assigned to a temporary pointer, then the game board array cell can point to that tank’s “next” pointer.  Then the first tank can be de-allocated.  Poof, it’s gone:

If the last tank at that grid position is destroyed, then the same exact algorithm can be performed to set the grid to that tank’s “next” pointer and de-allocate that tank.  The “next” pointer just happens to be null, so that board position is now empty and the rendering function will just render the background.

I’m going to wrap this discussion up for now, but next time I’m going to do some example code to demonstrate the basics of how this is all performed.



 

Pointers

Ok, I’m in the mood to do some technical blogging.  I was reading an article recently about the fact that many universities are teaching computer science using languages such as Java that don’t use pointers.  I’m starting to feel like one of those old guys saying things like “back in my day….”.  Here’s the article I was reading a while back: The Perils of JavaSchools.

First, I’m going to give you a bit of history about me.  I spent 6 years of my youth in the Navy as an electronics technician.  During that time I bought a computer that was just small enough to fit in the tech cabinet in the transmitter room (we kept tools and parts in that cabinet and I stored my computer on the bottom shelf).  The computer I bought was an Apple Macintosh.  Oh yeah, “THE” Macintosh.  With a grand total of 128k of memory.  This machine was just enough to wet my appetite for programming.  Of course, I only knew two languages at that time.  The languages I knew were Basic (with line numbers) and 8080 assembly (from a computer board I built by wire-wrapping, I’ll do a post on that later).  Anyway, Basic was very hard to use with line numbers and Apple upgraded the mac to a 512k version within months of my purchase.  So I upgraded my mac and I ran to the Apple store and looked for a new language.  I saw a box of Mac Pascal and the syntax looked very much like Basic, so I bought it.  Oooh, it was really cool and shiny.  Yup, I taught myself Pascal just so I could program games.  I had great ambitions back then.

So I’m writing code for a game I had in mind and suddenly, I discovered that Mac Pascal can only access 32k of global memory.  That was a bummer because I couldn’t store my game board and all the playing pieces in memory.  So I bought some books (yeah, no Google back then, this was 1985 or so) and learned dynamic memory techniques.  This was kind of a no brainer for me due to the fact that I already knew how to program in assembly language for an 8080 processor.  Therefore, I knew all about memory addresses.  The 8080 lacked a lot of features for sophisticated memory addressing, but it did use an H & L register combination to reference memory.

Anyway, back to pointers…

Uber-Simple Pointers

All right, a pointer is basically a memory address.  That’s it.  Nothing more.  The trick is how to work with pointers.  You could just put in a memory address and access the memory, but more than likely, the computer will crash or give you a memory fault.  That’s because the computer uses memory for the operating system and memory to run other things, before your program has a chance to start running.  Only the operating system knows what memory is in use at any given time.  So you have to ask the OS for memory, then the OS will give you an address to the location that you can use. 

Here’s an example of a computer with 10 bytes of memory that is not in use:

Each number represents the address of that memory cell.  To keep this simple, I’m going to ignore the amount of memory allocated at a time and assume that the OS only gives you one cell at a time.  This would not be very useful in reality, but it’s just an example.
So now your program starts and you are about to ask for some memory from the OS.  This is what the memory starts out as:

The gray cells represent the memory cells in use by the OS and your program.  You don’t really care about what memory is in use, because you just want a pointer to one memory cell that you can use.  So you call the “new” or the “malloc” command in C/C++ and you get a pointer to a cell of memory.  A typical program in C++ would look like this:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer;

    mypointer = (char *)malloc(1);
}

Now the character variable “mypointer” is not a character but an address or pointer to a character.  The OS will lookup a blank memory cell, mark it as “in use” and then give your program the address (by use of the malloc() procedure) which is stored in “mypointer”.  So now you’re memory would look like this:

And your variable “mypointer” would contain the address 5.  If you were to print the address by converting the pointer into an integer, you would see the actual address number.  However, you don’t really care what the address number is because “mypointer” will keep that for you and now you can read and write to that address location.  This process is called “allocating memory.”  Now I’m going to add a line of code to put a character into address 5:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer;

    mypointer = (char *)malloc(1);

    *mypointer=’a’;
}

Notice the “*” before the variable “mypointer”?  The star represents “location of” and means that we are putting the character “a” into the memory location that the variable “mypointer” contains.  If you left the star off the beginning of the pointer address, then “mypointer” would be replaced with the ascii value of ‘a’ (technically the compiler should complain that it’s not a number).  Now our memory looks like this:

All right.  I’m almost to the end of the “uber-simple pointer” example.  The final thing you must remember to do is give the memory back to the operating system when you’re finished with it.  Remember, you’re just borrowing the memory, if you don’t give it back, then it can’t be used by any other program running on your computer.  If you keep allocating and don’t give it back, then you’ll create what is called a “memory leak.”  This is where the computer keeps running out of memory because your program is allocating it and not giving it back.

To “de-allocate” memory, you can call the “free” command:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer;

    mypointer = (char *)malloc(1);

    *mypointer=’a’;

    free(mypointer);
}

On last thing.  When you start a program, set your new pointer variables to “null.”  Null is a special memory address (usually zero), that is universally accepted as a pointer that is pointing to nothing.  When you reference a pointer in a function and you’re not sure if it has been allocated yet, you can check to see if it is null first.  Here’s an example:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char * mypointer = NULL;
 
    if (!mypointer)
        mypointer = (char *)malloc(1);

    *mypointer=’a’;

    if (mypointer)
    {
        free(mypointer);
        mypointer=NULL;
    }
}
Notice how C will recognize a null pointer as a false variable.  This example is so tiny that it’s difficult to see the use in performing such extra work, but a large program might have variables declared in a location that is nowhere near where the pointer is allocated.  Using this technique will prevent you from referencing a memory location that is not allocated.  Such bugs are very difficult to find, but a null pointer error is obvious.  Also, notice how I re-assigned null to “mypointer” when I freed it up.  If this pointer is referenced in code after being freed, then the null value will cause your program to bomb and tell you that you made a mistake and used a freed pointer.

Conclusion

Pointers can get tricky, but if you follow the basic rules that I laid about above, you should be able to work through dynamic structures with ease.  In the future I’ll go over some very basic dynamic structures like linked lists and try to make it as simple and visual as possible.  But for now, good luck with your programming.