Data Structures IV

1. Introduction

This is the last in a series of four articles discussing the use of data structures in games. If you missed the first three (or skipped them), Part I explained why data structures are important, and covered Big O and generics, which will be important in order to understand this article. Parts II and III discussed different data structures and their strengths and weaknesses. Part II covered arrays, lists, and collections, and Part III covered linked lists, stacks, and queues. This article will explain dictionaries and trees, albeit briefly – both of these data structures are complex, and a more in-depth discussion is unfortunately out of scope for this article.

2. Dictionaries

One thing that's important to note about all of the data structures that have been discussed so far is that none of them are well suited to searching their contents. For example, say we have a collection of players in our game. We want to find the player named "Bob" in that collection, because we have just aimed a gigantic missile attack at him. Every one of the collections so far will take O(n) time to find Bob: they all have to go through their contents from beginning to end, checking each player to see if he has the desired name. In many cases, it can be desirable to quickly search through an entire collection to see if an element exists, or to jump straight to an element you know exists. The .NET Framework provides this with the Dictionary.

Dictionaries store elements as pairs of keys and values. You can search for a specific value by looking up its key. To use the previous example, the key would be the player's name, and the value stored would be the player itself.

Since every dictionary will have different types of keys and values, Dictionary has two generic parameters. The other collections discussed in this paper all have one generic parameter: just the type they are storing. Because of this, the syntax for creating dictionaries is different than the other collections:

List list = new List<string>();
Dictionary dictionary = new Dictionary<string, Player>();

The first line of code declares and instantiates a new list of strings. The second one declares and instantiates a dictionary that is keyed on strings, and stores a custom type called a Player.

A full discussion of how Dictionary is implemented in .NET is unfortunately out of scope for this article. To learn more about the implementation details, An Extensive Examination of Data Structures – Part 2 contains great information. In fact, the whole series of articles is definitely a worthwhile read. In brief, the Dictionary maintains an internal array, which is dynamically resized. When a new element is added to the Dictionary, a number called a hash code is computed from the key. That hash code is used to determine where the element will be placed in the internal array. Adding values can be done in two ways:

Dictionary<string, Player> dictionary = new Dictionary<string, Player>();
dictionary["Bob"] = new Player("Bob", PlayerIndex.One);

In both of these cases, a hash code is computed from the string key, “Bob” or “Joe”. The hash code is then used to store the Player object in the dictionary. Remember that in every other collection we've discussed, to find a specific element, we had to do a linear search through the collection, examining every one until the desired one is found. With a Dictionary, this is unnecessary; if we want to get the Player named Bob, we can simply compute the hash code of “Bob” to figure out where Bob would go, and then return the Player at that location.

Like the other collections that are implemented with a dynamically resizing array, adding new elements is a best case O(1), worst case O(n). Removing is O(1). In-order access and out of order accessing both take constant time; but it is important to note that this is not what dictionaries are optimized for. This is a good example of the problems with Big O that were discussed earlier. Although in-order access and out-of-order access both take constant time, the constant is a large number. There are a lot of steps associated with getting elements out of a Dictionary. If the primary reason you need a data structure is to store data that will simply be looped over, a Dictionary is not the ideal solution.

One common use for dictionaries in games is asset management. This can be seen in the XNA Framework ContentManager class. ContentManager has a Load method, which takes in a string parameter for the name of the asset to load. To provide this functionality, the ContentManager has an internal dictionary that maps from strings to loaded assets. When a user requests the asset "myTexture", the ContentManager checks the internal dictionary. If an asset by that name has been loaded already, the ContentManager returns it. Otherwise, it will load the asset, add it to the dictionary for later use, and then return it. This means that even if fifteen different classes in your game want to use the same texture, that texture is loaded into memory only once.

3. Trees

Trees are not one specific kind of data structure, but rather a class of data structures. There are many different kinds of trees, each designed to solve a different problem. Since there isn't one standard kind of tree, one isn't implemented in the .NET Framework, but trees are mentioned in this paper primarily because they are such a commonly used data structure in game programming.

Trees are similar to linked lists in some ways: the real core of the functionality is not found in the collection itself, but in its individual nodes. Remember that LinkedListNode has a .Next reference that points to the next LinkedListNode in the collection. A TreeNode is similar, but each TreeNode will have not just one reference, but multiple .Children references. Just as the name implies, they can be best visualized as a tree: the trunk splits into multiple branches, and each branch can split again, and so on.

In this example, the root of the tree is node A. It has two children, B and C. There are many different restrictions you can put on different trees: some require each node to have a specific number of children, others have a maximum depth to which the tree can grow. (The depth of the tree is how many levels of hierarchy there are. In this example, the depth is 4: the first level is A, the second is B and C, and so on.)

Functions such as adding and removing elements, searching, and accessing elements will be very different from tree to tree. Therefore, it is not possible to give performance metrics for basic data structure operations on trees.

Tree structures and hierarchical structures appear in many different contexts in game programming. One of the most common is that of a transformation hierarchy. The XNA Framework Model class uses a transformation hierarchy, so it's possible that you may have already used a tree structure in your game code. To see what a transformation hierarchy is, and why it is useful, let's look at an example.

Let's say you're writing a 3D game with a tank in it. Among other things, the tank has four wheels. The wheels need to spin, obviously, so they've been created as separate 3D pieces; that way you can draw them independently of the rest of the parts of the tank. Call each one of those 3D pieces a mesh. Now, no matter how the tank moves or turns, the wheel meshes should stay attached, in the same position relative to the tank. The most common way to accomplish this is with a transformation hierarchy. Imagine that every mesh in your game is a node in a tree, and can have child nodes, just like any other tree. Each node also has information about the mesh's current position and orientation. Here's the cool part: nodes also "inherit" their position and orientation from their parent node. In more mathematical terms, the position and orientation of nodes are relative to their parent node. So, in the tank example, the tree structure would look like this:

The main tank is the parent, and there are four children, one for each of the wheels. Each wheel node has different position information offsetting it from the main tank. One wheel node's position puts the wheel on the front of the tank on the left; one is the front right, and so on. Since these wheel nodes also "inherit" position and orientation from parent node, the tank can move, turn, and go wherever it wants and the wheel nodes will stay in the correct place.

At first glance, that may not see like that big of a benefit: it is certainly possible to write code in your Tank class that computes the proper location for the wheels every time the tank moves. However, this is a very common pattern, and transformation hierarchies can get fairly deep. Imagine a human character, with a body, upper arm, lower arm, hand, and fingers: it quickly becomes apparent that hard-coding fixups in every one of your classes is not appropriate, and that a solution like this one is necessary.

More complicated tree-based structures, such as QuadTrees, Octrees, and KD-trees are also extremely common in games. They are used to divide up the game world into more manageable chunks for efficient collision detection and visibility checking. Each one of those data structures could easily be a whole article, so unfortunately it's not possible to go into detail about them here.

4. Conclusion

Each one of the data structures described in this article warrants a thorough article of its own. Trees and dictionaries, in particular, deserve far more attention than they were given here. Both can be useful for game programming when used correctly.

In any case, I hope this article was at least useful as a starting point. Before you leap back into your code, however, let me give you one last rule of thumb: although it is always a good idea to keep performance in mind when writing your game, don’t worry about performance too soon. Make your code clean and easy to use first. When you do get performance problems, you’ll know where to spend your time optimizing. Good luck and happy coding.

An Extensive Examination of Data Structures – A six part article on MSDN regarding data structures, written by Scott Mitchell of 4GuysFromRolla.com.

Selecting a Collection Class – An MSDN article with rules of thumb for data structure selection.