I'm a bit confused as to how to semi-efficiently traverse a behavior tree.

At each think tick I traverse the tree depth first, until I hit an action that take time (lets call that a latent action, such as a MoveTo). On the next tick do I traverse the tree again (after the latent action has started but not finished), hit the latent action and tick it forward? What if I had a bunch of latent actions in a sequence come before my current latent action, I would not want to execute them again before I get to the action I left off on.

Is it that when you reach a latent action, that you queue this action up and go directly back to it instead of performing a tree traversal. But then how would parallels fit in? Is it that a parallel branch gets completely frozen by a latent action while its running, while the other branches keep on getting all their children ticked?

Sorry if I'm not making much sense, just trying to get a sense of how a tree traversal would work.

If you have a tree without parallel nodes, then you only need to store a single pointer to "cache" a node and just update that. Otherwise you need a more fully featured event-driven BT implementation.

See more here, I did a 1h presentation on the topic of BTs, starting simple and then moving into second-gen trees (such as the event-driven ones):
http://aigamedev.com/insider/tutorial/second-generation-bt/

Alex

Ok I have now watched that video (great of you to share), you start talking about event driven trees at around 36:14. I'm still not clear on event driven BTs though.

Is this the jist? If i hit a latent action (which would be a leaf node in your description). During the next tick of the BT, all i have to do is check if that latent action has completed. When it does complete, continue traversing the BT from where we left off when we had reached that action.

Where I am still getting confused is that if you didnt do this, and traversed the tree from the root. You might have gotten to a completely different latent action than when you traversed it the last tick, because conditions might have changed.

Is this now where parallels come in? If there are any conditions that should stop a latent action they must be contained in a parallely executed branch? To me this (if this is true) make parallels absolutely necessary for all but the simplest trees. For example if I am moving from A to B (in a latent action) and in the middle of that i spot the player, now i want to go into attack mode. It would seem you would need a parallel to do that.

Where I am also confused is if you do use parallels for bailing on a action, how does all this event driven stuff fit in. If you hit a latent action, then on the next tick you must check if that action is still executing AND traverse any part of the tree that could be happening in parallel. What is a good way for accomplishing that? When ever you hit a parallel, that subtree must be ticked at the next update as well as any parallel running latent actions? So now you have a queue of things to traverse per tick that can include latent actions as well as any parallel subtree branches?

I explained this in the talk briefly, but the best way to think about event-driven BTs is functionally equivalent to the other types of BTs. If your BT checks every condition on the way down the tree, then you need to do that also in your event driven approach. My BT implementation does not re-check all conditions at every traversal, we simply jump back to the point where we were at -- traversing from the root or not is up to you. If you want to re-check conditions, then you run those in a parallel node. I call those monitored behaviors that are periodically re-checked to make sure assumptions are not broken.

If you hit a latent action, then on the next tick you must check if that action is still executing AND traverse any part of the tree that could be happening in parallel. What is a good way for accomplishing that?

The core of an event driven implementation is a "scheduler" style class that stores active behaviors. At any point in time, in your behavior scheduler, you have one or more active behaviors -- which are almost always leaf nodes. The scheduler also keeps track of dormant/suspended nodes that traverse down to the leaves, but you don't always need to update those. Each tick you basically tick all leaf nodes... These leaf nodes could be conditions up in the tree that you want to re-check periodically as monitors, or an action low down in the tree.

As these behaviors are ticked, you basically propagate the result to its parent. The whole implementation of the tree update is done inside out. You can't resume as normal, you do the whole thing event driven!


I hope that makes sense. As I said, it's easier to start not event-driven, and then change your implementation later once you're comfortable with it, and make it 100% backward compatible.

Alex

One thing that has confused be about non-event driven behavior trees (traversing from the tree root every tick) is the problem of re-executing latent actions that may have led to my currently running latent action.

What I mean is that if I have a sequence whose children are all latent actions A, B, and C. And say that I have hit C and am in the middle of executing C, during the next tick i would have to go through A and B to get to C. That doesn't seem practical, in that A and B have already been performed (say they were two move commands), how do I get around that? Do I somehow mark that they have already have been executed, and not execute them again, how would that extend to other situations like that (e.g. B is a selector that has a child latent action?

during the next tick i would have to go through A and B to get to C. That doesn't seem practical

Hehe, did you watch the first part of the presentation too or did you jump straight to [color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]36:14? ;-)[/background]

[/font]

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]There's a member variable called m_CurrentChild in Sequences and Selectors that points to the currently active child. If a failure or success happens, the node deals with it. Traversing from the root to find the active node doesn't mean traversing from the very start every time![/background]

[/font]

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

[background=rgb(250, 251, 252)]Alex[/background]

[/font]

I did watch the rest of it, just apparently misunderstood. Say I had this tree:
-Sequence
---Condition
---MoveToA
---MoveToB

Say I am executing the second latent action MoveToB. On the next tick (non event driven BT) I start from root again. What prevents me from executing MoveToA before getting back to MoveToB? Im sure this just a fundamental misunderstanding I am having.

Even if i distinguished between looped sequences and non-looped sequences, i would still hit this. Is it just that MoveToA after having been executed once will then return true the next time i hit it and not execute? What would cause MoveToA to reset (from not executing) so that i might execute it later if I am looping that tree?

Thanks for your patience so far.

Ah, is it that the parent sequence node remembers its last RUNNING node, and when revised (the parent node that is) it chooses the the child node that was last running to tick?

Ah, is it that the parent sequence node remembers its last RUNNING node, and when revised (the parent node that is) it chooses the the child node that was last running to tick?

Yes, that's what m_CurrentChild points to. You can just get the active child of a Sequence and Selector that way.

Alex