Event Driven Behavior Tree: deterministic traversal order with parallel
- by Heisenbug
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:
The result of the traversing should be independent from which implementation strategy is used.
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:
do I have understand correctly how event driven BT work?
How can I guarantee the depth first order is respected with such an implementation?
is this a common issue or am I missing something?
