Problem Compiling Custom Priority Queue Module

Help Programming
,
1

Godot Version

3.6

Question

I am working on building a custom priority queue module for pathfinding purposes. When I try to compile and build the project, I get the following errors:
In core\method_bind.gen.inc at line 2176

'encode': is not a member of 'PtrToArg<R>'

In core\method_bind.gen.inc at line 2176

'encode': identifier not found

In C:\Program Files\Microsoft Visual Studio\2022\Community\MSBuild\Microsoft\VC\v170\Microsoft.MakeFile.Targets at line 45.

The command "echo Starting SCons && cmd /V /C set "plat=x64" ^& (if "x64"=="x64" (set "plat=x86_amd64")) ^& set "tools=True" ^& (if "debug"=="release" (set "tools=no")) ^& call "C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvars64.bat" !plat! ^& scons --directory="D:\Users\David Macpherson\godot" platform=windows target=debug progress=no tools=!tools! -j7" exited with code 2.

I am using Visual Studio Code 2022 to write the module.
The is a screenshot of the errors for reference:

image
image1919×152 14 KB

Module code

pqueue.h

/*
Reference for priority queue logic:
https://www.naukri.com/code360/library/priority-queue-in-data-structure
*/

#ifndef PQUEUE_H
#define PQUEUE_H

#include "core/variant.h"
#include "core/object.h"

#include <vector>

struct PQElement {
	float priority;
	Variant data;
};

class PQueue : public Object {
	GDCLASS(PQueue, Object);

	bool max_priority;
	std::vector<PQElement> pq;

	inline PQElement _create_new_element(float priority, Variant data) const;
	inline void _swap(int l_index, int r_index);

	bool _heapify_up(int index, int recur_count);
	bool _heapify_down(int index, int recur_count);

protected:
	static void _bind_methods();

public:
	void push(float priority, Variant data);
	void pop();
	Array top() const;
	bool empty() const;
	int size() const;

	PQueue(bool max_priority);
	PQueue();
	~PQueue();
};

#endif // !PQUEUE

pqueue.cpp

#include "pqueue.h"
#include "core/typedefs.h"

PQueue::PQueue(bool _max_priority) {
	max_priority = _max_priority;
}

PQueue::PQueue() {
	max_priority = true;
}

PQueue::~PQueue() {
	int size = pq.size();
	max_priority = true;
	for (int i; i < size; i++) {
		pop();
	}
}

PQElement PQueue::_create_new_element(float priority, Variant data) const {
	PQElement new_element{};
	new_element.priority = priority;
	new_element.data = data;
	return new_element;
}

void PQueue::_swap(int l_index, int r_index) {
	PQElement l_elem = pq[l_index];
	pq[l_index] = pq[r_index];
	pq[r_index] = l_elem;
}

bool PQueue::_heapify_up(int index, int recur_count = 0) {
	ERR_FAIL_COND_V_MSG(recur_count > MAX_RECURSION, true, "Max recursion reached");
	if (index == 0) {
		return true;
	}
	int parent_index = (index - 1) / 2;
	if (pq[index].priority > pq[parent_index].priority) {
		_swap(index, parent_index);
		_heapify_up(parent_index, recur_count + 1);
	}
}

bool PQueue::_heapify_down(int index, int recur_count = 0) {
	ERR_FAIL_COND_V_MSG(recur_count > MAX_RECURSION, true, "Max recursion reached");
	int l_index = (2 * index) + 1;
	int r_index = (2 * index) + 2;
	int largest = index;
	if (l_index < pq.size() && pq[l_index].priority > pq[largest].priority) {
		largest = l_index;
	}
	if (r_index < pq.size() && pq[r_index].priority > pq[largest].priority) {
		largest = r_index;
	}
	if (largest != index) {
		_swap(index, largest);
		_heapify_down(largest, recur_count + 1);
	}
	return true;
}

void PQueue::_bind_methods() {
	ClassDB::bind_method(D_METHOD("_create_new_element", "priority", "data"), &PQueue::_create_new_element);
	ClassDB::bind_method(D_METHOD("_swap", "l_index", "r_index"), &PQueue::_swap);
	ClassDB::bind_method(D_METHOD("_heapify_up", "index", "recur_count"), &PQueue::_heapify_up);
	ClassDB::bind_method(D_METHOD("_heapify_down", "index", "recur_count"), &PQueue::_heapify_down);
	ClassDB::bind_method(D_METHOD("push", "priority", "data"), &PQueue::push);
	ClassDB::bind_method(D_METHOD("pop"), &PQueue::pop);
	ClassDB::bind_method(D_METHOD("top"), &PQueue::top);
	ClassDB::bind_method(D_METHOD("empty"), &PQueue::empty);
	ClassDB::bind_method(D_METHOD("size"), &PQueue::size);
}

void PQueue::push(float priority, Variant data) {
	PQElement new_element = _create_new_element(priority, data);
	pq.push_back(new_element);
	_heapify_up(pq.size() - 1);
}

void PQueue::pop() {
	if (max_priority) {
		_swap(0, pq.size() - 1);
	}
	pq.pop_back();
	_heapify_down(0);
}

