Jump to content

  • Log In with Google      Sign In   
  • Create Account

Behavior Trees or FSM?


Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


  • You cannot reply to this topic
13 replies to this topic

#1 jdean300   Members   -  Reputation: 254

Like
1Likes
Like

Posted 07 February 2016 - 09:32 PM

I'm working on a top-down squad base shooter where the player controls the squad leader and can also issue commands to other teams within his squad.

 

My Requirements:

  • Soldiers respond well on their own, reacting to and defending themselves, taking cover, assessing dangers and tactical positions, etc.
  • Teams(3-4 soldiers) move cohesively, but are not just a square blob of men waiting to be blown up.
  • Teams should also be able to receive orders to accomplish an objective (provide cover, move here, take building, etc.).
  • Problem solving: if a player tells one team to enter a building but the door is locked they should look for other ways in and act accordingly, preferably taking into account the current combat situation. (if the squad is not in combat, don't open the door with C4... If we are in combat, don't waste time searching a huge building for an unlocked door...)

I have looked at dozens of tutorials on both Behavior Tree's and Finite State Machine's and they seem like they both could accomplish the task, each having it's own advantages and disadvantages. I have also implemented both and have prototyped some of the basic behaviors in each.

 

With FSM's, I can easily reason and understand the states and transitions involved, but can see the required number of states exploding quite quickly and it seems that every time a state is added I have to spend a lot of time checking the transitions and routes through the machine to try and recognize any problems. Simple to reason with, hard to extend.

 

With BT's I struggle to organize the tree's execution in my head, and the code to define the behavior tree is too abstract for me to build a working mental image of the tree, but I can very easily add/remove behaviors from the tree without having to change other nodes. Harder to reason about, easy to extend.

 

I am leaning towards BT's because of their extensibility, but I think i would need to implement a graphical editor in order to effectively reason about them. This wouldn't be too huge of a task - I have something very similar already put together for another project and so I expect it would only take a few hours time to create this.

 

Does it seem like I am doing something wrong?

Are neither of these the right answer?

Is the BT editor worth it, and out of curiosity, does anyone work with these exclusively in code?



#2 SeanMiddleditch   Crossbones+   -  Reputation: 14808

Like
2Likes
Like

Posted 08 February 2016 - 12:27 AM

You can combine the approaches. Advanced AI can rarely fit into a single paradigm and will often have many different moving pieces. Some will be state machines while some specific behaviors are much more easily modeled as behavior trees. Yet other behaviors will have needs that don't fit well into either architecture.

A squad-based AI can be easily broken down into components like:
- Spatial reasoning, such as detecting defensible and dangerous locations
- Formations and movement, including use of cover, sniper locations, bounding overwatch, etc.
- Goal planning, both individual survival and squad tactics
- Path finding

Building out an advanced AI to cover all the features you mention is likely to hit many of the common AI techniques.

Regarding editors, yes, it's ALWAYS worth it. The wiser companies invest very heavily into tools. Tools are how the game actually gets made, after all. Good tools are the difference between your content creators spending their time making lots of high quality content or spending their time struggling just to make mediocre content. Investing time and money into tools early on can save many times their cost down the road.

#3 jdean300   Members   -  Reputation: 254

Like
1Likes
Like

Posted 08 February 2016 - 01:38 AM

So, taking your input into consideration, here's my rough plan:

 

Spatial reasoning is mostly being done during level design right now - at runtime soldiers are just rating the positions based on the current situation (angle of incoming fire for example). I tried working on some algorithms to calculate points of interest automatically, but it was seeming easier to just manually place them during level design (for which I built a graphical editor).

 

FSM to control squad level tactics. A squads number of states is likely to be far less than that of an individual soldier, therefore a FSM should model their planning well without ballooning into a tangled mess of transitions. Also, a squad state is going to be tracking much more world data (soldier positions, other team positions, routes, etc) and it will be easier to manage that data in a state machine than a behavior tree.

 

Behavior trees for soldier level actions - BT's seem very reactive and fluid, and scale much better to a lot of fine grained actions than a state machine.

 

