Games 101: Data Structures in Games

Frequently people’s first foray into programming is in games. Sometimes developers come from other disciplines such as design or QA. Frequently I see the same programming mistakes occur due to a lack of understanding of basic data structures. I’ve made them, it seems everyone makes them. So I hope to spread some data structure love (using C#/Unity terminology) without scaring anybody by talking about O(N) notation.

So what are ‘data structures’?

Data structures, also known as ‘collections’ are simply ways to get access to stuff. This is a surprisingly complicated thing. You would think since you’ve got gigs of memory getting access to a few bytes is super quick. But sometimes you can end up looping over stuff, then creating a loop inside the loop and then you’re accessing and looking at a lot of data. That looking part? That’s wasting the CPU.

Wouldn’t it be great if you could figure out how to get just the data you want? And if you do it right, you can even end up writing less code. Pretty awesome, huh? That’s why data structures are so important.

Types of Structures

There are a *lot* of different data structures, and many, many of them are useful for games. Things like octrees and quadtrees, BSPs, and more. But we’re going to talk about the simple ones. The bread and butter:

• Arrays
• Lists
• HashSets
• Dictionaries

Data structures vary in many ways, but these questions define the most important differences between each type.

• Can I access any item quickly?
• Can I add items easily?
• Can I look up a value quickly based on another value?
• Are the items in a specific order?

Ye Ole Array

I’m assuming you have knowledge of Arrays but to review the basics:

• Its a list of elements.
• You can access each element quickly via something like myArray[elementIndex].

Arrays are fast and simple. The number of items in the Array is fixed. They can’t be changed to add or remove items (also known as ‘immutable’). In order to change the size you have to create a new one, then copy your stuff over from list A to list B.

So when do you want to use an Array?

1. When you know the number of items in the Array is never, ever going to change. If you are doing ‘new string[oldArray.Length+1]’ or similar code use a List.
2. You want to make sure no other code adds stuff to your array.

Examples

• Display a fixed number of footsteps as the player walks around.
• A fixed sized 2D grid of the playing field.
• A specific path that a unit can take.

Array Cheat Sheet

• Can I access any item quickly? YES
• Can I add items easily? NO
• Can I lookup a value quickly based on another value? NO
• Are the items in a specific order? YES

The List: An Array with Bells On

Lists are fancy containers for Arrays. They can be accessed quickly as well. Lists can grow and shrink. Items can be added to any point in a List. This is the ‘go to’ data type.

So when do you want to use a List?

1. When you have a number of items that you want to loop over.
2. Access to a specific item via an index is needed. Example: MyList[42]
3. You know you’ll be adding and removing items to the list as you go.

Examples

• A list of currently active units.
• A list of all enemies in the scene.
• A list of all units with a certain state (selected, transitioning, dying, etc)

List Cheat Sheet

• Can I access any item quickly? YES
• Can I add items easily? YES
• Can I lookup a value quickly based on another value? NO
• Are the items in a specific order? YES

The HashSet : Is It or Isn’t It?

The above structures are lists, now lets talk about hash-based structures. Lists have a major problem that HashSets and Dictionaries don’t: if you want to know if something’s in it, you have to loop through each item. For example, this is slow in a list:

MyItem myItem;
if(myList.Contains(myItem))
{
 // if your list contains a million things and that's the last item, guess what? :)
}

The above loops through the list, starting at the beginning, until it runs into the item you are looking for. But in a Hashset, almost the same code:

MyItem myItem;
if(mySet.Contains(myItem))
{
 // if your list contains a million things or one, it doesn't matter.
}

Yep, through the magic of data structures, the same code is super fast.

HashSets are slightly peculiar as well. You don’t usually get the item out of a HashSet. It just returns true if the item is in the set, and false if it is not.

So when do you want to use a HashSet?

1. When you simply want to know if an item is part of a set.
2. You don’t need to loop over all items.
3. You need to add and remove items to the set.

Examples

• Whether a unit is in a specific state (selected, dying, etc)

HashSet Cheat Sheet

• Can I access any item quickly? YES
• Can I add items easily? YES
• Can I lookup a value quickly based on another value? NO
• Are the items in a specific order? NO

The Dictionary

Have you ever had to find some data based on an entirely different object? Chances are: yes. For example you might have a Unit and you need to find the opposing unit the enemy has. You could loop through each item in a List ooooor:

Dictionary<Unit, EnemyUnit> opposingUnits;

EnemyUnit getOpposingUnit(Unit myUnit)
{
  return opposingUnits[myUnit];
}

Just like HashSet, the Dictionary is a hash-based structure so you know that its not looping over the collection under the hood. You can be certain it executes quickly.

So when do you want to use a Dictionary?

1. When you need to get a related object quickly based upon another object.
2. You don’t need to loop over all items.
3. You need to add and remove items to the set.

Examples

• Find a unit’s data when a collider is clicked.
• Find a location’s information based upon its x/y value and see if its occupied.
• Find a sprite image based upon a string.

Dictionary Cheat Sheet

• Can I access any item quickly? YES
• Can I add items easily? YES
• Can I lookup a value quickly based on another value? YES
• Are the items in a specific order? NO

Mixing Data Structures

You’ve probably noticed each structure has different strengths and weaknesses. The best part about data structures is that you can use different ones based on your needs, and you can use as many as you like. For example you can use a List for looping over items, and a Dictionary for quick access.

Choosing the Right Structure

Frequently it turns out that you may start out using one structure, and end up swapping it out for another. Sometimes I’ll use a HashSet only to find that I need a Dictionary at a later point. Getting a feel for what works comes with experience, but try asking the questions above when designing your games and you’ll get better at picking the right ones.

Example Code

I’ll leave you with a simple example of the collections mentioned in this post. Happy Coding! 🙂