Comments on: Introduction to Behavior Trees [...] main reference for behavior trees was this blog post by Björn Knafla. I also looked at two articles on how behavior trees were implemented in Spore [...] [...] main reference for behavior trees was this blog post by Björn Knafla. I also looked at two articles on how behavior trees were implemented in Spore [...]

]]>
By: Jim Smart/2011/02/24/introduction-to-behavior-trees/#comment-4696 Jim Smart Sat, 21 May 2011 17:25:14 +0000 ... by the way: awesome article - thanks so much for posting the link to it! … by the way: awesome article – thanks so much for posting the link to it!

]]>
By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-4675 Bjoern Knafla Sat, 21 May 2011 10:03:35 +0000 reference collection on pinboard.

Cheers,
Bjoern

]]>
By: Jim Smart/2011/02/24/introduction-to-behavior-trees/#comment-4654 Jim Smart Fri, 20 May 2011 18:21:37 +0000

Regards,
/Jim

]]>
By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-4021 Bjoern Knafla Sat, 14 May 2011 12:19:45 +0000 For some reason the link got lost on submit: First of all, thank you for the clear writeup. I do like your graphical representation of a BT. I havn't seen Alex videos yet, as I am more comfortable reading. I wonder if anyone has seen this: <a href="http://docs.google.com/viewer?a=v&q=cache:PAwpCAoY380J:www.bungie.net/images/Inside/publications/presentations/publicationsdes/engineering/gdc07.pdf+behaviour+tree+Behavior+Impulses&hl=en&gl=de&pid=bl&srcid=ADGEESgc-oCT_efWwp1YpFNIeQaCwecX-3QIxCZyFmTvTOsezrKsMz8CKnffatPMBnm8hsrOb1lIwC1Z9D8Iuocb5dwIcTGtiZ_DEOsvmQLqRWVO4JbEfQzUxMAhdtPGkt5DssWA95fb&sig=AHIEtbR3qRW1HCzkjJpHLp_1SmTrgg0foQ" rel="nofollow"></a> I am particularly intrigued by the concepts of masks in a BT. It is hard to grasp form the slides alone, but I think it deals with the concept of prioritizing or disabling certain nodes dynamically. I guess this could be realized by having selector nodes reference information and states from a knowledge model. I would love hear some more thoughts on this. First of all, thank you for the clear writeup. I do like your graphical representation of a BT. I havn’t seen Alex videos yet, as I am more comfortable reading.

I wonder if anyone has seen this:

I am particularly intrigued by the concepts of masks in a BT. It is hard to grasp form the slides alone, but I think it deals with the concept of prioritizing or disabling certain nodes dynamically. I guess this could be realized by having selector nodes reference information and states from a knowledge model. I would love hear some more thoughts on this.

]]>
By: Gajan/2011/02/24/introduction-to-behavior-trees/#comment-2606 Gajan Tue, 12 Apr 2011 01:15:19 +0000

Gajan

]]>
By: Gajan/2011/02/24/introduction-to-behavior-trees/#comment-2562 Gajan Mon, 11 Apr 2011 01:18:59 +0000 Thanks, yes it does clear out certain things I had on my mind. I am using the GameBrainAI's behavior tree library code. Currently, it does not have a concurrent node, and hence when a node is in executing/running status, the result is not propagated all the up to the root. Instead they just remember the last executed node(which can only be a single node) and resume directly. But when we use concurrent node, it is nice that you explained the need to send that "running" node status up to the root. I guess originally I wanted parallel node to handle events. But now I am trying out a different way without its requirement. Looking forward to more of your behavior tree series Thanks, yes it does clear out certain things I had on my mind. I am using the GameBrainAI’s behavior tree library code.
Currently, it does not have a concurrent node, and hence when a node is in executing/running status, the result is not propagated all the up to the root. Instead they just remember the last executed node(which can only be a single node) and resume directly. But when we use concurrent node, it is nice that you explained the need to send that “running” node status up to the root.
I guess originally I wanted parallel node to handle events. But now I am trying out a different way without its requirement.
Looking forward to more of your behavior tree series

]]>
By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-2473 Bjoern Knafla Fri, 08 Apr 2011 11:07:56 +0000 The Damian Isla paper is a fantastic motivator for behavior trees - but it doesn't answer many questions that pop when implementing one. I'd advice to read the Isla paper and then search AiGameDev.vom with the search term "behavior tree" for tutorials. Many of them are public. Alex's BT vocabulary is more expressive and more structured than Damian's (in my personal opinion) and he explains the details and the thinking neatly. And, if you are a paying member of AiGameDev.com - then the best sources for understanding BTs are Alex masterclass about "AI BLUEPRINTS FOR ACTION & COMBAT BEHAVIOR TREES" and "DYNAMIC DECISIONS: BUILDING AN AI THAT CAN CHANGE ITS MIND"! The Damian Isla paper is a fantastic motivator for behavior trees – but it doesn’t answer many questions that pop when implementing one.

