I'v been adventurous enough to try to implement a Quad-tree.
But I keep getting these Unhandled exceptions everywhere around the code, it seems like it doesn't allocate the memory or the memory of the allocated items get corrupted.
Am I doing something wrong inside my code? I know that if I place to many objects near each other the program will most likely crash due to it trying to produce infinite nodes since there are to many nodes inside the new node.
But it's crashing during start up so it's not that.
Hopefully someone can help me and spot the problem somewhere inside my code.
Here is an example of the error message I am getting:
Unhandled exception at 0x00488cf6 in SFML Quadtree.exe: 0xC0000005: Access violation reading location 0x00000000.
And down below is the vital and "minimal" ( excluding the Object class since it only contains a rectangle object ) and the headerfile of the Quadtree since well most of the information is already inside the .cpp file.
#include <iostream>
#include <SFML/Graphics.hpp>
#include "Quadtree.hpp"
int main()
{
sf::RenderWindow window(sf::VideoMode(800, 600, 32), "Quadtree - Structure and Split Example");
sf::Event evnt;
Quadtree qTree( 0,0, window.getSize().x, window.getSize().y, window, 0 );
int drawCalls = 0;
int collisionCalls = 0;
sf::Clock frameClock;
const float TIMER = 1.0f / 0.5f;
while(window.isOpen())
{
while(window.pollEvent(evnt))
{
if(evnt.type == sf::Event::Closed)
window.close();
if(evnt.type == sf::Event::MouseButtonReleased)
{
if(evnt.mouseButton.button == sf::Mouse::Button::Left)
{
qTree.add(new Object(sf::Mouse::getPosition(window).x, sf::Mouse::getPosition(window).y));
std::cout << "Added object to node" << std::endl;
std::cout << collisionCalls << " collisions performed." << std::endl;
collisionCalls = 0;
}
}
}
if(frameClock.getElapsedTime().asSeconds() > TIMER)
{
frameClock.restart();
std::cout << drawCalls << " drawcalls performed." << std::endl;
}
drawCalls = 0;
window.clear(sf::Color(94, 174, 255));
qTree.display(drawCalls);
window.display();
}
return 0;
}
And here is the Quadtree.cpp
#include "Quadtree.hpp"
#include <iostream>
const int Quadtree::MAX_DEPTH = 7;
const int Quadtree::MAX_OBJECTS = 4;
Quadtree::Quadtree(float x, float y, float width, float height, sf::RenderWindow& wndw, int depth)
{
quadX = x;
quadY = y;
quadWidth = width;
quadHeight = height;
window = &wndw;
nodeStatus = LEAF;
quadDepth = depth;
objectNumber = 0;
rect.setFillColor(sf::Color::Black);
rect.setOutlineColor(sf::Color::Magenta);
rect.setOutlineThickness(1);
rect.setPosition(x, y);
rect.setSize(sf::Vector2f(width, height));
quad.left = x;
quad.top = y;
quad.width = width;
quad.height = height;
for(int i = 0; i < 4; i++)
nodes[i] = NULL;
}
Quadtree::~Quadtree()
{
for(int n = 0; n < 4; n++)
{
if(nodes[n] != NULL)
delete nodes[n];
}
}
void Quadtree::add(Object* object)
{
objectNumber++;
objects.push_back(new Object(*object));
if(objectNumber >= MAX_OBJECTS)
{
split();
}
}
void Quadtree::split()
{
if(quadDepth >= MAX_DEPTH)
return;
for(int i = 0; i < objects.size(); i++)
{
pass(objects[i]);
delete objects[i];
objects.erase(objects.begin() + i);
--i;
}
}
void Quadtree::pass(Object* object)
{
/* Determite where it should be placed */
if(object->getX() > quadWidth/2) /* If true, place somewhere on the right side */
{
/* SE or NE */
if(object->getY() > quadHeight/2) /* It's the SE Node */
{
if(nodes[1] == NULL)
{
nodes[1] = new Quadtree(quadX + quadWidth/2, quadY + quadHeight/2, quadWidth/2, quadHeight/2, *window, quadDepth +1); // SE
}
nodes[1]->add(object);
return;
}
else
{
if(nodes[0] == NULL)
{
nodes[0] = new Quadtree(quadX + quadWidth/2, quadY, quadWidth/2, quadHeight/2, *window, quadDepth + 1); // NE
}
nodes[0]->add(object);
return;
}
}
else
{
/* Is it NW or SW*/
if(object->getY() > quadHeight/2)
{
/* SW */
if(nodes[2] == NULL)
{
nodes[2] = new Quadtree(quadX, quadY + quadHeight/2, quadWidth/2, quadHeight/2, *window, quadDepth +1);// SW
}
nodes[2]->add(object);
return;
}
else
{
if(nodes[3] == NULL)
{
nodes[3] = new Quadtree(quadX, quadY, quadWidth/2, quadHeight/2, *window, quadDepth +1); // NW
}
nodes[3]->add(object);
return;
}
}
}
void Quadtree::display(int& drawCalls)
{
drawCalls++;
window->draw(rect);
for(int n = 0; n < objects.size(); n++)
window->draw(objects[n]->getRect());
for(int i = 0; i < 4; i++)
if(nodes[i] != NULL)
nodes[i]->display(drawCalls);
}