Book Review: Data Structures and Algorithms for Game Developers

Data Structures and Algorithms for Game Programmers

Data Structures
and Algorithms for Game Developers

Allen Sherrod

Thoughts Overall:

Overall, I thought DSAGD was a worthwhile book. I can honestly say that I had fun reading through the basics again and coding up the data structure(s) with each chapter. It has been a good 7+ years since I have written any of the data structures covered in this book, and (as some people know) sorting has never been one of my strengths.

That said, there were also some technicalities about this book (mostly mechanical) that stick out like a sore thumb, which makes me disappointed because I think that they could have all been avoided had someone (not the author in particular) actually taken the time to sit down, read, and give the content a proper editing pass.

Do I Recommend this Book?

I’m usually pretty decisive on this issue, but in this case I’m actually a little bit ambivalent on whether I would recommend this book or not. I will say that DSAGD is not a book I would recommend everyone to read — it certainly depends on the programming level of the person in question.

If they are weak in the areas of (or have just started learning) data structures and sorting, then I think this book is perfect for them. In other words, I would have loved to have this book when I was in CSE 12 back in Spring of 2001 because it makes a point to explain things clearly. It also doesn’t hold your hand in terms of C++ like some other books I have on my book shelf; it just jumps straight into the details about what you need to know about the data structures themselves. I appreciated these aspects of the book a lot throughout the read.

However, I would not recommend this book to a seasoned programmer who is simply looking for a refresher in these topics. I recommend that they should turn to a more solid source (maybe Algorithms in C++ by Robert Sedgewick), as this book will leave them wanting.

Pros:

As I mentioned earlier, DSAGD does a good job of staying on track when it comes to what you need to know about fundamental data structures and sorting algorithms.

Here is a list of the data structures covered:

  • Array
    • Unordered Array
    • Ordered Array
    • Bit Array
  • Linked List
    • Singly-Linked List
    • Double-Ended Link List
    • Doubly-Linked List
  • Stack
  • Queue
  • Deque
  • Hash Table
    • Open-Addressing
      • Linear Probing
      • Quadric Probing
      • Double Hashing
    • Separate Chaining
  • Binary Tree
  • kd Tree
  • Heap
  • Priority Queue
  • Graph

Here is a list of the algorithms covered:

  • Sorting
    • Bubble Sort
    • Insertion Sort
    • Selection Sort
    • Merge Sort
    • Shell Sort
    • QuickSort
    • Radix Sort
  • Compression
    • Run-Length Encoding (RLE)
    • Huffman Coding
  • Misc
    • Partitioning

Everything listed above is explained well and has a corresponding implementation. Most of these implementations are fully fleshed out… my main complaint is that the kd tree is lacking in a couple of important features (such as a Remove() routine).

DSAGD also has a decent amount of examples of when to use certain data structures and sorting algorithms over others. Seeing how this is just as (if not more) important than knowing how to implement them on your own, I could put this point in either the Pros or Cons section, but I’m feeling generous here because I did in fact feel more confident about my stance on data structure usage after finishing DSAGD.

Also, I was pleasantly surprised to see that DXT compressions were covered in the final chapter. I’ve never spent much time in graphics-land, so while I had a basic idea of the differences across the formats nothing was particularly solid — this part of the book was certainly helpful.

Another unexpected surprise that I was happy to see was the provision of a fully functional, platform-independent implementation of a DDS (DirectDraw Surface) file loader (pg 502-509).

Cons:

No book is perfect. It is excusable to see a typo or two. But in this book there were enough spelling and grammar errors that it became noticeable… and that’s when it started to distract from the reading.

I also think that this book could have either been 100 pages shorter, or have 100 more pages worth of examples, data structures, and algorithm implementations (like a SkipList or a Remove() routine for the kd tree!). I make this claim based on the fact that there were places where the code was simply reprinted — for no good reason. I can understand when an author wants to explain things in-line with the code; so they print the implementation and then write a few paragraphs of explanation. I can also understand the benefit of having the entire class printed in completion after the routines and member variables and any miscellaneous assumptions have been explained. But it does not make sense to do both — please pick one or the other! Again, like the textual errors mentioned above, if it had happened only once or twice, I could see it being because there was reasoning behind it; but after the third time I seriously started to get the feeling the author was simply trying to fill space.

