Book Review: Data Structures for Game Programmers

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,
Michael Hubbard
http://michaelhubbard.ca

Terragen 2 (free version) Test

Finally got a chance to post some of the Terragen 2 tests I was looking into. I was very impressed with some of the quality that could be achieved with this program with minimal effort and intuitive interface. The image is from following the "First Scene" example in the Online Documentation. I thought the galleries were indeed better then my final result, but for only reading a few of the values and playing around a bit with the settings, I felt that the process was of a good quality and could likely be improved with practice.

Setting up the scene (following along the documentation) could likely be setup in only a couple of minutes, if I was to do the scene again I would estimate around five minutes of initial setup for getting the scene and then however long you needed to tweak values and colors.

It is not all silver lining unfortunately, I feel like the close up "grass" (just a green color) and some of the water would likely have to be touched up in photoshop as well as maybe adjusting some of the contrast and color. I think with some additional practice this could be improved in terragen, but I would need to do some trial and error to set appropriate color values for different lighting and atmosphere conditions.

On a whole, I think the result is very strong, the rendering time was a bit long (I had a number of other processes going simultaneously) but the total time for the 800x600 image was 1:16:34s with 2363295 micro-triangles. I am sure with a faster machine this would be greatly improved, although terragen documentation still suggests the rendering time could take 30+ minutes on even newer machines.

I will definitely be playing more with this tool in the future and will see what kind of results are generated from the mesh data that is exported into other 3d renderers.

Definitely worth a try if you enjoy terrains, and it is free for non-commercial use.

Until then, I remain.
Michael Hubbard
http://michaelhubbard.ca