Hello all!

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.
[/quote]

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 = 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);
delete objects;
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 != NULL)
nodes->display(drawCalls);
}


Your display function is gonna crash. You've got NULL in your nodes array for leaf nodes, but still try call display(sprite) on them. This is probably what's causing the crash on 1st run through the loop.

If you're getting a crash earlier than that, it's likely to be in code you're not showing.
You're also not initializing nodeStatus in the constructor.

Are you not releasing any memory? It looks like you're allocating, but not releasing. That might be the problem.

Your display function is gonna crash. You've got NULL in your nodes array for leaf nodes, but still try call display(sprite) on them. This is probably what's causing the crash on 1st run through the loop.

If you're getting a crash earlier than that, it's likely to be in code you're not showing.
You're also not initializing nodeStatus in the constructor.

I made quite some changes to my code, it works without crashing BUT I'm not sure if I'm handling the memory correct inside the add and pass methods.
The Object constructor takes an "const Object&" parameter which should make sure the memory is still pointed at thus not leaking any memory.

Are you not releasing any memory? It looks like you're allocating, but not releasing. That might be the problem.

I'm releasing the memory inside the destructor of a Quadtree and it calls every nodes ( that is not null ) and deletes them as well, causing a chain destruction starting from the bottom.

The new problem is when it's supposed to split up, noted in the "Pass" or "Split" method after the fist split it starts getting weird, it splits up the wrong nodes and adds the object to them. Is something wrong with my math?

EDIT: Here is a picture that explains the problem, notice the split in the right corner.

Forgot to add the x and y coordinates to the "pass(Object* object)" check. Fixed it now and it works wonders!
Still though can anyone see just by looking at the code if I have memory leaks?