I’m tired of books printing listings of the signatures of STL routines… and on top of that, getting them wrong. Yes, DSAGD talks about the STL in addition to the custom implementations listed earlier. At this point in the article, it should be apparent which I am more interested in… it’s why I bought the book in the first place! If you’re looking for a games-oriented view on the STL, check out chapters 8 and 9 in C++ for Game Programmers for a solid, well-written discussion. I own a couple books that focus exclusively on the STL, including: The C++ Standard Library: A Tutorial and Reference and Meyer’s Effective STL, and there are many more books dedicated to explaining the STL in detail out there, so I highly recommend going to one of those before thinking of using DSAGD as an STL reference.

My final complaint was the glossing over of scene-management topics at the end of the book. Granted, this was not what this book was about, and I still have yet to read a really good book on the subject of scene-management, but I felt like I had been taunted after I had finished reading that chapter. Sherrod prints a full implementation of a Vector3d class when he could have at least spent some more time talking about the QuadTree and Octree… or better yet: explaining a concrete implementation! Surely these spatial data structures aren’t difficult to implement on my own but I’m still wondering why he took a step backwards to print the Vector3d code… this is a data structures book, not a math primer.

Final Word:

Despite the aforementioned shortcomings, I think DSAGD handles the subject of the fundamental data structures and sorting algorithms very well. The book has a lot of potential and deserves a second edition to clean up the mechanical errors. In the meantime, just be prepared to skip multiple pages at a time when he reprints code, and don’t get your expectations up too high about the content of the final four chapters.

Assert

Assert is one of the most important, indispensable, underused devices in a programmer’s toolkit.

One thing that I’ve found is that I can’t live without is the assert mechanism. In fact, it’s the first thing I wrote in the Pulsar codebase. This is something that has “plagued” me ever since I was first introduced to it in Steve Maguire’s Writing Solid Code. Furthermore, throughout my reading adventures I’ve found a number of good passages about the assert mechanism. Unfortunately, this cardinal knowledge is spread across several books, so I’ve decided to compile a more compact, centralized synopsis to help give readers a detailed overview.

assert()

Whenever I research something, I always find it best to approach it from multiple angles in hopes to gain a more complete understanding. There are many different ways to “define” assert() — in fact, I have no less than 10 books in my own personal library that devote some portion of their text to this very device! [1]

So let’s start where I started: Writing Solid Code by Steve Maguire. Maguire devotes an entire chapter to the assert() mechanism, in which he outlines its potential to improve both the development and quality of a codebase. And if that wasn’t enough, he also exposes a few common pitfalls that have been known to gobble up the unsuspecting unseasoned programmer.

assert is a debug-only macro that aborts execution if its argument is false.

— Steve Maguire, Writing Solid Code

I love Maguire’s straightforward description — it’s simple and precise. However, while this is a nicely formulated answer for something like an interview question, I don’t recommend using this as your explanation for someone who’s never heard of assert() before. In fact, as we will see throughout this article there are many implications that need to be dug out of this pithy answer and brought to light.

Also, I want to emphasize the fact that assert() is a macro (or if you’re Stephen Dewhurst: a “pseudofunction”), not a function. This is an important point because we want to minimize the impact these checks make on our code as much as possible, so that the difference between the execution code for the debug and release builds is negligible. Calling a function proper is likely to cause a state change in our code which means both more overhead, the unloading / loading of registers, a change in the callstack, etc.

The C Programming Language (also often referred to as K&R) defines assert() as follows:

The assert macro is used to add diagnostics to programs:

void assert(int expression)

If expression is zero when assert(expression) is executed, the assert macro will print on stderr a message, such as

Assertion failed: expression, file filename, line nnn

It then calls abort to terminate execution. The source filename and line number come from the preprocessor macros __FILE__ and __LINE__. If NDEBUG is defined at the time <assert.h> is included, the assert macro is ignored.

To be clear, the K&R reference listing is specific to the assert() macro provided in the C Standard Library via the <assert.h> header (or the C++ equivalent <cassert>). It outlines not only the exact signature, but also provides details to its execution behavior. In comparison, Maguire’s definition is more about the concept of assert — the basics a programmer should bare in mind when they encounter or author an assert — allowing it to apply to any implementation: standard or custom.