I’d advice to read the Isla paper and then search AiGameDev.vom with the search term “behavior tree” for tutorials. Many of them are public. Alex’s BT vocabulary is more expressive and more structured than Damian’s (in my personal opinion) and he explains the details and the thinking neatly.

And, if you are a paying member of AiGameDev.com – then the best sources for understanding BTs are Alex masterclass about “AI BLUEPRINTS FOR ACTION & COMBAT BEHAVIOR TREES” and “DYNAMIC DECISIONS: BUILDING AN AI THAT CAN CHANGE ITS MIND”!

]]>
By: Gajan/2011/02/24/introduction-to-behavior-trees/#comment-2467 Gajan Fri, 08 Apr 2011 07:17:48 +0000

Thank you
Gajan

]]>
By: Gajan/2011/02/24/introduction-to-behavior-trees/#comment-2465 Gajan Fri, 08 Apr 2011 01:32:15 +0000
Two purposes :
1. Modeling the reactive behavior of autonomous agents or agent control.
E.g : A vehicle’s state machine (HCSM) is responsible for controlling the position of the vehicle at each step in the simulation. the state machines uses information about the state of the virtual environment to fire state transitions and to set parameters in control laws that determine vehicle motions.

The control subsystem ensures that each state machine is executed on a schedule, typically between ten and sixty times per second, depending on the type and complexity of the vehicle behavior model.

2. Directing such agents to produce desired situations.
To create scenarios they have developed director objects that manage situations by sending instructions to vehicles and traffic lights (their behaviors are modeled as HCSMs)
Directors are HCSMS that behave like daemon processes that monitor the state of an operating system and are activated when circumstances arise that require their services. Directors influence the behavior of scenario entities (cars, traffic lights). This means that Directors itself are modeled as HCSM.
Further , they have developed high-level textual scenario language to author scenarios. Then they translate textual scenario instructions into Hierarchical Concurrent State Machines (HCSMs) which becomes the Directors.
If you are familiar with interactive story telling, then you can think of “Drama Manager” concept which is roughly equivalent to “Directors” in this case.

If I put my question again, can we use behavior trees for developing such “Directors” that influence autonomous agents’ behavior.

I think you have already given some explanation to it. “you could view a BT as a scheduling mechanism for actions”
I think scheduling mechanism is the Directors’ job in the above case. then it make sense to me to use BT in the possibilities to control something.
May be I should think about a hybrid approach
– agent control by HCSM or similar which have the idea about the data they generate and consume as HCSM specifies data-in- and out-slots which will be needed as the interface to communicate with agent with some parameters.
– scenario control by BT as it function as a scheduling mechanism.

In some other related work, they include the scheduling mechanism of actions as part of scenario specification when the action has well defined start and end.

Anyway, I got some ideas from your posts. Thank you very much.

best
Gajan

]]>
By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-2436 Bjoern Knafla Thu, 07 Apr 2011 14:44:23 +0000 That's how I think about it, too. Though your last sentence isn't bullet proof - you only reach a certain child of a sequence if all the earlier sequence children succeeded (which can happen during one update). I'd reformulate it to state, that in a sequence each child traversal is dependent on the state of it siblings on the left, while traversal of each child of a concurrent node is affected by the traversal of all other children (though there is a primary left-to-right order of traversal). I'm not sure if this is what you were after? That’s how I think about it, too.

Though your last sentence isn’t bullet proof – you only reach a certain child of a sequence if all the earlier sequence children succeeded (which can happen during one update). I’d reformulate it to state, that in a sequence each child traversal is dependent on the state of it siblings on the left, while traversal of each child of a concurrent node is affected by the traversal of all other children (though there is a primary left-to-right order of traversal). I’m not sure if this is what you were after?

]]>
By: Gajan/2011/02/24/introduction-to-behavior-trees/#comment-2425 Gajan Thu, 07 Apr 2011 10:31:39 +0000
Regarding the hierarchical-concurrent-state-machine as mentioned in the above article and the paper referred. I have few questions:

- how exactly are behavior trees in your opinion better than hcsm in scenario control and in agent control?

