C++ Code Optimization – Optimizing a Particle System

In the fall quarter of 2013 at DePaul University, I took the GAM491 – Optimized C++ class. In this class we learned very advanced techniques to optimize any C++ code. As a final project, we were provided with an old and slow particle system. Each student was required to individually submit an optimized version of it applying as many techniques of what we have studied as possible. The rules were:

  • Keep the number of particles at 20000 for the benchmarks.
  • Keep the particles lifetime at 11 seconds.
  • Do not modify any OpenGL calls, just the modification of the  C++ code, the algorithms and the data structures used were allowed.
  • Do not change any of the particle system behavior.

The results of the optimizations that I made were impressive. They are shown below (an improvement by a factor of about 160 times):

Before

Before - Particle System

Before – Particle System

After

After - Particle System

After – Particle System

Advertisements

Converting an Existing XNA Game into a Networked Multiplayer One

Video demo is at the end.

In the GAM490 – Multiplayer Networking for Games class that I took at DePaul University, we studied a lot of interesting networking topics and then tried to apply them on a game-development related project. In order to prepare for that final networked game project, we studied and implemented best ways to serialize objects, taking into consideration the data sizes and their alignment requirements, so that objects can be efficiently stored and transferred over the network. Each student implemented his own TCP and UDP servers and clients using Windows Sockets, in order to understand the differences between the two protocols. We also studied how to write good data-driven programs employing input and output queues in order to make the processing of sent and received networked packets over the network simple and easy.

For the final project, we were supplied by and XNA game written by a previous student that each student was required to individually convert it into a networked multiplayer game. The requirements of the final game were:

  • Refactor the game code to make it completely data-driven using input and output queues to process the different game events.
  • Adding the ability to create a multiplayer network session either as an XNA system link, or an Xbox Live session. Each player must be able to either create a network session or join an existing one.
  • Adding a Game Lobby screen, in which players can view other players joined in the current session and from there they can start playing the game.
  • The game must be multiplayer playable on two separate machines connected by the network, and the game play must be exactly as that of the original locally-playable game.
  • The game must include network quality simulation configurations, simulating different network latencies, and percent packet loss.
  • The game must implement prediction and smoothing algorithms to account for the network latency and packet loss.
  • The game must be developed as incremental submission to Perforce with detailed description of each submission.
  • Detailed design documents must be submitted.

I had to choose between implementing the network topology of the game as a peer-to-peer topology or a client-server topology. I went for peer-to-peer as I thought it would be easier to implement since the game is a two-player one only, but in fact it was more challenging to implement as I had to deal with a lot of synchronization issues between the two machines which occur due to the network latency and the packet losses. To deal with these issues, good smoothing and prediction algorithms were very important.

Periodic update packets were added to the game to account for any losses. The number of these packets per one frame is adjustable by the game host, and they only contain the ships’ positions and rotations. Smoothing is done by linearly interpolating between the current ships position and rotation values and the new ones received from the newest periodic update. This makes the transition from an old value to a new value appear to be very smooth.

For the prediction, my algorithm is very simple. It starts by calculating the latency; i.e. the time it took the newly received periodic update packet to be delivered. Use this latency value to try to predict where the ship should have been now had this packet arrived on time.

Testing and debugging this game was a challenge, since I had to use two machines and constantly synchronize any code changes between the two. Perforce was very important for this project.

The final game is reviewed in the below video.

Building The Animation System of My Game Engine

For the second milestone of the Game Engine Programming II class that I took in the spring quarter 2013 at DePaul University, I added animation capability to both my game engine and my FBX converter. It was one of the most difficult tasks that I did for this class. It took a lot of iterations to write a good easy-to-use animation system. My intention was to make the system completely data-driven, having the FBX converter extracting all the needed animation data from the FBX file (an FBX file can contain multiple models, with each model having multiple animations in a so-called animation stacks) and placing these data as a table-indexed binary chunks into a .dpu file for the model data, and into a .bdpu file for the skeleton data. The extracted skeleton data are:

  • The skeleton bones hierarchy.
  • The skeleton’s animation stacks.
  • The keyframes associated with each bone in each animation stack.

I then made the game engine capable of loading these data, and using them to draw the bones and animate them.

The Math Engine Library that I wrote for the first part of this class had to be changed to support quaternion math operations and to fully integrate them with the existing vector and matrix operations. Linear & Spherical Linear Interpolation (LERP and SLERP) operations have been added as well. These operations are crucial to any animation engine.

The Animation Engine Features

  • Completely data-driven (loads all needed data from a flexible expandable binary file).
  • Ability to draw bones based on the data read from the binary file. Bones colors can be changed by the user of the system.
  • If the FBX model has multiple animations in multiple animation stacks, they will all be available for that model’s bones and any of them can be selected to be the current active animation in the engine.
  • Ability to play back the animations forward, backward, faster, and slower.

Next thing I will be working on is “Skinning”. The above features are demoed in the below video.

Building And Integrating CppUnitLite in Eclipse on Linux

For this tutorial, I will be demonstrating how to build and integrate the lightweight C++ Unit Testing Framework, CppUnitLite, into your eclipse projects. I will be using Eclipse Juno on Xubuntu, but the same can be done on any other platform of your choice.

If you are familiar with CppUnit, CppUnitLite is – as the website mentions – more barebones, lighter, and more portable as it avoids using some C++ features such as exceptions, and templates.

We will build it as a static library, so that we can then link into any of our projects that we would like to write unit tests for later.