Also, the fact that assert() is detailed in K&R states that it is an established device in C and C++ (as well as other languages). This means that you can use the assert() macro and be confident that it is both a portable and communal means of enforcing a necessary condition.

Assert statements are like active comments — they not only make assumptions clear and precise, but if these assumptions are violated, they actually do something about it.

— John Lakos, Large-Scale C++ Software Design
[Asserts] occupy a useful niche situated somewhere between comments and exceptions for documenting and detecting illegal behavior.

— Stephen Dewhurst, C++ Gotchas

Although these aren’t quite definitions, I chose to examine this pair of related excerpts because I think that together they conjure up an interesting idea that serves as an excellent supplement to the already said definitions. In particular, the notion that an assert is an “active comment” should make any programmer’s ears perk up.

How many times have you written the assumptions your function makes in a comment at the top of your code? How many times have you traced bugs down deep into the bowels of a codebase only to find that somebody (maybe you!) disregarded the assumptions outlined in the comment? If you follow Lakos’ advice and employ the use of assert statements to enforce the assumptions made in your code, you can rest assured that you’ll be notified if any of those assumptions are ever ignored again.

Finally, I want to finish this section with an important point made by Noel Llopis:

Asserts are messages by programmers for programmers.

— Noel Llopis, C++ for Game Programmers

This detail about the assert mechanism is probably the most forgotten over any other. Asserts are added to the code for a number of reasons (which we will soon get to), but none of them include the end-user.

Common Usage

After reading the above, you must be itching to see how to actually use an assert() in practice, so let’s take a look at a few common, simple, and admittedly contrived examples.

Example 1: Prohibiting the Impossible

Whenever you find yourself thinking “but of course that could never happen,” add code to check it.

— Andrew Hunt and David Thomas, The Pragmatic Programmer

Let’s say you have an enumeration of error codes which includes both fatal and non-fatal errors. In an effort to help make the distinction easier, the fatal error codes are negative while non-fatal error codes are positive. All errors are reported through the ErrorHandler, but create different objects depending upon whether they are fatal or non-fatal. Thus, you could add a “sanity check” to verify this assumption in the following manner:

enum ErrorCode
{
   ...  /* Fatal Errors < 0 */
   ...  /* Non-Fatal Errors > 0 */
}

class Error
{
public:
   virtual ~Error() = 0;

private:
   ErrorCode mErrorCode;
}

class FatalError : public Error
{
public:
   explicit FatalError(const ErrorCode errorCode)
      : mErrorCode(errorCode)
   {
      assert( mErrorCode < 0 );
   }

   virtual ~FatalError() {}
}


class NonFatalError : public Error
{
public:
   explicit NonFatalError(const ErrorCode errorCode)
      : mErrorCode(errorCode)
   {
      assert( mErrorCode > 0 );
   }

   virtual ~NonFatalError() {}
}


void ErrorHandler::HandleError(const ErrorCode errorCode)
{
   Error* error = NULL;
   if(errorCode < 0)
      error = new FatalError(errorCode);
   else if(errorCode > 0)
      error = new NonFatalError(errorCode);
   ...
}

The assert() statements are being used here to guard against the impossible. And it’s important to note that if the “impossible” does happen (and believe me, it can), you should terminate the program immediately with extreme prejudice[2].

Example 2: Enforcing Preconditions

Preconditions are the properties that the client code of a routine or class promise will be true before it calls the routine or instantiates the object. Preconditions are the client code’s obligations to the code it calls.

— Steve McConnell, Code Complete

Now let’s say you wrote a function that computes the square root for a given value: SquareRoot(). Since you’re not dealing with complex numbers in your code, you don’t want this function operating on a negative value. In fact, you’d like to be notified if this function does happen to receive a negative value because that would mean that whatever calculations are using this routine aren’t handling all the possibilities before calling your SquareRoot(). This sounds like a perfect place to use an assert()!

float SquareRoot(const float value)
{
   assert( value >= 0 );
   ...
}

In this case, we are using an assert() to enforce the precondition that value parameter must be nonnegative. Again, this is something that will help a programmer during an application’s development cycle, not an end-user.

Example 3: Enforcing Postconditions

Postconditions are the properties that the routine or class promises will be true when it concludes executing. Postconditions are the routine’s or class’s obligations to the code that uses it.

— Steve McConnell, Code Complete