scenario control : HCSMs being used for scenario control in the referred work and are termed “Directors”.
can be used to orchestrate specific conditions within a noisy environment as explained by Alex in his article in the discussion section as below.
I would like to know if BT can support such scenario control, is it better than HCSM in this context.

Alex wrote:
“However, one of the main proposed uses for the HCSM technique is not for agent control, but for scenario control. HCSMs being used in this manner are termed “Directors” and can be used to orchestrate specific conditions within a noisy environment. In the paper introducing the technique, the authors talk specifically about creating specific circumstances within the “Iowa Driving Simulator” (a precursor to the more modern “National Advanced Driving Simulator”), a virtual environment with a physical simulator component based around an actual vehicle shell, making for a very advanced simulation experience — comparable for example to airline training simulators.
The problem with this simulated environment at the time was that there was not a good technique to allow situations to be created that a user of the simulator would need to react to. For example, consider another driver in traffic who cuts the user off. It is difficult to orchestrate this as a general case whilst making the simulation seem fluid, since it depends to a large extent on the behavior of the user — not just from a timing point of view but also from an aggression point of view. A naive technique might have the other vehicle execute its maneuver when the user’s vehicle hits a specific trigger point in the road, but in a fully dynamic world, a vehicle sat waiting to be triggered would be very noticeable and jar the user out of the suspension of disbelief that the simulation encourages.”

Thank you.
Gajan.

]]>
By: Pradeep Jay/2011/02/24/introduction-to-behavior-trees/#comment-2401 Pradeep Jay Wed, 06 Apr 2011 16:53:09 +0000 Hey Pradeep, Thank you for your friendly feedback - it keeps me motivated to work harder on my writing. To your question: the way I understand and define concurrent nodes is that every time a concurrent node is updated/ticked/traversed, for example because one of its nodes returned "running" the update before, all of its child nodes are updated/ticked/traversed again. A concurrent nodes traverses its children in a left-to-right order, so only if one child returns "fail" or "error" the children on its right won't be visited during the current traversal step. There are two reasons why to visit even children that returned "success" again while one or a few other returned "running": 1. the child nodes that returned "success" might be checks that an invariant condition for all other children to run is fulfilled. Such an invariant condition might have returned "success" during the first traversal but I want it to be re-check as a guard during all following traversals, too. 2. If I'd only traverse children that returned "running" during the last traversal I'd need to keep a history of them to only visit these during the next update - and I don't want to waste memory to store such a history or worse, to fall back on dynamic memory allocations to keep it. All in all, the concurrent node appears to tick all its children "in parallel" but it's implemented in a purely sequential fashion - it's concurrent. Kevin Gadd has a great blog post about "concurrency" here: http://altdevblogaday.org/2011/04/03/solving-problems-with-asynchrony-cinematics/ Hm, the second behavior you describe could be implemented by putting special decorator / filter nodes atop each child node of a concurrent node. These decorators wouldn't update their children if they returned "success" but would just return "success" themselves. If such a "history decorator" wasn't visited during a traversal it would be reset ( for example during a post-update cleanup phase) to forget its history and to be prepared for the next "new" visit. What do you think? Hey Pradeep,

Thank you for your friendly feedback – it keeps me motivated to work harder on my writing.

To your question: the way I understand and define concurrent nodes is that every time a concurrent node is updated/ticked/traversed, for example because one of its nodes returned “running” the update before, all of its child nodes are updated/ticked/traversed again.

A concurrent nodes traverses its children in a left-to-right order, so only if one child returns “fail” or “error” the children on its right won’t be visited during the current traversal step.

There are two reasons why to visit even children that returned “success” again while one or a few other returned “running”:

1. the child nodes that returned “success” might be checks that an invariant condition for all other children to run is fulfilled. Such an invariant condition might have returned “success” during the first traversal but I want it to be re-check as a guard during all following traversals, too.

2. If I’d only traverse children that returned “running” during the last traversal I’d need to keep a history of them to only visit these during the next update – and I don’t want to waste memory to store such a history or worse, to fall back on dynamic memory allocations to keep it.

