Jump to content
  • Advertisement

Recommended Posts

You really ought to take a look at depth first search preorder traversal. Essentially, you'll just start at the initial parent node, then print in cascading fashion all of that "parents" descendants, then recurse or iterate to the next parent and so on.

Essentially, you are going to want to have a pointer to each nodes child left and right, then you can use a recursive call to consume the data (print or whatever task you are trying to accomplish from the scenegraph) call left, print, right.

dfs(SceneNode* head) {

     if(head == nullptr)

    //exit condition usually return if function is void

     dfs(head->left);

     //task to be completed

     dfs(head->right);
}

Edited by chatch1111

Share this post


Link to post
Share on other sites
Advertisement
6 hours ago, chatch1111 said:

Essentially, you are going to want to have a pointer to each nodes child left and right, then you can use a recursive call to consume the data (print or whatever task you are trying to accomplish from the scenegraph) call left, print, right.

dfs(SceneNode* head) {

     if(head == nullptr)

    //exit condition usually return if function is void

     dfs(head->left);

     //task to be completed

     dfs(head->right);
}

Unless I'm missing something, the above is for a binary tree, but DividedByZero is working with a general tree. (The discussion of recursive traversal is of course relevant either way though.)

Share this post


Link to post
Share on other sites
On 7/15/2019 at 10:35 AM, Zakwayda said:

Unless I'm missing something, the above is for a binary tree, but DividedByZero is working with a general tree. (The discussion of recursive traversal is of course relevant either way though.)

You aren't, I only mentioned it because the way I've seen a scenegraph constructed was as a tree, where the OP is just using a vector and iterating it in a seemingly inefficient manner which also seems error prone as it is not working how they want it to. Like anything else, there are a million ways to skin this cat, maybe not literally, but that's what I would lean towards because it's a proven way to accomplish the task at hand.

Share this post


Link to post
Share on other sites
On 7/15/2019 at 4:35 AM, chatch1111 said:

You really ought to take a look at depth first search preorder traversal. Essentially, you'll just start at the initial parent node, then print in cascading fashion all of that "parents" descendants, then recurse or iterate to the next parent and so on.

Essentially, you are going to want to have a pointer to each nodes child left and right, then you can use a recursive call to consume the data (print or whatever task you are trying to accomplish from the scenegraph) call left, print, right.

dfs(SceneNode* head) {

     if(head == nullptr)

    //exit condition usually return if function is void

     dfs(head->left);

     //task to be completed

     dfs(head->right);
}

Also note that this is not a pre-order traversal, but an in-order one.

Share this post


Link to post
Share on other sites
4 minutes ago, _Silence_ said:

Also note that this is not a pre-order traversal, but an in-order one.

Can confirm.. all nighter posting clearly I should stay away from

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • 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!