Using the same SquareRoot() function from Example 2, let’s add a check to ensure that our final output value sqrtValue is non-negative.

float SquareRoot(const float value)
{
   ...
   assert( sqrtValue >= 0 );
   return sqrtValue;
}

We could also add a check to ensure that our computation is correct:

float SquareRoot(const float value)
{
   ...
   assert( sqrtValue >= 0 );
   assert( FloatEquals(sqrtValue*sqrtValue, value, EPSILON) );
   return sqrtValue;
}

Example 4: Switch Cases

This is one of my favorite places to use the assert() because it helps guard against mistakes while allowing for code extension.

Let’s say you have a set of different platforms your code can output asset files for: Win32, Xenon, and PS3. However, it’s important to write your code in a way that allows for extension for additional platforms (say the Nintendo Wii). Here’s how we can enforce this in our AssetFileWriter:

bool AssetFileWriter::Write(const byte* data,
   const char* filename, const Platform platform)
{
   switch(platform)
   {
      case Platform::WIN32:
         /* write data to file for Win32 */
         break;
      case Platform::XENON:
         /* write data to file for Xenon */
         break;
      case Platform::PS3:
         /* write data to file for PS3 */
         break;
      default:
         assert(false);  /* invalid platform specified */
   }
   ...
}

Now when we get the green light to add the Wii to our list of supported platforms, we will be notified if we happen to forget to add the case in the AssetFileWriter.

Caveats

As Noel pointed out to us earlier, asserts are employed for the benefit of programmers, not end-users. They are active only for _DEBUG builds and are compiled out for all others. The consequences of forgetting this principle can be particularly dangerous. The details to this are two fold:

  1. The assert() expression argument should not contain any required code. This is because all instances of assert() in your code are omitted when compiling a non-debug build of your application.

    The canonical example of this is using a required function call inside assert() expression:

    bool WriteDataToFile(const char* filename, const byte* data);  /* prototype */
    
    assert( WriteDataToFile(filename, data) );  /* uh-oh... */
    

    Guess what happens when you compile a release build (or any build that defines NDEBUG for that matter)… no file for you! The solution to this should be clear, save the data you want to check to local variables and use those in the assert().

    const bool bFileWriteSuccessful = WriteDataToFile(filename, data);
    assert( bFileWriteSuccessful == true );  /* much better */
    

    To be perfectly clear, not all function calls must be avoided inside the assert(). For example, usage of strlen() or another const function guaranteed to have no side effects is perfectly fine to use inside the assert() expression. However, in C++ Gotchas, Dewhurst touts:

    Proper use of assert avoids even a potential side effect in its condition.

    — Stephen Dewhurst, C++ Gotchas

    alluding to functions that appear to be const from the outside, but actually perform some operations in order to return a value.

    Another good, yet more subtle example is the following:

    assert( ++itemCount < maxItemCount );   /* doh! */
    arrayOfItems[itemCount] = itemToAdd;    /* add item to list */
    

    In this case you'll find that the value of your itemCount never changes in the release builds because your increment was compiled out (which means you'll just keep overwriting the current item!) Here, we need to push the required increment operation out of the assert:

    assert( (itemCount+1) < maxItemCount );   /* safe check */
    arrayOfItems[++itemCount] = itemToAdd;    /* add item to list */
    
  2. assert() should not be treated as a means of or substitution for proper error-checking.

    The following code snippet resembles a case I have seen more often than I'd like to admit.

    char filename[MAX_PATH];
    OpenFileDialog(&filename, MAX_PATH);  /* fills in filename buffer*/
    assert( strlen(filename) > 0 );
    ...  /* do something with filename */
    

    Here the assert() is being used in a place where proper error-checking should be employed. This is dangerous because while the programmer is rightfully protecting the rest of their code from using an invalid filename, they are going about it in a way that assumes that a user will always proceed to choose a file in the OpenFile dialog. This is a bad assumption because the end-user most certainly has the right to (and will) change their mind about opening a file.

Asserts vs. Exceptions

An assert is different from an exception. A failed assertion represents an unrecoverable, yet programmer-controlled crash. A thrown exception represents an anomaly or deviation from the normal execution path -- both of which have the possibly of being recoverable.