All in all, the concurrent node appears to tick all its children “in parallel” but it’s implemented in a purely sequential fashion – it’s concurrent. Kevin Gadd has a great blog post about “concurrency” here: Hi Bjoern, thank you for an excellent explanation of traversal. It helped me understand behavior trees better. Its interesting that you say <blockquote>difference between a concurrent node and a sequence node is that concurrent nodes run all of their child behaviors on each traversal (if an early fail of one of them doesn’t prevent other siblings to run at all). A sequence always starts from the beginning or the last running behavior and only calls the next on if the former one finished successfully.</blockquote> It makes me wonder, what happens if one child(N1) of the concurrent node has returned success but the other(N2) returns "running". Does that mean on the next step 1. N1 is traversed again, since its under a concurrent node OR 2. N1 is skipped and N2 is traversed since its still marked as running I can imagine situations requiring both kind of traversals. Like say, if one child has a condition which has to be checked at every step to serve as a bail-out, then we would want to visit all child nodes of a concurrent node in every step. But if the children of concurrent node are just regular behaviors which doesn't need to be re-executed, then maybe its better to just execute only the child marked as running. In general, I find it difficult to see the operation of a concurrent node without real parallelization. Hi Bjoern,
thank you for an excellent explanation of traversal. It helped me understand behavior trees better.

Its interesting that you say

difference between a concurrent node and a sequence node is that concurrent nodes run all of their child behaviors on each traversal (if an early fail of one of them doesn’t prevent other siblings to run at all). A sequence always starts from the beginning or the last running behavior and only calls the next on if the former one finished successfully.

It makes me wonder, what happens if one child(N1) of the concurrent node has returned success but the other(N2) returns “running”. Does that mean on the next step
1. N1 is traversed again, since its under a concurrent node OR
2. N1 is skipped and N2 is traversed since its still marked as running

I can imagine situations requiring both kind of traversals. Like say, if one child has a condition which has to be checked at every step to serve as a bail-out, then we would want to visit all child nodes of a concurrent node in every step. But if the children of concurrent node are just regular behaviors which doesn’t need to be re-executed, then maybe its better to just execute only the child marked as running.

In general, I find it difficult to see the operation of a concurrent node without real parallelization.

]]>
By: Shocker: Naive Object-Oriented Behavior Tree Isn’t Data-Oriented » #AltDevBlogADay/2011/02/24/introduction-to-behavior-trees/#comment-1467 Shocker: Naive Object-Oriented Behavior Tree Isn’t Data-Oriented » #AltDevBlogADay Thu, 10 Mar 2011 22:06:49 +0000 It's not quite ready for distribution in its current form. I'm using right now in a game, so I thought I'd let it "bake" a little more to tune the design before making it available. I'll consider doing a blog post and packaging it up then. Don't give me credit for the minimal feature set idea - I lifted that completely from Alex's presentation! I struggled with Alex's lookup tables for a while also, but the more I thought about it, the more they seemed like the concept of polymorphism in object oriented programming (which is usually implemented with virtual tables). This is the thing that really got me hooked on BT - that you could reuse trees because they are "goal-based". The goals are just abstract actions that are implemented depending on the type of the agent or receiver. The implementation that an agent decides on could invoke another subtree, but that isn't required. I think this is where there is some confusion in the presentation because maybe Alex didn't make it completely clear that the two are separate concepts (of course I'm just making assumptions here, I don't want to speak for Alex). Sub-trees make sense even without lookup tables because they are sort of like subroutines: they shorten your code and can be reused (notice how I always come back to programming language concepts when thinking about BT. It is a very comfortable way to look at it I think). As far as dynamic memory goes, I am finding it useful to provide a hook for the agent to store data related to a running behavior rather than making the agent do it itself. I separate the tree from the thread of execution on that tree (I call the thread of execution a "Navigator"). A Navigator is created to execute a tree, and sends messages to the agent. The trees are read-only, so multiple navigators can be running on the same tree simultaneously. The agent can create contextual data and hand it to the navigator to retain on the current node. Since each node goes through three states: (Init, Tick, and Reset) then the agent can ensure that the contextual data is deleted when the action is complete. This is like the constructor/destructor concept in object oriented languages. The Navigator can check this also (or it can just delete the data itself). One navigator is created for one tree. Calling a subtree requires a new navigator, but that can be constructed as part the "Subtree" action. The new navigator can be stored in the contextual data slot for the Subtree action when the subtree is called. It is then deleted when the subtree returns a non-running completion code. This way you can have multiple instances of a subtree in "running" at the same time from a single parent tree because their navigators are stored in different parent tree nodes. This also supports recursion (although I'm not sure what that means for a Behavior Tree!) I am intrigued by your "dynamic" or "always restart from highest priority" or "reflex" selector. I can see the advantages of trying to stay aware of higher priority behaviors while still running the current behavior. This can also be done using a parallel, but maybe not so succinctly. There is value in small, easy to remember concepts vs. complex idioms. I like the term "dynamic" because it reminds that it keeps trying the higher priority items. It’s not quite ready for distribution in its current form. I’m using right now in a game, so I thought I’d let it “bake” a little more to tune the design before making it available. I’ll consider doing a blog post and packaging it up then.

