Data Structures For Game Programmers
Author: Ron Penton
Publisher: Premier Press
ISBN: 1-931841-94-2
Purchasing: [Amazon.Com] - RRP US$34.99
Reviewed: 9th February 2004

Front Cover Shot:

Overview

Game development, in my somewhat biased opinion, is one of the hardest programming disciplines. Granted there are harder, but looking over the majority of industry jobs, there are a huge number of easier jobs. Having met and discussed programming with many 100's of people, I've often found that most games programmers have a far better grasp of their field than others. I'm not entirely sure why this is, but I wouldn't be surprised if it were due to said programmers needing to be on the cutting edge of new technology; conversely, database programming - not much new there ;-)

So, anyway, enough of that... Why would these supposedly hardcore programmers be interested in a book about data structures? Well, put simply, they are one of the foundation building blocks of any program (game or otherwise). Also, everyone has to start somewhere - and not every game programmer is a god-like programmer.

Getting a thorough understanding of how the algorithms and data structures work is the first step in knowing how to choose a suitable data structure. Choosing a suitable data structure and accompanying algorithm(s) can and will make a difference, both in performance and functionality of the final code.

Everything you'd expect...

For anyone who's ever read a book on data structures (a.k.a 'Abstract Data Types', ADT's), there is always a certain number of common chapters. Arrays, linked lists, stacks, queues, trees etc.. - they're in every book, and they're also in this one. We also get an introduction to the Big-Oh notation for algorithm comparison (algorithms in this context is usually limited to insertion, deletion and searching), however it's not a heavily used concept in this book. In my travels, I've found it necessary to understand Big-Oh, but it's not usually been that essential when it comes to applied programming.

This book is dependent, from the outset, on C/C++ programming - granted, this covers the vast majority of games programmers; but it doesn't cover everyone. For those who know a little C/C++, but aren't "natural" C/C++ programmers there is a useful appendix to help you out.

Most of the concepts can be migrated to other languages/platforms, but some of the higher level languages (Java, VB) can make it overly difficult. C/C++ is extremely powerful for it's use of pointers, and C++ is very powerful with it's ability to use classes and templates. Thus, C++ allows for very concise and efficient data structure representation. Yet these two features aren't very common in other popular languages (Java hides pointers as much as possible, and is only just getting 'generics' built in) so if you're not at least capable of reading C++ code, you're going to find this book has limited scope.

... And then some more

After the book is done with the compulsory basics, it moves onto the interesting stuff: the content that you usually wouldn't find in another data-structure related text. We get quite a large section of the book dedicated to covering some of the more-world specialized algorithms - compression, random numbers, path finding...

These extensions are often far more useful in certain situations - data compression, for example, is a very specific topic, yet very useful in a lot of game programming tasks. Random numbers, might sound a little odd - but the number of times that a bit of randomness is thrown into the mix you might appreciate going beyond the rather limited "rand()" functions that C/C++ provides.

Path finding is a bit of an odd direction for this book - as it is truly an applied algorithm that can, for the most part, only be used for a very few specialized things (mostly AI related). The author sees it fit to cover an AI specific topic, yet there is almost no mention at all of graphics related algorithms.

Graphics algorithms go from hard to harder at the best of times, yet some of most classic game examples for tree structures are graphics-oriented (think 'BSP' and 'Quadtree'). However, there isn't really a solid discussion of these topics in this book.

As mentioned, the book is designed around C++ programmers, and there is a good section towards the start covering the template features. Templates are an advanced topic that some people (including myself for a long while) have trouble understanding - seeing a good discussion of these right at the start is definitely beneficial.

All in a consistent style

The style of this book is consistent - which is only a good thing when talking about data structures. Given that many text books on this subject can get very abstract when talking about the properties of data structures, it is refreshing to have a book like this where you can actually appreciate the examples being used. Pretty much every example in the book is done through understandable game-related terms.

This applied aspect is one of the most important things for this book, I've read similar books to this before - and they're often mind-numbingly vague or just plain dull. This book isn't - it has a hands on and usable approach to it.

Diagrams and tips/cautions/warnings are also a well used design feature common to most 'Premier Press Game Development' books. Algorithms and structures are often best explained using diagrams - and there are no shortage of diagrams in this book, and in the case of the 'sorting' chapter there are some animated samples on the CD that you can watch. You'll never forget your sorting algorithm speeds after you've watched samples like these. There are also a huge number of things that can go wrong when it comes to implementing data structures - the inset tips/cautions/warnings throughout the text are very valuable when it comes to highlighting key facts from the main text.

A few weaknesses

This book isn't a complete reference for all game-related data structures and algorithms. But in all fairness, such a book could occupy several times the number of pages available here. However, there are some sections of this book (in 'The Basics' section) - Not a complete reference, could probably skip some of the simpler aspects. However, there might be scope for an 'advanced edition' of this book that covers some of the more complex algorithms/data-structures used by games.

It is also noticeable that there is very little mention of the STL (Standard Template Library) in this book - it is referred to at the end of this book in the 'STLPort' form; but I'd very much liked to have seen it tied into the main text.

Basically, the STL may not be perfect - and sometimes hand rolled code as shown in this book is beneficial both practically and for learning - but the STL is there and ready to use. This basically saves us programmers from re-inventing the wheel each time we want a linked-list structure (for example); and given it's importance, the STL is also well defined and well tested. Thus I'd generally choose to (and I know many programmers would) trust a good STL implementation than their own hand-rolled code. It would have been nice to have a chapter format whereby you get a summary at the end along the lines of "...and this is how its done using the STL", just for comparison and for reference.

In Conclusion

This is a good book that deserves a place on most game programmers shelves - it can work both as a teaching tool and as a reference. For the more seasoned and advanced programmers there may be less usable information, but that doesn't count against the high quality of what is usable.