Saturday, December 27, 2008

(0) Comments

Setting up SDL in Code::Blocks

welcome to infomix.blogspot.com

1)First thing you need to do is download SDL headers and binaries.
You will find them on the SDL website, specifically on this page.

Scroll Down to the Development Libraries section and download the Mingw32 development library


Open gz archive and there should be a *.tar archive inside.
Open the *.tar and there should be a folder inside of that.
Copy that folder anywhere you like. For these tutorials I'm putting it in C:\

2)Start up Code:Blocks and go to the Compiler and Debugger settings.

3)Go to the Compiler tab under Search Directories. Click add:

then add in the include directory from the SDL folder you extracted.




4)Then under the linker tab add in the lib directory from the SDL folder:



5)Now take the SDL.dll from the SDL folder you extracted (it should be inside the bin subfolder) and copy it to where you're going to make your project. You're going to put SDL.dll in the same directory as your exe when you compile it.

Alternatively, you can copy SDL.dll to C:\WINDOWS\SYSTEM32 so your SDL app will find SDL.dll even if it's not in the same directory. The problem with this method is if you have multiple SDL apps that use different versions of SDL, you'll have version conflicts. If you have SDL 1.2.8 in SYSTEM32 when the app uses 1.2.13 you're going to run into problems. Generally you want to have your SDL.dll in the same directory as your executable developing and you'll always want to have SDL.dll in the same directory as the exe when distributing your app.

6)Now start up Code::Blocks and create a new empty project.
Then save the project where ever you want. I know Code::Blocks has an SDL project template, but I personally found it to be more combersome than doing things manually.

7)Next, go to the project -> properties.

8)Under the Build Targets tab, set Type to "GUI application". This is to make sure a console window does not pop up.

9)Go to the Compiler and Debugger settings again and under the Linker Settings tab paste:
-lmingw32 -lSDLmain -lSDL
in Other Linker Options
10)Add a new source file to the project with the following code:
#include "SDL/SDL.h" int main( int argc, char* args[] ) { //Start SDL SDL_Init( SDL_INIT_EVERYTHING ); //Quit SDL SDL_Quit(); return 0; }
Save the source and compile your project. If there are no errors, you're done. Otherwise go back and make sure everything is done. Double check that you have SDL.dll in the same directory as your exe or system32.
Also, In the archive you just downloaded there's a subfolder called "docs". It contains the SDL documentation.

I highly recommend that you extract them somewhere and keep it for reference.
ReadMore...

Saturday, December 27, 2008

(0) Comments

Setting up SDL in Dev C++

welcome to infomix.blogspot.com

1)First thing you need to do is download SDL headers and binaries.
You will find them on the SDL website, specifically on this page.

Scroll Down to the Development Libraries section and download the Mingw32 development library


Open gz archive and there should be a *.tar archive inside.
Open the *.tar and there should be a folder inside of that.
Copy that folder anywhere you like. For these tutorials I'm putting it in C:\

2)Start up Dev C++ and go to the Compiler Options.

3)Go to the Directories Tab and then the C++ include tab. Click the folder icon:

then add in the include directory from the SDL folder you extracted.




4)Then under the libraries tab add in the lib directory from the SDL folder:


5)Now take the SDL.dll from the SDL folder you extracted (it should be inside the bin subfolder) and copy it to where you're going to make your project. You're going to put SDL.dll in the same directory as your exe when you compile it.

Alternatively, you can copy SDL.dll to C:\WINDOWS\SYSTEM32 so your SDL app will find SDL.dll even if it's not in the same directory. The problem with this method is if you have multiple SDL apps that use different versions of SDL, you'll have version conflicts. If you have SDL 1.2.8 in SYSTEM32 when the app uses 1.2.13 you're going to run into problems. Generally you want to have your SDL.dll in the same directory as your executable developing and you'll always want to have SDL.dll in the same directory as the exe when distributing your app.

6)Now start up Dev C++ and start a new empty project.

7)Go to the project options.

8)Under the General tab, set type to Win32 GUI.
This is to make sure a console window does not pop up.

9)Under the Parameters tab, paste:
-lmingw32 -lSDLmain -lSDL
in the linker.

10)Add source new source file to the project.

11)Paste the following code into the new source file:
#include "SDL/SDL.h" int main( int argc, char* args[] ) { //Start SDL SDL_Init( SDL_INIT_EVERYTHING ); //Quit SDL SDL_Quit(); return 0; }
12)Now Compile. Save the new source file if necessary and make sure SDL.dll is in the same directory as the executable or in C:\WINDOWS\SYSTEM32. If there are no errors, you're finished. Otherwise go back and make sure you didn't skip a step.
Also, In the archive you just downloaded there's a subfolder called "docs". It contains the SDL documentation.

I highly recommend that you extract them somewhere and keep it for reference.
ReadMore...

Saturday, December 27, 2008

(0) Comments

Stacks and Queues

welcome to infomix.blogspot.com

Introduction

Stacks and queues are actually data structures created from linked lists. If you're not familiar with linked lists, see my Linked Lists Tutorial. This tutorial will actually be rather short because all we need to do is modify the linked list class that we developed in the linked list tutorial. Stacks and queues both just limit the way data is accessed in a linked list.
Stacks

Before we look at the implementation of a stack, let's talk about what a stack is. The best way to see how the stack data structure works is to imagine a stack of plates. If you want to add a plate to the stack, you have to add it to the top. If you want to take a plate from the stack, you have to take if from the top.

This behaviour is know as "Last In, First Out" because the last item you add to a stack is always going to be the first item you get from it. Adding an element to a stack is called "pushing" and removing an element is called "popping". Accessing the top element is called "peeking".

An example of when to use a stack would be for a simple AI character. Let's say the the AI character starts of patrolling. The stack of instructions for the character would look like this:

[Patrol]

Now let's say the AI spots some ammo. We'd like the character to get the ammo, so we push the instruction to get the ammo onto the stack.

[Patrol]->[Get Ammo]

Note that because we're using a stack, the AI will only execute the top instruction. In this case, the AI will go get the ammo. After the AI has the ammo, we pop that instruction from the stack. The stack looks like this again:

[Patrol]

The AI will resume patrolling because that is the instruction at the top of the stack. But what if, while the AI is going to get the ammo, the player wanders by? We obviously want to push an instruction to attack the player onto the stack. This is what the stack would look like:

[Patrol]->[Get Ammo]->[Beat Up the Player]

After the player has been beaten down, [Beat Up the Player] gets popped off the stack. The stack always remembers the previous state the AI was in, so it's a good data structure for representing this kind of behaviour. Note that in each frame of our game, all the AI has to do is 'peek' the instruction at the top of the stack to know what to do.

Something to note is that if we were just using a linked list for this, we would use AddTail() when we wanted to push an instruction and we'd use RemoveTail() when we wanted to remove one.

Internally, a stack really is just a linked list. All we have to do is get rid of the functions that access data at the beginning and middle of the list, rename the functions that access the tail, and we have ourselves a stack! No actual coding is really needed, so just quickly read through the changes (I commented them!) in the downloadable source code and check out the test harness.

Click here to download the source code for this part of the tutorial.
Queues

The queue data structure acts just like a line up. Think of a line at a store. The first person to get to the line will be the first person out. If someone else enters the line they enter at the back and get out last. This behaviour is called "First In, First Out" because the first element added to the queue is the first one processed.

If you've ever used some sort of download manager, you've used a queue. As you select the files to download, they get added to the back of the queue. The first item you select will be the first item downloaded. If you're downloading one file at a time, your download manager will only have access to the front of the queue.

Adding an element to a queue is called "enqueue-ing", removing an element from a queue is called "dequeue-ing", and accessing the element at the front is called "peeking".

For a game example of using queues, think of a factory in a real-time strategy game. When you want to build units, the factory uses a queue to keep track of what to build first. Let's say we tell a factory to build a tank. Our queue would look like this:

[Tank]

Now we tell the factory to build an airplane. Instead of overriding the tank, the airplane gets placed in line (remember that the front of the list gets processed first).

[Tank]->[Airplane]

If we tell the factory to build a robot now, we get this:

[Tank]->[Airplane]->[Robot]

When the tank is built, it is dequeued and we get this:

[Airplane]->[Robot]

Once the airplane is built, it is dequeued and it will be the robot's turn:

[Robot]

As with the stack, we just need to modify our linked list class to create a queue. We change the name of AddTail() to Enqueue(), RemoveHead() to Dequeue(), and GetFrontData() to Peek(). Any functions that don't serve a purpose can be removed. Check out the downloadable source code for the full imlementation of a queue.
ReadMore...

Saturday, December 27, 2008

(0) Comments

Standard Template Library

welcome to infomix.blogspot.com

Introduction