Don’t give me credit for the minimal feature set idea – I lifted that completely from Alex’s presentation!

I struggled with Alex’s lookup tables for a while also, but the more I thought about it, the more they seemed like the concept of polymorphism in object oriented programming (which is usually implemented with virtual tables). This is the thing that really got me hooked on BT – that you could reuse trees because they are “goal-based”. The goals are just abstract actions that are implemented depending on the type of the agent or receiver. The implementation that an agent decides on could invoke another subtree, but that isn’t required. I think this is where there is some confusion in the presentation because maybe Alex didn’t make it completely clear that the two are separate concepts (of course I’m just making assumptions here, I don’t want to speak for Alex). Sub-trees make sense even without lookup tables because they are sort of like subroutines: they shorten your code and can be reused (notice how I always come back to programming language concepts when thinking about BT. It is a very comfortable way to look at it I think).

As far as dynamic memory goes, I am finding it useful to provide a hook for the agent to store data related to a running behavior rather than making the agent do it itself. I separate the tree from the thread of execution on that tree (I call the thread of execution a “Navigator”). A Navigator is created to execute a tree, and sends messages to the agent. The trees are read-only, so multiple navigators can be running on the same tree simultaneously. The agent can create contextual data and hand it to the navigator to retain on the current node. Since each node goes through three states: (Init, Tick, and Reset) then the agent can ensure that the contextual data is deleted when the action is complete. This is like the constructor/destructor concept in object oriented languages. The Navigator can check this also (or it can just delete the data itself).

One navigator is created for one tree. Calling a subtree requires a new navigator, but that can be constructed as part the “Subtree” action. The new navigator can be stored in the contextual data slot for the Subtree action when the subtree is called. It is then deleted when the subtree returns a non-running completion code. This way you can have multiple instances of a subtree in “running” at the same time from a single parent tree because their navigators are stored in different parent tree nodes. This also supports recursion (although I’m not sure what that means for a Behavior Tree!)

