Structures For Game Programmers
Publisher: Premier Press
- RRP US$34.99
Reviewed: 9th February 2004
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 ;-)
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.
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.
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
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.
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
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...
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.
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
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.
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.
in a consistent style
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.
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.
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.
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.
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.
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
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.
Good all round coverage of an important
foundation block in programming
Very little reference to the STL, a
veritable gold mine for C++ programmers
Goes beyond the basics, and explains some
more game-specific structures/algorithms
Doesn't focus on some of the more specific
Examples used are consistent and will be
appreciated by any games developer.
Not quite a complete reference, probably
stops short of being useful for advanced
The use of diagrams is particularly useful
Explains the advanced features of C++ before
Inclusion of inset tips/warnings
throughout the text are very useful.