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
parallelnode, 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
FIFO policy of the scheduler, before
leaf_A node terminates the tasks in the scheduler are:
leaf_B will be scheduled (at the end of the queue), so the queue will become:
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
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?