• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Alundra

[c++] non-recursive way to iterate tree

14 posts in this topic

Hi all,

Imagine a scene manager who has a root node with children, so it's a tree.

One way is to iterate the tree using recursivity, but perf is not the best.

An alternative is to use a similare code to a showed code in the wxWidgets documentation :

wxTreeItemId FindItemNamed(wxTreeCtrl &tree, const std::wstring &name)
{
	std::stack<wxTreeItemId> items;
	if (tree->GetRootItem().IsOk())
		items.push(tree->GetRootItem());
 
	while (!items.empty())
	{
		wxTreeItemId next = items.top();
		items.pop();
 
		if (next != tree->GetRootItem() && tree->GetItemText(next) == name)
			return next;
 
		wxTreeItemIdValue cookie;
		wxTreeItemId nextChild = tree->GetFirstChild(next, cookie);
		while (nextChild.IsOk())
		{
			items.push(nextChild);
			nextChild = tree->GetNextSibling(nextChild);
		}
	}
 
	return wxTreeItemId();
} 

 

Is this method a good way to handle a tree ?

Thanks

Edited by Alundra
1

Share this post


Link to post
Share on other sites

This is simply a breadth-first search. It may be breadth-first for multiple reasons.

1. It avoids recursion that leads to stack overflow.

2. It finds the closest node to the root matching the supplied name, which seems to be what would be most useful.

1

Share this post


Link to post
Share on other sites

I have always listen that recursion is slow because of the cache miss.

For a QuickSort algorithm the solution is to have a MaxLevel variables en switch to InsertionSort if MaxLevel is reached.

For a a scene tree the best solution is to use recursion ?

0

Share this post


Link to post
Share on other sites

I have always listen that recursion is slow because of the cache miss.

No, "recursion is slow" is a false statement. There are situations where recursion might be slow, and then it has nothing to do with cache misses.

For a QuickSort algorithm the solution is to have a MaxLevel variables en switch to InsertionSort if MaxLevel is reached.

That's a solution to a specific problem of QuickSort, and not to a general problem with recursion.

For a a scene tree the best solution is to use recursion ?

Best solution to what?
0

Share this post


Link to post
Share on other sites

Best solution to what?

To traverse the tree for saving the scene, find an object by name or pointer, update each object and render the scene.

Edited by Alundra
0

Share this post


Link to post
Share on other sites

Write your code to be clear. If performance is a problem, use a profiler to see where the time is going. After that, if you find that traversing the tree is actually a performance bottleneck, then you can worry about this.

1

Share this post


Link to post
Share on other sites

That method is functionally identical to recursion, the only difference being that you have to manually manage your own stack, rather than using the machine stack.

 

At best, any speedup will be minimal - the time complexity is still linear in relation to the number of nodes in the tree.

 

What makes you think that recursion is too slow?

 

It might be worthwhile to mention that the heap usually is a lot bigger than the stack which alows for deeper traversal so both solutions are not exactly identical.

It is very likely that this won't be a limiting factor though.

 

 

About performance:

Always profile and benchmark.

If it's not too slow you don't have to care.

Otherwise it might be possible that std::stack is implemented as some kind of list with nodes allocated one by one which might lead to more cache misses than a contiguous block of stack memory which the recursive version would use.

0

Share this post


Link to post
Share on other sites

To traverse the tree for saving the scene, find an object by name or pointer, update each object and render the scene.

If you want to avoid cache misses when traversing a tree, then make sure that the tree's elements are stored contiguously in memory, in the order that they will be traversed. That way, it's the same as iterating through a linear array.

 

If the operation that you need to perform is "for each object", then you shouldn't even be using a tree in the first place, you should just have an array.

 

If the operation is "find object by name", then you want a hash map from names to object-pointers.

1

Share this post


Link to post
Share on other sites

Otherwise it might be possible that std::stack is implemented as some kind of list with nodes allocated one by one which might lead to more cache misses than a contiguous block of stack memory which the recursive version would use.

 

I don't think that can happen: By default std::stack uses std::deque as its underlying container (std::stack is not a container, but a container adaptor). There are multiple possible implementations of std::deque, but they won't be one-node-per-item implementations because of the performance guarantees (O(1) random access iterators).

0

Share this post


Link to post
Share on other sites
It's possible to get a one node per item deque implementation with a dynamic array containing pointers to the individual nodes, which gives you the constant time random access. Some standard library implementations have an N item per node implementation where N shrinks as sizeof(T) increases, which degenerates to N equals one after a point. IIRC, at least some versions of MSVC's standard library implementation work this way.
1

Share this post


Link to post
Share on other sites

Oh sorry, it would be a breadth-first search, if the items were going in one end of the data structure and out the other end.

On second examination, this does not appear to be the case.

0

Share this post


Link to post
Share on other sites

For a a scene tree the best solution is to use recursion ?

Usually a world has multiple data structures involved.

 

A scene or level or world is usually going to be used for many frequent searches and lookups.  Queries are both for existence and also for position. There will be frequent changes to objects in the world.

 

 

 

Generally there is a hash table containing all the objects.  The hash should be a guid assigned to each object.  This is generally the master list.

 

There is also generally a spatial tree, such as a loose quadtree, that indicates where the guid lives in the world.  When an object's position is updated this spatial tree needs to also get updated.

 

There may be yet another graph, called the scene graph, used for display.  Quite likely this graph is not part of the game world since it is part of the renderer's responsibility, not world management's responsibility.

Edited by frob
0

Share this post


Link to post
Share on other sites

Do you mean to have a root node and have children in it and have with that an array of SceneObject who is just all objects ?

Use the recursion to save/load and the array for other operations ?

0

Share this post


Link to post
Share on other sites

Do you mean to have a root node and have children in it and have with that an array of SceneObject who is just all objects ?

The idea is that you don't use a single data structure for everything. Many old engines tried to put absolutely everything into a "scene graph" (one graph to rule them all), which was a massive tree with a root node like you're describing, but that's a really bad idea. Data that's used for different purposes should be stored in different ways.
 

struct TransformNode
{
	Mat44 local;
	Mat44 global;
	vector<TransformNode*> children;
};

struct BoundingSphere
{
	Vec3 position;
	float radius;
};

struct Actor
{
	TransformNode* transform;
	BoundingSphere* sphere;
	Mesh* mesh;
	Material* material;
};

struct Scene
{
	TransformNode* rootTransform;//tree of data
	vector<BoundingSphere> spheres;//array of data
	list<Actor> actors;//linked list of data, pointers into the above array and tree
};
Edited by Hodgman
0

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
Sign in to follow this  
Followers 0