To be clear, you should use an assert() if the code after the assertion absolutely positively cannot execute properly without the expression in question evaluating to TRUE. One example of this is the pointer returned from malloc():

void* memBlock = malloc(sizeInBytes);
assert( memBlock != NULL );
...  /* use the allocated memory block */

If malloc() happens to return NULL (which can and does happen!), the rest of the code that follows which uses memBlock has no hope of working properly. As such, we have used an assert() so that we can control the termination of the application rather than allow the continued execution to do something worse.

Another good place for an assert statement is right before accessing an array at a given index. For example, say we have an ItemContainer class that holds an array of Items internally which has a const accessor routine GetItem(). Then we could use an assert() to check the requested Item index in the following manner:

const Item& ItemContainer::GetItem(const int itemIndex) const
{
   assert( (itemIndex >= 0) && (itemIndex < mItemCount) );
   return mItemList[itemIndex];
}

Because we unarguably don't want to be accessing memory outside the bounds of the array, we have employed an assertion to notify us if the calling code tries to do just that. The importance of this example is two-fold: not only are we protecting ourselves from silently accessing "foreign" memory, but we are also enabling an additional internal layer of debugging for the calling code (which may have a bug in the way it computes the itemIndex parameter).

While I'm not going to go into all the details of exceptions and when and when not to use them, I will offer an example of usage for comparison.

Let's say you have a routine that reads data from an external source (USB drive, network, etc.). What do you do if the data source is unplugged in the middle of a read? Do you terminate the program? NO WAY! The proper way to handle such a case is to throw an exception and let the exception propagate up to a safer point in the code where the exception can be handled by notifying the user with a nice little dialog box that says "I wasn't done. Plug it back in!", all without terminating the program. If it is the user's intention to exit after they unplug the data source, force them to do so via the conventional means your application has made available to them -- it's just good manners.

Asserts vs. Unit Tests

There's something else I want to be clear about: asserts are not a means of or substitution for unit testing. Just because we have included an assertion check to make sure the value of our SquareRoot() function is non-negative doesn't mean we should forgo any appropriate unit testing.

Unit testing can only take you so far. If you write good tests, you can get good coverage for your code; but you don't run unit tests for every value that ever enters your routine. That's why if you forget a case in your unit tests, all your tests will pass but you'll still have bugs. So both unit tests and asserts should be employed together. They are on the same team.

What if we want to test our assertions? Well, the best example I give you for this is outlined in a post about Assert from they guys at Power of Two Games: Stupid C++ Tricks: Adventures in Assert). Briefly, you need to test that an assertion thrown you will need to add some additional hooks into the way you manage your assert() to ensure that your unit tests handle assertion failures gracefully.

Implementing a Custom Assert Macro

In this section I'm going to examine some custom implementations of assert(). For the most part they all implement the same functionality, but I found it very interesting how many different ways I had come across in the books on my shelf. We'll also look at various implementation flaws (whether intentional or not) and finally wrap up with the implementation I use in Pulsar.

The assert example from C++ Gotchas:

