I have #AltDevBlogADay in my massive RSS subscription collection. I like to skim over the articles during my lunch break. Sometimes you can find some interesting articles on there that'll teach you something new or get you thinking about something old.
This posting by Jesse Cluff the other day was a good refresher on the finer points of Behavior Trees over [H]FSMs for behavior selection. There was one particular excerpt that I completely agreed with and wants to discuss here.
"So why use behaviour trees at all? Finite state machines are actually pretty decent (useful, well understood, and very importantly, intuitive). They have one critical weakness though. All the transitions between states are explicit."
I think he nailed it with this statement. Given a choice between a tree or a state machine, I'll always side with the tree for just this very simple reason. Most engines I've come across that have taken the route of FSM for behavior selection have suffered from the same basic problem: Inability to scale over time. I hear the argument a lot: "This NPC will be very simple and won't have a lot of state changes, so why go through all the trouble of making a large tree structure for only a few states?" If you're ever asked this, remember the appropriate response. "In 6 months time, he'll have a lot more state changes than you're thinking right now. And your 'quick, easy solution' is going to become so muddled and unmanageable, you'll want to rewrite it again and again."
The behavior FSM tends to make the "state" be the "behavior". Remember, a behavior is basically a form that takes input from the world (perception events, gameplay triggers, timers, etc.) and determines what the best way to handle that new information is. But what is required in the machine's state is also the transition rules. In the case of a behavior FSM, those transition rules are better defines as "the conditions that have an NPC change from one behavior to the next" e.g., the player has moved within 5m of me, so I need to stop attacking and start running away.
This means to satisfy the requirements of a behavior FSM, your behaviors will include the inputs needing attention as well as the conditions to change behavior. Sometimes those conditions will be "what must be true to enter this other behavior." Sometimes those conditions will be "what must be true to enter THIS behavior." But in either case, your behavior will have some set of conditions written into it, as well as a list of all other behaviors it can transition in to or out from.
And that means your behaviors aren't going to be module enough to be reused. So when that NPC starts growing and becoming more complex, you'll be modifying all of your behaviors over and over to incorporate that new complex logic. And that problem is going to scale linearly over time, becoming more and more troublesome.
Further on down the road, when you need to make a new type of that NPC (one that doesn't run away because he's braver, and he doesn't want to take cover because he has thick body armor), you're going to be tempted to reuse most of those behaviors. But to do that, you'll be having a lot of fun putting conditional checks around all those transition links and what-not to stop him from running away and taking cover.
The behavior tree on the other hand? It keeps all the transition logic outside of your "behavior" by rule of thumb, freeing your behaviors to be what they're meant to be: input/output decision lists. Need to make a new one? Just find where best it fits in the tree. No need to touch the other behaviors around it. Need to make a new archetype? Just make a new tree and reuse the behaviors you need, omitting the ones that aren't called for.
The tree is superior when you consider the practical ramifications of typical development cycles.
Kevin
