Event Driven Behavior Tree: deterministic traversal order with parallel

Question

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?

Answer 1

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.

Answer 2

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)