#ifndef NDEBUG
   #define assert(e) ((e) \
      ? ((void)0) \
      :__assert_failed(#e, __FILE__, __LINE__) )

#else
   #define assert(e) ((void)0)

#endif

I consider this the classic C skeleton of assert(). To customize, you would replace __assert_failed() with something that handles the assertion in a way tailored to your own needs.

Unfortunately, I have a problem with this method -- unless __assert_failed() is a macro that includes the code to invoke a breakpoint (__asm int 3; and the like), it assumes you will break inside the function and not at the line that broke your code. A little annoying -- but, seriously, even the little things are important. Following a recommendation to put the breakpoint code inside the assert() macro (not the handler function), you will be able to get the debugger to stop right at the failed assertion line rather than three callstacks up.

The custom assert example from Writing Solid Code:

#ifdef DEBUG
   void __Assert(char* filename, unsigned int lineNumber);   /* prototype */

   #define ASSERT(f) \
      if(f)          \
         {}          \
      else           \
         __Assert(__FILE__, __LINE__)

#else
   #define ASSERT(f)

#endif

This was the first custom assert() implementation I was introduced to. Looking back on it, one thing I don't like about it is that Maguire doesn't include a text version of the expression in the parameters provided to the assert handler.

Also notice that instead of ((void)0), absolutely nothing is evaluated for the Release build. This is a bit troublesome because, if you noticed, Maguire purposefully left off the semicolon after the __Assert(__FILE__, __LINE__) to give the compiler a reason to enforce the client to add one. But he's left room for error in the Release build.

The custom assert example from Code Complete:

#define ASSERT(condition, message) {    \
   if( !(condition) ) {                 \
      LogError( "Assertion failed: ",   \
         #condition, message );         \
      exit( EXIT_FAILURE );             \
   }                                    \
}

At first you might say... Aha! What about a dangling else?! But if you look closely at McConnell's code, he uses an additional pair of braces to enforce scoping on his version of assert(). The problem here is that you no longer are forced to append that semicolon.

Also, notice that McConnell doesn't break either -- he just exits. During development, I find it extremely handy to have a failed assert break into the debugger, not just print me an error message and bail.

Finally, where are the build configuration #ifdef's ? As is, this code's going to run in all builds!

These might all sound like me knit-picking, but hey! this is assert()! This is something I use EVERYWHERE! so it better be solid, pristine, and easy to use.

The custom assert example from C++ for Game Programmers:

#ifdef _DEBUG
   #define DO_ASSERT
#endif

#ifdef DO_ASSERT
   #define Assert(exp, text) \
      if(!(exp) && MyAssert(exp, text, __FILE__, __LINE__)) \
         _asm int 3;

#else
   #define Assert(exp, text)

#endif

Noel's got an interesting addition in his version of assert(): the DO_ASSERT symbol. I think this is actually a nice way to allow developers to turn assertions on and off for multiple builds, especially if you have more than just a Debug and Release configuration (i.e. a additional Debug build with optimizations turned on, or a "Final" build).

However, Noel's suffers from a very important problem: a dangling else. Let's say you happen to put this assert inside an if / else block. Guess what, that else is going to attach itself to the if inside the assert() when the macro expands, which is not the logic you had in mind. This can be combated with the scoping we've seen earlier, or my preference of a do / while(0) loop.

The authors of The Pragmatic Programmer argue that there's no need to follow suit when it comes to printing an error message and terminating the application outright with abort() in your assertion. In fact, they claim that as long as your assertion handler is not dependent upon the data that triggered the assert you are free to perform any necessary clean up and exit as gracefully as possible. In other words, when an assertion fails it puts control of the "crash" into the hands of the programmer.

A good example of this is exhibited by Steven Goodwin in Cross-Platform Game Programming:

#define sgxAssert(expr)
   do { \
      if( !(expr) ) { \
         sgxTrace(SGX_ERR_ERROR, __FILE__, __LINE__, #expr); \
         sgxBreak(); \
      } \
   }while(0)

Again, this seems to be missing the #ifdef -- maybe these authors are just trying to save trees?

Finally, taking all that I have learned -- my implementation of assert() looks something like the following:

#ifdef PULSAR_ASSERTS_ENABLED
   namespace pulsar { namespace AssertHandler {
      bool Report(const char* condition, const char* filename, int lineNumber);
   }}

   #define PULSAR_ASSERT(cond) \
      do { \
         if( !(cond) && pulsar::AssertHandler::Report(#cond, __FILE__, __LINE__) ) \
            PULSAR_DEBUG_BREAK(); \
      } while(0)

#else	// asserts not enabled
   #define PULSAR_ASSERT(cond) \
      do { \
         PULSAR_UNUSED(cond); \
      } while(0)

#endif  // end PULSAR_ASSERTS_ENABLED

I'm utilizing the same trick Noel offers in his version to separate out the enabling of asserts via a single defined symbol PULSAR_ASSERTS_ENABLED.

The PULSAR_DEBUG_BREAK() macro calls __debugbreak() rather than straight __asm int 3; for the sake of x64 compatibility.

The PULSAR_UNUSED() macro utilizes the sizeof() trick detailed in Charles' article.

I'm also utilizing the do / while(0) loop convention to wrap my macros (including the PULSAR_DEBUG_BREAK() and PULSAR_UNUSED()) for scoping and to enforce the requirement of a semicolon.

My AssertHandler has been implemented in the same spirit as exhibited by the guys at Power of Two. This was mainly because I like the idea of being able to test with my asserts, and even test that the asserts are being thrown in the first place! If you haven't taken a look at their article yet, I highly recommend you do.

Conclusion

This has been a fun (and two week long) ride to put this article together. I tried to take a comprehensive approach, and, as we can see, there's a lot that can go into such a tiny little mechanism...

As I said in the beginning, assert() is one of the most important tools I have for code development and after reading this I hope it's crystal clear why.

Footnotes

1. I use a lot of them, but not all, as references throughout this article.

2. In case you were wondering, why would we ever want to crash (as gracefully as possible) the program? Won't users lose their unsaved work? Won't they be mad? The answer is simple and resounding: YES. It is far better to abort the application than possibly allow for a user to continue using it in its invalid state while believing that everything is perfectly fine, or even worse corrupt their data. A user will most certainly be upset that they lost any unsaved work, but not anywhere near as angry as they would be if we corrupted their entire dataset!

References

Dewhurst, Stephen C. C++ Gotchas. 2003. pp 72-74.

Goodwin, Steven. Cross-Platform Game Programming. 2005. pp 262-265.

Hunt, Andrew and David Thomas. The Pragmatic Programmer. 2000. pp 113.

Lakos, John. Large-Scale C++ Software Design. 1996. pp 32-33.

Llopis, Noel. Asserting Oneself. Games From Within. 2005.

Llopis, Noel. C++ for Game Programmers. 2003. pp 386-402.

Kernighan, Brian and Dennis Ritchie. The C Programming Language. 2nd Ed. 1988. pp 253-254.

Maguire, Steve. Writing Solid Code. 1993. pp 13-44.

McConnell, Steve. Code Complete. 2nd Ed. 2004. pp 189-194.

Nicholson, Charles. Stupid C++ Tricks: Adventures in Assert. Originally posted on Power of Two Games. 2007.

Book Review: C++ for Game Programmers

C++ for Game Programmers

C++ for Game Programmers

Noel Llopis

Foreword

The following is a book review I wrote when I finished my first reading of C++ for Game Programmers back in early 2005. I’ve left it intact so it differs from the formatting of the other reviews I’ve posted.

I remember why I bought this book in the first place. It was December of 2004 and I was having some trouble while working through Zerbst’s 3D Game Engine Programming. I had never officially had a course on C++ and my knowledge of C was rudimentary. I kept reading about const and “pure virtual” member functions (among other things), and finally came to the conclusion that I needed to take a step back and learn about those before moving forward in Zerbst. I found C++ for Game Programmers at a not quite local Barnes & Noble and picked it up. I especially remember the fact that this book really met me where I was as a programmer: not bothering with the basics of programming, but rather concentrating on the aspects of C++ with which I was unfamiliar. As a result, I’ve had a special fondness for the book, as well as a great appreciation for its author.

Looking back, with maybe the exception of McGuire’s Writing Solid Code, I think this is one of the programming books I’ve reread the most. In addition to his clear presentation of the fundamentals, Noel touches several important and useful topics (a number of which I have incorporated into my own code base) in the later chapters.

It should be noted that a second edition has since been released by a different author. I don’t know how different it is from Noel’s edition.

The Review

Noel Llopis’ C++ for Game Programmers is an excellent reference for any game programmer at any level. The text focuses on both essentials of the C++ programming language like inheritance and constness as well as low-level systems within a game’s code base such as memory management and object serialization. The advice offered in Noel’s book has affected and improved every piece C++ I have written since I picked it up and started reading.

C++ for Game Programmers starts off by covering concepts that every C++ programmer should internalize: Inheritance (single and multiple), the const keyword, passing by reference, the C++ style casting, templates, and exception handling. Each topic discussion includes outlining their advantages and disadvantages, when and when not to use them, and is accompanied by simple, yet real-world code examples and scenarios relevant to game development.

After bootstrapping up these aforementioned fundamentals, Noel address principles every programmer is concerned about: performance, memory. The importance of these topics in game programming cannot be understated; both of these chapters are loaded with detailed explanations, practical examples, and useful recommendations. I think that one of the most important components of this book was the straightforward walkthrough of the need for and the implementation of a versatile memory management system (full source code provided on the CD) that can be easily integrated into any C++ project.

The next two chapters of this book are spent evaluating both the advantages and pitfalls found in the C++ Standard Template Library (STL). The overview includes direction on which data structures are good candidates for particular data sets found in games, as well as why they are poor candidates for others. Overall, these two chapters compose a very solid argument for using the STL in game development.

Part Three is where this text really shines. Starting with an in-depth discussion on Abstract Interfaces, the foundation is set for some extremely useful subsystems for game development, including for plug-ins, Runtime Type Information (RTTI), and object serialization. Even though most of the source code provided with these chapters is not designed to be thrown straight into a large code base, all of the important concepts needed for designing a game engine subsystem based on any one of the components mentioned above are clearly provided in the text.

One last, important feature is point of view taken throughout the book. It’s one thing to be working on a project, but it’s a completely different ball game to be working on a large-scale project. Noel brings industry-grade advice to the table for each and every topic covered in the book. This was something I appreciated again and again throughout my reading and I suspect others will too.

So, if you are looking for a book that doesn’t cover the just the basics of C++ programming in the light of game development: this book is for you!

Book Review: 3D Game Engine Programming

3D Game Engine Programming

3D Game Engine Programming

Stefan Zerbst

Foreword

The following is a book review I wrote for Amazon.com a while back. I’ve left it intact so it differs from the formatting of the other reviews I’ve posted.

3D Game Engine Programming was the first game programming book I ever bought. I’ve often said that this is the book that started me off on the right foot; however, as an introductory text to the vast subject, it was both a poor and a great choice.

To be completely honest, I was not ready for this large of a programming project. At the time I was still very new to programming, and had very little C++ experience. This became an impasse later on, which forced me to seek out and purchase another excellent book: C++ for Game Programmers. However, at the same time, Zerbst inspired me to continue on and piece together the components needed for the engine. As a result, after completing my first read through the text and implementing my very first iteration of a game engine, I knew that I had learned and accomplished a lot and I would be utilizing 3DGEP as one of my primary sources for future endeavors.

Undoubtedly, 3DGEP is one of the most comprehensive sources I have found on the subject and very well organized. If you really want to understand what goes into writing a game engine, I recommend steering away from the “Game Programming All in One” books and investing in 3D Game Engine Programming. Even six years later, I still find myself snatching it off my bookshelf for help on assorted topics with my current projects.

Simply put, Zerbst’s 3D Game Engine Programming is one of my favorite resources on the subject of game engine development. I highly recommend it.

The Review

Stefan Zerbst’s 3D Game Engine Programming is a 850-paged guide to constructing a modular, functional video game engine. This reference was one of the biggest reasons I became confident that I could complete a project of my own and has helped me tremendously in the design and building of an engine based upon the fundamentals of the ZFX Engine.

Even though the book does not go into detail and provide the code to all the bells and whistles of a commercial engine, it certainly outlines the basics and even provides code for testing. (I personally liked not having everything provided so that I could add my own features with a more personalized touch). Have no fear: all the basics are there to build off of!

In particular, the text guides the reader through the concepts and code needed to construct an engine that has the ability to support both DirectX and OpenGL (though DirectX is the main focus in the text), Vertex and Pixel Shaders (which is a big plus in upcoming game graphics!), and networkable players. In addition, the book brought extra possibilities such as Non-Player Characters, AI, and other various effects to the table for the reader to take note of where they could be added on to the engine. More importantly, he did do an excellent job of keeping these options (and more!) open without forcing his more ambitious readers to reprogram half the engine.

A very important thing I felt was the key to why I liked it so much was the fact that I understood how the components of the engine worked individually and as a whole to construct a functional game when I had finished the book. So many times have I read a programming book cover to cover and then still be lost on how everything fits together outside of the demos provided in the text– but this book was NOT like that at all. The concepts were presented clearly as well as explicitly outlined within the code.

However, I will note: this book is not for the faint of heart or for the inexperienced programmer. (Hopefully the size scares the aforementioned away in a direction to seek some more practice before coming back to this fantastic reference.) There is a LOT of code and while the text does take care of the graphics, DLL loading, and algorithmic aspects to a FPS game, the book does treat the reader as a programmer and not a novice.

One last, important feature is the Level Editor that is developed along side the engine (that’s right! you build a level editor too!). This chapter (14) is certainly one of the most useful parts of the text and is where a lot of key concepts come together.

So, if you are looking for a book that hits the ground running, providing a complete archive of source code and demos in an effort to construct a comprehensive game engine: this book is for you!