I am intrigued by your “dynamic” or “always restart from highest priority” or “reflex” selector. I can see the advantages of trying to stay aware of higher priority behaviors while still running the current behavior. This can also be done using a parallel, but maybe not so succinctly. There is value in small, easy to remember concepts vs. complex idioms. I like the term “dynamic” because it reminds that it keeps trying the higher priority items.

]]>
By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-1158 Bjoern Knafla Wed, 02 Mar 2011 12:54:34 +0000 Hi Bjoern, I, like you, have had to implement my own BT system in order to really understand this stuff. I am using the Unity game engine and of course started using AngryAnt's easy-to-use Behave library. But being a tinkerer, I couldn't leave well enough alone and created my own system. I think we all see the benefits of hoisting this stuff out of embedded script code and standardizing on a set of components to build our AI, but as they say, the devil is in the details. Exactly what are the fundamental building blocks? What is the abstraction model? Alex's introduction video is what really got me motivated. I think it would benefit us to come up with some common terms for the concepts. Starting with Alex's notation: Action - A named leaf node that performs some action Decorator - A named internal node that allows the agent to affect the tree navigation Sequence - Traverses its child nodes in order, left to right. The Sequence fails as soon as any child fails. If a child returns "running", then the Sequence returns "running", and that child will be traversed first on the next tick (skipping prior children) Selector - Traverses its child nodes in order, left to right. The Selector succeeds as soon as any child succeeds. The Selector fails only if all children fail. Like Sequence, Selector retains a "running" child and traverses it first on the next tick. Parallel - Child nodes are traversed in order, left to right. The Parallel construct completes (i.e. return status other than "running") based on some condition (e.g. One child fails, All child nodes fail etc.) You have: Priority Selector - with two options: 1) The same as "Selector" in Alex's notation 2) Always check child nodes from left to right (even if a child returned "running" on the previous tick). If one of the earlier child nodes returns Success or Running, then cancel the prior running node, otherwise continue running it. This concept is new to me, but seems very useful (maybe its the same as Joacim Jacobsson's dynamic selector?) I haven't been able to easily duplicate this with other node types, so I think this may be fundamental. Sequence Selector - Same as "Sequence" in Alex's notation Loops - Sequence Selectors that start over again when the last child completes. Random Selectors - picks a random child to visit. The child will be visited again on the next tick if it returns "running". Concurrent - Same as Alex's Parallel Action, Decorator - Same as in Alex's notation Conditions - Affect parent sequence or parallel based on outcome of condition Angry Ant's "Behave" is based on Alex's presentation, but adds some nice concepts: IAgent - an interface that executes a behavior tree The IAgent provides Init, Tick, and Reset methods. Init is called when an Action or Decorator is entered and was "ready" in your notation. It changes the item to the "running" state. Tick is called on a running item (immediately after Init if Init was called). Tick can return Success, Failure, or Running. Reset is called when an item changes back to "ready" from "running". Behave 1.2 now has a "Priority Selector" which is a little different than yours. Behave's version adds an additional IAgent function that returns an int which is the index of the child to visit. I'm sure I left out some imporant references, but I wanted to remark on the similarity of all this to language design. Behavior Trees are essentially a form of declarative programming language. And as with any programming language, there is a trade-off of what should be a languate feature, and what should be built from features of the language. I think Alex has it right with his concept of decorators. Rather than add Loop, Invert, Random Selectors etc., let the user's agent implement these features. To do a "Loop Sequence", just place a decorator named "Loop" above a normal Sequence. The key is to identify what is fundamental, and what can be built from combinations of fundamental building blocks. So here then is my vote for fundamental features (if I don't describe the feature, then it is the same as in Alex's notation). Action Decorator Sequence Selector Parallel - Same as Alex's, but with the following termination conditions: All Success - Success if all child nodes succeed (returns Failure as soon as one child fails) Any Success - Success as soon as any child node succeeds All Fail - Success if all child nodes fail (returns Failure as soon as one child succeeds) Any Fail - Success as soon as any child node fails All Done - Success when all child nodes complete (with any result status) Any Done - Success as soon as any child node completes (with any result status) Named Selector - (a Selector with a name) Similar to Behave's Priority Selector where the agent returns which of the children to run next Dynamic Selector - Like your Priority Selector with option 2 To implement Alex's goal-based concept, I have added a virtual table capability with agent inheritence and message forwarding in the agent. My agents also support: local and global variables; storing of extra state information for running nodes; an arbitrary number of constant parameters for actions, decorators, and named selectors. I use named selectors for: random selector, probability selector, and feedback selector (sort of a simple machine learning). I can also chain into a subtree with a "Subtree" Action. The subtree can be selected at runtime. Also, the virtual tables can be rebuilt at runtime as actors learn, become members of squads or larger groups, change allegiences etc. But I should mention that all this stuff is built up in the agent or by using idoms or collections of fundamental behavior tree nodes. (BTW, I did all this over a two week period. I think I mentioned that Alex's presentation was very motivating!) Hi Bjoern,

I, like you, have had to implement my own BT system in order to really understand this stuff. I am using the Unity game engine and of course started using AngryAnt’s easy-to-use Behave library. But being a tinkerer, I couldn’t leave well enough alone and created my own system. I think we all see the benefits of hoisting this stuff out of embedded script code and standardizing on a set of components to build our AI, but as they say, the devil is in the details. Exactly what are the fundamental building blocks? What is the abstraction model? Alex’s introduction video is what really got me motivated. I think it would benefit us to come up with some common terms for the concepts. Starting with Alex’s notation:

Action – A named leaf node that performs some action
Decorator – A named internal node that allows the agent to affect the tree navigation
Sequence – Traverses its child nodes in order, left to right. The Sequence fails as soon as any child fails. If a child returns “running”, then the Sequence returns “running”, and that child will be traversed first on the next tick (skipping prior children)
Selector – Traverses its child nodes in order, left to right. The Selector succeeds as soon as any child succeeds. The Selector fails only if all children fail. Like Sequence, Selector retains a “running” child and traverses it first on the next tick.
Parallel – Child nodes are traversed in order, left to right. The Parallel construct completes (i.e. return status other than “running”) based on some condition (e.g. One child fails, All child nodes fail etc.)

You have:
Priority Selector – with two options:
1) The same as “Selector” in Alex’s notation
2) Always check child nodes from left to right (even if a child returned “running” on the previous tick). If one of the earlier child nodes returns Success or Running, then cancel the prior running node, otherwise continue running it.
This concept is new to me, but seems very useful (maybe its the same as Joacim Jacobsson’s dynamic selector?) I haven’t been able to easily duplicate this with other node types, so I think this may be fundamental.
Sequence Selector – Same as “Sequence” in Alex’s notation
Loops – Sequence Selectors that start over again when the last child completes.
Random Selectors – picks a random child to visit. The child will be visited again on the next tick if it returns “running”.
Concurrent – Same as Alex’s Parallel
Action, Decorator – Same as in Alex’s notation
Conditions – Affect parent sequence or parallel based on outcome of condition

