I finished reading Data Structures for Game Programmers by Ron Penton recently and while I enjoyed aspects of it, I felt that it was targeted more at beginner to intermediate programmers.
Penton deals with many good tips for using template classes and shows some good examples for setting them up. The focus is mainly on arrays, lists, trees and graphs as well as some of the algorithms related to sorting and searching these structures. The most advanced algorithms and the most useful for game programmers is the A* pathfinding algorithm and heuristics associated with setting up AI to use the pathfinding.
The book itself is quite long and fairly thorough (the focus on arrays to graphs are nearly six hundred pages) however, I felt it would be useful if there was more of a comparison between the Standard Template Library structures and the custom built ones, and why certain choices were made for the custom built data structures (if to improve performance, usability or whatever). There are lots of examples that are used throughout the book using Simple Directmedia Layer (SDL) and while I was interested in how quickly the examples could be put together, it sometimes felt that a fair bit of the code was related to SDL.
The data structure book that I was taught in the second-year university data structure course was Algorithm Design: Foundations, Analysis, and Internet Examples by Michael T. Goordrich and Roberto Tamassia, and while I feel it is more advanced, it may be a more complete look at data structures and algorithms. The Algorithm Design book actually deals with AVL trees and Red-Black trees that are mentioned in Penton’s book but not discussed. While the Algorithm Design does not have extensive pathfinding examples and A* implementations (instead focusing on Dijkstra’s shortest path algorithm) the book may have given a broader view to the data structures themselves, as well as computer science interests like Big O notation and NP-Completeness related to the different structures and algorithms.
For the beginner and intermediate (game) programmer, Penton’s book does have some good insights, especially those related to pathfinding which are not often taught as often in data structure books. However, for the more advanced or professional game dev perhaps a more advanced book would be better suited, or perhaps if pathfinding is the only interest an AI book would be more appropriate.
Until next time,