I have been trying to understand behavior trees (BTs) and how they relate to HFSMs (or FSMs) for use in an up coming project. Specifically ive been trying to figure out how I would encode the capabilities of my current simple FSM into a BT. I know the following example might not be the best case for a BT, but im just trying to get a feel of how it could be implement via a BT. I have read a bit about BTs (and watched that AIGameDev video), and have yet to fully grasp them.

So i have 4 states in my FSM:
Idle
Suspicious
Attack
Flee

Idle can transition into Suspicious if there has been a perception of the players presence without actually seeing the player (e.g. player knocked over a lamp).
Idle can directly transition into attack if the player is visually spotted

Suspicious (enemy is actively searching for player) can transition into attack if the player is visually spotted
Suspicious can transition back to Idle after a certain amount of time searching.

Attack can transition to idle if the player has been killed
Attack can transition to Flee if the agent becomes too damaged
Fleeing is trying to get away from the player, while at the same time seeking out some health if the player is believe to have been evaded.

Flee can transition to suspicious if the agent has picked up some health

How could something like this be encoded into a BT, with selectors, sequences, parallels, decorators, etc. ?

After the entire tree is evaluated, is it reevaluated from the start?

Any guidance would be appreciated.

Thanks

The main thing you need to think about when constructing a BT is priority. That is, "if I don't need to do A, I can consider doing B". You repeat a lot of that until you get down the most basic thing... like an idle state. In your case, "Flee" is the highest priority -- it is self-preservation and nothing else matters at the time. If you are not fleeing, you are fighting, if you are not fighting, you might be looking. If you are doing none of those, you are idle. Each of those nodes would have a conditional check similar to what you are already doing.

Is my health low and there is an enemy? Flee. If not...
Is there an enemy? Fight.
Is there a sound? Suspicious.
Idle.

For the most part, you evaluate the BT every think cycle. If the conditions are the same, you end up right where you were. If they change, you might end up in a different place.

Now this is the simple version... there are obviously more things that you could do with it. For example, "fight" could have things like "move to opponent" and "attack". The former would have the simple condition that we are out of range of the target. If we are IN range, then we would fall through to "attack". Of course, we would only be in this branch if there was an enemy in the first place (the condition we checked above).

That's a quick primer on how to "think" in BTs.

What would the tree for this look like?

Like this?

selector
----sequence
--------condition
--------ActionFlee
----sequence
--------condition
--------ActionSuspicious
----sequence
--------condition
--------ActionAttack
----ActionIdle

The main thing you need to think about when constructing a BT is priority. That is, "if I don't need to do A, I can consider doing B". You repeat a lot of that until you get down the most basic thing... like an idle state. In your case, "Flee" is the highest priority -- it is self-preservation and nothing else matters at the time. If you are not fleeing, you are fighting, if you are not fighting, you might be looking. If you are doing none of those, you are idle. Each of those nodes would have a conditional check similar to what you are already doing.

Is my health low and there is an enemy? Flee. If not...
Is there an enemy? Fight.
Is there a sound? Suspicious.
Idle.

For the most part, you evaluate the BT every think cycle. If the conditions are the same, you end up right where you were. If they change, you might end up in a different place.

Now this is the simple version... there are obviously more things that you could do with it. For example, "fight" could have things like "move to opponent" and "attack". The former would have the simple condition that we are out of range of the target. If we are IN range, then we would fall through to "attack". Of course, we would only be in this branch if there was an enemy in the first place (the condition we checked above).

That's a quick primer on how to "think" in BTs.

For starters, yeah.

Perhaps this will help.

Here is an excerpt from one of my test BTs. Maybe it'll help





new Behavior(
new RootSelector(
//determins which branch to take
getEnemyState,

//Idle State
new Selector(
new Conditional(() => false)
),

//Active State
new Selector(
new Conditional(() => false)
),

//Combat State
new Selector(

//get a target
new Sequence(
//do i have a target?
new Inverter(new Conditional(hasLiveTarget)),
//get a target
new BehaviorAction(findTarget)
),

new Selector(
//attempt to move back into range of target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too close to the target
new Conditional(isTargetTooClose),
//not too far
new Inverter(new Conditional(isTargetTooFar)),
//can you move away
new Conditional(canMoveAwayFromTarget),
//move
new BehaviorAction(move)
),

//attempt to move within range of target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too far from the target
new Conditional(isTargetTooFar),
//not too close
new Inverter(new Conditional(isTargetTooClose)),
//can you move towards the target
new Conditional(canMoveTowardsTarget),
//move
new BehaviorAction(move)
)
),

//attempt to attack the target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too close to the target
new Inverter(new Conditional(isTargetTooClose)),
//are you too far from the target
new Inverter(new Conditional(isTargetTooFar)),
//can you attack the target
new Conditional(isTargetAttackable),
//attack target
new BehaviorAction(attackTarget)
),

//go idle until something happens.
new Sequence(
//assess self
new BehaviorAction(idle)
)

)
)
);