Angry Ant’s “Behave” is based on Alex’s presentation, but adds some nice concepts:
IAgent – an interface that executes a behavior tree
The IAgent provides Init, Tick, and Reset methods.
Init is called when an Action or Decorator is entered and was “ready” in your notation. It changes the item to the “running” state.
Tick is called on a running item (immediately after Init if Init was called). Tick can return Success, Failure, or Running.
Reset is called when an item changes back to “ready” from “running”.

Behave 1.2 now has a “Priority Selector” which is a little different than yours. Behave’s version adds an additional IAgent function that returns an int which is the index of the child to visit.

I’m sure I left out some imporant references, but I wanted to remark on the similarity of all this to language design. Behavior Trees are essentially a form of declarative programming language. And as with any programming language, there is a trade-off of what should be a languate feature, and what should be built from features of the language. I think Alex has it right with his concept of decorators. Rather than add Loop, Invert, Random Selectors etc., let the user’s agent implement these features. To do a “Loop Sequence”, just place a decorator named “Loop” above a normal Sequence. The key is to identify what is fundamental, and what can be built from combinations of fundamental building blocks.

So here then is my vote for fundamental features (if I don’t describe the feature, then it is the same as in Alex’s notation).
Action
Decorator
Sequence
Selector
Parallel – Same as Alex’s, but with the following termination conditions:
All Success – Success if all child nodes succeed (returns Failure as soon as one child fails)
Any Success – Success as soon as any child node succeeds
All Fail – Success if all child nodes fail (returns Failure as soon as one child succeeds)
Any Fail – Success as soon as any child node fails
All Done – Success when all child nodes complete (with any result status)
Any Done – Success as soon as any child node completes (with any result status)
Named Selector – (a Selector with a name) Similar to Behave’s Priority Selector where the agent returns which of the children to run next
Dynamic Selector – Like your Priority Selector with option 2

To implement Alex’s goal-based concept, I have added a virtual table capability with agent inheritence and message forwarding in the agent. My agents also support: local and global variables; storing of extra state information for running nodes; an arbitrary number of constant parameters for actions, decorators, and named selectors. I use named selectors for: random selector, probability selector, and feedback selector (sort of a simple machine learning). I can also chain into a subtree with a “Subtree” Action. The subtree can be selected at runtime. Also, the virtual tables can be rebuilt at runtime as actors learn, become members of squads or larger groups, change allegiences etc.

But I should mention that all this stuff is built up in the agent or by using idoms or collections of fundamental behavior tree nodes.

(BTW, I did all this over a two week period. I think I mentioned that Alex’s presentation was very motivating!)

]]>
By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-982 Bjoern Knafla Thu, 24 Feb 2011 16:01:52 +0000 Are you sure you didn't peek already? In the "About" dialog for the editor I have the line "Here there be dragons." ;) Are you sure you didn’t peek already? In the “About” dialog for the editor I have the line “Here there be dragons.” ;)

]]>
By: Savas Ziplies/2011/02/24/introduction-to-behavior-trees/#comment-980 Savas Ziplies Thu, 24 Feb 2011 15:14:40 +0000 Ah, now I get it. You are right - I am using the term "selector" in a more general way than you (and that might be a bad idea). For me a selector selects what child behavior to run and possible defines an order, too. That includes decorators and concurrent nodes. Perhaps I should have named it <em>group nodes</em> but I wanted to get away from the term <em>node</em> as much as possible as it implies a certain implementation style. The main reason to have a concurrent selector is its traversal semantic which enables to use conditions (or failing/succeeding actions) as invariant guards - what you seem to call <em>assumption monitors</em> (?). Without concurrent nodes it would be very simple to store the state of a BT as it would mainly be the last traversal stack. To update such a simpler BT would mean that you don't need to start traversal at the root but you could take the traversal stack and start working on the last node pushed onto it - e.g. the last sequence that was running. I'm not 100% sure yet if I am willing to give up the power and expressiveness of concurrent nodes to gain a simpler implementation and (more importantly) a simpler but more limited BT model. That's what makes this whole experiment so exciting to me :-) Ah, now I get it. You are right – I am using the term “selector” in a more general way than you (and that might be a bad idea). For me a selector selects what child behavior to run and possible defines an order, too. That includes decorators and concurrent nodes.

Perhaps I should have named it group nodes but I wanted to get away from the term node as much as possible as it implies a certain implementation style.

The main reason to have a concurrent selector is its traversal semantic which enables to use conditions (or failing/succeeding actions) as invariant guards – what you seem to call assumption monitors (?).

