Behavior trees are an increasingly common way to implement decision making and control systems for game NPCs. As more studios use them, a diversity of design patterns and implementation techniques is appearing. Sometimes it can become rather difficult to draw the line between other techniques; to what extent is this AI a behavior tree?
In an interview late last year with Christian Gyrling, AI & Animation Programmer on UNCHARTED 2, he explained the approach that Naughty Dog uses to implement its combat AI. Their approach draws ideas or resembles utility systems, heuristic planners, or motivational graphs. In this article, you'll find the transcript from the UNCHARTED 2 interview (now available here for a limited time), some follow-up question that Christian was kind enough to answer by email, and my analysis.
[This is a transcript of an interview conducted live online with Christian Gyrling on December 6th, 2009 as part of AiGameDev.com PREMIUM. You can get access to the full high quality audio/video recording from this page for a limited time.]
Alex Champandard: You mentioned using some kind of behavior tree for the AI, was that also using the same system that the rest of the game used, this interpreted hierarchical state-machine like system?
Christian Gyrling: So... if there are other systems using that?
Alex: My question is, what do you call the behavior tree, this "modified" behavior tree? [Is it the same as the HFSM?]
Christian: Oh, no. To me, when I think of a behavior tree, it’s usually that you have some way of going through your nodes and they are either considered to be like in random, like you pick a random node and it will be your decision, and you’ll have them in some kind of priority order or in sequence. We basically — this doesn’t scale super well, but — we basically allow all behavior nodes to make a more informed decision.
Like "going to cover" for example; you might say that "going to cover" would be something that’s perfect for me to do right now, but to actually know if you want to go to cover, you need to A) find cover positions, and there might or might not be any at all, or there might not be any available — and the second thing is, B) that the one and only cover that exists might be so bad that you would actually prefer to just stay where you are, go to some other place and just stay out in the open to fire. So what we do is, we allow all behaviors to ask for information about the world points, visability, stuff like that, and then, we rank them collectively; so it’s more of a kind of hive-mind behavior tree... *laugh*
Alex: A bit like a voting system where you'd have each one of them give you a score and you pick the one with the highest score?
Christian: Effectively. Actually it’s not even the behaviors, we have another system that does the tactical decision making. The behaviors are more responsible for what and where, and we have another system that selects which one will be most appropriate.
[This follow-up interview was conducted with Christian Gyrling via email earlier this year.]
Alex Champandard: Is it just one level of the tree that's a "hive mind"?
Christian Gyrling: It's like a behavior tree where the selection of the behavior is implicit instead of explicit. Each behavior that is a potential candidate for running will be asked to provide a series of tactical positions. They are then gathered and evaluated for such things as LOS and distance to target/friends and then the 'cost' is weighted. The behavior with the chosen point is selected. It sounds pretty good and it has some advantages and some natural behavior but it can also become slightly uncontrollable and is not as easy to work with when it comes to creating fun moments and situations where the AI essentially is carrying out short scripted (but interruptible) sequences.
We are using something very similar to the blackboard solution that Damian was talking about to allow for decoupled systems and to allow frame-delayed responses as well as LODing and throttling of the use of system resources such as # of raycasts or update rate of perception data.
Alex: How many behaviors are competing for activation?
Christian: Usually no more than 10 at any given time. A few of our behaviors are more involved such as "combat in the open" which for other companies might be 10-15 behaviors for that alone.
Alex: What's the scope of a behavior (e.g. running time) within this hive mind?
Christian: Any behavior is running for as long as it wants to unless asked to stop. The AI will re-evaluate the potential behaviors every second or so unless shot or otherwise interrupted.
Alex: Are these behaviors self-contained or can they potentially have dependencies?
Christian: They are self-contained and the AI will work with any of the behaviors or all of them and the number does not matter.
Alex: Are the evaluation functions complex?
Christian: Not especially if I compare it to other engines I've worked on. It is however more separated in the sense that the evaluation is clearly removed from the behavior itself. This is a nice feature which allows for nice throttling of the processing needed to select a behavior. Most AI systems do use LOS, distances, timers and more to affect the selection of any given behavior in a behavior tree.
Alex: Did you spend a long time tweaking the evaluation functions?
Christian: Yes, this is always something that is hard because the tweaking is what makes the AI. Fortunately the tweaking is mostly exposed to our combat designer(s) so they play with the numbers to get the AI to do what they want. It is all configurable and they can swap out sets of weights at runtime to achieve changes in behavior based on time, regions, enemies killed and more...
Alex: Does the system sometimes feel too complex to extend?
Christian: Yes, and we have a few solutions planned for our future AI. :)
Many thanks for Christian for taking the time to do both of these interviews!
The approach from Naughty Dog that Christian describes borrows elements from many different techniques. I find it fun and educational to dig into these topics, so here's my comparative analysis:
- Heuristic Planners
A planner typically generates loads of solutions (in varying order), and those solutions are evaluated by a heuristic to determine which is worth investigating further. The heuristic also helps compare two existing solutions together, so you can pick the best. In the case of the UNCHARTED 2 combat AI, each behavior generates possible solutions as positions in space, which are then evaluated by a higher-level tactical heuristic with criteria like LOS to enemies, relative position to friendlies, etc. These two approaches are very similar...
- Motivational Graphs & Utility
Motivational Graphs (see the article in AI Game Programming Wisdom 2) are like a tree of behavior with continuous activation rather than boolean. Think fuzzy behavior trees. The approach in UNCHARTED 2 is similar since each behavior instance (e.g. move into a specific cover point) has floating point utility attached to it, and that can be used to rank the different options. This makes the combat behaviors less "boolean" and the decision boundaries are probably less obvious because of it.
- Behavior Trees?
The particular "hive-mind" architecture that Christian described I wouldn't call a behavior tree. You could easily have the lower-level details of each behavior (e.g. MoveIntoCover) managed by a BT, but the top-level will require entirely customized code to have each behavior generate positions it's interested in, return them, and have them evaluated globally.
The big problem with this approach is the same that utility systems suffer from; performance and extensibility. Performance is a tradeoff because you need more CPU/SUP time to evaluate many more pieces of information to be able to tactically rank all these options — but it should result in better behaviors. Extensibility isn't ideal because it's hard to tweak a set of behaviors to work as a consistent whole when you're just working with continuous equations, and adding a new behavior into the mix could throw the whole existing balance off...
It'll be interesting to see how Christian and Naughty Dog tackle this problem in their future games. If you have any ideas on how to resolve these problems don't hesitate to post them in the comments below! (Also be sure to go and watch the full audio/video interview, or read the transcript.)