The Standard Template Library (STL) is a collection of classes that represent commonly used data structures and algorithms. These classes should be treated like another feature of the C++ language. Although you should be able to write your own linked list (see my Linked List tutorial if you don't know what a linked list is), there's really no need to write your own for every project you do. The classes in the STL are thoroughly tested and optimized. In fact, there are some cases, such as the string class, where you should almost always use the standard library.

The STL classes belong to the namespace std, so you have to either put using namespace std; at the top of your file or preceed any references you make to the library with std::. STL uses templates extensively, so see my Templates Tutorial if you aren't familiar with them.

There are already a lot of STL references out there, so I'm going to stick to showing you functionality in these tutorials. Treat it like when you first learned how to use arrays; you didn't want to know how to program them, you just wanted to know when and how to use them.

Currently I have the following discussions available:

std::string

std::vector

std::stack

std::queue

The string Class

A lot of books that teach introductory C++ tell you to use char pointers for string handling. I learned it this way and it drove me nuts. I was learning Java at the same time and couldn't figure out why C++ didn't have string support. It's such a necessary aspect of programming! What I didn't know is that C++ does have a standard string class, which is aptly named string.

Whenever possible, I recommend using string instead of char pointers. The string class is clean, provides great functionality, and you don't need to worry about buffer overflows like you do with char pointers.

This discussion will cover some of the functionality offered by the string class. Most of the functions are self-explanatory, so I'll just list the most useful ones here with a description of what each one does. I've also included a sample application that demonstrates the use of the different string functions.

Note that you can declare and use a string variable just like any variable in C++. As I said before, you should treat the classes in the STL just like any other C++ programming language feature.

c_str() // returns a const char* representation of the string
length() // returns the length of the string
at(int index) // returns the char at the specified index, counting starts at 0
operator[](int index) // overloaded so you can access characters like an array
clear() // erases the string
substr(int start, int end) // returns the substring from start to end
find(char*/string str) // searches the string for a substring (takes a string or a char*)

Click here to download the source code for this tutorial.
The vector Class

First off, the STL vector class does not represent a mathematical vector. Actually, it's almost identical to a one dimensional array. The vector class just comes with some great added functionality. It also resizes dynamically so you don't have to worry about it growing too large or wasting too much memory.

The vector class is templated, so you would declare a vector of integers like this:

vector intVector;

The <> notation might seem a little odd to you. If it does, check out my Templates Tutorial.

A powerful feature of the STL is the use of iterators. Iterators are pointers that point into the structures of the STL. You can have an iterator that points into a vector that stores integers, and point it to the first element of the vector. You can then increment the iterator and it will point to the second element of the vector. You use the increment operator (++) to do this.

You can compare the locations of two iterators using standard conditional operators ( <, >, <=, >= ). The statement itr1 < itr2 will return true if itr1 points to an element that is closer to the start of the vector.

If you want to get the value stored at the element an iterator points to, use the de-reference operator (*) like this:

*itr;

STL structures have begin() and end() functions which return iteratorsat the beginning of the stucture and one past the end of the structure (not the element at the end, one past it) respectively.

Here's a quick example of using iterators, see the downloadable source code for a more thorough demonstration.

// Declare some iterators that point into vectors of integers
vector::iterator itr1 = intVector.begin();
vector::iterator itr2 = intVector.end();

itr1++; // move the iterator one element forward
itr1 < itr2; // true if itr1 points to an element coming before itr2
itr += 2; // move the iterator up by 2 elements

// This is how you would use iterators to loop through a vector
for (vector::iterator itr = intVector.begin(); itr < intVector.end(); itr++)
{
cout << *itr; // *itr gets the value from the element itr points to
}

Here is a list of useful vector functions. See the downloaded source code for working examples of each of these.

push_back(T value) // add an element to the end of the list
insert(iterator itr, T value) // insert an element at a specific position
operator[](int index) // access an element
at(int index) // access an element, throws exception if index is too big
begin() // return an iterator to the beginning of the vector
end() // return an iterator to one past the end of the vector
clear() // erase everything in the vector
pop_back() // remove the element at the end of the vector

If we need to sort our vector, we can use the STL sort() function. This function takes an iterator to the first element and one past the last element we want sorted. If you want to sort the whole vector, use begin() and end() like so:

vector::iterator itr1 = intVector.begin();
vector::iterator itr2 = intVector.end();
sort(itr1, itr2);

I find the vector class to be the most useful structure in the STL. In fact, I use it in almost all of the tutorials on this site. It's really nice having the instant access of an array with the dynamic size of a linked list. I suggest you try using the vector in place of arrays, unless you have a good reason to be using an array.

Click here to download the source code for this tutorial.

The stack Class

Before we discuss the STL stack, let's talk about what a stack is. I'll use the common example of a stack of plates. If you want to add a plate to the stack, you add it to the top. If you want to take a plate off of the stack, you take it from the top. This behaviour is known as Last In, First Out because the last element you add to the stack is the first one to come off.

The stack data structure acts just like a stack of plates. We call a function to add an element and it adds the element to the top of the stack. When we want to access an element from the stack, we call a function that returns the top element. When we want to remove an element, we call a function that removes the top element.

Note that we don't have access to any element other than the one on top (the one most recently added). The act of adding an element to a stack is called "pushing" and the act of removing an element is called "popping".

If you want to understand how a stack is implemented internally, check out my tutorial on Stacks and Queues. Be warned though, stacks are normally built from linked lists so you'll probably have to read that tutorial too if you don't already know how a linked list works. If you just want to use a stack and don't want to have to write it, use the STL stack. Also realize that the STL stack is highly optimized and that STL provides algorithms to do things like sort the data in it (just like with std::vector).

The STL stack is so easy to use that I'm just going to list the functions STL provides and let you download a demonstration to see it in action.

// Declare a stack, dataType can be any data type
stack myStack;

myStack.push(item); // pushes an element onto the top of the stack
myStack.pop(); // pops the top element off of the stack
myStack.top(); // returns the element on the top of the stack
myStack.size(); // returns the number of elements on the stack
myStack.empty(); // returns true if the stack has no elements

Click here to download the source code for this tutorial.
The queue Class

The queue data structure is a structure that behaves in a First In, First Out manner. Think of a line up at the store. Customers enter the line at the back and exit the line from the front. With the stack, the most recently added element is processed first. With the queue, the most recently added element has to wait its turn.

The STL queue provides a great implementation of a queue. It also adds the functionality to access the back of the queue (maybe the customer at the back gets tired and decides to leave). A better example of a std::queue then might be a road block. The first car that gets to the road block gets to go first (unless the driver gets busted), the car at the back of the road block can make a run for it, and the cars in the middle are stuck there.

If you want to understand how a queue is implemented internally, check out my tutorial on Stacks and Queues. Be warned though, as with stacks, queues are normally built from linked lists so you'll probably have to read that tutorial too if you don't already know how a linked list works. Either way, I suggest you use the STL queue because it's well tested and optimized.

Here's the list of functions that comes with the queue. And don't forget to download the source code and see the queue at work.

// We declare a queue like this, dataType can be any data type
queue myQueue;

myQueue.push(item); // adds an element to the back of the queue
myQueue.pop(); // removes the element at the front of the queue
myQueue.front(); // returns the element at the front of the queue
myQueue.back(); // returns the element at the back of the queue
myStack.size(); // returns the number of elements in the queue
myStack.empty(); // returns true if the queue has no elements
ReadMore...

Saturday, December 27, 2008

(0) Comments

Linked Lists

welcome to infomix.blogspot.com

Along with arrays, linked lists form the basis for pretty much every other data stucture out there. This makes learning and understand linked lists very important. They are also usually the next step in memory management that people encounter after learning pointers.

I've written a linked list structure specifically for this tutorial which can be found in the downloadable source code. I commented it thoroughly so it should be able to stand alone as its own tutorial. To make things even easier on you, I will go through the list structure function by function and discuss what the function does as well as show pictures that demonstrate what's going on.

I recommend that you open the downloadable source code now and follow along. Reading both at the same time will allow you to see the theory as well as the implementation.

f you plan on getting more advanced at game programming, spend some time learning linked lists! If you need a refresher on pointers, see my Pointers Tutorial. And if you don't know what a template is, see my Template Tutorial.
What is a Linked List?

A linked list is a node-based data structure. What does that mean? It means that a linked list is a structure composed of smaller structures called nodes, which store the actual data in the list. We link these data storing nodes together into a list to create a linked list. Here is a picture of a linked list:

The squares in this picture represent the nodes of the list. Notice that each square (node) contains a data member and a pointer called Next which points to the next node in the list. The last node in a linked list always points to NULL. Here is the code for a node structure:

template
class Node
{
DataType Data;
Node Next;
};

So we know that a linked list contains a group of structures called nodes which are linked together. Each node stores some data and a pointer to the next node in the list. The last node in the list points to NULL. This node is called the tail. The front node is called the head.

Now that we know what a linked list is, let's discuss why we would use one and then go on to discussing the implementation of a linked list.
Why Use a Linked Lists?

When we want to store data, we usually first think of an array. Arrays are definately the most popular way to store data. After we decide on the size of our array, we can add data to it simply by specifying where we want it to be within our array; we access data the same way.

This means that arrays gives us instant access to our data. Even better, aside from pointers that we might have pointing to our arrays, we never really need to worry about memory management. So why use a data structure that is constructed entirely from pointers?

The reason is that linked lists allow us to store varying amounts of data. With arrays, we have to decide on the amount of data to store from the beginning, and we can never easily change this size. With linked lists however, all we need to do is create a new node and tag it on the end of the list.

The choice between using an array or using a linked list is a matter of memory vs. speed. If you're not worried about wasting memory and you want a lot of speed, just use a really big array. Some memory will be wasted if you don't use up the entire array, but you get a lot of speed because you can access the data in an array instantly by specifying the index you want to access.

Linked lists on the other hand are good when you need the memory. You never waste space with a linked list because you never need to have more nodes than you have data. Unfortunately, you don't get instant access time with linked lists. You can't just say you want node 3 of a list and get it instantly. The reason is that you only have pointers to the front and back of a linked list.

Take a look at that picture I just showed you. Head points to the front of the list and Tail points to the back. If you want to get node 3, you have to start at Head and work your up through the list to get to node 3.

For this reason, you probably won't find yourself using linked lists as much as you use arrays. However, linked lists form the basis for more advanced structures like Stacks, Queues, Trees, and Graphs. So pay attention!
The Structure of a Linked List

I'm now going to go through the creation of a linked list. I will only be discussing the concepts here. See the downloadable source code for a heavily commented implementation of a linked list. I strongly suggest that you read this along with the code. Make sure you understand how everything works because once you do, you'll have a much better understanding of programming in general.

Once we have a node structure defined, we create a class to handle the linking of these nodes. This class will be our main linked list structure. The only data members of the class will be a pointer to the first node (the head), a pointer to the last node (the tail), and a variable that keeps track of the number of nodes in our structure.

When we initialize a linked list, we set its head and tail pointers to NULL so that they're not pointing to anything weird. This is what our list looks like after intialization:

Adding Nodes to a List

So we have both our head and tail pointers pointing to NULL. Now let's try adding some nodes. There are three ways to add a node to a linked list. We can add it to the front of the list, the back, or we can add it somewhere in the middle.

Adding a node at the head of a list. When adding a node at the front of the list, we set the new node's Next pointer to point to the head and the Head pointer to point to the new node. There are two scenarios we have to deal with when doing this.

The first scenario occurs when the list is empty. When this happens, we assign the new node's Next pointer to the head, which results in it pointing to NULL because the head was NULL. This way we get the Head pointer pointing to the new node, and the new node's Next pointer pointing to NULL.

But what about the tail? If the tail points to the last node in the list, and there's only one node in the list, then it should point to the new node too. In the end, we have a new node which points to NULL, and our Head and Tail pointers point to the new node.

Here's what our linked list looks now.

The second scenario occurs when we already have nodes in the list. Because we are adding a new node at the head of the list, the node that is currently the head of the list becomes the second node in the list, and the new node takes its place at the front. So, to add a node to the front of the list we first assign the new node's Next pointer to the current head, and then we set the Head pointer to the new node.

Here's a picture to illustrate the process:

In (1), we just have our original list with one element in it. In (2), we have created a new node and set its Next pointer to the current head of the list. In (3), we have set our new node as the head. Notice how the node that was the head (the blue node) is still the tail.

Here's a picture of our list after another node is inserted:

So the new node (yellow) is set to point to the old head (red). Then the new node (yellow) is made the head of the list. After this process, we can see that the new node (yellow) is the head, the old head (red) is the second node in the list, and the old tail (blue) is still the tail.

Adding a node at the back of a list. When we add a node at the end of our list, we set its Next pointer to NULL because the last node in a linked list has nothing to point to.

The same two senarios occur when adding to the back of a list as when adding to the front. There will either be something in the list already, or there won't. The process of adding a node at the end of an empty list is the same as adding a node at the front of an empty list. In both cases we set the new node's Next pointer to NULL, and then set the link list's Head and Tail pointers to the new node.

The process of adding the node when there is already something in the list, however, is slightly different. To add a node at the end of a list, we first have to set the current tail node's Next pointer to the new node. We then set the linked list's Tail pointer to the new node.

Here's a picture illustrating the process:

In (1), we just have our original list with one element in it. In (2), we have created a new node and set the old tail node's Next pointer to the new node. In (3), we have set the linked list's Tail pointer to our new tail node.

Here's a picture of our list after another node is inserted:

The new node (yellow) becomes the tail node and has it's Next pointer set the NULL. The old tail (red) becomes the second last node in the list.

Adding a node in the middle of a list. The process of adding a node somewhere in the middle of a linked list is slightly more complicated than adding a node at the front or the back.

The first problem that can occur is when we try to add the node to a location in the list that doesn't exist. For example, say we have a list of 5 nodes and we try to add a node between the 10th and 11th node. Wouldn't work now would it? There are two things we can do in this case. We can do nothing, or we can just add the node to the end of our list. I like to add the node at the end of the list so that's what we'll do. To accomplish this, we just call our AddTail function.

Another problem is trying to add a node in the middle of an empty list. We've already got this problem covered though! If there are no nodes in our list, then any location we try to add a node at won't exist, so our AddTail function will be called. AddTail already handles the case of an empty list!

If the above problems don't occur, we'll have a valid location at which we need to add our new node. Let's first take a look at a list with five nodes.

Now let's assume we want to add a node between node 2 (red, counting starts at 0!!!) and node 3 (green). We've got a few problems here. First, we don't have a pointer to either of these nodes. We only have pointers to the start and end of the list. To get around this, we'll have to start at the front of the list and travel from node to node until we get to the red node.

Another problem is how to insert the new node once we get there. If we immediately set the red node's pointer to point to our new node, we'll lose the rest of the list. Here's a picture:

See, if we just set the red node's Next pointer to the new node, we no longer have anything pointing to the green node. The green node will become a memory leak and our list will be ruined. What we need to do is first set our new node's Next pointer to the green node, and then we can set the red node's Next pointer to the new node.

At the end of the process, our linked list looks like this:

Removing Nodes From a List

Removing nodes from a list is a fairly easy process. We just have to make sure to avoid losing references to nodes (and thus causing memory leaks). Note that in each case we first check to make sure the list is not empty. If it is empty, we don't have to do anything.

Removing a node from the front of a list. We have a dilemna when removing a node from the front of a list. If we start by deleting the node at the front of the list, we get the following:

We have indeed gotten rid of the node at the front of the list, but we've also lost all references to the red node! So let's try first moving the linked list's Head pointer to the next node in the list before we delete anything.

Now the problem is how to actually delete the node at the front of the list. Since we've moved our Head pointer forward, we no longer have any reference to the front of the list.

The solution to our problem is to first create a temporary node pointer that points to the head of the list. We then change the linked list's Head pointer. Finally, we delete the front of the list by deleting the node that the temporary pointer points to (it points to the front node).

Here's the process in photo-realistic detail:

So in (1), we create our temporary pointer. In (2), we move our Head pointer up one node. In (3), we delete the node that the temporary pointer points to.

Removing a node from the end of a list. As with removing a node from the front of a list, we are faced with problems when we try to delete a node from the end of a list. Our first idea might be to just delete the node that our linked list's Tail pointer points to. Let's see what happens:

We no longer have our Tail pointer pointing to anything. This isn't as big of a problem as with removing the front node because we can still reach the last node in the list. We just start from Head and keep moving up until the node we're at points to NULL. Remember, the last node of a list always points to NULL. We can then set our Tail pointer to the end node.

Advanced readers might be bothered by what I just said. When we delete the object that a pointer points to, the pointer still points somewhere. We have to explicilty set our pointer to NULL before it actually points to NULL. We could very well crash our program by searching our linked list for a NULL reference that isn't there (because we just deleted the tail, we didn't set the new tail's pointer to NULL).

The solution is to first start at the front of the list and move to the node that is before the last node. Here's a picture:

Now our temporary node pointer points to the node that will become the tail of our list. This node's Next pointer also just so happens to point to the current tail. All we have to do now is delete the node that our current node's (the one that our temporary pointer points to) Next pointer points to (which is the current tail), set the Next pointer to NULL, and make our linked list's Tail pointer point to the node our temporary pointer points to. Here's the picture:

In (1), we have a pointer to the node that will become the new tail. In (2), we delete the current tail. In (3), we change the linked list's Tail pointer to point to the new tail.

Removing a node from the middle of a list. We're almost done! Removing a node from the middle of a list is a lot like removing a node from the end. We create a temporary node pointer and move it to the node before the one we want to delete. Now we have to be careful though. Let's see what happens when we just delete the node like we did with the tail node.

Here we've deleted the third node in our list. In doing so, we've lost all reference to the fourth node in the list. What we need is another temporary node pointer to point to the fourth node while we delete the third node. That way, we can reconnect our list. Picture time!

In (1), we have two temporary variables pointing to the nodes before and after the node we'll be deleting. In (2), we delete the node. In (3), we set the node before the deleted node to the node after the deleted node. After this process, we'll have a properly connected list, minus the deleted node.

Note that another way to do this would be to create a temporary pointer and set it to the node to be deleted. Then connect the nodes that come before and after the node to be deleted. Then, delete the node.

Retrieving data from a linked list. Getting data out of a linked list is really easy. Since each node contains data, all have to do is get to the node that has the data we want. For the cases where the data is in the first or last node, we just use our Head and Tail pointers. If the data is somewhere in the middle of the list, we create a temporary node pointer and move it up the list until we get to the node we want. That's it!

By now I hope you fully understand how a linked list works. If you haven't been going through the downloadable source code already, I suggest you do it now. Being able to write your own linked list is the key to being able to write more advanced data structures like graphs and trees.
ReadMore...

Saturday, December 27, 2008

(0) Comments

Function Templates

welcome to infomix.blogspot.com

Before we look at what function templates are, let's look at a problem that will lead to an understanding of why we would use them. Say we have a function that computes the sum of the squares of two values and takes integers as parameters.

// Take two integers and returns the sum of their squares
int SumOfAllSquares(int opp, int adj)
{
return opp*opp + adj*adj;
}

Now let's assume that we also want to perform this operation on floats and doubles. To do this, we would have to rewrite the same function for both data types.

// Take two floats and returns the sum of their squares
float SumOfAllSquares(float opp, float adj)
{
return opp*opp + adj*adj;
}

// Take two doubles and returns the sum of their squares
double SumOfAllSquares(double opp, double adj)
{
return opp*opp + adj*adj;
}

Although this method works, it's not very elegant. If we had some larger functions and we wanted them to be able to handle a whole set of different data types, we'd be doing a lot of copy-pasting and we'd have a lot of repetitive code.

This is where the benefit of templates comes in. Templates are a C++ feature that allow you to write code that can handle general data types. By "general datatypes", I mean that templates allow you to write functions that can work on multiple types.

The syntax for declaring a template is

template

followed by the declaration of the function. What this statement does is declares that our function will work with a data type that is specified when the function is called. class T denotes the variable T as a general data type.

Here's a complete example of how we would use a templated function. Note that the variable T can have any name, it doesnt have to be called T.

// Take two general values and return the sum of their squares
template
DataType SumOfAllSquares(DataType opp, DataType adj)
{
return opp*opp + adj*adj;
}

// We call the function as if it's defined for whatever data type we're using
int iX = 8, iY = 9;
float iX = 4, iY = 6;

int iR = SumOfAllSquares(iX, iY);
float fR = SumOfAllSquares(fX, fY);

Note that we specified that both parameters are of type DataType and that the return type is also of type DataType. We don't necessarily have to have all of the parameters or the return value be of general type (we did here because we're returning the same type that's passed in), but we must be sure that any operations we perform on the types are defined.

For example, this function works fine with numerical types, but what if we have a class that represents a person in a game? If we haven't specified numerical operations on the person class, our program will have no idea what to do when we tell it to add and multiply two of them together.

See the downloadable source code for this tutorial to see templated functions in action.
Class Templates

Now that we have seen how templated functions work, let's take a look at templated classes.

Templated classes are mostly used when building large data structures that need to be able to store different data types. The same reasoning works for classes as for functions. We can either make a class that uses say, an int, and then copy-paste when we want to use other data types, or we can template the class and use any data type we want.

Like I said before, templates are widely used with data structures (see my Linked Lists Tutorial for an example of a templated data structure), but I'm going to use a simpler class example here.

// Declare a class that uses templated data types
template
class NumberHolder
{
public:
// The constructor takes three pieces of meaningless data
NumberHolder(DataType num1, DataType num2, DataType num3) :
m_Num1(num1), m_Num2(num2), m_Num3(num3) {}

// Note that each accessor returns a 'DataType'
DataType GetNum1() { return m_Num1; }
DataType GetNum2() { return m_Num2; }
DataType GetNum3() { return m_Num3; }

// Note that each mutator takes a 'DataType'
void SetNum1(DataType num) { m_Num1 = num; }
void SetNum2(DataType num) { m_Num2 = num; }
void SetNum3(DataType num) { m_Num3 = num; }

private:
DataType m_Num1;
DataType m_Num2;
DataType m_Num3;
};

First of all, sorry for the lame example. I didn't want to build a data structure here so I took the easy way out and wrote a meaningless class. If you want to see an example of templated classes in real use, see my Linked List Tutorial.

Notice that in the above code we were able to use DataType just like it was a normal data type (like an int or a char). This allowed us to use this class with any reasonable type of data. To instantiate an object from this class, we would have to specify the type of data we want to use. After we specify the data type, DataType will be replaced by the specified type.

// We specify the type within the <> brackets
NumberHolder iNumHolder(2, 4, 5);
NumberHolder fNumHolder(2.0f, 4.0f, 5.0f);
NumberHolder dNumHolder(2.0f, 4.0f, 5.0f);

// Now we can use the objects like normal
int x = iNumberHolder.GetNum1();
fNumHolder.SetNum2(9.0f);

There are two more things you should know about templates.

First, you can only write a templated classes within a single file. If you try to separate the definition and the implemention into .h and .cpp files, you'll get link errors. So be sure to define your templated classes within indepenent header files.

Second, you aren't restricted to only using one data type for templates. You can have your templates take as many different general types as you like. For example, putting

template

before a class would allow you to specify two different types when instantiating objects from it. This is great for data structures that need to hold multiple data types.

I hope you now have a good idea about how templates work. As always, if you need help just ask!
ReadMore...

Saturday, December 27, 2008

(0) Comments

Function Pointers

welcome to infomix.blogspot.com

Function pointers are a great C++ feature! Some people have a hard time remembering the syntax though, which is why I've put it at the top of this page. If you ever forget it, just come back here.

A function pointer is a pointer that points to functions. Say we want our game to have a menu system. We'll have a function that controls the main menu, functions that control sub-menus (like options and settings), a function that handles the actual game, and a function that displays a message when the player quits the game.

What we need is some way to call the right function depending on what state the game is in. One option is to keep a variable that stores the state of our game and check it each frame. I'll show you some code that would do this and then explain why we would want to do it another way.

If you need a refresher on pointers, now would be a good time to check out my Pointers Tutorial.

Here's some code that handles a menu system without using function pointers:

// First we need to enumerate some values to make our code readable.
// These obviously represent our game states.
enum GameState
{
MENU,
OPTIONS,
GAME,
EXIT,
REALLYQUIT
// the Exit() function checks to see that the user
// really wants to quit and returns REALLYQUIT
};

// I'll just write the prototypes to our games functions.
// Each returns the game state to switch to. If we're in
// one state and don't want to switch, we can just return
// the same state (if we're in Game(), we can return GAME).
GameState Menu();
GameState Options();
GameState Game();
GameState Exit();

// This variable keeps track of the current game state.
// It is global so the game functions have access to it.
// Since we're starting our game in the main menu, we'll
// set the current state to MENU.
GameState CurrentState = MENU;

int main()
{
bool playing = true;

// Now we start a while loop and check which state we're in
while (playing)
{
// We'll use a switch statement to handle the states.
// Note that changes to the current state will be made
// within the state functions. If we're in the menu and
// the player wants to play the game, Menu() will set
// CurrentState to GAME. All the switch statement does
// is figure out which state function to call.
switch (CurrentState)
{
case (MENU):
Menu();
break;
case (OPTIONS):
Options();
break;
case (GAME):
Game();
break;
// Exit will return REALLYQUIT if it's time to quit
case (Exit):
if (Exit() == REALLYQUIT)
playing = false;
break;
}

}
return 0;
}

Alright, so in each iteration of the while loop we check to see what state we're in and run the appropriate function.

One argument against this method is that the switch statement has to perform up to four conditional statements for every frame of our game. My main problem with this method, however, is that it's a little ugly. When we want to add more states to our game, perhaps an option screen for video modes, we not only have to add the logic to each of our menu functions, we also have to add the new state to our GameState enumeration and switch statement (which also increases the number of conditional operations).

It would nice if there was a way we could call one function from our while loop and never have to change it. Function pointers provide this functionality!
Using Function Pointers

A function pointer is exactly what it sounds like, a pointer that points to a function. When we declare a function pointer, we also declare what type of function it will point to (i.e. the return type and parameters). This means that a function pointer can only point to one type of function. A function pointer to a function that returns an int and takes no parameters can only point to functions that return int's and take no parameters.

We declare a function pointer like this:

Return_Type (*Pointer_Name)(Parameters)

This means that the function pointer Pointer_Name points to functions that return whatever Return_Type is and take whatever parameters we put in place of Parameters. We assign functions to the function pointer like this:

Pointer_Name = myFunction;

Note that we do not include the parameters when we assign a function pointer, only the function name. Now that our function pointer points to something, we call it like this (let's assume the function takes an int as a parameter):

Pointer_Name(32);

This will call the function that Pointer_Name points to with 32 as the parameter. In this case, Pointer_Name points to myFunction so the above line is exactly the same as if we had done this:

myFunction(32);
Back to our Game State Problem

So we now have a pointer that points to functions, but how does that help us with our game state problem?

Well, we already have the functions and our while loop set up. So what if we point a function pointer to the menu function and call the function pointer from the while loop? We'll assume that when the player decides to start a game, the menu handles pointing the function pointer to the game function, and that the game function will then handle pointing the pointer to whatever state comes next, and so on.

Let's code this and then discuss what happens.

// Note that we no longer need a switch statememt, so we no
// longer need the enumerations or the CurrentState variable.

// Our functions don't need to return the current state anymore.
// We just have them return false if it's time to exit our loop.
bool Menu();
bool Options();
bool Game();
bool Exit();

// Here is where we declare our function pointer. It is
// global so the state functions have access to it. Note
// that the return type and parameters match our game
// state functions.
bool (*StatePointer)();

int main()
{
bool playing = true;

// Let's point the function pointer to the menu function.
// Remember that we leave out the brackets.
StatePointer = Menu;

// Now we start a while loop and call our function pointer.
// When a state changes, it will be handled in our game
// functions so we never need to deal with this section of
// code again.
while (playing)
{
// Call the function pointer and assign the result
// to our playing variable. If a function returns
// false, our loop will quit.
playing = StatePointer();

}

return 0;
}

Now that we've placed all of the responsibility on our game functions, we can forget about main() entirely. When the while loop starts, it calls the function pointer, which points to whatever function handles the current state of our game.

We start with it pointing to the menu program. If the user chooses to play the game, the function pointer will be assigned to the game function from within the menu function. If the user chooses to quit, the function pointer will be assigned to the exit function. If the user makes no selection, the while loop will just keep calling our function pointer.

I've written a simple menu program and heavily commented it for you. I highly recommend that you check it out before continuing with this tutorial.

Click here to download the source code for this section of the tutorial.
State Stacks

The previous example relied on the fact that the game functions will change the function pointer to point to whatever state comes next. This means that the options menu could set the pointer to the main menu, it could set it to the game function, or it could set it to the exit function. But what if we wanted our system to be a bit more restrictive?

For instance, think of some of the games you've played. A lot of them start with the main menu. After the main menu, you can select to start a game, go to the options screen, or exit the game. If you select the options menu, it will pop up with a new menu where you can select more submenus like input, sound, and graphics settings.

Let's say we select the options menu from our main menu. The options menu pops up and we select to see our input settings. Once we're done staring at our input settings, we hit the escape key. This causes the input settings to disappear and we're back to where we just were, the options menu. We hit escape again and we're back to the menu.

Using our previous method, we would have the menu set our pointer to the the options menu, the options menu set our pointer to the input settings, the input settings set our pointer to the options menu, and finally we would have the options menu set the pointer to the main menu.

A better way to do this is to use a stack. If you're not familiar with stacks, I have written a tutorial that can be found here. Also, I'll be using the STL implementation of a stack; see my STL Tutorial for an introduction to the STL stack (it'll only take a sec, trust me).

So we now all know that a stack stores data like a stack of plates. If we add a plate to the stack, it goes on top, and if we take a plate from the stack, we take it from the top.

Alright, so what does a stack have to do with function pointers? Well, let's say we have a stack of function pointers that control the states of our game. When we start our program, we push a pointer to the menu function onto the stack. The stack now looks like this:

(bottom) Menu (top)

When we choose to open the options menu, the stack looks like this:

(bottom) Menu->Options (top)

Selecting the input menu, we get this:

(bottom) Menu->Options->Input (top)

When we hit escape, we don't have to have the input function do anything. We can just tell our stack to pop its top element. We now have this:

(bottom) Menu->Options (top)

After hitting escape again, we get:

(bottom) Menu (top)

Remember how with our last method we had to have the playing variable keep track of whether the while loop should continue or not? We no longer need that. All we have to do is check to see if our stack is empty and we'll know to quit the loop. If we hit escape again with our current stack, the pointer to the menu function will be popped and the stack will be empty.

Adding states to our game is easy now too. We just have to write our function and push a pointer to it on the stack when we want to run it. In each iteration of our while loop we'll just call whatever function is at the top of the stack.

So I guess I better show some code now, eh? See the downloadable source code for this section of the tutorial for a working example. Note that we can't just initialize a stack of function pointers. If we try this:

stack StateStack;

our compiler will go nuts. STL stacks can't just take function pointers. My solution to this problem is to encapsulate a function pointer within a struct. The std::stack has no problem with storing structs. Here's the final version of our game state example:

// Declare our struct which holds a function pointer
struct StateStruct {
void (*StatePointer)();
};

// Note that our functions no longer need to return false if it's time to
// exit the program. We just have to check if the state stack is empty.
void Menu();
void Options();
void Game();

// I've decided to have exit be a helper function for the MainMenu. If MainMenu is the only
// thing left on the stack, then we know that the user is trying to quit if 0 is pressed.
// MainMenu will call Exit() which will ask the user if it's really time to quit. Note that
// this function returns a boolean, so our function pointers can't point to it. If this is
// confusing, see the MainMenu implementation in the downloadable source code below.
bool Exit();

// Here's our state stack. We're declaring a std::stack that holds StateStructs.
// Remember that StateStruct is just a struct that contains a function pointer.
stack g_StateStack;

int main()
{
// Let's now start by pushing a Menu pointer onto the stack. First, we have to
// declare a StateStruct structure and point its function pointer to MainMenu.
// Then we push the whole structure onto the stack.
StateStruct menu;
menu.StatePointer = MainMenu;
g_StateStack.push(menu);

// We will now continually call the function pointer at the top of our stack.
// Notice how our while loop's terminating condition is now an empty stack.
while (!g_StateStack.empty())
{
// All we have to do here is call the function at the top of the stack.
g_StateStack.top().StatePointer();
}

return 0;
}
ReadMore...

Saturday, December 27, 2008

(0) Comments

Pointers

welcome to infomix.blogspot.com

This tutorial is my attempt at clarifying pointers for anyone still confused about them. Pointers are notoriously hard to grasp, so I thought I'd take a shot at explaining them. The more information out there on pointers, the better.

I'll be giving code demonstrations thoughout this tutorial and will also include a downloadable program that you can use to test different aspects of pointers. I'm not sure how much can be gained by copying out the code here line for line, but I do encourage you to play around with the code.

First, let's briefly talk about how memory is stored in a computer. You can think of memory as sequential rows of storage spaces, each with its own address. When you declare variables, your program stores the information in one of those spaces (or a group of spaces if it needs the extra room) and remembers where it is. If you have declared a variable and you want to know where your program put it, you can use the address-of operator to get the address.

int age = 21; // declare the variable on the stack
cout << "age: " << age << endl; // print the value stored in age
cout << "&age: " << &age << endl; // print the location of the value
The Stack, Free Store, and Global Namespace

Now let's talk about the difference between the stack, the global namespace, and the free store.

The stack is part of the area in memory that is reserved for your program. Any local variables that you declare on the stack (ie. normal variable declarations like "int age;") stay there until your program is finished, at which point that area in memory will automatically be cleaned up. If you declare a variable in a function, loop, or conditional statement to be on the stack, it will only exist until the end of that statement. Afterwards, that part of the stack will be cleared and anything declared there will be gone.

Global variables exist in the global namespace and the memory they take up is automatically freed at the end of your program. They act just like variables declared on the stack with the exception that they can be accessed from anywhere in your program.

The memory in your computer that is not being taken up by the stack or the global namespace is called the free store (a.k.a. "the heap"). This area of memory is pretty much fair game for any program that wants to use it. Unlike the stack and the global namespace, variables declared on the freestore exist until you explicitly delete them. If you don't delete them by the end of your program, they will just sit there until you restart your computer. This situation is most commonly called a memory leak and is usually very difficult to detect because there's no easy way to see what is stored on the free store.

Before we discuss why we would want to store data on the free store, let's look at how you would declare a variable there. This is also a good time to download the source code that comes with this tutorial, read the comments, and see what you get when you run the program.

Here's some code that declares a value on the freestore:

// a variable has been declared but set to NULL, nothing has been put on the freestore yet
int* width = NULL;
// now something is on the freestore (30), and width holds the address that points to it
width = new int(30);

Don't worry, we're going to get to why we would do this in a minute. First, I want you to really understand what goes on when we declare a pointer. The variable width does not represent the value 30, it just stores the location in memory where 30 exists. If we had another pointer to that location in memory and changed the value there, width would then point to that new value. This is because width doesn't represent the value 30, it just points to whatever is sitting at that location on the free store.

Once again please check out the downloadable source for this tutorial.

Let's now look at some of the operations we can perform on pointers and then get to why we would use them.

// Assume that width has already been declared as a pointer

// This prints out whatever is stored in the width variable. In this case, it's the location
// on the free store that the pointer points to, not the value it points to
cout << "\nwidth: " << width << endl;

// This prints out the address of the variable width. This is just like what we did with age
// above. It's the address of the variable, not the value at the variable (which is also an
// address). The address we get from this is the address of the location on the stack where
// we store the address to the value stored on the free store.
cout << "&width: " << &width << endl;

// The indirection operator (*) is used to print out the value a pointer points to. In this
// case it points to the value 30.
cout << "*width: " << *width << endl;

// Now that we're done using our pointer, we MUST delete it!
delete width;
Using Pointers

Alright, so why use pointers? Remember when we talked about the stack and how local variables only exist where they're declared? For example, if we declare a variable on the stack within a function, it will only exist until the end of that. But what if we want our data to persist? This happens for all kinds of reasons. We might have some data representing the location of an enemy in a game. We'll need that data to be available in all kinds of functions (collision detection, rendering, AI processing, etc). So let's look at ways we can do this.

The first way would be to just declare the enemy data in a function and start passing it to other functions. It'll be a bit of a pain because all of our functions will need an extra parameter, but there's an even worse problem with this method. When you declare a variable on the stack in a function, it only lasts as long as that function. If you try passing that data to another function, the new function can't just use the same place on the stack where the data is stored because it could be erased at any time. Thus, the new function has to make its own room on the stack and copy the data. This process is called "passing by value".
Passing by Reference vs. Passing by Value

This brings me to the difference between passing by reference and passing by value. When you pass by value, an entirely new area in memory is created by the function you've passed the data to and the information is copied over. This is fine for something like an integer, but what about a data structure that consists of tons of data? You'll really slow your program down if it has to constantly copy large amounts of data.

Before I talk about passing by reference, let's look at the global variable solution to our problem. With global variables we can have all of our data stored in one place and it can be accessed from anywhere. So what's the problem with this approach?

Well, the problem with global variables is that we can have all of our data stored in one place and it can be accessed from anywhere (yes, I did just repeat myself). This is great for smaller programs. You don't have to create extra parameters in your functions just so you can access data from different parts of your program, and there's no penalty like with passing by value.

The problem comes when you try to write large scale applications. Think of the complexity of most games now. They have phyics engines, graphics engines, sound, input, networking...way too much stuff to be able to keep track of with a mess of global variables. Especially when you have a team of 30 people working on a project. Instead of expecting everyone to keep track of every variable in the program, a different method must be used.

So now we come to the pointer solution and the definition of passing by reference. When we pass by reference, we only pass the address of the data (the data is located on the free store) to the function that we want to access the data. The address is of fixed length (whatever the size of a pointer is on your machine), so we aren't slowing our program down by copying large amounts of data. We also don't need to worry about the data not being there because we are the ones who control its deletion. Note that we can still cause ourselves problems by deleting something on the free store and then trying to access it from somewhere else.

Let's now talk about reference variables and follow with example of passing by reference and passing by value. Reference variables are not pointer variables, but they are very similar. Both reference variables and pointer variables store the address of data on the free store. They differ in how we use them.

To declare a reference variable, you simply add a & after the variable like so:

int& ref;

Reference variables are good for passing the address of a value to a function. If you're wondering why having the function take a pointer isn't just as good, see the following code.

Here's a listing of three functions, one that takes the value of a variable, one that takes a pointer to a variable, and one that takes the address of the variable:

// Just takes the values of the parameters passed to it
// and copies them into the variables x and y
int AddByValue(int x, int y)
{
return x + y;
}

// Takes pointers to the parameters passed to it
int AddByReference1(int* x, int* y)
{
// You have to use the indirection operator because they're pointers
return (*x) + (*y);
}

// Takes the values by reference
int AddByReference2(int& x, int& y)
{
return x + y; // ah, that's nice!
}

// Here's how you would call each function
int x = 4;
int y = 7;

// This one's pretty straight forward, just call it and
// it'll copy the values you pass to it
AddByValue(x, y);

// We have to send the addresses because the function takes pointers.
// Remember, a pointer just stores the address of the data, if we
// were allowed to just send in x and y (without the & operator) we'd
// be telling the variable x to point to the non-existent address 4
// and the variable y to point to the non-existent address 7
AddByReference1(&x, &y);

// Aren't reference parameters great? We just send in the variables
// and it's taken care of for us
AddByReference2(x, y);

As you can see, using reference variables as parameters allows us to use cleaner code than would be possible using pointers as parameters. When we used pointers, we had to pass the function parameters using the address-of operator. We also had to use the indirection operator when we added the two values (we had to use the indirection operator to get the actual value stored at the location the pointers pointed to, otherwise we would have added their addresses. Try it out and see what you get!).

When we had the function take reference variables, everything was taken care of for us. So the moral of the story is, when you want to pass by reference, use reference variables as function parameters.
Conclusion

That concludes our discussion of pointers. Please let me know if you think I could make this any better. And be sure to download the source and play with it if you haven't already.

One final note: When people explain pointers they often make it sound like pointers are the only thing you should ever use. They do this because they are trying to convince you of their importance. However, don't think that you should only ever use pointers.
ReadMore...

Saturday, December 27, 2008

(0) Comments

Block Breaker (Breakout)

welcome to infomix.blogspot.com

What this tutorial covers

* The creation of a Breakout clone
* Loading level information from a file
* Building off of previously written code

Introduction

This tutorial will move faster than previous tutorials because you should already understand most of what's here from the Pong tutorial. Breakout really is just an extension of Pong. All we need to do is cut out the computer opponent and replace it with some blocks that will "break" when the ball hits them.

To make things a little more interesting, we'll be loading the locations of the blocks from .txt files. It's important to get used to loading data from external files because you'll be doing it like crazy for larger projects. Level data, model information, scripts, and generally all of the actual content in a game is loaded from external files. Not only does this allow you to load information from data files that were created by other programs (thus saving you from having to enter that information in by hand), this also saves you from having to recompile every time you need to change a value. If your program loads the data in at run-time, you just have to make the necessary changes to your files and re-run the program. No recompiling required.

Although we'll be building off of the code from the Pong tutorial, I think that it would get confusing if I just told you what changes to make. Instead, I'll be going through all of the code for the project and will let you know when we've already covered something. With that in mind, it's time to start a new project!
Getting started

Click Here if you need the files from the Introduction tutorial.

The first thing we need to do is start a new project called "Block Breaker" and copy in "Main.cpp" and "Defines.h" from the Introduction tutorial. Also remember to copy "SDL.dll", "SDL_ttf.dll", and "ARIAL.TTF" into you project directory and set Project->Block Breaker Properties->C/C++->Code Generation->Runtime Library to Multi-threaded DLL (/MD). You'll also need the bitmap for this tutorial, which can be found in the downloadable source code.
The Code
Defines.h

We'll be storing our blocks in an array, so we need to specify how many blocks we want when we intialize the array. We might want to change this value later, so we'll define it here.

Since the only real strategy in Breakout is to get the ball above the blocks (so it'll keep rebounding off of the "roof"), it's a good idea to always have space between the sides of the screen and the blocks. It's tedious to have to break through a bunch of blocks before you can get to the roof. We'll define the amount of space here.

The player will be given a certain amount of lives and will have to pass a certain amount of levels. We'll define that information here too.

The rest should be self-explanatory, so here's what you should add after #define FRAME_RATE 1000/FRAMES_PER_SECOND:

// Location of images within bitmap
#define PADDLE_BITMAP_X 0
#define PADDLE_BITMAP_Y 0
#define BALL_BITMAP_X 100
#define BALL_BITMAP_Y 0
#define YELLOW_X 0
#define YELLOW_Y 20
#define RED_X 0
#define RED_Y 40
#define BLUE_X 80
#define BLUE_Y 20
#define GREEN_X 80
#define GREEN_Y 40

// Minimum distance from the side of the screen to a block
#define BLOCK_SCREEN_BUFFER 40

// Maximum number of blocks allowed
#define MAX_BLOCKS 80

// Number of rows and columns of blocks
#define NUM_ROWS 6
#define NUMCOLS 9

// Location of the player's paddle in the game
#define PLAYER_Y 550

// Dimensions of a paddle
#define PADDLE_WIDTH 100
#define PADDLE_HEIGHT 20

// Dimensions of a block
#define BLOCK_WIDTH 80
#define BLOCK_HEIGHT 20

// Diameter of the ball
#define BALL_DIAMETER 20

// Paddle speed
#define PLAYER_SPEED 10

// Ball speeds
#define BALL_SPEED_MODIFIER 5 // divide location on paddle by this
#define BALL_SPEED_Y 10 // max speed of ball along y axis

// Maximum number of times the player can miss the ball
#define NUM_LIVES 5

// Number of levels, increase this value to add new levels
#define NUM_LEVELS 3

// Locations of output text
#define LIVES_X 5
#define LIVES_Y 5
#define LEVEL_X 75
#define LEVEL_Y 5
Includes

We'll use the std::string for building output strings as well as for building file names (covered later). For file I/O, we'll use fstream. I'll show you how to perform file I/O when we get to initializing our blocks. For now, add this to "Main.cpp":

#include // We'll use the STL string for text output and for our file names
#include // We need to read in our levels from files
Global Data

Although the Entity structure we used in the Pong tutorial would work here for the paddle and the ball, I decided to split them into two different structures. The structure we'll be using for our blocks will be slighty different and I didn't want to have one general struct (Entity) and one specific one (Block). Thought it might get confusing...

You should have no problem with the Ball and Paddle structures, so I'll just post them. The only change is that the Paddle struct no longer has a y_speed variable. The Ball struct is just the Entity struct with a new name. Add the following to "Main.cpp":

// The paddle only moves horizontally so there's no need for a y_speed variable
struct Paddle
{
SDL_Rect screen_location; // location on screen
SDL_Rect bitmap_location; // location of image in bitmap

int x_speed;
};

// The ball moves in any direction so we need to have two speed variables
struct Ball
{
SDL_Rect screen_location; // location on screen
SDL_Rect bitmap_location; // location of image in bitmap

int x_speed;
int y_speed;
};

The Block structure doesn't need speed variables but it does need to keep track of the number of times the block has been hit. The blocks will change color when they get hit until their hit count reaches zero. Here's the Block struct:

// The block just stores it's location and the amount of times it has been hit
struct Block
{
SDL_Rect screen_location; // location on screen
SDL_Rect bitmap_location; // location of image in bitmap

int num_hits; // "health"
};

For global data we need the player's paddle, the ball, the player's lives, the current level, the number of blocks, and an array to hold the blocks.

Paddle g_Player; // The player's paddle
Ball g_Ball; // The game ball
int g_Lives; // Player's lives
int g_Level = 1; // Current level
int g_NumBlocks = 0; // Keep track of number of blocks
Block g_Blocks[MAX_BLOCKS]; // The blocks we're breaking

Notice that we keep track of the number of blocks. Since the number of blocks in our game will vary, the block array will almost never be full. When we loop through the array to draw the blocks or detect collisions, we'll need to know how far into the array to look. We don't want to loop into a part of the array that's empty and try to work with something that isn't there.
Function Prototypes

These functions should look pretty familar by now, add them right after the prototype for Exit():

void GameWon();
void GameLost();

// Helper functions for the main game state functions
...
void HandleWinLoseInput();

You can also delete the prototype and definition for DrawBackground(), unless you want a background for your game.

For collision detection, we need a function for checking collisions between the ball and the player's paddle, and one for checking for collisions between the ball and the blocks. We'll also have a function that handles the event of a block being hit by the ball. This function will take the index of the block that's been hit as a parameter.

You'll notice that we no longer pass parameters to CheckBallCollisions(). This is because there's only one paddle now. You'll also notice the I've included a function that checks to see if a point is inside a rectangle. Since our collision detection is based on checking for bounding rectangles, this function should save us a lot of time.

bool CheckBallCollisions();
void CheckBlockCollisions();
void HandleBlockCollision(int index);
bool CheckPointInRect(int x, int y, SDL_Rect rect);

The following prototypes are straight out of the Pong tutorial with the exception of ChangeLevel() which...changes the level.

void HandleBall();
void MoveBall();
void HandleLoss();
void HandleWin();
void ChangeLevel();

The last function to add is InitBlocks(). This function will load the locations and hit counts of the blocks according to what level we're on. We'll call it at the beginning of the game, as well as when we change levels or restart the game.

void InitBlocks();
Init()

Everything in Init() has already been covered, so I'll just give you the code. The only real change here is that we call InitBlocks().

void Init()
{
// Initiliaze SDL video and our timer.
SDL_Init( SDL_INIT_VIDEO | SDL_INIT_TIMER);
// Setup our window's dimensions, bits-per-pixel (0 tells SDL to choose for us),
// and video format (SDL_ANYFORMAT leaves the decision to SDL). This function
// returns a pointer to our window which we assign to g_Window.
g_Window = SDL_SetVideoMode(WINDOW_WIDTH, WINDOW_HEIGHT, 0, SDL_ANYFORMAT);
// Set the title of our window.
SDL_WM_SetCaption(WINDOW_CAPTION, 0);
// Get the number of ticks since SDL was initialized.
g_Timer = SDL_GetTicks();

// Initialize the player's data

// screen locations
g_Player.screen_location.x = (WINDOW_WIDTH / 2) - (PADDLE_WIDTH / 2); // center screen
g_Player.screen_location.y = PLAYER_Y;
g_Player.screen_location.w = PADDLE_WIDTH;
g_Player.screen_location.h = PADDLE_HEIGHT;
// image location
g_Player.bitmap_location.x = PADDLE_BITMAP_X;
g_Player.bitmap_location.y = PADDLE_BITMAP_Y;
g_Player.bitmap_location.w = PADDLE_WIDTH;
g_Player.bitmap_location.h = PADDLE_HEIGHT;
// player speed
g_Player.x_speed = PLAYER_SPEED;
// lives
g_Lives = NUM_LIVES;

// Initialize the ball's data //

// screen location
g_Ball.screen_location.x = (WINDOW_WIDTH / 2) - (BALL_DIAMETER / 2); // center screen
g_Ball.screen_location.y = (WINDOW_HEIGHT / 2) - (BALL_DIAMETER / 2); // center screen
g_Ball.screen_location.w = BALL_DIAMETER;
g_Ball.screen_location.h = BALL_DIAMETER;
// image location
g_Ball.bitmap_location.x = BALL_BITMAP_X;
g_Ball.bitmap_location.y = BALL_BITMAP_Y;
g_Ball.bitmap_location.w = BALL_DIAMETER;
g_Ball.bitmap_location.h = BALL_DIAMETER;
// speeds
g_Ball.x_speed = 0;
g_Ball.y_speed = 0;

// We'll need to initialize our blocks for each level, so we have a
// separate function handle it
InitBlocks();

// Fill our bitmap structure with information.
g_Bitmap = SDL_LoadBMP("data/BlockBreaker.bmp");

// Set our transparent color (magenta)
SDL_SetColorKey( g_Bitmap, SDL_SRCCOLORKEY, SDL_MapRGB(g_Bitmap->format, 255, 0, 255) );

// We start by adding a pointer to our exit state, this way
// it will be the last thing the player sees of the game.
StateStruct state;
state.StatePointer = Exit;
g_StateStack.push(state);

// Then we add a pointer to our menu state, this will
// be the first thing the player sees of our game.
state.StatePointer = Menu;
g_StateStack.push(state);

// Initialize the true type font library.
TTF_Init();
}
InitBlocks()

Loading information from external files can be frustrating at times. If you try to perform the file I/O before you even know that your program works properly, it will be very hard to tell whether the bug is in your game code, your I/O code, or if there's something wrong with the file itself. When I first wrote the code for this tutorial, I used a loop to intialize the blocks to dummy values and made sure that the code worked. I then went ahead and started loading level information from a file.

So what information are we going to load from a file? For this project, we'll only be loading the number of hits our blocks can take (i.e. their health). We'll store this information in .txt files. Here's what "level1.txt", the file for the first level, looks like:

0 3 3 3 3 3 3 3 0
2 0 3 3 3 3 3 0 2

2 2 0 3 3 3 0 2 2
2 2 2 0 3 0 2 2 2
2 2 2 2 0 2 2 2 2
2 2 2 0 4 0 2 2 2

Our game area will consist of 6 rows and 9 columns of blocks. Each block will be a certain color that depends on how many hits it has left. When we read in these values, we'll skip any blocks that have been given a zero for their hit count.

You'll notice that there are spaces between each number in "level1.txt". When we read in a value, we'll use the overloaded >> operator, which will read a string of characters from our file until it reaches a space or new line character. We only want it to read one character at a time, so we put spaces between each number.

The first thing we need to do in InitBlocks() is declare a file stream object. This is the object that contains the functions we need to carry out our I/O. We then construct a string according to what level the player is on. This code looks a lot like what we did for outputting the player and computer scores in the Pong tutorial, only now we're constructing a string for the name of a file. After that, a call to fstream's open() function will allow us to begin reading information from our file. Add the following code to "Main.cpp":

void InitBlocks()
{
fstream inFile;

// The following code creates a string storing the proper file name. If
// g_Level = 1, we get: "data\\level" + "1" + ".txt" = "data\\level1.txt"
char level_num[256]; // for itoa
string file_name = "data\\level"; // the file will always start with "level"
itoa(g_Level, level_num, 10); // convert g_Level to a string
file_name.append(level_num); // append the level number
file_name.append(".txt"); // we'll just use txt's for our levels

// Open the file for input. Note that this function takes a
// char* so we need to use the std::string's c_str() function.
// ios::in specifies that we want to read from this file.
inFile.open(file_name.c_str(), ios::in);

We now loop through each block in our game and read in its hit count from the file. We'll be using nested for loops for this. The outside loop will be for the rows of blocks, the inside loop will be for the columns. We'll set the location of the current block being intialized according to where we are in in the loop. Note that we'll also need a variable to keep track of what block we're at in the array. We'll call this variable index. Here's the code for the start of the loop:

int index = 0; // used to index blocks in g_Blocks array

// Temporary variable to hold the number we read in from our file
int temp_hits;

// Iterate through each row and column of our blocks
for (int row=1; row<=NUM_ROWS; row++)
{
for (int col=1; col<=NUMCOLS; col++)
{

We now read in the next value from our file. We'll store this value in temp_hits so we can make sure it's not zero. If it is, we'll just skip the current block. There's no need to store blocks with zero hits left. If the hit count isn't zero, we intialize the block's num_hits variable as well as it's location. Notice that we apply BLOCK_SCREEN_BUFFER to make sure our blocks are always a specific distance from the sides of the screen.

// Read the next value into temp_hits
inFile >> temp_hits;

// If temp_hits is zero, we go on to the next block
if (temp_hits != 0)
{
g_Blocks[index].num_hits = temp_hits;

// We set the location of the block according to what row and column
// we're on in our loop. Notice that we use BLOCK_SCREEN_BUFFER to set
// the blocks away from the sides of the screen.
g_Blocks[index].screen_location.x = col*BLOCK_WIDTH - BLOCK_SCREEN_BUFFER;
g_Blocks[index].screen_location.y = row*BLOCK_HEIGHT + BLOCK_SCREEN_BUFFER;
g_Blocks[index].screen_location.w = BLOCK_WIDTH;
g_Blocks[index].screen_location.h = BLOCK_HEIGHT;
g_Blocks[index].bitmap_location.w = BLOCK_WIDTH;
g_Blocks[index].bitmap_location.h = BLOCK_HEIGHT;

Now we set the color of the block according to its hit count. A switch statement handles this process nicely. With that done, we increment the index variable as well as g_NumBlocks. Remember that every time we add a block we have to increment g_Numblocks and we have to decrement it every time we remove a block.

// Now we set the bitmap location rect according to num_hits
switch (g_Blocks[index].num_hits)
{
case 1:
{
g_Blocks[index].bitmap_location.x = YELLOW_X;
g_Blocks[index].bitmap_location.y = YELLOW_Y;
} break;
case 2:
{
g_Blocks[index].bitmap_location.x = RED_X;
g_Blocks[index].bitmap_location.y = RED_Y;
} break;
case 3:
{
g_Blocks[index].bitmap_location.x = GREEN_X;
g_Blocks[index].bitmap_location.y = GREEN_Y;
} break;
case 4:
{
g_Blocks[index].bitmap_location.x = BLUE_X;
g_Blocks[index].bitmap_location.y = BLUE_Y;
} break;
}

// For future use, keep track of how many blocks we have.
g_NumBlocks++;
index++; // move to next block
}
}
}

With our loop completed, we just have to call close() to tell fstream that we are done reading from the file.

inFile.close();
}
Game()

We actually don't need to make that many changes to Game(). As with the Pong tutorial, we need to make a call to HandleBall(). Add the line

HandleBall();

just below the call to HandleGameInput().

Now we need to draw the ball, paddle, and blocks. For the blocks, we iterate through g_Blocks, drawing each block. Add the following after the call to ClearScreen():

// Draw the paddle and the ball
SDL_BlitSurface(g_Bitmap, &g_Player.bitmap_location, g_Window,
&g_Player.screen_location);
SDL_BlitSurface(g_Bitmap, &g_Ball.bitmap_location, g_Window,
&g_Ball.screen_location);

// Iterate through the blocks array, drawing each block
for (int i=0; i{
SDL_BlitSurface(g_Bitmap, &g_Blocks[i].bitmap_location, g_Window,
&g_Blocks[i].screen_location);
}

All that's left is to display the current level and the number of lives the player has left. This code should look very familar to you:

// Output the number of lives the player has left and the current level
char buffer[256];

string lives = "Lives: ";
itoa(g_Lives, buffer, 10);
lives.append(buffer);

string level = "Level: ";
itoa(g_Level, buffer, 10);
level.append(buffer);

DisplayText(lives, LIVES_X, LIVES_Y, 12, 66, 239, 16, 0, 0, 0);
DisplayText(level, LEVEL_X, LEVEL_Y, 12, 66, 239, 16, 0, 0, 0);
GameWon() and GameLost()

Since we're using the code from the Introduction tutorial, we need to add GameWon(), GameLost(), and HandleWinLoseInput(). Instead of making you copy them out of the Pong tutorial, I'll just give you the code here:

// Display a victory message.
void GameWon()
{
if ( (SDL_GetTicks() - g_Timer) >= FRAME_RATE )
{
HandleWinLoseInput();

ClearScreen();

DisplayText("You Win!!!", 350, 250, 12, 255, 255, 255, 0, 0, 0);
DisplayText("Quit Game (Y or N)?", 350, 270, 12, 255, 255, 255, 0, 0, 0);

SDL_UpdateRect(g_Window, 0, 0, 0, 0);

g_Timer = SDL_GetTicks();
}
}

// Display a game over message.
void GameLost()
{
if ( (SDL_GetTicks() - g_Timer) >= FRAME_RATE )
{
HandleWinLoseInput();

ClearScreen();

DisplayText("You Lose.", 350, 250, 12, 255, 255, 255, 0, 0, 0);
DisplayText("Quit Game (Y or N)?", 350, 270, 12, 255, 255, 255, 0, 0, 0);

SDL_UpdateRect(g_Window, 0, 0, 0, 0);

g_Timer = SDL_GetTicks();
}
}

// Input handling for win/lose screens.
void HandleWinLoseInput()
{
if ( SDL_PollEvent(&g_Event) )
{
// Handle user manually closing game window
if (g_Event.type == SDL_QUIT)
{
// While state stack isn't empty, pop
while (!g_StateStack.empty())
{
g_StateStack.pop();
}

return;
}

// Handle keyboard input here
if (g_Event.type == SDL_KEYDOWN)
{
if (g_Event.key.keysym.sym == SDLK_ESCAPE)
{
g_StateStack.pop();

return;
}
if (g_Event.key.keysym.sym == SDLK_y)
{
g_StateStack.pop();
return;
}
// If player chooses to continue playing, we pop off
// current state and push exit and menu states back on.
if (g_Event.key.keysym.sym == SDLK_n)
{
g_StateStack.pop();

StateStruct temp;
temp.StatePointer = Exit;
g_StateStack.push(temp);

temp.StatePointer = Menu;
g_StateStack.push(temp);
return;
}
}
}
}
HandleGameInput()

HandleGameInput() is going to look just like the one from the Pong tutorial, only we now want to check for collisions with the sides of the walls here. Remember that we got rid of HandleWallCollisions() because it took an Entity as a parameter but we split the ball and paddle into different structures. We could write two functions, one for the ball and one for the paddle, but it really wouldn't save us any coding. There's nothing new here, so I have to dump some more code on you. Don't worry, we're almost at the new stuff.

void HandleGameInput()
{
static bool left_pressed = false;
static bool right_pressed = false;

// Fill our event structure with event information.
if ( SDL_PollEvent(&g_Event) )
{
// Handle user manually closing game window
if (g_Event.type == SDL_QUIT)
{
// While state stack isn't empty, pop
while (!g_StateStack.empty())
{
g_StateStack.pop();
}

return; // game is over, exit the function
}

// Handle keyboard input here
if (g_Event.type == SDL_KEYDOWN)
{
if (g_Event.key.keysym.sym == SDLK_ESCAPE)
{
g_StateStack.pop();

return; // this state is done, exit the function
}
if (g_Event.key.keysym.sym == SDLK_SPACE)
{
// Player can hit 'space' to make the ball move at start
if (g_Ball.y_speed == 0)
g_Ball.y_speed = BALL_SPEED_Y;
}
if (g_Event.key.keysym.sym == SDLK_LEFT)
{
left_pressed = true;
}
if (g_Event.key.keysym.sym == SDLK_RIGHT)
{
right_pressed = true;
}
}
if (g_Event.type == SDL_KEYUP)
{
if (g_Event.key.keysym.sym == SDLK_LEFT)
{
left_pressed = false;
}
if (g_Event.key.keysym.sym == SDLK_RIGHT)
{
right_pressed = false;
}
}
}

// This is where we actually move the paddle
if (left_pressed)
{
// Notice that we do this here now instead of in a separate function
if ( (g_Player.screen_location.x - PLAYER_SPEED) >= 0 )
{
g_Player.screen_location.x -= PLAYER_SPEED;
}
}
if (right_pressed)
{
if ( (g_Player.screen_location.x + PLAYER_SPEED) <= WINDOW_WIDTH )
{
g_Player.screen_location.x += PLAYER_SPEED;
}
}
}
CheckBallCollisions(), HandleBall(), and MoveBall()

You're probably sick of copy-pasting by now, so let's get the rest over with. CheckBallCollisions() just handles collisions with the player's paddle now. There's no need to pass it any parameters because there's only one paddle. HandleBall() is the exact same except for a call to HandleBlockCollisions() at the end.

MoveBall() has changed a bit more. Since we got rid of HandleWallCollissions(), we check for wall collisions here. We also now check for collisions with the top of the screen so the ball doesn't disappear into the abyss. If the ball passes the player, we reset it as before and then decrement the player's lives. If the player has zero lives left, we call HandleLoss().

// Check to see if the ball is going to hit the paddle
bool CheckBallCollisions()
{
// Temporary values to keep things tidy
int ball_x = g_Ball.screen_location.x;
int ball_y = g_Ball.screen_location.y;
int ball_width = g_Ball.screen_location.w;
int ball_height = g_Ball.screen_location.h;
int ball_speed = g_Ball.y_speed;

int paddle_x = g_Player.screen_location.x;
int paddle_y = g_Player.screen_location.y;
int paddle_width = g_Player.screen_location.w;
int paddle_height = g_Player.screen_location.h;

// Check to see if ball is in Y range of the player's paddle.
// We check its speed to see if it's even moving towards the player's paddle.
if ( (ball_speed > 0) && (ball_y + ball_height >= paddle_y) &&
(ball_y + ball_height <= paddle_y + paddle_height) ) // side hit
{
// If ball is in the X range of the paddle, return true.
if ( (ball_x <= paddle_x + paddle_width) && (ball_x + ball_width >= paddle_x) )
{
return true;
}
}

return false;
}

void HandleBall()
{
// Start by moving the ball
MoveBall();

if ( CheckBallCollisions() )
{
// Get center location of paddle
int paddle_center = g_Player.screen_location.x + g_Player.screen_location.w / 2;
int ball_center = g_Ball.screen_location.x + g_Ball.screen_location.w / 2;

// Find the location on the paddle that the ball hit
int paddle_location = ball_center - paddle_center;

// Increase X speed according to distance from center of paddle.
g_Ball.x_speed = paddle_location / BALL_SPEED_MODIFIER;
g_Ball.y_speed = -g_Ball.y_speed;
}

// Check for collisions with blocks
CheckBlockCollisions();
}

void MoveBall()
{
g_Ball.screen_location.x += g_Ball.x_speed;
g_Ball.screen_location.y += g_Ball.y_speed;

// If the ball is moving left, we see if it hits the wall. If does,
// we change its direction. We do the same thing if it's moving right.
if ( ( (g_Ball.x_speed < 0) && (g_Ball.screen_location.x <= 0) ) ||
( (g_Ball.x_speed > 0) && (g_Ball.screen_location.x >= WINDOW_WIDTH) ) )
{
g_Ball.x_speed = -g_Ball.x_speed;
}

// If the ball is moving up, we should check to see if it hits the 'roof'
if ( (g_Ball.y_speed < 0) && (g_Ball.screen_location.y <= 0) )
{
g_Ball.y_speed = -g_Ball.y_speed;
}

// Check to see if ball has passed the player
if ( g_Ball.screen_location.y >= WINDOW_HEIGHT )
{
g_Lives--;

g_Ball.x_speed = 0;
g_Ball.y_speed = 0;

g_Ball.screen_location.x = WINDOW_WIDTH/2 - g_Ball.screen_location.w/2;
g_Ball.screen_location.y = WINDOW_HEIGHT/2 - g_Ball.screen_location.h/2;

if (g_Lives == 0)
{
HandleLoss();
}
}
}
CheckBlockCollisions()

When we checked for collisions between the ball and the player's paddle, we checked to see if any of the four corners of the ball had made contact with the paddle. This worked fine since we knew that the ball would always hit the top of the paddle.

Things are slightly different with the blocks though. We want the ball to hit the top and bottom of the blocks, and we also want it to hit the sides. More importantly, we need to be able to tell whether the ball has hit a side or the top/bottom of a block. Obviously if the ball hits the top/bottom of a block we want to change its vertical direction, and if it hits a side of a block we want to change its horizontal direction.

If we handle collisions by checking the corners of the ball, we'll have no idea which direction we need to deflect the ball. Think about the top-right corner of the ball hitting a block. How can we tell if it hit the block from the side, the top, or both?

The simplest solution to this problem is to check the middle points of each side of the ball. If the middle point of the left side of the ball hits something, we can be pretty confident that we need to deflect the ball to the right. To save on typing, we'll store these values in temporary variables. Here's what we have so far:

void CheckBlockCollisions()
{
// Temporary values to save on typing
int left_x = g_Ball.screen_location.x;
int left_y = g_Ball.screen_location.y + g_Ball.screen_location.h/2;
int right_x = g_Ball.screen_location.x + g_Ball.screen_location.w;
int right_y = g_Ball.screen_location.y + g_Ball.screen_location.h/2;
int top_x = g_Ball.screen_location.x + g_Ball.screen_location.w/2;
int top_y = g_Ball.screen_location.y;
int bottom_x = g_Ball.screen_location.x + g_Ball.screen_location.w/2;
int bottom_y = g_Ball.screen_location.y + g_Ball.screen_location.h;

Now we need to loop through the blocks and check for collisions. One thing to note is that the ball might hit more than one block. If the top/bottom of the ball hits a block and the left/right side of the ball hits another block, we'll need to deflect it vertically and horizontally. Because of this, we'll loop through the entire array and keep track of any sides of the ball that have hit something. When we've checked every block, we'll make the appropriate changes to the ball's direction. Here's our ball-to-block collision detection loop:

for (int block=0; block {
// top
if ( CheckPointInRect(top_x, top_y, g_Blocks[block].screen_location) )
{
top = true;
HandleBlockCollision(block);
}
// bottom
if ( CheckPointInRect(bottom_x, bottom_y, g_Blocks[block].screen_location) )
{
bottom = true;
HandleBlockCollision(block);
}
// left
if ( CheckPointInRect(left_x, left_y, g_Blocks[block].screen_location) )
{
left = true;
HandleBlockCollision(block);
}
// right
if ( CheckPointInRect(right_x, right_y, g_Blocks[block].screen_location) )
{
right = true;
HandleBlockCollision(block);
}
}

Note the use of CheckPointInRect(). We'll get to its implementation soon. All it does is return true if the given point is inside the given rect. HandleBlockCollision() takes care of removing the block. We'll go through its implementation next.

Now it's time to handle deflecting the ball. This should be pretty self-explanatory. You'll notice that we also move the ball by BALL_SPEED in the direction that we're deflecting it. This is to make sure that the ball isn't inside the block after the function finishes.

if (top)
{
g_Ball.y_speed = -g_Ball.y_speed;
g_Ball.screen_location.y += BALL_DIAMETER;
}
if (bottom)
{
g_Ball.y_speed = -g_Ball.y_speed;
g_Ball.screen_location.y -= BALL_DIAMETER;
}
if (left)
{
g_Ball.x_speed = -g_Ball.x_speed;
g_Ball.screen_location.x += BALL_DIAMETER;
}
if (right)
{
g_Ball.x_speed = -g_Ball.x_speed;
g_Ball.screen_location.x -= BALL_DIAMETER;
}
}
HandleBlockCollision()

HandleBlockCollision() takes the index to the block that has been hit and handles changing the block's hit count. If the block's hit count reaches zero, we remove that block from the array.

Since we don't need to worry about the order of blocks in the array, we can just copy the last valid block in the array (located at g_Blocks[g_NumBlocks-1]) over top of the block at index. This effectively removes the block from the array while saving us from having to shift everything around. Note that we have to decrement g_NumBlocks so we don't access any blocks twice.

void HandleBlockCollision(int index)
{
g_Blocks[index].num_hits--;

// If num_hits is 0, the block needs to be erased
if (g_Blocks[index].num_hits == 0)
{
g_Blocks[index] = g_Blocks[g_NumBlocks-1];
g_NumBlocks--;

Everytime we remove a block, we need to see if it was the last block in the level. If it is, we change levels with a call to ChangeLevel().

// Check to see if it's time to change the level
if (g_NumBlocks == 0)
{
ChangeLevel();
}
}

If the block's hit count hasn't reached zero, we just have to change its color. This is done with almost the same switch statement as in InitBlocks(). The only difference is that we don't have to handle the block having 4 hits left.

// If the hit count hasn't reached zero, we need to change the block's color
else
{
switch (g_Blocks[index].num_hits)
{
case 1:
{
g_Blocks[index].bitmap_location.x = YELLOW_X;
g_Blocks[index].bitmap_location.y = YELLOW_Y;
} break;
case 2:
{
g_Blocks[index].bitmap_location.x = RED_X;
g_Blocks[index].bitmap_location.y = RED_Y;
} break;
case 3:
{
g_Blocks[index].bitmap_location.x = GREEN_X;
g_Blocks[index].bitmap_location.y = GREEN_Y;
} break;
}
}
}
CheckPointInRect()

This function returns true if the given point is within the given rect. The algorithm is the same as we've been using in all of the tutorials. We're just putting it into its own function so we don't have to type long if statements anymore.

bool CheckPointInRect(int x, int y, SDL_Rect rect)
{
if ( (x >= rect.x) && (x <= rect.x + rect.w) &&
(y >= rect.y) && (y <= rect.y + rect.h) )
{
return true;
}

return false;
}
ChangeLevel()

To change the level, we first need to increment g_Level. We then check to see if the player just finished the last level, in which case we call HandleWin(). Otherwise, we reset the ball, set g_NumBlocks to zero, and call InitBlocks(). InitBlocks() will load the necessary data from the next level file.

void ChangeLevel()
{
g_Level++;

// Check to see if the player has won
if (g_Level > NUM_LEVELS)
{
HandleWin();
return;
}

// Reset the ball
g_Ball.x_speed = 0;
g_Ball.y_speed = 0;

g_Ball.screen_location.x = WINDOW_WIDTH/2 - g_Ball.screen_location.w/2;
g_Ball.screen_location.y = WINDOW_HEIGHT/2 - g_Ball.screen_location.h/2;

g_NumBlocks = 0; // Set this to zero before calling InitBlocks()
InitBlocks(); // InitBlocks() will load the proper level
}
HandleLoss() and HandleWin()

These two functions are almost identical. They first pop all of the states off of the state stack. They then reset the ball, player's lives, level, block count, and blocks in case the player chooses to restart the game. Finally, they push the appropriate state onto the stack.

void HandleLoss()
{
while ( !g_StateStack.empty() )
{
g_StateStack.pop();
}

g_Ball.x_speed = 0;
g_Ball.y_speed = 0;

g_Ball.screen_location.x = WINDOW_WIDTH/2 - g_Ball.screen_location.w/2;
g_Ball.screen_location.y = WINDOW_HEIGHT/2 - g_Ball.screen_location.h/2;

g_Lives = NUM_LIVES;
g_NumBlocks = 0;
g_Level = 1;
InitBlocks();

StateStruct temp;
temp.StatePointer = GameLost;
g_StateStack.push(temp);

}

void HandleWin()
{
while ( !g_StateStack.empty() )
{
g_StateStack.pop();
}

g_Ball.x_speed = 0;
g_Ball.y_speed = 0;

g_Ball.screen_location.x = WINDOW_WIDTH/2 - g_Ball.screen_location.w/2;
g_Ball.screen_location.y = WINDOW_HEIGHT/2 - g_Ball.screen_location.h/2;

g_Lives = NUM_LIVES;
g_NumBlocks = 0;
g_Level = 1;
InitBlocks();

StateStruct temp;
temp.StatePointer = GameWon;
g_StateStack.push(temp);
}
Conclusion

That's all for this tutorial. Breakout and Pong are very similar, so there really wasn't a lot of new stuff to cover. The most important thing we did here was set up our game to read level information from external files. If you want to change the levels, you can just load the .txt files in notepad and change them around. If you want to add new levels, just create more .txt files and change NUM_LEVELS.
ReadMore...