Data Structures for Game Programmers (Premier Press Game Development) [Paperback]

Ron Penton (Author)

Book Description

ISBN-10: 1931841942 | ISBN-13: 978-1931841948 | Publication Date: November 25, 2002 | Edition: 1

"Data Structures for Game Programmers" replaces endless pages of boring text with exciting gaming technology and eye-catching graphics. The complex subject of data structures is made easy to understand and fun to learn. Start with an explanation of how the most popular data structures and algorithms work. Then you're on your way as you create your own! From simple arrays and bit vectors to intense binary tree graphs and hash tables, this book covers it all. It even tackles the algorithms used for sorting, searching, compression, and recursion. Plus, you will actually see each concept put into practice through interactive graphical demonstrations included on the CD!

Editorial Reviews

About the Author

Ron Penton is an independent programmer with a primary interest in computer games. He began using GW-BASIC in 1989, moved on to Visual Basic 4 in 1995, QBasic in 1996, and learned C++ in 1997. Ron began working on his degree in 1998 at the Rochester Institute of Technology, and is working on completing his Bachelors in Computer Science at the University of Buffalo. Ron contributed a chapter in the book titled “Game Programming All in One” published by Premier Press.

Product Details

• Paperback: 884 pages
• Publisher: Muska & Lipman/Premier-Trade; 1 edition (November 25, 2002)
• Language: English
• ISBN-10: 1931841942
• ISBN-13: 978-1931841948
• Product Dimensions: 9.3 x 7.4 x 2 inches
• Shipping Weight: 3.4 pounds
• Average Customer Review: 4.3 out of 5 stars  See all reviews (15 customer reviews)
• Amazon Best Sellers Rank: #866,392 in Books (See Top 100 in Books)

Customer Reviews

Most Helpful Customer Reviews

63 of 79 people found the following review helpful:

2.0 out of 5 stars Tries, but doesn't quite get there, September 3, 2003

By 

John Hattan (Southlake, TX United States) - See all my reviews
(REAL NAME)   

This review is from: Data Structures for Game Programmers (Premier Press Game Development) (Paperback)

Publishing a book on data structures and algorithms isn't an easy task, because there's no computer science genre that's got as much of a pedigree. With titles ranging from a dozen good college textbooks to Sedgewick's five-volume _Algorithms_ series to Knuth's dense and eternally-unfinished _Art of Computer Programming_ series, any new book on data structures and algorithms is facing some serious competition. When I learned that Ron Penton, a newcomer to the programming book scene, was entering the foray with _Data Structures for Game Programmers_, I was skeptical. Could a book explaining the deep subject of data structures and algorithms written by someone with comparatively little experience in programming hold its own against books written by lifelong academics?

Unfortunately, that answer is "not really". While _Data Structures for Game Programmers_ does a reasonable job of explaining the data structures and algorithms that are necessary for games, the book suffers from serious organization problems and a lack of depth.

The book does cover the expected basics and follows the standard format, with a chapter on arrays, a chapter on linked lists, a chapter on binary trees, a chapter on stacks & queues, etc. These are covered reasonably well, showing how the structures are represented, the advantages and disadvantages of each, and how to code them. The book does try to distinguish itself from a standard college data structures textbook in two ways. First, each data structure and algorithm includes an interactive example program on the included CD. These examples are very well done and are an excellent way to see constructs "in action". Second, the example programs are all game-oriented, mostly involving a Zelda/Ultima style adventure game.

Around page 600, the book takes a turn into algorithm territory, and it does take a more game-oriented focus following the obligatory chapter on sorting. Chapters on data compression, random numbers, and path-finding are natural fits for all kinds of games.

