Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a tree of gameobjects, so every node contains a list of children. In update function: Is it better to do recursive or linear walking through game objects.


update() { 
    update self;
    foreach child call update;//recursive call
}

or


array of children = root.getAllChildrenRecursive
foreach child in array of children call update; //linear walking through gameobjects.
share|improve this question
1  
As is often the answer: It depends. Pick what works for you. Having chosen linear updating for my game, I can update all input components at once, then all AI components at once, then most other components. –  Jonathan Hobbs Aug 22 '12 at 11:08
    
Assuming that both of these variants are being called on each update, the second one is worse than the first one, because you recursively traverse your tree to get all children and you need to create a container that holds them every update... If you really want to have linear updates, you should have hooks that register adding and removal of children and add/remove them to your data-structure at this time. Eg. Remove/add children to the array when they are actually being added and removed, not build that structure for every update. –  bummzack Aug 22 '12 at 13:39
    
bummzack: great comment, I have seen that approach to store gameobjects in array when they are added. I will do so too, only one difficulty in syncing that containers but this approach I liked most of all. –  bobenko Aug 22 '12 at 19:42
add comment

4 Answers

up vote 7 down vote accepted

If you only have a few gameobjects it doesn't really matter. But if you are planning support for lots of gameobjects, I suggest you take at look at the following question:

Game engine and data driven design

And continue to read the following article (originally printed in Game Developer):

Data-Oriented Design (Or Why You Might Be Shooting Yourself in The Foot With OOP)

Another thing you should consider is if your scene hierarchy is the most efficient/flexible/maintainable. I suggest you read the following blog about component based game engine:

Evolve Your Hierarchy

And maybe continue reading this excellent Q/A:

Component based game engine design

... but before you start on spending a huge amount of time trying to create the perfect game engine remember that "premature optimization is the root of all evil". Always use a profiler to see where the bottle neck is in your game / game engine.

share|improve this answer
    
+1. Isn't the concept actually called Data Oriented Design? As I read just a few articles on the approach, isn't it built on the idea of not breaking the cache as an almost central and religious law? –  teodron Aug 22 '12 at 16:22
    
Yes - I have added a good article originally printed in Game Developer. I agree that data oriented design can be too extreme for some usages but for others it is a must (a particle engine is a good use-case for data oriented design) –  Mortennobel Aug 22 '12 at 19:51
    
I have already implemented component-based system, but thanks for feedback. I know there is a lot of articles about profiling but maybe there is some that you liked much. –  bobenko Aug 22 '12 at 21:13
    
Profiling tools are very platform specific. In general you should use a tool use sampling or instrumentations (in other words you should not make any changes to your code yourself - let the profiler do the work). –  Mortennobel Aug 22 '12 at 21:24
add comment

IMHO: If you are programming some real-time application, you should avoid recursion if it's possible. Recursion has to push and pull curent context and it's slowing down your app. It's also more memory complex.

Of course if you have just few objects, it's not so dramatic. But when you will add more and more objects in future, it will be slower and slower.

You can read something about it in this article on wikipedia.

share|improve this answer
add comment

Recursion and depth-first traversal are not the same thing.

This is also not about the merits of scene graph versus lists of components or whatever. It's also more of a general computer science issue than it is a gamedev issue.

Bummzack's comment about how wasteful it is to create a whole new list is extremely important. You need to traverse your tree in-place where it sits, not pull some list out of it as though it were a database. There are two general methods for doing this: recursion and iteration.

In general, iterative is faster than recursive unless you are working in a language with tail call optimization, but you should still write code in the most intuitive way possible. If you're dealing with a tree of objects, often the most intuitive approach for traversal is a recursive solution.

However, be sure to mark this as a potential trouble spot, (ie: // TODO PERFORMANCE Keep an eye on performance for this traversal). If you find it's slowing the game down, consider changing to an iterative traversal method.

It's about something like this:

void ProcessTree(Node root)
{
    PreProcess(root);
    foreach (var child in root.children) {
        ProcessTree(child);
    }
    PostProcess(root);
}

versus something like this:

void ProcessTree(Node root)
{
    Stack<Node> traversalStack = new Stack<Node>();
    traversalStack.push(root);
    while (!traversalStack.isEmpty {
        var current = traversalStack.peek();
        if (!current.preProcessedAlready) {
            PreProcess(current);
        }

        if (current.hasChild) {
            current = current.firstChild;
            traversalStack.push(current);
            continue;
        } else if (current.hasSibling) {
            PostProcess(current);
            traversalStack.pop()
            current = current.nextSibling;
            traversalStack.push(current);
            continue;
        } else {
            PostProcess(current);
            traversalStack.pop();
            current = traversalStack.pop();
            while (!traversalStack.isEmpty) {
                if (current.hasNextSibling) {
                    traversalStack.push(current.nextSibling)
                    break;
                } else {
                    current = traversalStack.pop();
                    PostProcess(current);
                }
            }
        }
    }
}

The difference is you keep allocating a whole new stack frame for visitation, versus just adding a small stack node, which you can cache by pooling the stack nodes or just figuring out the maximum depth of your tree.

I'm pretty sure I screwed up the iterative example logically and in terms of efficient code flow, so please edit/comment with fixes. Wikipedia has a good article on tree traversal for better examples (most seem to be binary trees unfortunately). There's also a way to avoid using a stack if you maintain some extra pointers in the Node object as per this StackOverflow answer.

Do the easy thing (recursion, or occasionally iteration, depending on the problem) first and build something more robust or performant as you need it, but also don't 100% depend on your method, be willing and able to switch if it's called for. I ran into this issue on Unity recently. Our tree by necessity had much more depth than breadth, so the iterative method cut out 4 seconds of loading time (for our data and our processing, NOT A BENCHMARK) compared to recursive.

share|improve this answer
    
Great, thanks for feedback, what unity are you talking about? Unity3d? if Unity3d can you suggest have they have implemented it, as I suppost they use iterative. So you have written about 4 seconds, is it possible to switch between this two methods in Unity? –  bobenko Aug 23 '12 at 16:48
    
You switch methods by changing what code you use to traverse your data structure. It's not some switch you flip. I was working in Unity3d when I ran into this, but it doesn't have anything to do with Unity's transform hierarchy. It's the Mono VM's (Unity's scripting engine) performance for deeper-than-average recursion. We were maintaining our own tree of data unrelated to to Unity's transform hierarchy. The 4 seconds was specific to our data's structure and what we were doing to process it, it is not a benchmark. Use recursion like bummzack suggested until you run into performance problems. –  michael.bartnett Aug 23 '12 at 17:30
add comment

Go with linear, as it's easier to follow and iterate through objects than it does adding more to a stack and unwind. If the order in which the gameobjects are updated is not very crucial to the behavior and interaction between, linearly updating would be all you'd need. It all depends on how strongly coupled the objects' behaviors are on each other.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.