Behavior Tree update

(A) Does the tree re-evaluate on every tick from its root down to all children until meeting that Action which is found being still in progress and having it execute a bit further?

This is the best place to start. The tree always has the concept of an "active" Action (one, or more) but it's easiest to traverse from the root to find it. Each selector branch in the tree then knows which decisions it made, each sequence knows which position it's at, and you can easily find the active Actions.

If you insert a parallel into the mix, it's just as easy, except you start two sub-traversals from then onwards. (Note that parallels are not often used in commercial games yet.)

(B) Or does the tree somehow "remember" what its last Task was that hasn't finished yet and simply continues with that task on next tick?

Once you have (A) working, use that as your fixed specification and find ways to optimize it without breaking or changing the behavior. You'll probably find you can implement an event-driven implementation that doesn't need to tick from the root, and instead can just maintain an active list of behaviors and propagate changes around only if things change.

This type of implementation is my favorite, but you might not need it. Performance of type (A) of BT is probably going to be good enough, especially if you optimize the memory usage a bit.


Alex

Thanks for the hints, Alex. The thing about events would have been my next question: How could the BT pointfully stop a specific Action that reports to be be "still_running" and notifying it of getting stopped? I think a classic example would be a character being able patrol and to fight an enemy. I'm considering a simple BT like this:


[html] (?)
/\
/ \
/ \
/ \
[->] [A:Patrol]
/\
/ \
/ \
/ \
[C:HasEnemy] [A:Fight]


NB:
(?) = selector
[->] = sequence
[C: ...] = condition
[A: ...] = action
[/html]

Then, to have the Patrol Action no longer run when an enemies comes by, the tree might have to be changed a bit (notice that the order of the sub-trees is now swapped!) :

[html] (?)
/ \
/ \
/ \
/ \
/ \
/ \
[->] [->]
/\ /\
/ \ / \
/ \ / \
/ \ / \
[A:Patrol] [C:HasEnemy] [A:Fight]
|
|
[C:HasEnemy]


NB:
= Inverter Decorator
[/html]

And this is where my understanding of BTs starts lacking: Is it correct that the Patrol Action would then simply no longer be updated (no matter of the status it reports on every tick) without ever giving it the chance to "shut down in a controlled manner"? I can sense that I could add even more nodes in the BT to somehow help the Patrol Action getting notified or even executing a completely new Action, which could deal with the "shutdown of the Patrol behavior" - kind of a "helper Action" for "the real Action". The more I think in that direction the more I get the feeling that the BT can easily become overbloated and thus getting more and more lost in details.

And this is where my understanding of BTs starts lacking: Is it correct that the Patrol Action would then simply no longer be updated (no matter of the status it reports on every tick) without ever giving it the chance to "shut down in a controlled manner"? I can sense that I could add even more nodes in the BT to somehow help the Patrol Action getting notified or even executing a completely new Action, which could deal with the "shutdown of the Patrol behavior" - kind of a "helper Action" for "the real Action". The more I think in that direction the more I get the feeling that the BT can easily become overbloated and thus getting more and more lost in details.

I solved this by adding an optional activate and deactivate function for each node. Whenever you activate a new node, you call the activate funciton, you switch a path, you first deactivate all nodes of the obsolete path part (back to front order) . In this case you can clean up any action, the lifecycle of a active node is therefore:

activate->update->...->update->deactivate

In your example it could look like

PatrolAction:
- activate: print("starting partrolling")
- update: print("still patrolling ...")
- deactivate: print("stopped patrolling")

FightAction:
- activate: print("starting fighting")
- update: print("still fighting...")
- deactivate: print("stopped fighting")


Swtiching from patroling to fighting branch would look like:

starting partrolling
still patrolling ...
still patrolling ...
still patrolling ...
>> event which switched to fight branch
stopped patrolling
starting fighting
still fighting..
still fighting..
still fighting..
>> enemy killed, switching back to patrolling branch
stopped fighting
starting partrolling
still patrolling ...
still patrolling ...
...


That's an interesting idea, Ashaman. Do you also have any mechanism that kicks in once a particular node is no longer being visited?

Elaborating on Alex' idea:

On a per-tick basis, we could keep track of all nodes being visitied in an "active list" and assign them the current tick-counter. Everytime a node gets visited, its tick-counter gets updated (so that it reflects the global tick-counter). After a traversal of the tree is finished, we compare the tick-counters of all nodes in the active list with the global tick-counter. If we find that some nodes of the active list contain tick-counters of the past, we then know that these nodes haven't been visited in the last tick and could explicitly give them the chance to clean up.

Just some quick thoughts. And I suppose this idea may introduce some undesired side-effects, e. g. when a new node is getting control before no-longer-active nodes start their cleanup process (like starting a new animation, then stopping the old one on the same animator).


Greetings,
Shadax

That's an interesting idea, Ashaman. Do you also have any mechanism that kicks in once a particular node is no longer being visited?