First, we need to get the source code form the CppUnitLite website. Go there and get it. Once you do, extract the zip file. You’ll find that it contains a lot of files and a couple of folders. We only need a sub-set of those, specifically the folders in the CppUnitLite sub-folder highlighted in the below screen shot.

Needed Files

Now go ahead and open up Eclipse. Select File > New > C++ Project.

New C++ Project Menu

From the C++ Project Window, name your project CppUnitLite, and make sure you selected a Static Library project type. Now click on Next >.

Static Library

For the build configuration, you can just select Debug for now. Then click Finish.

Build Configuration

You are now ready to import the source files. Right-click the project and click Import … from the menu.

Import

From the Import window, select General > File System as the import source. Then click Next >.

Import Source

From the next window, click on the Browse button, and navigate to the folder where the needed CppUnitLite sources (highlighted at the top of this post) are located. Now select only the needed files. Make sure NOT to select the two sub-folders Cpp and CppUnitTests. When you’re done, click Finish.

Import Files

Now before we build, I hope you noticed on their website that they have this important note about a bug in the CHECK_EQUAL macro, and the revised one has been provided. This macro is located in the file Test.h. Copy the correct one from the website, and paste over the wrong one in the file.

CHECK_EQUAL Bug

CHECK_EQUAL Correction

Now Build the project. This will create a sub-folder named Debug under your project. If you take a look inside it, you’ll find a file named libCppUnitLite.a. This is the static library file that you would want to link in your projects later.

Build

Library File

Now we’re done with building the library, and we need to experiment with it to write some simple unit tests. For demonstration purposes, we will create a new project, import the library, and the header files of CppUnitLite there, and write some simple unit tests just to show how things work. Create a new C++ project, and make sure the project type is Executable this time. Name the project whatever you want. I named it TestCppUnitLite. Now click Finish.

Test Project

We will create a sub-folder under this project in which we will import the CppUnitLite library and header files shortly. Right-click on the project name and select New > Source Folder. Name the folder CppUnitLite.

Source Folder Menu

Now right-click on that newly created folder, and select Import. From the Import window, as shown above, select General > File System as the import source and click Next >. Click the Browse button and navigate to the folder where we built the library. Once you do that select only the library file (libCppUnitLite.a) from the list and click finish.

Import Library

Repeat exactly the same above mentioned process again to import the header files. Just browse to where they are and import them into the same folder. You’ll need to import 6 header files namely Test.h, TestHarness.h, TestResult.h, TestRegistry.h, SimpleString.h, and Failure.h. Then click Finish.

Import Headers

Now it’s time to write some simple code. Right-click on the project name, and click New > Source File. Name the file main.cpp and click Finish.

Main CPP

All you need to write is the following code. It’s kind of like a boiler-plate code to start running the tests and reporting the results.

#include "CppUnitLite/TestHarness.h"
int main()
{
     TestResult tr;
     TestRegistry::runAllTests(tr);
     return 0;
}

At this moment there isn’t any tests to run, so we need to write some very simple tests just to show how things work. We will create a new source file and we will name it tests.cpp. In this newly created file we will write some tests, some of them are intended to fail just to show how CppUnitLite reports a test failure. Notice that CppUnitLite used predefined macros to enable us to write these simple unit tests easily. Copy and paste the following code into tests.cpp.

#include "CppUnitLite/TestHarness.h"
TEST(EqualitySuccess, EqualityGroup)
{
     int a = 5;
     CHECK(a == 5);
}
TEST(EqualityFailure, EqualityGroup)
{
     int a = 6;
     CHECK(a == 5);
}
TEST(GreaterSuccess, GreaterGroup)
{
     int a = 50;
     CHECK(a > 30);
}
TEST(GreaterFailure, GreaterGroup)
{
     int a = 50;
     CHECK(a > 100);
}

For any test you write, First you’ll need to include the TestHarness.h header file, which includes all of the others for you. Next you’ll need to use the TEST macro. the TEST macro takes two arguments, the first is the test name, the second is the test group. This is useful when you want to create multiple tests that belong to a single group. As you can see above I have to test groups, each of which has two tests, one that is intended to succeed, and the other is intended to fail.

I’m using the CHECK macro for all of my tests above, but you have others too that you can use such as CHECK_EQUAL, LONGS_EQUAL, .. etc. They’re defined in the header file Test.h.

Now we need to build and run those tests to see the result. But WAIT!! If you try to build now, you’ll fail as the linker doesn’t know how to link to the library file. You must specify that yourself.

Right-click the project name and select Properties. From the Properties window, go to C/C++ Build > Settings. From the Tool Settings tab, under GCC C++ Linker > Libraries, you’ll need to do two things.

Linker

You’ll need to add  the library search path. Click on the Add… button next to Library Search Path (-L) and click on the Workspace button, and select the folder where we imported the library file. click Ok, and then Ok again.

Linker Search Path

Next you’ll need to specify the name of the library. From the same window click on the Add… button next to Libraries (-l) and type CppUnitLib. Remember our library file is name libCppUnitLite.a, but GCC C++ Linker doesn’t need the lib or .a parts of the name. So if you named your library libMonkey.a, just type Monkey when you add the library :). Click Ok and then Ok again to exit the project Properties window.

Linker Library

Now everything is ready to build and run. Build the project and run it as a C++ Application, and see the output on the console window. You’ll see that it reports the two intentional failures, what conditions that failed, in which files they are, and in which lines as well.

Console

That’s it! As you can see it’s quite easy and simple to work with CppUnitLite. Thanks everyone! Happy unit testing.