While working on a grid-based game, I figured I’d make my own pathfinding for funsies. But I was missing (or couldn’t find it in the documentation…) a simple Priority Queue/Binary Heap. I did notice that TArray supports some heap-like functionality, so I made a simple wrapper to basically turn it into a very simple heap. It also helps me to not accidentally invalidate the heap while using TArray’s methods.
I figured this might come in handy for some other people as well!
The code’s layout get’s completely butchered on this page… If you want a better formatted one, here’s the link to the gist (that’ll also be updated if need be):
template <typename InElementType>
struct TPriorityQueueNode {
InElementType Element;
float Priority;
TPriorityQueueNode()
{
}
TPriorityQueueNode(InElementType InElement, float InPriority)
{
Element = InElement;
Priority = InPriority;
}
bool operator<(const TPriorityQueueNode<InElementType> Other) const
{
return Priority < Other.Priority;
}
};
template <typename InElementType>
class TPriorityQueue {
public:
TPriorityQueue()
{
Array.Heapify();
}
public:
// Always check if IsEmpty() before Pop-ing!
InElementType Pop()
{
TPriorityQueueNode<InElementType> Node;
Array.HeapPop(Node);
return Node.Element;
}
TPriorityQueueNode<InElementType> PopNode()
{
TPriorityQueueNode<InElementType> Node;
Array.HeapPop(Node);
return Node;
}
void Push(InElementType Element, float Priority)
{
Array.HeapPush(TPriorityQueueNode<InElementType>(Element, Priority));
}
bool IsEmpty() const
{
return Array.Num() == 0;
}
private:
TArray<TPriorityQueueNode<InElementType>> Array;
};
// -- Usage
// Lower number means higher priority
// -- Construction
TPriorityQueue<UTile*> Frontier;
// -- Adding elements: (element, priority)
Frontier.Push(TargetTile, 0.0f);
Frontier.Push(Grid->At(10, 16), 8.0f);
Frontier.Push(StartTile, 1000.0f);
// -- Iteration
while (!Frontier.IsEmpty()) {
UTile* Current = Frontier.Pop(); // Removes it from the top of the heap
Current->DoMagic();
}
Happy programming!