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

You usually have a list o child nodes in every node so this is a simple recursive iteration

MyFunc [Node root]
  PRINT root
  FOR EVERY Node child IN root -> Children DO
    PRINT child
    CALL MyFunc [child]

in pseudo code

Thanks.

Just having a tough time working it out in practise.

In fairness, recursion is not that simple if you haven't seen it before. I'm going to assume OP has not formally studied comp sci (that's not a knock - it's just that traditional comp sci teaches recursion fairly early on, the later builds on the basics to teach data structures and algorithms that are implemented using recursion. It becomes more intuitive once you've been exposed to it). If that's the case, this might help: https://medium.com/code-zen/recursion-demystified-24867f045c62

There are lots of places to learn about recursion, and any developer (gamedev or otherwise) would be well-served to learn it and learn how to apply it. Hope this helps.

@masskonfuzion Yes you are right, I haven't formally studied computer science. I am completely self taught. My formal qualification is in electronics (but that was completed in the mid 90's. Time flies).

Thank you for the link. I will take a look right away.

I have made some progress (sort of).

I can input the name of the parent I want to list the hierarchy for and it does display the children through to the end, which is great.

But, if there is more than one child at a given point it will just list the first one and then grab its first child and so on.

void	Graphics::SceneNodeTreeList(std::string name)
{
	std::string szChild = "";

	for (std::vector<SceneNode>::iterator it = sceneNodeVector.begin(); it != sceneNodeVector.end(); ++it)
	{
		if (it->name == name)
		{
			std::cout << it->name << "\r\n";

			label:
			
			for (std::vector<std::string>::iterator it2 = it->childVector.begin(); it2 != it->childVector.end(); ++it2)
			{
				// loop through immediate children
				szChild = "";
				for (unsigned n = 0; n < it2->size(); ++n)
					szChild += it2->at(n);
				std::cout << szChild << "\r\n";

				// Does this have child and so on?
				for (std::vector<SceneNode>::iterator it3 = sceneNodeVector.begin(); it3 != sceneNodeVector.end(); ++it3)
				{
					if (it3->name == szChild)
					{
						it = it3;
						goto label;			// Nasty, I know.
					}
				}

				// Never makes it here due to goto statement
			}
		}
	}
}

As I said, works fine if there is only ever once child at any given point, but skips past any subsequent child at that node.

Probably more of a logic issue I have here, but if anyone can give any suggestions that would be awesome.

Thanks again

A simple way to get used to recursion is to see each level as a seperate data structure with its own class functions, and so on. Thus at top level you have "class NodeLevel1" and function "visit_level_1". At the sub-level you have "class NodeLevel2" and function "visit_level_2", and so one.

Then you can just write code as usual, creating the right sub-structure and calling the right next level functions.

If you do that for 2-3 levels, you will notice that all code is exactly the same, except for the level numbering. At that point you realize you simply merge all the data structures and functions onto a generic "class Node" and function "visit", introducing the recursive calls.

53 minutes ago, DividedByZero said:

I have made some progress (sort of).

I can input the name of the parent I want to list the hierarchy for and it does display the children through to the end, which is great.

But, if there is more than one child at a given point it will just list the first one and then grab its first child and so on.

void	Graphics::SceneNodeTreeList(std::string name)
{
	std::string szChild = "";

	for (std::vector<SceneNode>::iterator it = sceneNodeVector.begin(); it != sceneNodeVector.end(); ++it)
	{
		if (it->name == name)
		{
			std::cout << it->name << "\r\n";

			label:
			
			for (std::vector<std::string>::iterator it2 = it->childVector.begin(); it2 != it->childVector.end(); ++it2)
			{
				// loop through immediate children
				szChild = "";
				for (unsigned n = 0; n < it2->size(); ++n)
					szChild += it2->at(n);
				std::cout << szChild << "\r\n";

				// Does this have child and so on?
				for (std::vector<SceneNode>::iterator it3 = sceneNodeVector.begin(); it3 != sceneNodeVector.end(); ++it3)
				{
					if (it3->name == szChild)
					{
						it = it3;
						goto label;			// Nasty, I know.
					}
				}

				// Never makes it here due to goto statement
			}
		}
	}
}

 

As I said, works fine if there is only ever once child at any given point, but skips past any subsequent child at that node.

Probably more of a logic issue I have here, but if anyone can give any suggestions that would be awesome.

Thanks again

 

There are some style and performance issues there, but I'll skip those as they'd be a bit off topic. I'll mention some things though that might make the code easier to read and understand:

- You might look into the 'auto' keyword. Among other things, it'd make your 'for' loops less verbose.

- Further, you might also look into range-based for loops, which can make these sorts of loops simpler still.

- Unless I'm misreading, this bit:

for (unsigned n = 0; n < it2->size(); ++n)
    szChild += it2->at(n);

Appears to be adding one std::string instance to another. You should be able to do that more concisely and expressively using e.g. operator+=().

- I won't advise against using 'goto', as I don't want to create controversy. This sort of thing can certainly be implemented without it though, so I'd question whether it's really needed here.

- You may have a reason for storing all the nodes in a single vector and referencing children by name, but I'll just point out that you could instead reference children by pointer (in one form or another), which would eliminate the 'name lookup' step and might simplify the code. This would introduce some additional considerations, such as ownership, lifetime, pointer invalidation, and so on. But, it is an alternative to consider.

Beyond that, it might be worth starting with a recursive implementation, as Alberth was talking about. Once implemented, you could just stick with the recursive version if the trees aren't too deep, but regardless it might be a good starting point, as it can provide insight as to what other implementations (e.g. iterative) might look like.

Thanks again, guys. Will certainly need to look into all of this.

And FWIW, I have previously never used 'goto' in my life - haha! Was just the easy way out at present to get something semi-workable.

You can usually have anything with Goto be done in more readable code because goto often creates loops that are hard to maintain and even harder to debug. Some utility like stack trace dosen't work correctly with goto because you technically never leaved the function.

Goto however has still some usecases, LZ4 for example is implemented using goto to achieve some performance impacts