Squad level tactics could be sent to soldiers via their individual blackboards, but I think it would be easy enough to build some kind of hybrid data structure available to the squad and it's members where a soldiers requests to the blackboard are automatically scoped to their own set of knowledge - either data they put in the board or data that was set by the squad manager... Hmm, fun programming problem.

 

Thank you for your input - it helped me solidify my plan quite a bit.


Edited by jdean300, 08 February 2016 - 01:40 AM.


#4 Alberth   Members   -  Reputation: 4282

Like
1Likes
Like

Posted 08 February 2016 - 05:09 AM

Sorry to possibly throw a wrench in your plans.

 

I have exactly 0 experience in making an AI, but have been reading about various tactics in implementing things, as they look interesting.

 

I know FSMs (but in a different context), and browsed BTs a bit (and like you I have problems picturing its execution).

Recently I ran into GOAP (goal oriented action planners). In GOAP, you let go of rigid order in decision making, and instead have individual actions that you combine into achieving a goal.

 

I cannot tell you how this compares to FSM or BT, or even if it actually works, due to my 0 experience, but it sounds like this may be an alternative that could be of use, for some part of the decision making.



#5 AllEightUp   Moderators   -  Reputation: 5265

Like
2Likes
Like

Posted 08 February 2016 - 07:47 AM

As Sean say's there is no hard either/or choice to make, FSM and BT are inherently mixable.  On the other hand, I have shipped titles with only FSM's and others with only BT like approaches.  When I have mixed I usually break things down into two groups, items with well known and fixed rules defining entry/exit/transition use FSM and items where the rules are a bit more sloppy become BT's.  For instance, a relatively common FSM state: moveTo.  It moves the actor from point a to b and exits only if the target has been changed or reached, an interrupting event such as death, decision interrupt (i.e. a new enemy shows up in target area) occurs etc.  Generally you code such a thing up and reuse it in lots of places and it is a tool you don't have to tweak a lot.  On the other hand, the decision to call moveTo is often based on a list of priorities which BT's make fairly easy, i.e. if I'm low heath and that's a good hiding spot, moveTo, or I'm low health and in cover, don't moveTo, etc.

 

Getting into the more specific of your goals though.  Generally speaking FSM versus BT does not solve for the squad tactic side of the equation.  In this area you generally need an invisible actor which is a representation of the squad and handles the overall intelligence.  Generally speaking this means turning off the individual unit decision making and letting the invisible object be a general planner.  In the past I have done this using multiple levels of FSM and BT where the squad intelligence says things like move into this area which spawns a FSM which moves the individual units to new points in the general area.  The top level intelligence gets a notification when moved or some interesting thing has happened and starts planning the next thing for the squad to do.

 

The hierarchical behavior systems as mentioned are easy to describe but often a nightmare to implement.  So, rather than worrying so much about the one or other choice, I'd suggest you look into planning how you would do something simple like having a squad go to a location and take cover with all the little edge case rules needed such as two units don't try for the same cover, the individually go to their closest cover, sniper units stay to the rear of expected area of action, etc.  Getting that figured out in a hierarchical or other AI system is a massive pain in the ass but when done correctly looks awesome to the end player that watches "smart" behavior of enemies.

 

Hope this gives you some more ideas and refinement.



#6 jdean300   Members   -  Reputation: 254

Like
1Likes
Like

Posted 08 February 2016 - 11:51 AM

I know FSMs (but in a different context), and browsed BTs a bit (and like you I have problems picturing its execution).

Recently I ran into GOAP (goal oriented action planners). In GOAP, you let go of rigid order in decision making, and instead have individual actions that you combine into achieving a goal.

 

 

Thanks for the suggestion, I've read about GOAP before and was planning on exploring them with the squad level actions.

 

As Sean say's there is no hard either/or choice to make, FSM and BT are inherently mixable.  On the other hand, I have shipped titles with only FSM's and others with only BT like approaches.  When I have mixed I usually break things down into two groups, items with well known and fixed rules defining entry/exit/transition use FSM and items where the rules are a bit more sloppy become BT's.  For instance, a relatively common FSM state: moveTo.  It moves the actor from point a to b and exits only if the target has been changed or reached, an interrupting event such as death, decision interrupt (i.e. a new enemy shows up in target area) occurs etc.  Generally you code such a thing up and reuse it in lots of places and it is a tool you don't have to tweak a lot.  On the other hand, the decision to call moveTo is often based on a list of priorities which BT's make fairly easy, i.e. if I'm low heath and that's a good hiding spot, moveTo, or I'm low health and in cover, don't moveTo, etc.

 