Following the algorithms are a few short appendices covering the basics of C++ (or as much as can be covered in 30 pages, which isn't much), a few pages on how PC memory is organized, a quick overview of SDL (the graphics library used to make the example programs), and twenty pages on STL.

Unfortunately, the short shrift given to STL is one of the problems with the book. While the value of STL was once debated, it is now blessed by ISO as the C++ standard library and is now as much a part of C++ as the if( ) statement. About half of the data structures covered in the book are already implemented in STL, and the rest can be made out of combinations of STL containers and algorithms. The book, however, ignores STL in favor of building all data structures from the ground up. While I understand the need to show how data structures look and work internally, the chapters should at least mention that the structures are already part of C++ and don't need to be implemented directly.

Early on I mentioned the organizational problems with the book, and a couple of them are significant. The first is how, despite the fact that the book is aimed at C++ beginners, the book opens with a fairly advanced chapter on templates. The templates chapter is followed by a far-simpler chapter on arrays. Despite having not covered arrays yet, the chapter on templates implements an array container assuming that arrays are already understood. Even worse, chapter 9 is a tutorial on how to write classes in C++, even though C++ classes have been in heavy use since chapter two! I honestly don't know if this is a case of chicken-egg syndrome run amok or if it's a case of an author and editor not spending enough time organizing the layout of the book, but it does make for a confusing read.

My final complaint about the book is about the relative lack of depth given to the subjects. While simple structures like arrays are covered comprehensively, there is too much "this is too advanced a topic for this book" later on. For example, the chapter on binary trees shows how to build and climb a binary tree. The chapter does correctly state that binary trees suffer from a significant flaw, which is that the search efficiency is very dependent on the order of the data inserted. The chapter also states that there are ways around this flaw, namely AVL and red-black trees which re-balance themselves. That's where the book stops, though. Even though the book could cover balanced trees with a few more pages, the book just recommends you look elsewhere and leaves (no pun intended) binary trees with their flaws. This is later repeated in the chapter on minimax trees, mentioning that tree-searches can have their performance improved significantly, but not detailing those ways because, according to the author, the chapter was getting too big and most folks aren't interested in minimax trees anyway.

In conclusion, _Data Structures for Game Programmers_ tries to achieve a lofty goal, staking a space among books written by the top people in the field. Unfortunately, though, it only partially reached that goal, covering some topics well and gaining big points for the quality of the programs on the included CD, but falling well short of the mark in organization and depth of advanced coverage.

22 of 27 people found the following review helpful:

5.0 out of 5 stars Wow!, January 11, 2003

By 

Gregory Baird (San Jose, CA) - See all my reviews

This review is from: Data Structures for Game Programmers (Premier Press Game Development) (Paperback)

Let me be frank; I HATE DATA STRUCTURES. They are BORING. I'm a sophomore in a Computer Science program, and I've just finished taking a data structures course, and I barely passed it. All college Data Structure books are written for people who like to read extremely boring mathematical proofs, and I can't read that stuff. So, a friend of mine told me to get this book, so I got it on sale, and boy, I am glad.

I've bought Prima/Premier books before, and they are usually good, but also disappointing because the first 40% of the book is always an introduction on things like "a complete tutorial on direct3d" or something. Well this book is different: it gets RIGHT TO THE POINT, IMMEDIATELY. The first two chapters are ALL of the intro material (algorithm analysis and templates), then Chapter 3 jumps right into the data structures!

Okay, so arrays may seem to be a bit simplistic, so I skipped that chapter at first. The later chapters in the book are more interesting, but then I noticed in a later chapter, a reference to a complex issue in the array chapter (processor caching). So I went back and and re-read that chapter, and WHOA! He literally shows you EVERYTHING there is to know about arrays, even complex stuff like caching that a normal data structures book would never even touch!

This book is amazing; and covers TONS of topics. There's no TOC listed at this site yet, so here's a list of what it's got: Arrays, 2D Arrays, 3D Arrays, Bitvectors, Linked Lists, Hash Tables, Stacks, Queues, Recursion, Trees, Binary Trees, Heaps, Minimax trees, Graphs, AI Machines, Data Sorts, Compression Algorithms, Pathfinding (BEST CHAPTER!), and he even goes over the creation of a simple 2D game and complete map editor for it.

Every chapter is packed full of diagrams and figures, notes, and demo's. For every major concept, there is a "Graphical Demonstration" on the CD, that shows you how it works! And, for every chapter, there's also one or more "Game Demonstration"s. These show you how to integrate the data structurs into a game! The CD is so awesome that it could practically sell on its own!

The bottom line is: this book takes the boring and difficult subject of data structures, and turns them into something anyone can understand, in a fun and exciting way. 5 stars!

12 of 14 people found the following review helpful:

5.0 out of 5 stars Don't miss this one!, March 10, 2003

By 

jmcguire - See all my reviews

This review is from: Data Structures for Game Programmers (Premier Press Game Development) (Paperback)

The title is scary. Really scary. Data structures ... *shudder* ... it brings up nightmare images of professors who droned for hours while the class snored ... it sounds like one of those books that is so dry you have to soak it in water before you read it. It isn't.

This book is excellent. My husband thinks I'm nuts because it kept me up late reading in bed, but it's that good. The author explains complex concepts very clearly, with some humor to keep it entertaining. He's a game programmer writing for other game programmers, which is a refreshing change from the myriad books that seem to be by academics writing for review committees.

It explains all of the many ways data can be handled, from simple arrays to recursive structures, hashing, and other complex forms. Ok, any good advanced programming book would tell you this -- but they rarely if ever bring up considerations like how memory caching should influence your choice of data structures, or the impact of those choices on game design.

In addition to data structures, the author covers what you can do with them, and why. Topics such as pathfinding are covered and demonstrated. SDL, a cross-platform graphics library, is used for the demos and the coverage of that is almost worth the price of admission. (though I recommend Focus on SDL in addition)

If you're writing a game you need to know this stuff. Read this book.