Sponsored By

In this reprinted <a href="http://altdevblogaday.com/">#altdevblogaday</a>-opinion piece, Relic's Jesse Cluff explains why you should use behavior trees, and why you might consider them over finite state machines.

Jesse Cluff, Blogger

September 14, 2011

4 Min Read

[In this reprinted #altdevblogaday-opinion piece, Relic Entertainment's Jesse Cluff explains why you should use behavior trees, offering an example why you might want to consider them over finite state machines.] I'm going to assume you're familiar with behavior trees already, however I would still consider this post as introductory in nature. So why use behavior 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. As the state machine grows these transitions become a huge tangle and changing the structure of the state machine becomes all but impossible (hierarchical finite state machines do mitigate some of this tangle reasonably well though). Enter behavior trees, where the execution of a particular subtree is only dependent on the portion of the tree that leads directly to it. Making large scale changes to tree structure is still non-trivial, but it is at least doable. Now, what about those state transitions we got rid of? Was the gain in flexibility really free? The answer of course is no. First, there is the very obvious performance cost that results from having to repeatedly validate the conditions for the current behaviors. Naively, every time the tree is refreshed you must recompute all your conditions to ensure that your current behaviors are still valid. This does have the nice side effect of making behaviors very reactive to changing conditions though. And you never have the problem of being stuck in a state because there wasn't a valid transition out of it. But is there another cost besides performance? One I've rarely heard mentioned is that behavior tree logic can be somewhat unintuitive. This is due to the fact that the conditions that must be true for a behavior to start must stay true for it to continue to run! This is completely different than state machines, where you only need the condition to transition to the state. State machine logic seems to map more naturally to most real world systems (where the conditions that trigger a state are different from the conditions that end it, as opposed to behavior tree logic which only has one set of conditions that has to stay true for a behavior to run). Let's think of a concrete example. Say an agent needs to be between 4 and 5 meters from their target to start a particular attack, and this attack requires specialized AI to be running throughout the execution. Now of course the attack doesn't stay within this initial boundary. If you're dealing with a state machine that's fine, all you needed were the starting conditions. But a behavior node might need different conditions for starting and remaining active. Typically the conditions for the node need to include some kind of boolean OR wrapper node that holds both the initial conditions and the conditions required for it to remain active. This makes for messy behavior trees that can be hard to understand and difficult for new users to create. But one very simple way to deal with this problem is with a decorator called a Latch Decorator. This decorator doesn't do anything if its child returns false (it just returns false itself), but once its child returns true, it "latches on" and stays on. You can then group your conditions and attach them to this decorator and once the conditions are true to start your behavior they will stay true. So when will it turn off you might ask? Well you can have it latch for a given number of seconds if you wish, but typically you just leave it on until the node resets once the behavior that follows it is finished. The mechanism for this is implementation specific, but as an example the behavior following it will eventually return false, this could cause the parent of this subtree to not evaluate it on the next update. Nodes typically detect this for the purposes of either shutting down or reinitializing when control flow returns to them. Anyway, quite a lot of discussion for such a simple little node. But the devil is in the details isn't it? [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]

About the Author(s)

Daily news, dev blogs, and stories from Game Developer straight to your inbox

You May Also Like