using a specially modified Selector, you can implement state-like controls on the which paths to take in your BT. In this example, i just have a simple method getEnemyState that returns the integer value of an enumerator that has the same number of enumerations as available branches. This particular BT is a test combat branch that implements a very simple roguelike behavior pattern. One thing you'll notice is some redundant conditionals in this, its just to make sure things haven't changed since the BT was last searched. the " () => false " arguments for the first two branches are just method lambda expressions to act like a method that always returns false, so if for some reason they are taken, they come back with something. The last sequence is also a placeholder from when i was going to add some additional behaviors with the idle command, though its still perfectly valid to use one child though.

The Root Selector looks like follows:



public class RootSelector : Selector
{

private BehaviorComponent[] rs_Behaviors;

private Func<int> rs_Index;

/// <summary>
/// The selector for the root node of the behavior tree
/// </summary>
/// <param name="index">an index representing which of the behavior branches to perform</param>
/// <param name="behaviors">the behavior branches to be selected from</param>
public RootSelector(Func<int> index, params BehaviorComponent[] behaviors)
{
rs_Index = index;
rs_Behaviors = behaviors;
}

/// <summary>
/// performs the given behavior
/// </summary>
/// <returns>the behaviors return code</returns>
public override BehaviorReturnCode Behave()
{
try
{
switch (rs_Behaviors[rs_Index.Invoke()].Behave())
{
case BehaviorReturnCode.Failure:
ReturnCode = BehaviorReturnCode.Failure;
return ReturnCode;
case BehaviorReturnCode.Success:
ReturnCode = BehaviorReturnCode.Success;
return ReturnCode;
case BehaviorReturnCode.Running:
ReturnCode = BehaviorReturnCode.Running;
return ReturnCode;
default:
ReturnCode = BehaviorReturnCode.Running;
return ReturnCode;
}
}
catch (Exception)
{
ReturnCode = BehaviorReturnCode.Failure;
return ReturnCode;
}
}
}

Just remember, this is an example. Your architecture may require it to look a little different.

[Update: just wanted to clean a few things up for clarification]

Here is an example from one of my behavior trees:




new Behavior(
new RootSelector(
//determins which branch to take
getEnemyState,

//Idle State
new Selector(
new Conditional(() => false)
),

//Active State
new Selector(
new Conditional(() => false)
),

//Combat State
new Selector(

//get a target
new Sequence(
//do i have a target?
new Inverter(new Conditional(hasLiveTarget)),
//get a target
new BehaviorAction(findTarget)
),

new Selector(
//attempt to move back into range of target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too close to the target
new Conditional(isTargetTooClose),
//not too far
new Inverter(new Conditional(isTargetTooFar)),
//can you move away
new Conditional(canMoveAwayFromTarget),
//move
new BehaviorAction(move)
),

//attempt to move within range of target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too far from the target
new Conditional(isTargetTooFar),
//not too close
new Inverter(new Conditional(isTargetTooClose)),
//can you move towards the target
new Conditional(canMoveTowardsTarget),
//move
new BehaviorAction(move)
)
),

//attempt to attack the target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too close to the target
new Inverter(new Conditional(isTargetTooClose)),
//are you too far from the target
new Inverter(new Conditional(isTargetTooFar)),
//can you attack the target
new Conditional(isTargetAttackable),
//attack target
new BehaviorAction(attackTarget)
),

//go idle until something happens.
new Sequence(
//assess self
new BehaviorAction(idle)
)

)
)
);



using a specially modified Selector, you can implement state-like controls on the which paths to take in your BT. In this example, i just have a simple method getEnemyState that returns the integer value of an enumerator that has the same number of enumerations as available branches.

In my game I like to think of behaviors as being analogous to goals. If you have an object running through data from the simulation, he could think "Ok, I have a big mean mother-hubbard charging right at me." State machines, behavior trees, goal hierarchies, they all look at the "how". So your Flee goal (I will call them goals now) could consist of an entire hierarchy of other goals. We call these composite goals. Goals that the agent actually uses that produce an end result are called atomic goals.

CompositeGoal_Think -> Oh snap, ogre alert!!!

--CompositeGoal_Flee -> I want to live damn it!!!

----CompositeGoal_Navigate->Where should I go?

------AtomicGoal_Move->Time to haul ass!!!

Note that this goal hierarchy omits what could be quite a complex set of goals. For instance, you could have subgoals within navigate that don't make it just move towards a pointt, but use a navigation graph, waypoint list, or any number of navigation techniques to get to where it wants to go.

But really, it is all about the think goal in this case. The Think goal could be conssidered your "state machine", because it is the very root of your hierarchy, and could be responsible for changing the entire heirarchy. It is the same with any composite goal.

Consider for a moment that our hero is running away and comes to a creek he has to jump across in order to continue.

CompositeGoal_Think -> Oh snap, ogre alert!!!

--CompositeGoal_Flee -> I want to live damn it!!!

----CompositeGoal_Navigate -> Oh crap! Creek. Need to readjust my priorities.

------CompositeGoal_JumpAcrossRiver

--------AtomicGoal_JumpTo -> Some gonna find a point at the other side of the river where I can land and just jump!

