🔒 Locked

Quadtree delete-method

Started by yoursort Jun 8, 2006 at 12:31 PM 11 replies 10.2k views

Original Post

Jun 8, 2006 at 12:31 PM

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;
	
}

lancekt

Jun 8, 2006 at 12:36 PM

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;

yoursort

Jun 8, 2006 at 12:45 PM

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

Prototype

Jun 8, 2006 at 12:49 PM

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]

lancekt

Jun 8, 2006 at 1:06 PM

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?)

Prototype

Jun 8, 2006 at 1:21 PM

Refcounted objects come to mind.
For example COM often uses this construct.

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

Demus79

Jun 8, 2006 at 3:11 PM

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 ?

yoursort

Jun 9, 2006 at 8:55 AM

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.

Demus79

Jun 9, 2006 at 9:35 AM

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

yoursort

Jun 9, 2006 at 11:06 AM

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 subtreedelete (a->mpChild[0]);// ... some time laterif(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. :(

xSKOTTIEx

Jun 9, 2006 at 11:12 AM

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.

Zahlman

Jun 9, 2006 at 3:47 PM

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 = depth > 0 ? new QuadTree(foo, bar, depth - 1) : 0;    }  }  void deleteChild(int which) {    delete children; // invokes the destructor and does recursive deletion    // if necessary.    children = 0;  }  ~QuadTree() {    for (int i = 0; i < 4; ++i) {      deleteChild(i);    }  }};

Topic Locked