WIXLIB

IntroductionxiiiOpenGL is not specific to any one operating system, allowing this book to beused by Windows , Macintosh , Linux , and any other operating system andhardware that supports it.This book will be using the OpenGL utility toolkit and will focus on onlygraphics topics that are needed to illustrate the points in question, allowing youto focus on the information at hand.Performing general rendering on OpenGL is easy and does not distract fromthe main concepts and topics.T HE S OFTWARE N EEDEDFOR THISB OOKFor this book you will need a C compiler to compile any source code into anexecutable and, for some of the later chapters, an OpenGL-compatible graphicscard. All chapter code for this book was compiled and tested on Windows XP, MacOS X, and the latest Ubuntu distribution of Linux. Any operating system andhardware that supports OpenGL 1.4 should be compatible with everything thatwill be done in this book. To run the executable files that come packaged on theCD-ROM, you’ll need Windows 98 or higher, Mac OS X or higher, or Linux. Userswith other operating systems can compile the chapter code using their compiler ofchoice for their platform.H OWTHISB OOK I S O RGANIZEDThis book is made up of 15 chapters. Each chapter goes over the manual creationof a set of data structures and, where applicable, the C Standard Template Library (STL) counterpart. The first 12 chapters deal with data structures and algorithms that are used in general computer programming. Chapters 13 and 14 discussdata structures that can be found in game and simulation applications, and Chapter 15 provides a summery. The breakdown of the chapters of the book is as follows:Chapter 1, Introduction to Data Structures, introduces the topic of data structures and algorithms in general. This chapter also gives readers some insightinto what they can expect from the remainder of the book.Chapter 2, Arrays, covers arrays, which are the most basic data structure thatexists in programming languages that support them. In this chapter we discusssingle- and multidimensional arrays, various algorithms that can be applied toarrays (e.g., insertion, removal, and so forth), bit arrays, ordered arrays, and theSTL implementation of dynamic arrays, the vector template class.

xivIntroductionChapter 3, Recursion, deals with the topic of recursive methods in programming using self-referencing functions and algorithms.Chapter 4, Introduction to Sorting, discusses sorting algorithms that can beperformed in data structures. This chapter is an introduction to sorting andcovers topics such as the merge sort, the bubble sort, the selection sort, and theinsertion sort.Chapter 5, Link Lists, looks at the link list data structure by discussing threevariations known as the singly linked list, the doubly linked list, and the doubleended linked list. Also discussed in this chapter are iterators, which can be usedto move through the elements of a data structure, and the C ’s implementation for linked lists in a template class called list.Chapter 6, Stacks and Queues, discusses three types of data structures knownas stacks, queues, and priority queues. This chapter also discusses the C STLimplementation for each of these data structures.Chapter 7, Hash Tables, focuses on creating hash table data structures and thealgorithms that operate on them. In this chapter we’ll also look at differenttypes of hash tables and algorithms such as quadric probing, separate chaining,and linear probing.Chapter 8, Advanced Sorting, builds off of Chapter 4, Introduction to Sorting,by discussing more advanced sorting algorithms. These algorithms include theradix sort, the quick sort, the shell sort, and partitioning.Chapter 9, Trees, discusses the general and binary tree data structures and thealgorithms that are commonly performed on them. An understanding ofbinary trees can go a long way toward understanding binary space partitiontrees, which are discussed later in the book.Chapter 10, Heaps, is a straightforward discussion about heap data structuresand the common algorithms that can be performed on them.Chapter 11, Graphs, deals with the graph data structure, which is shaped by anabstract problem. Weighted graphs and their use in artificial intelligence arealso discussed.Chapter 12, Additional STL Algorithms, overviews the remaining C STL.Because the STL is so useful to C programmers, the chapter covers as muchinformation as possible.Chapter 13, Scene Management, discusses bounding volume hierarchies suchas quad trees and octrees and talks about creating and rendering a special typeof binary tree called the BSP tree, variations of which are used in many gamessuch as Half-Life 2 and Doom 3. Other topics are also discussed such as portal rendering, potential visibility sets, and level of detail.Chapter 14, Data Compression, deals with algorithms that can compress andencrypt data. This chapter also discusses various texture compression techniques that are very useful to game developers.

IntroductionxvChapter 15, Conclusions, is the final chapter in the book and concludes thediscussion of data structures and algorithms.Appendix A, Additional Resources, is a list of resources that can be beneficial forthose wanting to learn more about general computer programming and gamedevelopment.Appendix B, Chapter Review Question Answers, provides the answers to allchapter questions in the book.Appendix C, OpenGL, gives a brief review of the OpenGL graphical API andthe OpenGL utility toolkit (GLUT). These tools are used for the graphicsrelated chapters of the book, and this appendix gives brief information forthose who need a refresher or for those using it for the first time.Appendix D, Nonstandard Containers and Algorithms, is a more detailed lookat a few resources that provide STL implementations, nonstandard code, anddocumentation for STL-related code.B EYONDTHISB OOKThe topic of data structures and algorithms is huge. There is a lot to learn, especiallywhen game development is involved. To further complicate matters, optimizationsand efficiency is also a crucial area when dealing with this subject. Appendix A hasa list of helpful book and Web resources that might be of great value to you. Also,www.UltimateGameProgramming.com is a community of hobbyist game programmers looking to learn as much as they can from one another.

