Data Structures for Games: Bidirectional Dictionary for Unity in C#
I am glad that finally, I could continue to write on data structures for Unity. In this post, I will try to explain how to create a BiDictionary or a bidirectional dictionary. I am not aware of any recognized name for this data type. It is simply a two-way dictionary type in which you can also retrieve keys using values.
Applications of Bidirectional Dictionary
We use dictionaries because we would like to access some values fast with keys. We may also need to access the keys using the values. This happens especially in game development.
An example scenario
Imagine that you have a grid based game. You keep the grid information inside a matrix. Each cell of the grid corresponds to a matrix index. Therefore, the world coordinate of that cell could be kept in a dictionary with the matrix index as a key. To be more precise, this dictionary would give us the coordinate of the tile when we use a matrix index.
For this scenario, using a normal Dictionary type is enough. However, let’s create more use cases and see if we will need something more. Imagine that, this is a game in which you interact with the tiles by touching them. Every touch gives you a coordinate and you want to know which tile this coordinate corresponds to. Check the illustration below;
As you can see, we need a bidirectional need for the tiles and coordinates. As a solution, you can keep two dictionaries. However, maintaining two different dictionaries may not be the most maintainable way. Instead, using a bi-dictionary would be perfect for this case.
Other possible usages
You should only use this data type when it really helps with the performance. I think you would know when you will need it. If you are;
- trying to search keys of a dictionary with a for loop
- keeping two dictionaries: “key -> value”, and “value -> key”
- calculating some value back and forth constantly (cases which you can precalculate)
We may increase the possibilities here, but if you are transforming two values to each other, this is a strong sign that you should use a bidirectional dictionary.
So, How to Implement a Bidirectional Dictionary?
The easiest and most common way to implement a bidirectional dictionary is by using two dictionaries. You just need to add the keys and values in a bidirectional way. Before giving more implementation details, let’s see the interface and reason why I didn’t implement the IDictionary interface.
public interface IBiDictionary<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>> { Dictionary<TKey, TValue> KeyMap { get; } Dictionary<TValue, TKey> ValueMap { get; } void Add(TKey key, TValue value); bool ContainsKey(TKey key); bool ContainsValue(TValue value); bool RemoveKey(TKey key); bool RemoveValue(TValue value); void Clear(); int Count(); new IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator(); IEnumerator<KeyValuePair<TValue, TKey>> GetValueEnumerator(); }
The main problem with the interfaces comes from the collections library, I can’t have the separation for “key” and “value”. For example, Contains would check only the keys but, the name is not implying that action. I would rather have ContainsKey as a method name.
We can still support the ICollection interface, but I leave this to you. However, for this version, I will only support the IEnumerable interface so that it could be used with iterators.
Let’s Implement the Interface
The most important methods are “add(key, value)” and “remove” methods. Because we shouldn’t forget to maintain both of the dictionaries.
{ public void Add(TKey key, TValue value) { if (key != null && value != null) { forward.Add(key, value); reverse.Add(value, key); } } public bool RemoveKey(TKey key) { var value = forward[key]; return value != null && reverse.ContainsKey(value) && reverse.Remove(value) && forward.Remove(key); } public bool RemoveValue(TValue value) { var key = reverse[value]; return key != null && forward.ContainsKey(key) && forward.Remove(key) && reverse.Remove(value); } }
Here in the add() method, I wanted to make a null check first. Because we don’t want to end up with null keys. The rest is straight-forward. Then for the remove methods, I am using the same pattern. You don’t have to be that cautious. Some of the checks I do would never occur. However, I wanted to be more defensive in this case. I guess you get the main point. Now you can implement your own minimalist bidirectional c# dictionary or you can use my implementation directly.
By the way, forward and reverse are the dictionaries I use. I didn’t want to bloat the post with every detail. Just check the Github page for details.
How to Add it to a Unity Project
You may copy-paste from the Github repository and add it to your project folder. Or, an alternative and more clear way is adding the line below to your manifest.json. Unity would handle the rest and you would be able to use this implementation.
"com.erdiizgi.datastructures": "https://github.com/erdiizgi/DSUnity.git#v0.1.0"
You can have different implementations of the IBiDictionary, and if you bind the implementations using a DI Container like Zenject, you can get the maximum work-ability with this interface.
Conclusion: Bidirectional Dictionary
Bidirectional 1-to-1 dictionaries can be quite handy for game development. I have never seen it in the Java world, but I had a couple of usages for my grid-based games. If you are on this page, you either need it, or you are a curious reader. In both cases, please give me feedback, if this is enough for you or if now please contribute to the open-source project I am trying to spread around.
Questions
I have couple of question for you;
- In the Add() method, should we do only a null-check? I mean if the key or value is null should we throw an exception so that the end-user would know?
- Do you think that we should implement the IDictionary interface or at least the ICollection interface?
In case you need another data type that is not inside the Unity libraries or C#’s collection library, please let me know in the comments. So, I can have another data type to work on.