These are the basic features of my bht implementation:
1. every node has a accept, acitvate, update, deactivate function:
accept: a quick test if all requirements are met to activate a node.
activate: once accepted, it will be activated once
update: update the nodes with three results: null => keep updating, true => node proccessing finished and succeed, false => node processing aborted/failure
deactivate: clean up once you stop updating a node
2. I keep track of the active path. All group nodes (priority, sequence, selection etc.) always consider the active path and try to keep on the current path.

A simple example bht:

root(priority)
- scan_for_enemy(sequence)
-- move_to_enemy(action)
-- attack_enemy(action)
- find_next_patrol_point(sequence)
-- move_to_patrol_point(action)
-- look_around(action)

The priority node takes the first node which accepts or the one on the active path. The sequence nodes update the node on the active path until it returns true(continue with next node) or false(abort sequence).

Here's an exmaple of the acitve path over time:

// AI started, no enemy around
root-> find_next_patrol_point->move_to_patrol_point
// after finishing the move_to_patrol_point(result=true), the next node will be taken
root-> find_next_patrol_point->look_around
//the look around action will stop after 1 minute, the AI will "start" again
root-> find_next_patrol_point->move_to_patrol_point
// an enemy comes in sign, the scan_for_enemy node accepts,
// this results in a abort of the "-> find_next_patrol_point->move_to_patrol_point" (calling deactivate on the nodes)
// and starting a new path:
root-> scan_for_enemy->move_to_enemy
// enemy has been reached resulting in stopping of the move_to_enemy action(result=true)
root-> scan_for_enemy->move_to_enemy->attack_enemy
// enemy has been killed resulting in stopping of the attack_enemy action(result=true), the AI will "start" again with the patrolling "path"
root-> find_next_patrol_point->move_to_patrol_point


Sorry for the late reply. Just to get this right: so, in your BT you always have no more than 1 active leaf-node and keep track of it ? And you continuously re-evaluate the whole tree on every simualtion tick? And when a different node eventually becomes active, you disable the old current node (and all its parents up to the root of the tree) and switch execution control to the new node?

I'm not sure about my above assumption when it's about Parallels. I'd assume that a leaf-node would no longer be marked as the active one, but rather the Parallel then, right?

Sorry for the late reply. Just to get this right: so, in your BT you always have no more than 1 active leaf-node and keep track of it ? And you continuously re-evaluate the whole tree on every simualtion tick? And when a different node eventually becomes active, you disable the old current node (and all its parents up to the root of the tree) and switch execution control to the new node?

Yes, the basic idea is right. The re-evaluation of the whole tree is not necessary. Only nodes on the path are re-evaluated and other nodes which are child to a priority node on the path. The disabling of the old nodes is only necessary up to the node where the new path will branch of.

I'm not sure about my above assumption when it's about Parallels. I'd assume that a leaf-node would no longer be marked as the active one, but rather the Parallel then, right?

Parallels are an issue. To solve it I allow only one standard and several "stateless" parallel nodes, that is the stateless nodes will be re-evaluated completly each tick and should be of simple structure to avoid an unnecessary performance impact.

That's an interesting idea, Ashaman. Do you also have any mechanism that kicks in once a particular node is no longer being visited?

Elaborating on Alex' idea:

On a per-tick basis, we could keep track of all nodes being visitied in an "active list" and assign them the current tick-counter. Everytime a node gets visited, its tick-counter gets updated (so that it reflects the global tick-counter). After a traversal of the tree is finished, we compare the tick-counters of all nodes in the active list with the global tick-counter. If we find that some nodes of the active list contain tick-counters of the past, we then know that these nodes haven't been visited in the last tick and could explicitly give them the chance to clean up.

Just some quick thoughts. And I suppose this idea may introduce some undesired side-effects, e. g. when a new node is getting control before no-longer-active nodes start their cleanup process (like starting a new animation, then stopping the old one on the same animator).


Greetings,
Shadax

This could also be resolved via the use of a counter / wait decorator containing the tree branch you want to process periodically. The decorator just returns a Return Code of "Running" while waiting/counting and "Success" or "Failure" when it isnt waiting/counting depending on what the child returns to it. This would easily allow all sorts of differing wait-like conditions across your BT. Counter would be based on a cycle count and wait could be based on time elapsed from a game time global.

Would that resolve your concern?

Hello,

I think my concern was that I saw problems where there shouldn't be any. Call it lack of experience. Alex and Ashaman73 were right, there's basically always one active node that gets processed frame per frame until it finishes (with success or failure). When something in the world happens, then that active node gets asked if it can handle the event. If it can't, there might be another node in the tree that can. In that case, the so-far-active node gets cancelled by some manager (usually by the containing tree structure itself), and then starts the new node. Passing control to another node follows a clean sequence ("sequence" here is not meant in terms of a "sequence node" of the BT): (1) ask a potential candidate to take over control. If it accepts, then (2) shut down the old node and (3) start the new node and then (4) keep updating the then-active node until it finishes or a new event occurs that it can't handle.

NB: I wasn't accustomed to the term "priority selector" in Ashaman73's sample, but having read that Spore article on the net, I can now see the difference between a *simple selector* and a *priority selector* wheres the latter one is always re-evaulated until it hits the currently active path on each frame.

Please correct me if I'm wrong (or tell me whether I'm right).


Greetings,
Shadax