Tricks of the Windows Game Programming Gurus:Algorithms, Data Structures, Memory Management, and Multithreading

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

## Part III
Hardcore Game Programming

Chapter 11
  Algorithms, Data Structures, Memory Management, and Multithreading
Chapter 12
  Making Silicon Think with Artificial Intelligence
Chapter 13
  Playing God: Basic Physics Modeling
Chapter 14
  Putting It All Together: You Got Game!

## Chapter 11
Algorithms, Data Structures, Memory Management, and Multithreading

> You think I can get a hug after this?”

> —Bear, Armageddon

This chapter is going to talk about all those little details that slip through the cracks in any game programming book (even mine). We’re going to discuss everything from writing games so they can be saved, to making demos, to optimization theory! This chapter will help you with some of those lingering details. Then, when we cover artificial intelligence in the next chapter, you should have all the general game programming concepts under control so the 3D math doesn’t make you crack!

Here’s what’s in store in this chapter:

  • Data structures
  • Algorithm analysis
  • Optimization theory
  • Mathematical tricks
  • Mixed-language programming
  • Saving games
  • Implementing multiple players
  • Multithreaded programming techniques

### Data Structures

Probably one of the most frequent questions I’m asked is, “What kind of data structures should be used in a game?” The answer is: the fastest and most efficient data structures possible. However, in most cases you won’t need the most advanced, complex data structures that computer science has to offer. Rather, you should try to keep things simple. And speed is more important than memory these days, so you should sacrifice memory before you sacrifice speed!

With that in mind, I want to take a look at a few of the most common data structures used in games and give you some insight into when and how to use them.

#### Static Structures and Arrays

The most basic of all data structures is, of course, a single occurrence of a data item such as a single structure or class. For example:

    typedef struct PLAYER_TYP // tag for forward references

            {

            int state; // state of player

            int x,y; // position of player

            // ...

            } PLAYER, *PLAYER_PTR;

> Tip: In C++, you no longer need to use `typedef` on structure definitions to create a type; a type is automatically created for you when you use the keyword `struct`. In addition, C++ `struct`s can have methods and even public and private sections.

    PLAYER player_1, player_2; // create a couple players

In this case, a single data structure along with two statically defined records does the job. On the other hand, if there were three or more players, it would probably be a good idea to use an array like this:

    PLAYER players[MAX_PLAYERS]; // the players of the game

Here you can process all the players with a simple loop. Okay, great, but what if you don’t know how many players or records there are going to be until the game runs? When this situation arises, I figure out the maximum number of elements that the array would have to hold. If it’s reasonably small number, like 256 or less, and each element is also reasonably small (less than 256 bytes), I will usually statically allocate it and use a counter to count how many of the elements are active at any time.

You may think that this is a waste of memory, and it is, but a preallocated array of a fixed size is easier and faster to traverse than a linked list or more dynamic structure. The point is, if you know the number of elements ahead of time and there aren’t that many of them, go ahead and preallocate an array statically by making a call to `malloc()` or `new()` during startup.

> Warning: Don’t get carried away with static arrays. For example, if you have a structure that is 4KB and there may be from 1 to 256 static arrays, you definitely need a better strategy than allocating 1MB in case there may be 256 of them at some point. In this case, it might be better to use a linked list or to dynamically reallocate the array and increase its size on demand.

#### Linked Lists

Arrays are fine for simple data structures that can be precounted or estimated at compilation or startup, but data structures that can grow or shrink during run-time should use some form of linked lists. Figure 11.1 depicts a standard abstract linked list. A linked list consists of a number of nodes, each node containing information and a link to the next node in the list.

Figure 11.1 A linked list.

Linked lists are cool because you can insert a node anywhere in the list, and you can delete a node from anywhere in the list. Take a look at Figure 11.2 to see this graphically. The capability to insert and delete nodes (and hence, information) during run-time makes linked lists very attractive as data structures for games.

Figure 11.2 Inserting into a linked list.

The only bad thing about linked lists is that you must traverse them node by node to find what you’re looking for (unless other secondary data structures are created to help with the searching). For example, say that you want the 15th element in an array. You would access it like this:

    players[15]

But with linked lists, you need a traversal algorithm to traverse the list to find the 15th element. This means that the searching of linked lists can take a number of iterations equal to the length of the list (in the worst case). That is, `O(n)`—read “Big O of `n`.” This means that there are on the order of `n` operations for `n` elements. Of course, there are optimizations and secondary data structures that you can employ to maintain a sorted indexed list that allows access almost as fast as the simple array.

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.