------AtomicGoal_Move->Once I'm done with that, time to keep hauling ass.

Here is an excerpt from one of my test BTs. Maybe it'll help





new Behavior(
new RootSelector(
//determins which branch to take
getEnemyState,

//Idle State
new Selector(
new Conditional(() => false)
),

//Active State
new Selector(
new Conditional(() => false)
),

//Combat State
new Selector(

//get a target
new Sequence(
//do i have a target?
new Inverter(new Conditional(hasLiveTarget)),
//get a target
new BehaviorAction(findTarget)
),

new Selector(
//attempt to move back into range of target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too close to the target
new Conditional(isTargetTooClose),
//not too far
new Inverter(new Conditional(isTargetTooFar)),
//can you move away
new Conditional(canMoveAwayFromTarget),
//move
new BehaviorAction(move)
),

//attempt to move within range of target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too far from the target
new Conditional(isTargetTooFar),
//not too close
new Inverter(new Conditional(isTargetTooClose)),
//can you move towards the target
new Conditional(canMoveTowardsTarget),
//move
new BehaviorAction(move)
)
),

//attempt to attack the target
new Sequence(
//check to verify you still have a target
new Conditional(hasLiveTarget),
//are you too close to the target
new Inverter(new Conditional(isTargetTooClose)),
//are you too far from the target
new Inverter(new Conditional(isTargetTooFar)),
//can you attack the target
new Conditional(isTargetAttackable),
//attack target
new BehaviorAction(attackTarget)
),

//go idle until something happens.
new Sequence(
//assess self
new BehaviorAction(idle)
)

)
)
);



Not sure what language or pseudo code form this is, but doesnt it seem that he word 'new' used for every function call/whatever is redundant/cluttery ?

This (Behavior Trees) is basicly nested if-then logic which is OK for some types of logic processing but most more complex decision making requires
actual 'state' that gets resumed so to to bypass reprocessing previously passed decisions and allows concentrating on calculating decisions
in the current context.

Ive looked at FSM use for quite complicated AI (FSM for 'solutions' picked by a planner) and saw that you usually have to load up each state
with logic testing local resume-conditions to see if the current state/context still applies (and then usually transitioning backwards to a FSM
predecessor state or even restarting the FSM
Similarly the design also has shunts/shortcuts to precheck fulfilment of a states pass requirements and skipping that states actions to go on
to subsequent states in the sequence.

The BT like construct would be used to control the state transitions within a FSM (but custom to each state)


1)Moveto Toolbin
2)Grab Hammer
3)Moveto Worksite
4)Hammer Something

if you start this task/solution and you already have a hammer you should have the logic skip the first 2 states

If you get to the worksite (probably a recursive FSM to make that happen) and you no longer have a hammer (retest possession of the tool) then
you need to back up to the point where the hammer is acquired . That state will check position and if you are 'there' then it will skip the move and
go do the next state.

Notice it only runs the decsion logic IF the context calls for it and not every time.
At each state in the sequence you dont want to have to retest all the preconditions (which in more complex AI may dwarf the processing of simple if-then statement tests)

Just for state 1 you might need to test:

where am I (position is often alot more than just coords)
Can I move (what means)
Where is the toolbin (has it moved) - find it - path or repath



if you are at state 3 you check if you have a hammer (appropriate type maybe) and who cares about testing precondition of [revious state that are not relevant
to the current context. Processing of the above is usually ALOT more work than just looking in simple variables.

There are other logic constructs/features like handling retries on failures (and how many before giving up - often a complex cost allowance system) that can muck up the logic or handling parallel subtasks (where the most opportune gets done first and its results are maintatined while the other task is then done)

When you have this added complexity to the definition of the decision process suddenly the FSMs organization around localized context becomes much more useful.





Behavior Trees are one tool that has its use in the right place and FSMs in their place.

I might use the ordered test logic of a BT to do an overall (frequently run) situational test (one where you do test everything thru a static priority first ordering)
to find when current activities are to be aborted and new priorities force complete reevalution of the situation from a fdifferent logical point of view.

EX- hitpoints at low threshold -- all behavior changes to survival mode and all previously calculated priorities and subtask priorities are null and void.



Similarly if you have fairly dumb objects who's entire decision tree is short/simple to calculate (thus not all that much cost to rerun every/frequent decision cycle)
then simplifying the coding to be less than what a FSM requires can be simpler to create. Some physics reactive code might be like this because
you are choosing/arbitrating between modal processing for discrete factors (ex- set-on-fire event intersected with splashed-with-water event )

In really complex simulated environments you probably start using a multidimentional lookup table because of all the combinations and the irregular logic and
special endcases that likely exist (and laying out the logic linearly will be tedius and hard to visualize/validate)






Oh and an added comment is that even FSMs get to large/unwieldy when dealing with complex decisions/tasks so that Hierarchical FSMs would be used to try to keep their individual complexity down AND in my designs there is a planner type decision picking/evaluating between potential solutions that gets done, and then those sub-solution are FSMplus . Note - the 'evaluation' when picking the best solution is a one-pass set of tests per solution that probably will resemble BTs stacked logic