Array PQueue::top() const {
	ERR_FAIL_COND_V_MSG(pq.size() == 0, Variant(), "Can't take value from empty queue.");
	PQElement element = (max_priority) ? pq.back() : pq.front();
	Array a;
	a.push_back(element.priority);
	a.push_back(element.data);
	return a;
}

bool PQueue::empty() const {
	return pq.empty();
}

int PQueue::size() const {
	return pq.size();
}
2

So, I did some testing and found that defining a custom struct to store the data being sorted was causing the problems.

struct PQElement {
	float priority;
	Variant data;
};

I’m not sure how to rectify this. I think it might have something to do with registering the type, but I think it is more to do with the Godot engine itself.

I modified my module to use the Godot Array to store the data instead of a struct. The build now compiles.

pqueue.h

/*
Reference for priority queue logic:
https://www.naukri.com/code360/library/priority-queue-in-data-structure
*/

#ifndef PQUEUE_H
#define PQUEUE_H

#include "core/variant.h"
#include "core/object.h"
#include "core/array.h"

#include <vector>

class PQueue : public Object {
	GDCLASS(PQueue, Object);

	bool max_priority;
	std::vector<Array> pq;

	inline Array _create_new_element(float priority, Variant data) const;
	inline void _swap(int l_index, int r_index);

	bool _heapify_up(int index, int recur_count);
	bool _heapify_down(int index, int recur_count);

protected:
	static void _bind_methods();

public:
	void push(float priority, Variant data);
	void pop();
	Array top() const;
	bool empty() const;
	int size() const;

	PQueue(bool max_priority);
	PQueue();
	~PQueue();
};

#endif // !PQUEUE

pqueue.cpp

#include "pqueue.h"
#include "core/typedefs.h"

PQueue::PQueue(bool _max_priority) {
	max_priority = _max_priority;
}

PQueue::PQueue() {
	max_priority = true;
}

PQueue::~PQueue() {
	int size = pq.size();
	max_priority = true;
	for (int i = 0; i < size; i++) {
		pop();
	}
}

Array PQueue::_create_new_element(float priority, Variant data) const {
	Array new_element;
	new_element.append(priority);
	new_element.append(data);
	return new_element;
}

void PQueue::_swap(int l_index, int r_index) {
	Array l_elem = pq[l_index];
	pq[l_index] = pq[r_index];
	pq[r_index] = l_elem;
}

bool PQueue::_heapify_up(int index, int recur_count = 0) {
	ERR_FAIL_COND_V_MSG(recur_count > MAX_RECURSION, true, "Max recursion reached");
	if (index == 0) {
		return true;
	}
	int parent_index = (index - 1) / 2;
	if (float(pq[index][0]) > float(pq[parent_index][0])) {
		_swap(index, parent_index);
		_heapify_up(parent_index, recur_count + 1);
	}
	return false;
}

bool PQueue::_heapify_down(int index, int recur_count = 0) {
	ERR_FAIL_COND_V_MSG(recur_count > MAX_RECURSION, true, "Max recursion reached");
	int l_index = (2 * index) + 1;
	int r_index = (2 * index) + 2;
	int largest = index;
	if (l_index < pq.size() && float(pq[l_index][0]) > float(pq[largest][0])) {
		largest = l_index;
	}
	if (r_index < pq.size() && float(pq[r_index][0]) > float(pq[largest][0])) {
		largest = r_index;
	}
	if (largest != index) {
		_swap(index, largest);
		_heapify_down(largest, recur_count + 1);
	}
	return true;
}

void PQueue::_bind_methods() {
	ClassDB::bind_method(D_METHOD("_create_new_element", "priority", "data"), &PQueue::_create_new_element);
	ClassDB::bind_method(D_METHOD("_swap", "l_index", "r_index"), &PQueue::_swap);
	ClassDB::bind_method(D_METHOD("_heapify_up", "index", "recur_count"), &PQueue::_heapify_up);
	ClassDB::bind_method(D_METHOD("_heapify_down", "index", "recur_count"), &PQueue::_heapify_down);
	ClassDB::bind_method(D_METHOD("push", "priority", "data"), &PQueue::push);
	ClassDB::bind_method(D_METHOD("pop"), &PQueue::pop);
	ClassDB::bind_method(D_METHOD("top"), &PQueue::top);
	ClassDB::bind_method(D_METHOD("empty"), &PQueue::empty);
	ClassDB::bind_method(D_METHOD("size"), &PQueue::size);
}

void PQueue::push(float priority, Variant data) {
	Array new_element = _create_new_element(priority, data);
	pq.push_back(new_element);
	_heapify_up(pq.size() - 1);
}

void PQueue::pop() {
	if (max_priority) {
		_swap(0, pq.size() - 1);
	}
	pq.pop_back();
	_heapify_down(0);
}

Array PQueue::top() const {
	ERR_FAIL_COND_V_MSG(pq.size() == 0, Variant(), "Can't take value from empty queue.");
	return (max_priority) ? pq.back() : pq.front();
}

bool PQueue::empty() const {
	return pq.empty();
}

int PQueue::size() const {
	return pq.size();
}