Without concurrent nodes it would be very simple to store the state of a BT as it would mainly be the last traversal stack. To update such a simpler BT would mean that you don’t need to start traversal at the root but you could take the traversal stack and start working on the last node pushed onto it – e.g. the last sequence that was running.
I’m not 100% sure yet if I am willing to give up the power and expressiveness of concurrent nodes to gain a simpler implementation and (more importantly) a simpler but more limited BT model. That’s what makes this whole experiment so exciting to me :-)

]]>
By: Alex/2011/02/24/introduction-to-behavior-trees/#comment-974 Alex Thu, 24 Feb 2011 11:22:37 +0000 Hey, thanks for all the great discussions on Twitter! I definitely need to check out your <a href="https://github.com/jjacobsson/calltree" rel="nofollow">behavior tree compiler</a> in more depth. Lookiing at other implementations after hitting serious roadblocks in need of decisions is so helpful. And there are so many small and big decisions to make during the design and implementation of a BT - I didn't really expect that and often have a hard time to foresee the consequences of some of the decisions. Actual use of the stuff will identify where I decided wrongly. Hey, thanks for all the great discussions on Twitter!

I definitely need to check out your behavior tree compiler in more depth. Lookiing at other implementations after hitting serious roadblocks in need of decisions is so helpful. And there are so many small and big decisions to make during the design and implementation of a BT – I didn’t really expect that and often have a hard time to foresee the consequences of some of the decisions. Actual use of the stuff will identify where I decided wrongly.

]]> By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-971 Bjoern Knafla Thu, 24 Feb 2011 10:58:13 +0000 Hey Alex, thanks for chiming in with your great explanations! Hey Alex, thanks for chiming in with your great explanations!

]]>
By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-969 Bjoern Knafla Thu, 24 Feb 2011 10:43:45 +0000 Great stuff Bjoern! Makes me wish I had named my "dynamic selector" "priority selector" instead since that's much more telling. :) Guess I'll rename it... eventually... Great stuff Bjoern!

Makes me wish I had named my “dynamic selector” “priority selector” instead since that’s much more telling. :)

Guess I’ll rename it… eventually…

]]>
By: Bjoern Knafla/2011/02/24/introduction-to-behavior-trees/#comment-967 Bjoern Knafla Thu, 24 Feb 2011 10:23:14 +0000 Ok, thanks, I'll have a look at it. Ok, thanks, I’ll have a look at it.

]]>
By: Alex/2011/02/24/introduction-to-behavior-trees/#comment-964 Alex Thu, 24 Feb 2011 09:19:11 +0000 snake5, FSMs are very low-level and you spend all your time wiring up transitions. When you think about NPC behavior, that's not a good model to use and it often results in a large mess of states and transitions. BTs use top-down task decomposition, which is much more intuitive. Bjoern's diagrams aren't the easiest to understand at first glance, but even designers get used to it quickly :-) Here's my GDC talk on the subject, which talks about the differences between BTs and FSMs in practice: http://aigamedev.com/insider/presentations/behavior-trees/ (You just need a free account.) Alex snake5,

FSMs are very low-level and you spend all your time wiring up transitions. When you think about NPC behavior, that’s not a good model to use and it often results in a large mess of states and transitions. BTs use top-down task decomposition, which is much more intuitive. Bjoern’s diagrams aren’t the easiest to understand at first glance, but even designers get used to it quickly :-)

Here’s my GDC talk on the subject, which talks about the differences between BTs and FSMs in practice:
I didn't find one important question being answered anywhere - how exactly are behavior trees in your opinion better than FSMs? Since I'm a big fan of FSMs and as it's somehow hard to follow the design/implementations of behavior trees (even harder than reading FSMs), I'd like to have a good reason to make the transition. Now it only seems that they're like more restricted FSMs with behavior duplication (I hope you don't mind my imprecise oversimplification) I didn’t find one important question being answered anywhere – how exactly are behavior trees in your opinion better than FSMs? Since I’m a big fan of FSMs and as it’s somehow hard to follow the design/implementations of behavior trees (even harder than reading FSMs), I’d like to have a good reason to make the transition. Now it only seems that they’re like more restricted FSMs with behavior duplication (I hope you don’t mind my imprecise oversimplification)

]]>
By: Savas Ziplies/2011/02/24/introduction-to-behavior-trees/#comment-957 Savas Ziplies Thu, 24 Feb 2011 07:47:33 +0000 [...] This post was mentioned on Twitter by Mike Acton, Bjoern Knafla and jaymin kessler, Nay. Nay said: RT "@mike_acton: #AltDevBlogADay Introduction to Behavior Trees