3
\$\begingroup\$

I've studied several articles and listen some talks about behavior trees (mostly the resources available on AIGameDev by Alex J. Champandard).

I'm particularly interested on event driven behavior trees, but I have still some doubts on how to implement them correctly using a scheduler.

Just a quick recap:

Standard Behavior Tree

  • Each execution tick the tree is traversed from the root in depth-first order
  • The execution order is implicitly expressed by the tree structure. So in the case of behaviors parented to a parallel node, even if both children are executed during the same traversing, the first leaf is always evaluated first.

Event Driven BT

  • During the first traversal the nodes (tasks) are enqueued using a scheduler which is responsible for updating only running ones every update
  • The first traversal implicitly produce a depth-first ordered queue in the scheduler
  • Non leaf nodes stays suspended mostly of the time. When a leaf node terminate(either with success or fail status) the parent (observer) is waked up allowing the tree traversing to continue and new tasks will be enqueued in the scheduler
  • Without parallel nodes in the tree there will be up to 1 task running in the scheduler
  • Without parallel nodes, the tasks in the queue(excluding dynamic priority implementation) will be always ordered in a depth-first order (is this right?)

Now, from what is my understanding of a possible implementation, there are 2 requirements I think must be respected(I'm not sure though):

Now, some requirements I think needs to be guaranteed by a correct implementation are:

  1. The result of the traversing should be independent from which implementation strategy is used.
  2. The traversing result must be deterministic.

I'm struggling trying to guarantee both in the case of parallel nodes. Here's an example:

Parallel_1
-->Sequence_1 
---->leaf_A
---->leaf_B
-->leaf_C

Considering a FIFO policy of the scheduler, before leaf_A node terminates the tasks in the scheduler are:

P1(suspended),S1(suspended),leaf_A(running),leaf_C(running)

When leaf_A terminate leaf_B will be scheduled (at the end of the queue), so the queue will become:

P1(suspended),S1(suspended),leaf_C(running),leaf_B(running)

In this case leaf_B will be executed after leaf_C at every update, meanwhile with a non event-driven traversing from the root node, the leaf_B will always be evaluated before leaf_A.

So I have a couple of question:

  1. do I have understand correctly how event driven BT work?
  2. How can I guarantee the depth first order is respected with such an implementation?
  3. is this a common issue or am I missing something?
\$\endgroup\$
0
\$\begingroup\$

I'm not sure that I'd call what you describe Event Driven BTs, but then again, driving a BT fully with events is no small feat.

Addressing your specific issue, you're right. If you have a unique scheduler you'll run into ordering issues as you've shown. The answer is to have hierarchical schedulers, to support parallel nodes.

In your example, you'd have three schedulers: one for the root of the tree, one for each of the branches of the parallel node. Each scheduler runs sequentially as you'd expect, only instead of queuing just nodes they can queue other schedulers.

Root: P1(suspended),SCH1(running),SCH2(running)
SCH1: S1(suspended),leaf_A(running)
SCH2: leaf_C(running)

So now when leaf_A transitions into leaf_B, the order will be maintained.

\$\endgroup\$
  • \$\begingroup\$ thanks for your answer. In the meanwhile I succeded in preserving the task order even with a single queue scheduler. The point I was missing it was that (using a single queue) I must always remove task from front and push them back (even if suspended). It seems that the correct order of execution is implicitly guaranteed this way (I have no formal proof though). \$\endgroup\$ – Heisenbug Oct 10 '14 at 10:46
  • \$\begingroup\$ just another question: why do you say "I'm not sure that I'd call what you describe Event Driven BTs"? \$\endgroup\$ – Heisenbug Oct 10 '14 at 10:52
  • \$\begingroup\$ Mostly because your implementation doesn't go into details about how high priority tasks can take over execution, if they are suspended. That's where the event part kicks in, so when the state of the world changes the BT reacts without re-evaluating the whole hierarchy. Doing this in a general way is challenging, and I believe goes beyond just running the leaf tasks. \$\endgroup\$ – Sergio Oct 11 '14 at 2:36
  • \$\begingroup\$ I thought that "when the state of the world changes the BT reacts without re-evaluating the whole hierarchy" was just what I'm supposed to do in an event-driven implementation and what I'm actually doing. Btw I haven't much experience on AI, I guess a discussion with you on chat would be really useful :).. \$\endgroup\$ – Heisenbug Oct 11 '14 at 9:46
  • \$\begingroup\$ The problem is monitoring the state of the world. In a polling implementation, you are constantly reevaluating the tree, so it just works. In an event driven implementation, you need to find a way to "awake" the tree when it's going to change. This won't always be when a task is finished, it can be when something higher priority becomes true. So you have to externalize all those hooks so that the tree (or a subset) is activated as a response to an external event. Doing this in a general way is hard, especially with certain analog conditions, like distance checks. \$\endgroup\$ – Sergio Oct 11 '14 at 15:52
0
\$\begingroup\$

Actually the order of execution in my question was wrong. When a task terminates, if it immediately awake its parent pushing it in front of the queue the depth first order is respected.

Here's how the queue status is supposed to be just after leaf_A task terminates:

S1(running), P1(suspended),leaf_C(running) | [leaf_A(completed)]

When leaf_A terminates it must awake immediately its parent (S1) pushing it in front of the FIFO queue, so it will be executed first.

When it gets executed, will be suspended and it's next child task is scheduled (leaf_B) in front of the queue so, it will be executed before leaf_C as supposed to be:

leaf_B(running), P1(suspended),leaf_C(running), | S1(suspended)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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