Jump to content
  • Advertisement
Sign in to follow this  
yoursort

Quadtree delete-method

This topic is 4572 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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)
		{
			mpChild->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
Advertisement

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
Thank you for the fast answer!
I allready thought off that deleting the this-pointer can´t be good. ;)
I will try your suggestion as soon I´ve some time!
Thx

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
Refcounted objects come to mind.
For example COM often uses this construct.


SomeClass::Release() {
refcount--;
if (!refcount) delete this;
}

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)
{
delete mpChild;
mpChild = 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!