Jump to content
  • Advertisement
Sign in to follow this  
Michele Bosi

how to iterative tree traversal

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

I have a tree data structure that I use for my scene graph that I traverse each frame to update 20.000 nodes, I am currently doing the typical recursive traversal but probably it would be quicker if I converted the recursive traversal in an iterative one, does anyone have any hint on how to do that? Here is how my data structure looks like:
class Node
{
public:

 ... some data ...

 std::vector<Node*> Children;
};

void do_something_before(Node*) 
{ 
  ... 
} 

void do_something_after(Node*) 
{ 
  ... 
} 

// function to translate into an iterative one

void traverse(Node* node)
{
  do_something_before(node);

  for(int i=0; i<node->Children.size(); ++i )
    traverse(node->Children);

  do_something_after(node);
}
Thanks

Share this post


Link to post
Share on other sites
Advertisement
No, it wouldn't be quicker. The traversal is insignificant compared to the work done on individual nodes anyway. If you really wanted, you could turn it into an O(1) algorithm in terms of memory usage by using parent pointers, instead of a stack, but this wouldn't speed up things one bit.

Share this post


Link to post
Share on other sites
Quote:
Original post by Michele Bosi
probably it would be quicker if I converted the recursive traversal in an iterative one

Unlikely. Anyways, if you want to do depth-first graph traversal, you need to use a stack. In the case of recursion, this is implicit; the stack used is the call stack. For iteration, you'll need to keep an actual stack around. The algorithm is as follows.


push the root node onto the stack
While the stack is not empty:
pop a node off the top of the stack
push the children onto the stack
do any node drawing stuff you like

The do_something_before() is trivial to add to this. The do_something_after(), not so much. Probably the easiest way to implement it is to allow a Node to detect when it is the last child of its parent; it can then handle that stuff. The alternative is to have a second stack of indices into the first stack, so you can tell when a particular subtree is completed.

Share this post


Link to post
Share on other sites
You might find that the best gain you can easily get out of such an algorithm is to allocate your Node objects from a pool or a pre-allocated array, thus making more effective use of the memory cache when traversing the tree. Obviously it also helps if you can keep the Nodes as small as possible.

Share this post


Link to post
Share on other sites
Thanks Kylotan, also from other tests I did it turned out that at the level of performances the code is the cache friendliness of the data structures becomes quite important, its easy to see also if one adds some dummy data to the node and does some timings. This is surely the direction I will go and forget about iterative node traversal (for now).

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!