Getting into the more specific of your goals though.  Generally speaking FSM versus BT does not solve for the squad tactic side of the equation.  In this area you generally need an invisible actor which is a representation of the squad and handles the overall intelligence.  Generally speaking this means turning off the individual unit decision making and letting the invisible object be a general planner.  In the past I have done this using multiple levels of FSM and BT where the squad intelligence says things like move into this area which spawns a FSM which moves the individual units to new points in the general area.  The top level intelligence gets a notification when moved or some interesting thing has happened and starts planning the next thing for the squad to do.

 

The hierarchical behavior systems as mentioned are easy to describe but often a nightmare to implement.  So, rather than worrying so much about the one or other choice, I'd suggest you look into planning how you would do something simple like having a squad go to a location and take cover with all the little edge case rules needed such as two units don't try for the same cover, the individually go to their closest cover, sniper units stay to the rear of expected area of action, etc.  Getting that figured out in a hierarchical or other AI system is a massive pain in the ass but when done correctly looks awesome to the end player that watches "smart" behavior of enemies.

 

Hope this gives you some more ideas and refinement.

 

Thank you very much for your suggestions. Regarding the invisible actor - that's exactly how I was thinking about it actually. I hadn't thought to spawn an FSM (or even a BT) for a certain goal however, and will definitely explore that.

 

When I said I was going to use an FSM for squad level actions, I definitely wasn't thinking it would be the golden ticket that would solve everything, and I might not even implement it as a typical FSM, but I think the general concept of states with well defined transitions between them lends itself well to the high level structure of a squad AI.

 

Definitely just need to start putting stuff together.



#7 Norman Barrows   Crossbones+   -  Reputation: 5253

Like
2Likes
Like

Posted 08 February 2016 - 12:17 PM

i find a good approach is to define the desired behavior first.  just write down a prioritized set of rules of behavior.

 

this will often indicate which parts are simply prioritized conditions that the unit should respond to (behavior or decision tree, IE an big if then else statement), and which parts are more FSM like behavior (transitions between different states, such as "graze, "flock", wander" and "migrate" for wild animals in Caveman 3.0 which are not in combat or hunting prey), and which call for something else.

 

for spatial analysis, influence maps seem to show promise. generation time is short, lookup time is short. could be a good alternative to pairwise comparison of targets, or targets and locations.

 

note that different algos may or may not always yield optimum results.  a correctly programmed Btree or FSM should always yield optimal results - its a simple garbage in garbage out proposition. more "fuzzy" algos, such as weighted decision systems and planners, may yield less predictable - but perhaps sometimes sub-optimal - yet still viable -behaviors.

 

also don't overlook "hierarchy of subsystems" as an AI architecture approach.  top level behaviors might be Btree, FSM, etc, but the code that responds to those conditions might be FSM, planner, weighted decision system, etc - whatever works best for that particular task. this gives you the flexibility of using any algo at any point that's appropriate, and the power of divide and conquer - the AI can be dealt with on a task by task basis, IE one small bit at a time.


Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

 

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

 

 


#8 Norman Barrows   Crossbones+   -  Reputation: 5253

Like
1Likes
Like

Posted 08 February 2016 - 12:23 PM

algo selection can also depend on where you want your AI to fall on the predictable vs optimal scale. if you always want optimal behavior, an expert type system is called for - using the AI algos of your choice - typically Btree, FSM, and other "non-fuzzy" rule-based type algos. if you want it to be less predictable at the expense of sometimes dong a less than optimal move just to be less predictable, then a more "fuzzy" algo such as weighted decision system, NN, planner, or simply some randomness  thrown into a non-fuzzy algo is called for.


Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

 

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

 

 


#9 Norman Barrows   Crossbones+   -  Reputation: 5253

Like
1Likes
Like

Posted 08 February 2016 - 12:32 PM

in your particular case, both squad level and unit level AIs are obviously called for, so that's at least two levels of hierarchy.

 

