Data Structures for Games: Priority Queue for Unity in C#

I am so excited for my first post about data structures used in games. One of my professors used to say that applications are nothing but data structures and algorithms together. I don’t know if this theory still holds, but data structures are quite important parts of any kind of application including games. As a first topic, I’d like to write about Priority Queue, since it is not part of the C#’s Collection API.

Priority Queue is a special type of a Queue. Whereas a standard Queue works on first in, first out (FIFO) principle, a priority queue works with priorities assigned to each item. High priority items are dequeued before the elements with low priority.

Applications of Priority Queue

Before going in details of Priority Queue, let’s see in which cases we can use it.

Example Scenario

I have mostly used a priority queue for solving AI problems in my games. Let’s say we are creating a cool bot for a board game. This game provides you three moves at each turn. The bot will decide which order of the moves are the most valuable ones for the next turn.

As a simple solution to this AI problem, we can have a tree structure. The root represents the current state of the board. It will have many children representing the three moves to the available positions (in my game, it was around 270 children). Then, at every child we will have other possible moves to the available positions. At the end, we will evaluate the value of each chain of moves in the leaves of this tree.

I could keep some kind of score property in the nodes, then sort the leaves of the tree, based on the score. Then I could pick the highest one. However, I preferred to use a Priority Queue. So, I have placed the nodes with their score as a priority. Why?

• It helped me to optimize this query. Instead of evaluating 270 children, I have traversed only the most prominent ones.
• In order to create different levels of difficulty. Based on the chosen difficulty, priority queue gave me the second best or the third best set of prominent children.
• I have also wanted to hide sorting and choosing best candidate behaviors from the evaluation of the tree. It was already quite complex and I didn’t want it to be more complex.
• It was reusable for other bot implementations.

So I am quite happy with the results.

Other possible usages of Priority Queues

• Dijkstra’s Shortest Path Algorithm can be implemented using Priority Queue.
• It can be also used to implement Huffman’s compression algorithm.
• A* path finding algorithm
• A sorting algorithm called Heap Sort is implemented using Priority Queue.
• It is possible to give more examples like Prim’s algorithm, or Load Balancing algorithms. Simply, we can use it everywhere that is an application of queue where priority is involved.

So, How to Implement a Priority Queue?

Well, let’s know our requirements first;

• We need items with priorities.
• These items will be inserted into somewhere, a container or a list.
• We should be able to reach or delete the element with the highest priority.

public interface IPriorityQueue<T>
{
    /// Inserts and item with a priority
    void Insert(T item, int priority);

    /// Returns the element with the highest priority
    T Top();

    /// Deletes and returns the element with the highest priority
    T Pop();
}

We can obviously have more features but let’s keep it simple.

Items with Priorities

I guess, this is easy. We can just have a struct with two fields.

struct Item 
{
   int element;
   int priority;
}

Insert

In order to support insert operation we can use a List<Item>. It will take only O(1) time, so it is not bad.

Top() and Pop()

Using List structure was good for Insert method, but for Top() and Pop() methods, it may not be the best. Because we need to sort the list based on the priorities, then pick the first or the last element based on the sorting order.

If we use a Linked List, it would take less time for Pop(). However, I believe that our most important method here is the Top(). Therefore, we should be looking for optimizing it.

What About Using Heaps?

When it comes to Priority Queue implementation, Heaps are the best candidate. It provides much better performance then lists. Only drawback is the Insert performance — It would be O(log n) — which is not a big loss. Pop() can be done in O(log n) and most importantly Top() will be in O(1) time.

As far as I remember from the school years, we can even make the Insert in O(1) time, if we use a Fibonacci heap. Since it is harder to implement, I will fork from an implementation I found on GitHub done by squezy.

There is no need to go into details for heaps, because — trust me — it is not a short topic. In addition to that, you don’t need to know how they are implemented. However, a little short introduction would help to understand the next step.

Briefly, What the Heck is a Heap?

There are two type of heaps I would like to introduce. The first one is a Binary heap. It is a binary tree which satisfies the min-heap property — the value of each node is greater than or equal to the value of its parent and the root has the minimum value. — or max-heap property which is not so hard to guess, it is the opposite of min-heap property. So, the operations like insert or delete, should maintain this properties.

While Binary heap maintains the heap property all the time, there are other heaps which are more relaxed. Fibonacci Heap is a good example which has better amortized complexity due to its flexible nature. It does the operations lazily, so most of the operations are in O(1) time. In case you are curious, it would be sufficient to read its Wikipedia explanation.

Back to the Priority Queue

Since we will implement the Priority Queue using Fibonacci Heaps, we should be aware of that, it maintains a min-heap property. Therefore, the priority being represented by a lower number, would have a higher priority. For instance, let’s think a set like {1, 4, 3, 5}. The highest priority will be ‘1’ in this set.

public class PriorityQueue<TElement, TPriority> : IPriorityQueue<TElement, TPriority>
    where TPriority : IComparable<TPriority>
{
    private readonly FibonacciHeap<TElement, TPriority> heap;

    public PriorityQueue(TPriority minPriority)
    {
        heap = new FibonacciHeap<TElement, TPriority>(minPriority);
    }

    public void Insert(TElement item, TPriority priority)
    {
        heap.Insert(new FibonacciHeapNode<TElement, TPriority>(item, priority));
    }

    public TElement Top()
    {
        return heap.Min().Data;
    }

    public TElement Pop()
    {
        return heap.RemoveMin().Data;
    }
}

As you see in the above implementation, it is just so easy to implement a priority queue backed with a Fibonacci heap. In case you want to see the whole code, here is the link for the repository. If you would like to use this in your projects, just add this line to your dependencies in manifest.json.

"com.erdiizgi.datastructures": "https://github.com/erdiizgi/DSUnity.git#v0.0.2"

You can have different implementations of the IPriorityQueue, and if you bind the implementations using a DI Container like Zenject, you can get the maximum work-ability with this interface.

Conclusion

Priority queue can be useful when your game requires some kind of decision making process. It can hide some unnecessary complexity and they can be quite performant when they are backed by Fibonacci Heaps.

C# Collection API doesn’t contain these data structures out of the box, but there are a lot of implementations you can find online. I am planning to maintain this Data Structures repository with the new posts. In case you have questions to ask, please drop me a comment below. Feel free to contribute to the repository as well. (please use the development branch for the pull requests)