About the Authorllen Sherrod (Smyrna, GA) is the host of the game programming websitewww.UltimateGameProgramming.com for beginner, student, and hobbyistgame programmers, where he writes regular columns and develops code forthis popular site. He has been programming in many different languages such as C,C , C#, Java, QBasic, Visual Basic, and Assembly for the past seven years. Hegraduated from DeVry University with a bachelor’s degree in computer informationsystems. Allen Sherrod is also the author of the books Ultimate Game Programmingwith DirectX, Game Graphics Programming, and Ultimate 3D Game Engine Designand Architecture as well as a contributor to Game Programming Gems 6, Game Developers Magazine, and Gamastura.A

1Introduction to DataStructuresIn This ChapterData Structures and AlgorithmsData Structures in Games and SimulationsC versus Java and C#The C STLTemplate Classes and FunctionsBig-O Notation1

2Data Structures and Algorithms for Game Developershe purpose of this chapter is to define data structures and algorithms interms of what they are, why they exist, and how they are used in computerprogramming. This chapter will also introduce topics such as how datastructures fit into game development, template classes and their benefits, C ’sStandard Template Library, and the big-O notation and how it can be used to measure the performance of algorithms. This chapter is an introduction on which thefollowing chapters will build.This book assumes that you have some experience with the C programminglanguage and object-oriented programming (either with C or another high-levelobject-oriented programming language such as Java or C#). Although you do notneed an expert level of knowledge, you do need at least some understanding ofclasses in C . Experience with data structures and various algorithms is not assumed beyond the basic data structure known as arrays.TD ATA S TRUCTURESANDA LGORITHMSData structures are the building blocks of software engineering. Every applicationhas to manage and manipulate data in some meaningful way to perform a task. Inmodern video games this data is used to create a complex interactive experience inwhich gamers can have many different experiences. By themselves data structuresare not very useful, but when they are combined with algorithms, some meaningful output takes place. In this book we will look at many different data structuresand algorithms that are common in general computer programming as well asgames and simulations development.DEFINITIONOFDATA STRUCTURESA data structure defines how data is arranged in memory and can be operated onby using various algorithms. One of the most basic data structures used in generalcomputer programming is the array. An array is a data structure because it defineshow data is arranged in memory, in this case a heap of variables or objects of aspecific type (or types in typeless languages), which can be operated on by variousalgorithms (e.g., insertion into the array, deletion, searching, sorting, and so forth).The data structures that will be examined in this book include the following:ArraysLink listsQueues

Chapter 1 Introduction to Data Structures3StacksHeapsGraphsScene graphsOctreesQuad-treesBinary treesMinimax treeskd treesSphere treesBounding volume hierarchiesHash tablesPortals and sectorsAnother way to look at a data structure is as a structure that is often user-definedand represents some kind of physical object. Data structures are also objects thatcontain objects.DEFINITIONOFALGORITHMSAn algorithm is code that manipulates data in data structures. Most algorithms examined in this book apply to general data structures that include inserting itemsinto a data structure, deleting items, sorting, and iterating. Some of the algorithmsthat will be looked at throughout this book include the us sorting algorithmsVarious searching algorithmsTransversalVarious algorithms for balancing treesData compressionTexture compressionData encryptionTexture filters

4Data Structures and Algorithms for Game DevelopersD ATA S TRUCTURESING AMESANDS IMULATIONSData structures form the foundation of many techniques performed in modernvideo games and are essential to creating the kinds of experiences gamers expect.Alone, a data structure is an arrangement of data in memory, but when combinedwith special-purpose algorithms those data can be processed and used efficientlyand effectively. Because of the nature of a data structure, by definition, the subjectalone is a general topic. Data structures and algorithms in game development areoften used to speed up the processing of a game’s data. In the following sectionswe’ll take a brief look at some of their uses and why they are important to a gameapplication. Later in the book we will take a more detailed look at the data structures used in video games.This book focuses on how we can manage data objects in a gaming application.These data describe entities that need to be processed in a manner that benefits theoverall application’s performance, performs some calculations needed to create aneffect (e.g., artificial intelligence, physics, etc.), or takes data in one form and transforms them into another. The main questions that will be addressed in this bookare:How to store data efficiently in the computer’s memoryHow to process data efficientlyWhat algorithms work best under what situations and whyHow various popular algorithms compare to one another in specific situationsWhat data structures can help the processing of game data in certain situationsSome data structures that we’ll look at model real-world situations and objects.For example, a queue data structure, which we’ll look at in Chapter 6, can be usedto store a queue of networking messages for an online game. Another example ofthis can be seen in a graph where the nodes of the graph represent cities across theUnited States, which we’ll look at in Chapter 13.DATA STRUCTURESFORSCENE MANAGEMENTComplex virtual environments in modern video games are often more complexthan the hardware can handle all at once. In games thousands of polygons are rendered and processed, special effects are updated and drawn, and physics need to beprocessed that can quickly overwhelm any system’s hardware. Since the beginningof 3D games, data structures and algorithms have been used to speed up the rendering of complex scenes that otherwise would bring an application’s performancedown to noninteractive (unplayable) rates.

Chapter 1 Introduction to Data Structures5Using data structures for managing scenes often comes down to situations suchas needing a fast means of determining what geometry is visible to avoid sendinggeometry down the pipeline that can’t be seen by the viewer, avoiding or minimizing bottlenecks and state changes in the system, and efficiently managing the staticand dynamic objects that exist in the game world. Scene and resource managementare two of the topics that are essential to all modern 3D games and their frameworks, also known as the game engine.As an example of state management, consider a situation where a game has 20high-resolution textures that are shared among 500 surfaces. If the rendering codesets up the texture and other effect parameters, renders the surface, and then movesonto the next object and does the same thing for all objects, the application couldbe wasting a lot of processing time with unnecessary rendering state changes.Grouping surfaces together that use the same states (textures, shaders, and so forth)reduces the number of state changes, which increases performance. Not only doesthis mean rendering all surfaces that use texture A together before moving to allthat use texture B, but it also means not wasting processing time moving the samedata down the system if it is already there (e.g., sending the same shader uniformvalues that are already there or re-applying the current shader). State changes suchas textures and shaders are very expensive, and spending time reducing them is farmore beneficial than allowing them to take place in a complex gaming environment. This kind of optimization occurs in many areas of game development, especially rendering, and can be used to push the envelope of what a system can do inreal time.DATA STRUCTURESFORARTIFICIAL INTELLIGENCEArtificial intelligence (AI) drives many gaming experiences. It can be simple orcomplex. Even in simple AI systems various data structures and algorithms areused to control the behavior of dynamic game elements. As the AI gets more complex, speed becomes more of an issue because the more complex the algorithms, themore processing time is needed to complete its operations. Combine that withmultiple objects, each needing to execute AI algorithms, and you can find yourselftrying to balance realism with performance, much like rendering and physics. Forthis reason, game AI is often not as complex and extensive as AI used in roboticsand other such technologies, but game AI is a very complex and growing field. Asgamers’ demands increase, so will this and other areas of game development.DATA STRUCTURESFORPHYSICS DYNAMICSANDCOLLISIONSPhysics is becoming a standard feature in modern 3D games. Physics in gamesdeals with the realistic representation of a game object as well as how it interactswith its environment. This includes forces that act on the objects (e.g., gravity,

6Data Structures and Algorithms for Game Developerswind, and so forth) as well as the resulting forces that result from objects interacting with each other, mainly through collisions.Physics and collisions have their own set of data structures and algorithms(e.g., point masses, rigid bodies, algorithms to apply external forces, resolve interactions, and so forth) that are performed to allow objects to interact in real timewith each other and their environment. Because physics and collisions are so expensive, other data structures and algorithms that are used for scene managementare also used in physics to help eliminate unnecessary calculations, such as tryingto find collisions between two objects that have no way of being able to touch oneanother in order to improve performance.Data structures can be seen in many areas of application design. Being able toefficiently define data structures and the algorithms that operate on them is the keyto creating a solid and effective product.C VERSUSJ AVAANDC#Many differences distinguish C , Java, and C# from each other. Java and C# havevery similar syntax, and anyone familiar with one will have an easier time learningthe other. One of the biggest differences that set Java and C# apart from C ismemory management. With Java and C# automatic memory management takesplace within the runtime environment. This frees the programmer from a great dealof memory management responsibilities. It also means that Java and C# programmers do not have to worry about dangling pointers, accidental memory leaks, and,to a degree, memory fragmentation. With C the management of memory is theresponsibility of the programmer working on a project. This further complicates thedevelopment of an application. In C an error with the memory (e.g., danglingpointers, buffer overflow, and so forth) can crash an application or the system, as wellas other potentially disastrous scenarios that for the most part are unpredictable.Memory management is also tied with performance, which is always cruc

which fits in with game development. These chapters cover scene management techniques used to help process a 3D scene in real time for rendering as well as physics and collisions, to name a few. This project is my third book, with the first being Ultimate Game Programming with DirectXand the second bein