Sign in to follow this  
yoursort

Quadtree delete-method

Recommended Posts

Hello, I need your help. I´m developing a quadtree class for a small game engine. Currently my project targets normal Windows but in the future I will migrate the code to compile for Windows Mobile. So don´t wonder about using fixed-point math. The creation of a quadtree runs fine but my deletion method works not right. Every quadtree-node has a pointer to its parent and 4 pointers to its children. The method should delete this node and all its children. The quadrant order is 1 -> top left, 2->top right, 3->bottom left, 4->bottom right. Please have a look at my code. I´m staring at it but I can´t find anything wrong. I don´t know if I can do "delete this" at the last line of the code? Thank you for your help!
// Delete a QuadtreeNode and its children
void QuadtreeNode::DeleteQuadtree()
{
	for(int i = 0; i < 4; i++)
	{
		// Recursively delete children of this node
		if(mpChild[i])
		{
			mpChild[i]->DeleteQuadtree();
		}
	}

	// Update parents child pointer to NULL
	if(mpParent)
	{
		// Compute the quadrant the obects AAR is in
		// and set parents child pointer to NULL
		if(mCenter.y > mpParent->mCenter.y)
		{
			if(mCenter.x < mpParent->mCenter.x)
				mpParent->mpChild[0] = NULL;
			else
				mpParent->mpChild[1] = NULL;
		}
		else
		{
			if(mCenter.x < mpParent->mCenter.x)
				mpParent->mpChild[2] = NULL;
			else
				mpParent->mpChild[3] = NULL;
		}

		
		
	}

	// Delete this node
	delete this;
	
}

Share this post


Link to post
Share on other sites

You shouldn't ever delete the this pointer.

The best way to do this would probably be to have DeleteQuadtree delete the node's four children. Then to delete a quadtree you'd call root_node->DeleteQuadtree and then delete the root node.

Or, you could delete the node's children in the node's destructor, and thus be able to destroy the entire quadtree with:
delete root_node;

Share this post


Link to post
Share on other sites
Deleting 'this' is perfectly fine, as long as you don't use any of the object's members after doing so. Some design patterns even rely on this mechanism.

To elaborate, consider this code:

#include <iostream>

struct A {
void Addr() { std::cout << std::hex << this << std::endl; }
};

int main()
{
A* b = new A();
std::cout << std::hex << b << std::endl;
b->Addr(); // should print the same address
return 0;
}


You should get the same address in both cases which means 'this' is just an ordinary pointer that happens to point to the current object.
Hope this helps.

[Edited by - Prototype on June 8, 2006 1:49:22 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Prototype
Deleting 'this' is perfectly fine, as long as you don't use any of the object's members after doing so. Some design patterns even rely on this mechanism.


Legal or not, it makes code harder to understand and I've never seen a situation where it couldn't be removed in favor of something clearer. (Perhaps I'm wrong though... do you have any examples?)

Share this post


Link to post
Share on other sites

I agree, "delete this" is perfectly fine.

I am not sure what is the purpose for you to give the node itself a self-deletion possibility. I can imagine that there are some uses for it too.

However, if that feature isn't needed, why not just write :



void Quadtree::~Quadtree()
{
for(int i = 0; i < 4; i++)
{
// Recursively delete children of this node
if(mpChild[i])
{
delete mpChild[i];
mpChild[i] = NULL;
}
}
}



This way you don't have to worry about NULLifying the parents pointer.

What actually happens with your code ? It crashes or something ?

Share this post


Link to post
Share on other sites
First, thank you.
But the problem still exists:
I´ve implented the destructor variant from Demus79. The child-pointers were correctly set to NULL in the destructor but after the "delete node;" command has finished the child pointers point to the address 0xfeeefeee ?? This is != NULL and so my other methods try to use the data members of the deleted node and my programm crashes.

Share this post


Link to post
Share on other sites

When running under debug mode the debug runtime fills freed memory areas with 0xfeeefeee (stands for free).

So if you "delete this" node, it will happen that all the member variables of "this" will receive 0xfeeefeee value.

What you seem to be doing wrong is that you are accessing an object after it has been deleted.

Could you show your code again ?

Best regards

Share this post


Link to post
Share on other sites
Yes Demus that´s right. I´m accessing an object after it is deleted because the pointer that points on this (deleted) object points to 0xfeeefeee and not to NULL!

In my code I try the following:


// Creates a quadtree (depth=3)
a = BuildQuadtree(Vector2(), 200, 3);

// Deletes first subtree
delete (a->mpChild[0]);

// ... some time later
if(a->mpChild[0])
{
drawQuadtree(node->mpChild[0], hdc, ...);
}




a->mpChild[0] == TRUE because it doesn´t points to NULL and the drawQuadtree()-Function accesses data from the deleted subtree and it crashes. :(

Share this post


Link to post
Share on other sites
What I've done with collapsing of nodes in Quadtrees is to return garbage that you want to be deleted.

that is, if the node is to be deleted, it returns a reference to itself and the parent deletes it. if it does not need to be deleted, then you can return null, and simply do a quick check. its better than deleting this.

Share this post


Link to post
Share on other sites
Quote:
Original post by yoursort
Yes Demus that´s right. I´m accessing an object after it is deleted because the pointer that points on this (deleted) object points to 0xfeeefeee and not to NULL!

In my code I try the following:

*** Source Snippet Removed ***

a->mpChild[0] == TRUE because it doesn´t points to NULL and the drawQuadtree()-Function accesses data from the deleted subtree and it crashes. :(


An object destructor can only take care of itself. It cannot take care of a pointer that used to point to it. (Consider that there may be several pointers to the current object, and the object doesn't "know about" any of them.)

You could wrap the deletion in the calling code:


template <typename T>
void safe_delete(T*& ptr) {
delete ptr; ptr = 0;
}


However, it looks like you're having the problem within a member function - you delete one child of a quadtree node, but not in the parent's destructor.

I'm going to refactor all of that. First, I'm going to use 'QuadTree' as the class name, under the assumption that you don't have some wrapper object pointing to the root node. Then, I provide a member function to delete a child safely (nulling out the pointer), and for doing the recursive drawing. I implement the destructor in terms of the child-deletion function, and convert BuildQuadtree into a constructor (DeleteQuadtree is not needed; it turns into the destructor. You really, really should use constructors and destructors for their intended purpose.)


class QuadTree {
// other stuff
QuadTree* children[4];
public:
QuadTree(Vector2 x, int y, int depth) : /* initialization based on x and y here */ {
for (int i = 0; i < 4; ++i) {
// I have no idea what the other parameters specify or what calculations
// you need to do... figure it out for yourself from your existing code :)
children[i] = depth > 0 ? new QuadTree(foo, bar, depth - 1) : 0;
}
}
void deleteChild(int which) {
delete children[i]; // invokes the destructor and does recursive deletion
// if necessary.
children[i] = 0;
}
~QuadTree() {
for (int i = 0; i < 4; ++i) {
deleteChild(i);
}
}
};

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this