Event Driven Behavior Tree: deterministic traversal order with parallel

Posted by Heisenbug on Game Development See other posts from Game Development or by Heisenbug
Published on 2014-08-22T14:12:45Z Indexed on 2014/08/22 16:37 UTC
Read the original article Hit count: 272

Filed under:
|
|
|

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?

© Game Development or respective owner

Related posts about ai

Related posts about events