I have forgotten recursion through tree elements

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

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 on other sites
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 on other sites
Quote:
 Original post by EndarIt'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 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

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 17
• 14
• 10
• 9
• 11
• Forum Statistics

• Total Topics
634094
• Total Posts
3015500
×