Custom priority queue

Development Programming & Scripting C++
, , ,
1

Hi

I’m trying to implement the answer from this question: https://answers.unrealengine.com/questions/180188/analogue-of-priority-queue.html

But I am encountering the following two errors on compile:

Error LNK1120 1 unresolved externals
Error LNK2019 unresolved external symbol “public: __cdecl AVolumeNavigator::NodePriority::NodePriority(int)” (??0NodePriority@AVolumeNavigator@@QEAA@H@Z) referenced in function "public: void __cdecl AVolumeNavigator::FindRoute(class AVASFVVolume *,class AVASFVVolume *)const " (?FindRoute@AVolumeNavigator@@QEBAXPEAVAVASFVVolume@@anonymous_user_f2147170@Z)

My files:
.h

struct NodePriority
{
	//explicit NodePriority(AVASFVVolume *InVolume, float InPriority);
	explicit NodePriority(uint32 InPriority);
	//AVASFVVolume Volume;
	uint32 Priority;
};

struct NodePriorityPredicate
{
	bool operator() (const NodePriority& A, const NodePriority& B) const
	{
		return A.Priority > B.Priority;
	}
};

.cpp

TArray<NodePriority> frontier;
frontier.HeapPush(NodePriority(12), NodePriorityPredicate());

Once I have this working with your help, I want to include the *InVolume pointer which I’m supposing can just be implemented in my struct in the way that I have commented out at the moment.

Thanks for taking a look!

2

Hi Jayae,

The first error is a generic error saying that some symbols (1, in this case) aren’t resolved.

The second error is likely the important one. It indicates that the constructor for the NodePriority structure isn’t resolved. This is usually due to not defining the constructor in the *.cpp file. Another common cause is a typo in the name of (or less fequently the arguments to) the constructor. If you’ve already double-checked those issues, could you include the definition you have?

3

Hi Roomon

Oh right! In that case I think I’ve just not fundamentally understood the linked answer. I assumed that the constructor had been defined fully in line 4 of my header file. I’ll go away and learn more about structs :slight_smile:

As my struct is contained within the class header file, I’m guessing I’ll need to define the constructor in the .cpp file something like

classname::structname structname(uint32 InPriority)
{
...
}
4

Logging my current answer here in case others have the same question
.h

	struct NodePriority
	{
		AVASFVVolume* volume;
		float priority;
		
		NodePriority(AVASFVVolume* InVolume, float InPriority)
		{
			volume = InVolume;
			priority = InPriority;
		}

		NodePriority() //default constructor for when only declaring new NodePriority variable
		{
			volume = NULL;
			priority = 0.0f;
		}		
	};
5

For people finding this now, there’s (in my opinion) a better way to do it via overriding the < operator and wrapping a TArray up a bit.

Keep in mind: A lower number means higher priority

CODE

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

// -- 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();
}