🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to General and Gameplay Programming

Vector question

DividedByZero · 2019-07-16T21:07:09

Hi Guys, I am in the process of making a basic parenting system and all is going well so far. I have an initial vector of SceneNode's class SceneNode { public: std::string name; std::vector <std::string> childVector; }; And am able to populate a basic tree. So in my test case I have this. Parent Child1 GrandChild Child2 If I query the Parent (like below) for (std::vector<SceneNode>::iterator it = sceneNodeVector.begin(); it != sceneNodeVector.end(); ++it) { if (it->name == name) { std::cout << it->name << "\r\n"; // List immediate children for (std::vector<std::string>::iterator it2 = it->childVector.begin(); it2 != it->childVector.end(); ++it2) { std::cout << "\t"; for (unsigned n = 0; n < it2->size(); ++n) std::cout << it2->at(n); std::cout << "\r\n"; // How do I get the children of the children and so on? } } } It displays this (which is a good start) Parent Child1 Child2 But how would I go about coding this so it will display all children of the children, right down to the last level? Any help would be greatly appreciated. Thanks in advance :)

General and Gameplay Programming Programming C++

Started by DividedByZero July 12, 2019 10:41 AM

14 comments, last by chatch1111 4 years, 11 months ago

chatch1111

July 15, 2019 08:35 AM

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

ChrisHatch-Resume.doc

Zakwayda

2,389

July 15, 2019 03:35 PM

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

chatch1111

July 16, 2019 07:07 PM

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.

ChrisHatch-Resume.doc

_Silence_

1,076

July 16, 2019 08:58 PM

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.