MinHeap Priority Queues, an alternative for ds_priority

Last updated on Dec 20, 2023

Since GameMaker 2.3, I've started using the ds_ functions less and less, with their old-school memory management requirements and managing numeric indexes, and all the bugs that can come from that.

The alternatives for ds_map is clearly a struct; and ds_grid, ds_stack and ds_queue are also achievable using arrays in a relatively trivial way. But ds_priority is one of the more complex ones to replace since under the hood it's not just a straightforward data structure, it needs a few extra bells and whistles to work.

Long story short, I now just use my own constructor-based replacement for ds_priority that implements a Heap under the hood. Here it is for everyone who wants a more modern priority queue that is GC'd:

What is a ds_priority?

A ds_priority is a datastructure that helps keep track of items and priorities, often referred to as a "priority queue". You can insert value-priority pairs into it in any order you want, and at any time you can query for the lowest or highest priority value in the list.

This is useful for things like correctly ordering your UDP netcode packets which arrive out-of-sequence. Or taking a list of characters with different initiative values and figuring out their move order. Or it's the core of graph and path-finding algorithms such as A*.

From a computational-efficiency point of view, it is a "sort-on-insert", meaning all the computational power necessary to make sure things are order are incurred at the moment of inserting the value. In games, this is quite good for situations where you gradually add values to the ds_priority since you spread out the computation power of sorting; so that when you pull values out of it later, you incur less processing power, which means fewer lag spikes. This is in contrast of the opposite approach of inserting into an unsorted array (which is very fast), and then having to sort the array when you need to use it, which is slow and can incur a lag spike when you do it.

The Heap data structure

I won't get into the details of how this works, but suffice to say that a Heap is a way of structuring data in a way where the priority-order is maintained. ds_priority is almost certainly a Heap data structure under the hood. You can find out more about the Heap data structure on Wikipedia:

MinHeap vs MinMaxHeap

The main difference between my MinHeap implementation and ds_priority (aside from MinHeap being implemented as a constructor and arrays, meaning you don't have to worry about memory management) is that ds_priority is a MinMaxHeap, in that it keeps track of both the minimum and maximum priorities of the heap. You can easily read and remove either the minimum priority item or the maximum priority item at any given time.

My MinHeap and its brother, MaxHeap implementation only does one of these: MinHeap lets you only remove the minimum priority value item from the heap, and doesn't have a way for you to look at the maximum priority. And similarly MaxHeap only lets you remove the maximum priority value item.

It is possible to write a MinMaxHeap implementation, I just haven't done it. I haven't come across a situation where both are needed yet. I've only seen use-cases where you want one or the other. But perhaps this will change, time will tell.

MinHeap Usage Example

Using the code linked at the top of the article, minheap usage looks something like:

turn_order = new MaxHeap();
// insert a bunch of values and their priorities
turn_order.insert(PlayerA, 4);
turn_order.insert(PlayerB, 6);
turn_order.insert(PlayerC, 2);

// Who has the lowest priority?
var _highest_priority_player = turn_order.peek_max_value();

// Process players in turn
while (turn_order.get_length() > 0) {
  var _player = turn_order.pop_max_value();
  process_turn(_player);
}

If you're looking for a more modern way to make a priority queue, use a Heap implementation like this one, and free yourselves from the tyranny of having to memory-manage ds_priority