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.