Jump to content
  • Advertisement

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement

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

Share this post


Link to post
Share on other sites
Posted (edited)

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.

Edited by masskonfuzion
Fixed wording of a thought

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

 

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

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!