and unit level AI would have lower level subsystems such as the "seek best available cover" AI code. "fire on target", "take opportunity fire", "maneuver for shot" etc.

 

if you want to conceptually visualize the squad level AI as an "invisible actor / general", that's you're business - it should't make any difference.  what it is actually is what you would do if you controlled the squad.  so it IS sort of like an "invisible general".


Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

 

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

 

 


#10 IADaveMark   Moderators   -  Reputation: 3367

Like
1Likes
Like

Posted 10 February 2016 - 03:13 PM

Read.

 

http://intrinsicalgorithm.com/IAonAI/2012/11/ai-architectures-a-culinary-guide-gdmag-article/ 


Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#11 Khatharr   Crossbones+   -  Reputation: 6435

Like
1Likes
Like

Posted 11 February 2016 - 10:25 PM

Sorry to possibly throw a wrench in your plans.

 

I have exactly 0 experience in making an AI, but have been reading about various tactics in implementing things, as they look interesting.

 

I know FSMs (but in a different context), and browsed BTs a bit (and like you I have problems picturing its execution).

Recently I ran into GOAP (goal oriented action planners). In GOAP, you let go of rigid order in decision making, and instead have individual actions that you combine into achieving a goal.

 

I cannot tell you how this compares to FSM or BT, or even if it actually works, due to my 0 experience, but it sounds like this may be an alternative that could be of use, for some part of the decision making.

 

GOAP is really for high-level strategizing. It can be pretty smart, but it's really only good at selecting action states. For a game like Shadowrun it would be simpler, but in a top down squad shooter like OP describes it would likely be hybridized with an FSM or similar.


void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#12 braindigitalis   Crossbones+   -  Reputation: 15182

Like
0Likes
Like

Posted 12 February 2016 - 02:25 AM

Sorry to possibly throw a wrench in your plans.
 
I have exactly 0 experience in making an AI, but have been reading about various tactics in implementing things, as they look interesting.
 
I know FSMs (but in a different context), and browsed BTs a bit (and like you I have problems picturing its execution).
Recently I ran into GOAP (goal oriented action planners). In GOAP, you let go of rigid order in decision making, and instead have individual actions that you combine into achieving a goal.
 
I cannot tell you how this compares to FSM or BT, or even if it actually works, due to my 0 experience, but it sounds like this may be an alternative that could be of use, for some part of the decision making.

 
GOAP is really for high-level strategizing. It can be pretty smart, but it's really only good at selecting action states. For a game like Shadowrun it would be simpler, but in a top down squad shooter like OP describes it would likely be hybridized with an FSM or similar.

You can make squad behaviour with a goap by having enemies exchange world state when they meet. E.g. Two enemies meet in a corridor, one has seen you before at x,y,z and the other hasn't. The first enemy pauses and they exchange information, now the second enemy knows you used to be at x,y,z and they can coordinate a combined plan of attack.

I'm planning on doing this myself to make enemies act like a team. In my case enemies only communicate with members of the same faction/race.

Thoughts?

Games Currently In Development: Firework Factory | Seven Spells Of Destruction | Latest Journal Entry: The claw is gonna get ya! (if the explosions don't!) (04-Apr-2016)


#13 IADaveMark   Moderators   -  Reputation: 3367

Like
2Likes
Like

Posted 12 February 2016 - 10:42 AM

You can do that with any architecture -- not just GOAP. You are confusing the decision reasoner with the knowledge representation layer.


Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#14 Shadax   Members   -  Reputation: 108

Like
1Likes
Like

Posted 18 February 2016 - 04:35 PM

Regarding an architectual mix between BTs and FSMs: Crytek uses exactly that approach. Basically the AI's decision making system is a classic BT with all the typical nodes (Sequence, Selector, Loop, Action, custom Decorators, etc.). Plus, it offers a StateMachine node that houses multiple State nodes. These are decorators that in turn house a single BT on their own. Transitions between States of the particular level a BT lives in can be triggered arbitrarily from within that BT by sending a signal. So, instead of having to propagate success or failure all the way up in the hierarchy, a signal can be sent, which gets handled by the StateMachinde by activating different State (i. e. BT).

 

 

Cheers!






Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.




PARTNERS