Below is the script for the quadtree... I'm relatively new to the concept of pointers, so my guess is that I have done something wrong with a double pointer, or something along those lines!
#include "BoidQuadTree.h"
#include <iostream>
Quad::Quad(float boundary_TL_x, float boundary_TL_y, float boundary_BR_x, float boundary_BR_y, unsigned short max_Nodes, unsigned short max_Depth)
{
this->max_Depth = new unsigned short(max_Depth);
this->max_Nodes = new unsigned short(max_Nodes);
this->nodes_Remaining = new unsigned short(max_Nodes);
this->boundary_TL = new Vector(boundary_TL_x, boundary_TL_y);
this->boundary_BR = new Vector(boundary_BR_x, boundary_BR_y);
this->TL = nullptr; // no need to allocate memory yet
this->TR = nullptr;
this->BL = nullptr;
this->BR = nullptr;
this->boids = new Boid*[max_Nodes]; // Intitialise all pointers to nullptr
}
Quad::~Quad()
{
if (this->TL == nullptr) { // only deleted if not branched
delete this->max_Depth;
delete this->max_Nodes;
delete[] this->boids;
}
delete this->boundary_TL; // always deleted
delete this->boundary_BR;
delete this->TL;
delete this->TR;
delete this->BL;
delete this->BR;
delete this->nodes_Remaining;
}
bool Quad::Insert(Boid* boid)
{
if (boid != nullptr) {
if (this->InBoundary(boid->position)) {
if (this->TL == nullptr) {
if ((*this->nodes_Remaining) > 0) { // if there is a free position
this->boids[(*(this->max_Nodes)) - (*(this->nodes_Remaining))] = boid;
(*(this->nodes_Remaining)) -= 1;
std::cout << "inserted" << std::endl;
return true; // successfully inserted boid pointer
}
else { // no free positions in current quad...
if (*this->max_Depth > 1) { // Further depth still avaliable, therefore branch all boid pointers into new quads! (can delete boid data from this after branching to free space)
this->TL = new Quad(this->boundary_TL->x, this->boundary_TL->y, this->boundary_TL->x + (this->boundary_BR->x / 2), this->boundary_TL->y + (this->boundary_BR->y / 2), *(this->max_Nodes), *(this->max_Depth) - 1);
this->TR = new Quad(this->boundary_TL->x + (this->boundary_BR->x / 2), this->boundary_TL->y, this->boundary_BR->x, this->boundary_TL->y + (this->boundary_BR->y / 2), *(this->max_Nodes), *(this->max_Depth) - 1);
this->BL = new Quad(this->boundary_TL->x, this->boundary_TL->y + (this->boundary_BR->y / 2), this->boundary_TL->x + (this->boundary_BR->x / 2), this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
this->BR = new Quad(this->boundary_TL->x + (this->boundary_BR->x / 2), this->boundary_TL->y + (this->boundary_BR->y / 2), this->boundary_BR->x, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
std::cout << "Branched!" << std::endl;
for (unsigned short i = 0; i < *(this->max_Nodes); i++) {
this->PushToBranch(this->boids[i]);
}
this->PushToBranch(boid);
delete[] this->boids; // Delete now unneeded data
delete this->max_Nodes;
delete this->max_Depth;
return true;
}
else {
std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Not enough depth to insert boid pointer! Returning false." << std::endl;
std::cout << boid->position->x << " " << boid->position->y << std::endl;
return false;
}
}
}
else { // this quad has branched
this->PushToBranch(boid);
std::cout << "inserted into branch" << std::endl;
}
}
else {
std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Boid not inside the valid range of the quadtree! Returning false." << std::endl;
return false;
}
}
else {
std::cout << "FUNC LOCATION : Quad::Insert() ERROR! Attempted to insert a nullptr! Returning false." << std::endl;
return false;
}
}
void Quad::Insert(Boid** boids_Array, unsigned int number_Of_Boids)
{
for (unsigned int i = 0; i < number_Of_Boids; i++) {
this->Insert(boids_Array[i]);
}
}
bool Quad::InBoundary(Vector* position)
{
if (position->x >= this->boundary_TL->x && position->x <= this->boundary_BR->x && position->y >= this->boundary_TL->y && position->y <= this->boundary_BR->y) {
return true;
}
else {
return false;
}
}
void Quad::PushToBranch(Boid* boid) // determines where to insert() boid (to be used on boids that are already checked to be in radius!), and
{
if (boid->position->x <= this->boundary_TL->x + (this->boundary_BR->x / 2)) {
if (boid->position->y <= this->boundary_TL->y + (this->boundary_BR->y / 2)) { // TL
this->TL->Insert(boid);
}
else { // BL
this->BL->Insert(boid);
}
}
else {
if (boid->position->y <= this->boundary_TL->y + (this->boundary_BR->y / 2)) { // TR
this->TR->Insert(boid);
}
else { // BR
this->BR->Insert(boid);
}
}
}
The main issue is that it works fine for a very small number of boids, but if i Insert() even 10 (with different randomised positions that are well within the scope of the tree) to a quadtree with a max_Depth of 100 and a max_Nodes value of 1 or 2, i end up with hundreds of branches and around 20 depth errors which makes no sense? Any help would be much appreciated! I am losing my mind ;-;
I was calculating the boundaries of the branches incorrectly! Thanks for all the help and feedback :)
updated calculation
this->TL = new Quad(this->boundary_TL->x, this->boundary_TL->y, (this->boundary_TL->x + this->boundary_BR->x) / 2, (this->boundary_TL->y + this->boundary_BR->y) / 2, *(this->max_Nodes), *(this->max_Depth) - 1);
this->TR = new Quad((this->boundary_TL->x + this->boundary_BR->x) / 2, this->boundary_TL->y, this->boundary_BR->x, (this->boundary_TL->y + this->boundary_BR->y) / 2, *(this->max_Nodes), *(this->max_Depth) - 1);
this->BL = new Quad(this->boundary_TL->x, (this->boundary_TL->y + this->boundary_BR->y) / 2, (this->boundary_TL->x + this->boundary_BR->x) / 2, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);
this->BR = new Quad((this->boundary_TL->x + this->boundary_BR->x) / 2, (this->boundary_TL->y + this->boundary_BR->y) / 2, this->boundary_BR->x, this->boundary_BR->y, *(this->max_Nodes), *(this->max_Depth) - 1);