| Site Index:
Information Buy It! News Table Of Contents Erratta | Table Of Contents
Complete Text-only Table Of Contents Data Structures for Game Programmers Ron Penton Acknowledgments About the Author Letter from the Series Editor Introduction Who Is This Book For? Topics Covered in This Book Concepts The Basics Recursion and Trees Graphs Algorithms Appendixes What's on the CD? The Simple Directmedia Layer Coding Conventions Used in This Book Artwork Are You Ready? Part I: Concepts Chapter 1: Basic Algorithm Analysis A Quick Lesson on Algorithm Analysis Graphical Demonstration: Algorithm Complexity Conclusion Chapter 2: Templates What Are Templates? Template Functions Template Classes Multiple Parameterized Types Using Values as Template Parameters Problems with Templates Visual C++ and Templates Under the Hood Conclusion Part II: The Basics Chapter 3: Arrays What Is an Array? Graphical Demonstration: Arrays Native C Arrays and Pointers An Array Class and Useful Algorithms Storing/Loading Arrays on Disk Application: Using Arrays to Store Game Data Analysis of Arrays in Games Conclusion Chapter 4: Bitvectors What Is a Bitvector? Graphical Demonstration: Bitvectors Creating a Bitvector Class Application: The Quicksave Bitfields Analysis of Bitvectors and Bitfields in Games Conclusion Chapter 5: Multi-Dimensional Arrays What Is a Multi-Dimensional Array? Graphical Demonstration Native Multi-Dimensional Arrays Dynamic Multi-Dimensional Arrays Application: Using 2D Arrays as Tilemaps Application: Layered Tilemaps Analysis of Multi-Dimensional Arrays in Games Conclusion Chapter 6: Linked Lists What Is a Linked List? Singly Linked Lists Doubly Linked Lists Reading and Writing Lists to Disk Application: Game Inventories Application: Layered Tilemaps Revisited Analysis and Comparison of Linked Lists Conclusion Chapter 7: Stacks and Queues Stacks Queues Conclusion Chapter 8: Hash Tables What Is Sparse Data? The Basic Hash Table Enhancing the Hash Table Structure Graphical Demonstration: Hash Tables Implementing a Hash Table Application: Using Hash Tables to Store Resources Conclusion Chapter 9: Tying It Together: The Basics Why Classes Are Good Storing Data in a Class Making a Game Conclusion Part III: Recursion and Trees Chapter 10: Recursion What Is Recursion? The Towers of Hanoi Graphical Demonstration: Towers of Hanoi Conclusion Chapter 11: Trees What Is a Tree? Graphical Demonstration: Trees Building the Tree Class The Tree Iterator Building a Tree Traversing a Tree Game Demo 11-1: Plotlines Conclusion Chapter 12: Binary Trees What Is a Binary Tree? Structure of Binary Trees Graphical Demonstration: Binary Trees Coding a Binary Tree Traversing the Binary Tree Application: Parsing Conclusion Chapter 13: Binary Search Trees What Is a BST? Graphical Demonstration: BSTs Coding a BST Application: Storing Resources, Revisited Conclusion Chapter 14: Priority Queues and Heaps What Is a Priority Queue? What Is a Heap? Graphical Demonstration: Heaps Coding a Heap Class Application: Building Queues Conclusion Chapter 15: Game Trees and Minimax Trees What Is a Game Tree? What Is a Minimax Tree? Graphical Demonstration: Minimax Trees Game States More Complex Games Application: Rock Piles More Complex Games Conclusion Chapter 16: Tying It Together: Trees Expanding the Game Further Enhancements Conclusion Part IV: Graphs Chapter 17: Graphs What Is a Graph? Types of Graphs Implementing a Graph Graphical Demonstration: Graphs Graph Traversals The Graph Class Application: Making a Direction-Table Dungeon Application: Portal Engines Conclusion Chapter 18: Using Graphs for AI: Finite State Machines What Is a Finite State Machine? Complex Finite State Machines Implementing a Finite State Machine Graphical Demonstration: Finite State Machines Even More Complex Finite State Machines Graphical Demonstration: Conditional Events Game Demo 18-01: Intruder Conclusion Chapter 19: Tying It Together: Graphs The New Map Format Game Demonstration 19-1: Adding the New Map Format Converting Old Maps The Directionmap Map Editor Upgrading the Tilemap Editor Conclusion Part V: Algorithms Chapter 20: Sorting Data The Simplest Sort: Bubble Sort The Hacked Sort: Heap Sort The Fastest Sort: Quicksort Graphical Demonstration: Race The Clever Sort: Radix Sort Other Sorts Application: Depth-Based Games Conclusion Chapter 21: Data Compression Why Compress Data? Run Length Encoding Huffman Trees Data Encryption Further Topics in Compression Conclusion Chapter 22: Random Numbers Generating Random Integers Generating Random Percents Generating Random Floats Generating Non-Linear Random Numbers Conclusion Chapter 23: Pathfinding Basic Pathfinding Robust Pathfinding Weighted Maps Thinking Beyond Tile-Based Pathfinding. Conclusion Chapter 24: Tying It Together: Algorithms Making the Enemies Smarter with Pathfinding Conclusion Conclusion Extra Topics Further Reading and References Conclusion Part VI: Appendixes Appendix A: A C++ Primer Basic Bit Math Standard C/C++ Functions Used in This Book Exceptions Why C++? Class Topics Conclusion Appendix B: The Memory Layout of a Computer Program The Memory Sections The Code Memory The Global Memory The Stack The Free Store Conclusion Appendix C: Introduction to SDL The Licensing Setting Up SDL Setting Up SDL_TTF Distributing Your Programs Using SDL The SDLHelpers Library The SDLFrame The SDLGUI Library Conclusion Appendix D: Introduction to the Standard Template Library STLPort STL Versus This Book Namespaces The Organization of STL Containers Conclusion |