Jump to content
  • Advertisement
Sign in to follow this  
Endar

I have forgotten recursion through tree elements

This topic is 4388 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

It's official. I have no idea how recursion works anymore. I'm attempting to search my scene graph for a node subtree, and have it removed. The only problem is that I keep getting stack overflow due to a recursion error. How do I structure the code so it returns up the call stack once I've done the removal and won't search the rest of the tree?
/**
 * Remove a node subtree from the scene graph
 * \param root The root of the subtree to search for the scene graph node to remove
 * \param node The node of the scene graph to remove
 */
void CSceneGraph::removeNode(scene::ISceneGraphNode* root, scene::ISceneGraphNode* node)
{
	util::list<ISceneGraphNode*>::iterator i;

	for(i=m_nodeList.begin(); i != m_nodeList.end(); ++i){

		// if we have found the subtree
		if( (*i) == node ){
			// erase it
			m_nodeList.erase(i);
			return;
		}

		// recursively call remove on every subtree in the node
		removeNode( (*i), node );
	}

}



[Edited by - Endar on October 14, 2006 11:51:34 PM]

Share this post


Link to post
Share on other sites
Advertisement
Your for line should be


for(i=root->m_nodeList.begin(); i != root->m_nodeList.end(); ++i) {


removeNode is being infinitely called to search through CSceneGraph::m_nodeList, as in each search it spawns off new functions to keep searching through the same list :) You forgot to reference the root node.

A couple things. I wouldn't rely on pointer comparison. It should work, but you never know a node you are searching for has been reallocated for some reason. You should uniquely identify each node with a name or something, and search that name.

Second, you should keep a straight hashmap (or map) of all your nodes in a scene manager or whatever. That way you can easily lookup any node (very fast) and remove it from the scene.

Also, you should typedef your containers, like

typedef util::list<ISceneGraphNode*> NodeList;


That way, you just declare NodeList::iterator and you won't have to change multiple lines of code just to change the container type.

Share this post


Link to post
Share on other sites
Quote:
Original post by Endar
It's official. I have no idea how recursion works anymore.

I'm attempting to search my scene graph for a node subtree, and have it removed. The only problem is that I keep getting stack overflow due to a recursion error.

How do I structure the code so it returns up the call stack once I've done the removal and won't search the rest of the tree?

*** Source Snippet Removed ***
I can tell you what's wrong with your current function, but to tell you how to do it correctly we'll need to know a little about ISceneGraphNode and how the tree is structured.

As for your function, note that the root argument is never used, which is a good first indication that something is wrong with the logic.

Now to me it looks like the function iterates through the entire node list every time it's called. Say for the sake of argument that the node you wish to remove is not the first node in the list. On the very first iteration of the loop, removeNode() is called again immediately, and with the same node argument. In fact, the only termination conditions for the recursion are an empty list, or if the node you wish to remove is the first entry in the list. Otherwise, the function recurses indefinitely and the stack overflows.

Share this post


Link to post
Share on other sites
Aha!! Success!!

Thanks guys. I was completely forgetting to reference the child node list of the scene graph node we were supposed to be searching in.

I was just having one of those times when you find a small bug, fix it, and then because you assume that everything is going to be right, your eyes see it as right, even when it's wrong.

:D

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!