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 Big-O Notation O(c) O(Log2n) O(n) O(n log2n) O(n2) O(n3) O(2n) Comparing the Various Complexities Graphical Demonstration: Algorithm Complexity Conclusion Chapter 2: Templates What Are Templates? Template Functions Doing It the Old Way Doing It with Templates Template Classes Multiple Parameterized Types Using Values as Template Parameters Using Values of a Specific Datatype Using Values of Other Parameterized Types 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 Increasing or Decreasing Array Size Inserting or Removing an Item Native C Arrays and Pointers Static Arrays Declaring a Static Array Accessing an Array Passing an Array into a Function Inside an Array Initializing a Static Array Example 3-1 Dynamic Arrays Allocating a Dynamic Array Malloc Calloc New Deleting a Dynamic Array Free Delete Resizing a Dynamic Array Realloc Resizing Arrays Created with new Example 3-2 An Array Class and Useful Algorithms The Data The Constructor The Destructor The Resize Algorithm The Access Operator The Conversion Operator Inserting an Item Between Two Existing Items Removing an Item from the Array A Faster Removal Method Retrieving the Size of an Array Example 3-3 Storing/Loading Arrays on Disk Writing an Array to Disk Reading an Array from Disk Considerations for Writing and Reading Files Application: Using Arrays to Store Game Data The Monster Class Declaring a Monster Array Adding a Monster to the Game Making a Better Insertion Algorithm Removing a Monster from the Game Checking for Monster Removal Playing the Game Analysis of Arrays in Games Cache Issues Resizing Arrays Inserting/Removing Cells Conclusion Chapter 4: Bitvectors What Is a Bitvector? Graphical Demonstration: Bitvectors The Main Screen Using the Buttons Creating a Bitvector Class The Data The Constructor The Destructor The Resize Algorithm The Access Operator The Set Function The ClearAll Function The SetAll Function The WriteFile function The ReadFile Function Example 4-1 Application: The Quicksave Creating a Player Class Storing the Players in the Game Initializing the Data Structures Modifying Player Attributes Saving the Player Array to Disk Playing the Game Bitfields Declaring a Bitfield Using a Bitfield 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 Declaring a Multi-Dimensional Array Initializing a 2D Array Initializing Arrays with More than Two Dimensions Initializing Non-Symmetrical Multi-Dimensional Arrays Initializing Variable Length Multi-Dimensional Arrays Accessing a Multi-Dimensional Array Inside a Multi-Dimensional Array Inside 2D Arrays Expanding to Higher Dimensions A Note on Conventions Passing Multi-Dimensional Arrays to Functions Example 5-1 Dynamic Multi-Dimensional Arrays The Array2D Class The Template Parameters The Data The Constructor The Destructor The Get Function The Resize Function Getting the Size of the Array Example 5-2 The Array3D Class Code Listing Example 5-3 Application: Using 2D Arrays as Tilemaps Storing the Tilemap Generating the Tilemap Drawing the Tilemap Playing the Game Application: Layered Tilemaps Redefining the Tilemap Reinitializing the Tilemap Modifying the Rendering Algorithm Playing the Game Comparing Performance Comparing Size Analysis of Multi-Dimensional Arrays in Games Conclusion Chapter 6: Linked Lists What Is a Linked List? Singly Linked Lists Graphical Demonstration: Singly Linked Lists Structure The SListNode Class The InsertAfter function Iterators Encapsulating a Linked List The Constructor The Destructor The Append Function The Prepend Function The RemoveHead Function The RemoveTail Function The SListIterator Class The Constructor The Start Function The Forth Function The Item Function The Valid Function The GetIterator Function Using Iterators The Insert Function The Remove Function Example 6-4 Final Thoughts on Singly Linked Lists Doubly Linked Lists Graphical Demonstration: Doubly Linked Lists Creating a Doubly Linked List The Node Structure Doubly Linked List Algorithms Inserting a Node Removing a Node Reading and Writing Lists to Disk Writing a Linked List Reading a Linked List Application: Game Inventories The Player Class The Item Class Adding an Item to the Inventory Removing an Item from the Inventory Playing the Demo Application: Layered Tilemaps Revisited Declaring the Tilemap Creating the Tilemap Drawing the Tilemap Analysis and Comparison of Linked Lists Algorithm Comparisons Size Comparisons Real-World Issues Conclusion Chapter 7: Stacks and Queues Stacks What Is a Stack? Graphical Demonstration: Stacks The Stack Functions Implementing a Stack Linked Stacks The Push Function The Pop Function The Top Function The Count Function Using the DLinkedList Functions Why Use a Linked Stack? Arrayed Stacks The Constructor The Push Function The Pop Function The Top Function The Count Function Why Use an Arrayed Stack? Application: Game Menus The Stack and the Array Creating a Menu Class Adding a Menu to the Stack Removing a Menu from the Stack Playing the Demo Queues Graphical Demonstration: Queues The Queue Functions Implementing a Queue Linked Queues The Dequeue Function The Front Function Arrayed Queues The Structure The Constructor The Enqueue Function The Dequeue Function The Front Function The Access Operator Resizing Application: Command Queues The Player and the Coordinates Adding a Command to the Queue Removing a Command from the Queue Playing the Game Conclusion Chapter 8: Hash Tables What Is Sparse Data? The Basic Hash Table Collisions Hashing Functions Digit Addition Double Hashing Other Hash Functions Hashing Strings Enhancing the Hash Table Structure Linear Overflow Quadratic Overflow Linked Overflow Inserting into a Linked Overflow Table Searching for Keys Graphical Demonstration: Hash Tables Implementing a Hash Table The HashEntry Class The HashTable Class The Data The Constructor The Insert Function The Find Function The Remove Function Example 8-1: Using the Hash Table The Hash Function Creating the Hash Table Inserting Keys Finding Keys Removing Keys Application: Using Hash Tables to Store Resources The String Class Using the Table How the Demo Loads Resources Playing the Demo Conclusion Chapter 9: Tying It Together: The Basics Why Classes Are Good Storing Data in a Class Hiding Data Implementing a Class with No Data Hiding Implementing a Class with Data Hiding Inheritance The Object Class Virtual Functions Pure Virtual Functions Why Do You Need to Use Pointers? How Virtual Functions Work The Item Class Inheritance Types The Person Class Using the Classes in a Game Using the Child-Specific Features Enabling RTTI in Visual C++ Using RTTI Another Way, Without RTTI Tips Making a Game Adventure: Version One Designing the Base The Map The Cells The Items The People Designing the Interfaces The Map Interface The Object Interface The Item Interface The Person Interface Creating an Implementation for the Map The Direction Table The TileCell Class The TileMap Class Interface The TileMap Class Implementation The Constructor The Destructor The GetCell Function The LoadFromFile Function The Draw Function The CanMove Function The Move Function The GetCellNumber Function The GetClosestDirection Function The Item Class Implementation The Person Class Implementation The Constructor The Destructor The Copy Constructor and Assignment Operator The SetDirection Function The SetHealth Function The SetArmor Function The AddItem Function The NextWeapon and PreviousWeapon Functions The GetCurrentWeapon Function The GetAttackTime Function The Attack Function The GetGraphic Function The GetAttacked Function The IsDead Function The PickUp Function Creating People and Items Game Logic Data and Initialization The LoadMap Function The SetNewMap Function Miscellaneous Functions The Artificial Intelligence The Attack Function The Pickup Function The CheckForDeadPeople Function The Game Loop Playing the Game Game 2-[md]The Map Editor The Map The Drawing Information The Tile Drawing Saving the Map Loading the Map Using the Editor Conclusion Part III: Recursion and Trees Chapter 10: Recursion What Is Recursion? A Simple Example: Powers The Towers of Hanoi The Rules Solving the Puzzle Solving the Puzzle with a Computer Terminating Conditions Example 10-1: Coding the Algorithm for Real Graphical Demonstration: Towers of Hanoi Conclusion Chapter 11: Trees What Is a Tree? The Recursive Nature of Trees Common Structure of Trees Graphical Demonstration: Trees Tutorial Step 1: Build a Basic Tree Step 2: Traverse the Tree Step 3: Build a More Complex Tree Step 4: Play Around Building the Tree Class The Structure The Constructor The Destructor The Destroy Function The Count Function The Tree Iterator The Structure The Basic Iterator Functions The Constructor The Assignment Operator The ResetIterator Function The Vertical Iterator Functions The Root Function The Up Function The Down Function The Horizontal Iterator Functions The Other Functions Building a Tree Top Down Bottom Up Traversing a Tree The Preorder Traversal Coding the Preorder Function Using the Function Pointer The Postorder Traversal Graphical Demonstration: Tree Traversals Game Demo 11-1: Plotlines Using Trees to Store Plotlines Declaring the Tree Initializing the Tree Changing Levels Playing the Game Conclusion Chapter 12: Binary Trees What Is a Binary Tree? Fullness Denseness Balance Structure of Binary Trees Linked Binary Trees Arrayed Binary Trees Size of Arrayed Binary Trees Traversing Arrayed Binary Trees Size Efficiency Graphical Demonstration: Binary Trees Coding a Binary Tree The Structure The Constructor The Destructor and the Destroy Function The Count Function Using the BinaryTree Class Traversing the Binary Tree The Preorder Traversal The Postorder Traversal The Inorder Traversal Graphical Demonstration: Binary Tree Traversals Application: Parsing Arithmetic Expressions Parsing an Arithmetic Expression Recursive Descent Parsing Tokens Variables Scanning Parsing Using the Algorithm Source Listing Executing the Tree Playing the Demo Conclusion Chapter 13: Binary Search Trees What Is a BST? Inserting Data into a BST Finding Data in a BST Removing Data from a BST The BST Rules Sub-Optimal Trees Graphical Demonstration: BSTs Coding a BST The Structure Comparison Functions The Constructor The Destructor The Insert Function The Find Function Example 13-1: Using the BST Class Application: Storing Resources, Revisited The Resource Class The Comparison Function Inserting Resources Finding Resources Playing the Demo Conclusion Chapter 14: Priority Queues and Heaps What Is a Priority Queue? What Is a Heap? Why Can a Heap Be a Priority Queue? Needed Heap Attributes Inserting an Item into a Heap Removing an Item from a Heap Heap Efficiency Graphical Demonstration: Heaps Coding a Heap Class The Structure The Constructor The Enqueue Function The WalkUp Function The Dequeue Function The WalkDown Function Application: Building Queues The Units Creating a Factory The Heap Enqueuing a Unit Starting Construction Completing Construction Playing the Demo 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 The Gamestate The Constructor The Equivalence Operator The Empty Function The Global Variables Generating the Game Tree Generating the MiniMax Tree The Heuristic Function The MiniMax Calculation Function Simulating Play The Player's Turn The Computer's Turn Playing the Game Setting up the Game Playing More Complex Games Never-Ending Games Huge Games Limited Depth Games Conclusion Chapter 16: Tying It Together: Trees Expanding the Game Altering the Map Format Game Demo 16-1: Altering the Game The New Item Class Determining Whether the Item Is Gettable Determining Whether the Item Is an Exit Determining the Exit Number The Constructor The Modified Map Class Modifying the TileMap Class Modifying the Player Class Modifying the Game Logic Loading the Exit Templates The PickUp Function The SetNewMap Function Playing the Game The Map Editor Saving the Exits to Disk Reading the Exits from Disk Playing the Demo Further Enhancements Conclusion Part IV: Graphs Chapter 17: Graphs What Is a Graph? Linked Lists and Trees Graphs Parts of a Graph Types of Graphs Bi-Directional Graphs Uni-Directional Graphs Weighted Graphs Tilemaps Implementing a Graph Adjacency Tables Direction Tables General-Purpose Linked Graphs Bi-Directional Graphs Uni-Directional Graphs Graphical Demonstration: Graphs Graph Traversals The Depth-First Search The Breadth-First Search A Final Word on Graph Traversals Graphical Demonstration: Graph Traversals The Graph Class The GraphArc Class The GraphNode Classes The Structure The Functions Adding an Arc Finding an Arc Removing an Arc The Graph Class The Structure The Constructor The Destructor Adding a Node to the Graph Removing a Node from the Graph Adding an Arc to the Graph Removing an Arc from the Graph Finding an Arc in the Graph Clearing All the Marks The Depth-First Search The Breadth-First Search Application: Making a Direction-Table Dungeon The Map Creating the Map Drawing the Map The Helper Structures The DrawMap Function Moving Around the Map Playing the Demo Application: Portal Engines Sectors Determining Sector Visibility The Depth-Limited Depth-First Search Using the DLDFS in a Portal Engine Coding the Demo The Sector Class The Map Initializing the Map Drawing the Map Calling the DrawMap Function Playing the Demo 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 Multiplying States Conditional Events Representing Conditional Event Machines Multi-Dimensional Arrays Other Methods Linked Ranges Trees Graphical Demonstration: Conditional Events Game Demo 18-01: Intruder The Code The Constants The Enumerations The AI Class The Globals The Machines The AIs The Player Other Globals Initializing the Machines The First Step Initializing the Arcs Handling Events The Auxiliary Functions The ProcessAI Function Playing the Demo Conclusion Chapter 19: Tying It Together: Graphs The New Map Format The New Room Entry Structure The File Format Game Demonstration 19-1: Adding the New Map Format The DirectionMap The DirectionCell Class The MapEntry Class The DirectionMap Class The Data The DirectionMap Functions The Constructor The Destructor The LoadFromFile Function The Map Functions The Draw Function The CanMove Function The Move Function The GetItem and SetItem Functions The GetPerson and SetPerson Functions The GetCellNumber Function The GetNumberOfCells Function The GetClosestDirection Function Changes to the Game Logic The New Image Set The New LoadMap Function Playing the Game Converting Old Maps The Directionmap Map Editor The Initial Map Setting and Clearing Tiles Loading a Map Saving a Map Using the Editor Upgrading the Tilemap Editor The Save Function The Load Function Conclusion Part V: Algorithms Chapter 20: Sorting Data The Simplest Sort: Bubble Sort Worst-Case Bubble Sort Graphical Demonstration: Bubble Sort Coding the Bubble Sort Optimizations Psuedo-Code The C++ Code Example 20-1 The Hacked Sort: Heap Sort Graphical Demonstration: Heap Sort Coding the Heap Sort The WalkDown Function The HeapSort Function Example 20-2 The Fastest Sort: Quicksort Picking the Pivot Performing the Quicksort Graphical Demonstration: Quicksort Coding the Quicksort The MedianOfThree Function The QuickSort Function Example 20-3 Graphical Demonstration: Race The Clever Sort: Radix Sort Graphical Demonstration: Radix Sorts Coding the Radix Sort The Bin Size Base 2 Base 4 Base 16 Example 20-4 Other Sorts Application: Depth-Based Games The Player Class The Globals The Player Comparison Function Initializing the Players Sorting the Players Drawing the Players Playing the Game Conclusion Chapter 21: Data Compression Why Compress Data? Data Busses The Internet Run Length Encoding What Kinds of Data Can Be Used for RLE? Graphical Demonstration: RLEs Coding an RLE Compressor and Decompressor The Structure The Constructor The Compression Algorithm The Decompression Algorithm The SaveData Function The LoadData Function Example 21-1 Example 21-2 Huffman Trees Huffman Decoding Creating a Huffman Tree The Frequency Table Generating the Tree Graphical Demonstration: Creating a Huffman Tree Coding a Huffman Tree Class The Huffman Node Class The Frequency Class The Frequency Comparison Function The Huffman Class The Declaration, Typedefs, and Data The Constructor Calculating the Tree Compressing Data Decompressing Data Saving the Tree to Disk Loading the Tree from Disk Saving the Data to Disk Loading the Data from Disk Converting the Binary Tree to an Array The Convert Function Creating the Lookup Table Example 21-3 Test Files Example 21-4 Data Encryption Further Topics in Compression Conclusion Chapter 22: Random Numbers Generating Random Integers Generating Random Numbers in a Program Using rand and srand Seeding the Generator Using a Non-Constant Seed Value Generating a Random Number Within a Range Modulo Range Determination Why This Is a Bad Method Division Range Determination Generating Random Percents Generating Random Floats Generating Non-Linear Random Numbers Probability Distribution Graphs Adding Two Random Numbers Adding Three Random Numbers Graphical Demonstration: Random Distribution Graphs Conclusion Chapter 23: Pathfinding Basic Pathfinding Random Bouncing Object Tracing Robust Pathfinding The Breadth-First Search Modifying the BFS Pathfinder Modifying the Visitation Order A True Breadth-First Search Graphical Demonstration: Distance First Pathfinder Coding the Distance-First Pathfinder The Base Code The Cell Class The Coordinate Class The Comparison Function Clearing the Cells The Distance Function The Constants The Distance-First Pathfinder Making a Smarter Pathfinder Graphical Demonstration: Simple Heuristic Pathfinder Problems with This Pathfinder Coding the Simple Heuristic Pathfinder The Heuristic Function The Simple Heuristic Pathfinder Making a Better Heuristic Graphical Demonstration: Complex Heuristic Problems with This Heuristic Coding the Complex Heuristic The New Heuristic Function The Complex Heuristic Pathfinder The A* Pathfinder Graphical Demonstration: A* Coding the A* Pathfinder Graphical Demonstration: Path Comparisons Weighted Maps Application: Stealth The Variables Loading and Saving the Map Finding the Path Walking the Path Playing the Game Bonus Feature: Editing the Map Thinking Beyond Tile-Based Pathfinding. Line-Based Pathfinding Quadtrees Waypoints Conclusion Chapter 24: Tying It Together: Algorithms Making the Enemies Smarter with Pathfinding Adding Pathfinding to the TileMap Class The Coordinate Class and Comparison Function The New Data The ClearCells Function The Heuristic Function The AStar Function Modifying the GetClosestDirection Function Adding Pathfinding to the DirectionMap Class The CellCoordinate Class The New Data The ClearCells Function The Heuristic Function The AStar Function Modifying the GetClosestDirection Function Visualizing the GetClosestCell Algorithm Is That All? The Person's Following Status The New ProcessAI Function Efficiency Playing the Game Conclusion Conclusion Extra Topics Further Reading and References Data Structure Books Sams Teach Yourself Data Structures and Algorithms in 24 Hours Introduction to Data Structures and Algorithm Analysis with C++ Introduction to Algorithms, 2nd Edition The Art of Computer Programming Effective STL The C++ Standard Library: A Tutorial and Reference C++ Books Object Oriented Programming in C++ Sams Teach Yourself C++ in 21 Days C++ How to Program Game Programming Books Game Programming All in One Focus On SDL Focus On 3D Terrain Programming Focus On 3D Models Game Scripting Mastery AI Techniques for Game Programming Web Sites Conclusion Part VI: Appendixes Appendix A: A C++ Primer Basic Bit Math Binary Numbers Converting from Binary to Decimal Converting from Decimal to Binary Computer Storage Bitwise Math Bitwise Math in C++ Bitshifting Standard C/C++ Functions Used in This Book Basic Input/Output Screen Output Keyboard Input File I/O The FILE Structure Opening a File Writing to Disk Reading from Disk Closing the File Math Functions The Time Function The Random Functions The srand Function The rand Function Exceptions Assertions Return Codes Exceptions Why C++? Class Topics Constructors Destructors Operator Overloads Conversion Operators The This Pointer Inline Functions Function Pointers Conclusion Appendix B: The Memory Layout of a Computer Program The Memory Sections The Code Memory The Global Memory Global Variables Static Variables The Stack Local Variables Parameters Return Values The Free Store Conclusion Appendix C: Introduction to SDL The Licensing Setting Up SDL The Files Setting Up the Files Setting Up Visual C++ Setting Up Your Project Setting Up SDL_TTF Distributing Your Programs Using SDL SDL_Video The Structures Initializing the Video Loading and Drawing Bitmaps Freeing Surfaces SDL Event Handling SDL_Timer SDL_TTF The SDLHelpers Library The SDLFrame The SDLGUI Library The SDLGUI Class The GUI Objects The Drawing Function Wrappers The Utility Functions The Event Functions The Display Functions The SDLGUIItem Class The Visibility Functions The Position Functions The Input Functions Focus Functions The Drawing Function The SDLGUI Items The SDLGUIFrame Conclusion Appendix D: Introduction to the Standard Template Library STLPort STL Versus This Book Namespaces The Organization of STL Containers Sequence Containers The Vector The Deque The List Associative Containers Container Adaptors The Miscellaneous Containers Conclusion