Category: Gamedev

So while I am writing some code on my Point’n’Click-Adventure-GameEngine (which will be online on GitHub in a few days – hopefully) I suddenly stumble over a small problem: The developer working with the Engine may want to increase performance by putting multiple images into one big textureatlas. But how do I save and access the rectangles in the most performant way?

Using an Array

Obviously one approach would be simply saving it into an array. An array in C# works basically the same way as it does in C: You give it an entry pointer (not entrypoint, that’s something different!) and move it along the length of the saved data to the chunk of bytes that contain the requested object. Definitly the fastest way possible to save and access data. So we are done here. Or are we?

(VSauce music starts playing)

Are there other options?

But of course, there are!

We could use a List, two Lists that are aligned to each other or a Dictionary.

The List itself would be a bad idea, because a List in C# is basically an Array wrapped into another class with some fancy methods built around it.

What about the two Lists? They basically want to be a Dictionary but are not as performant. Let me elaborate:

Imagine two Lists, one contains the keys, the other one contains the values. The keys are saved in List A at the same location as the values in List B, so the following code should give us the desired result:

public TValue GetValue(TKey key)
{
    return B[A.IndexOf(key)];
}

The problem is: What happens when the key is at the last position in the array? We have to iterate through the whole thing, just to get the key-value connection. This hurts my performance-oriented heart.

So we step to the last type: The Dictionary.

The Dictionary saves the day

First, let me explain how a Dictionary works in C#:

The Dictionary consists of two arrays: The Bucket and the Entries.

These Arrays do basically the same as the two lists in the upper example, but there is a big difference. We save the keys and the values seperatly into collections, but we actually get the data from the Entries-array. Which index we use is determined by the hashcode of the given key. (Source)

Funfact: The Dictionary<TKey, TValue> class in .Net has 1382 lines of code and consists of multiple nested classes and structs. Yet it is rather performant.

After more than 3 entries in the collection the Dictionary<TKey, TValue> surpasses the List<T> when it comes to lookup times. Since the engine targets more than two sprites per atlas (I am optimistic about that), the Dictionary is preferred. (Source)

Conclusion

Go for a Dictionary if you want to be performant, except when you know that a regular array can do the job ofcourse.