At GDC ‘07 there was a talk about behavior trees. It’s the type of AI that Halo 2 uses, as described by described by Damian Isla at GDC ‘05. The first part of this year’s talk was by Lauren McHugh who’s working on the AI for Spore — EA’s delayed mega-hit for 2009. (You can get the audio without slides for a whole $8 from the store.)
Anyway, Lauren mentioned that the programmers are responsible for creating the behavior trees in C++. While it’s not ideal for turn-around times, it’s certainly a very powerful approach. In fact, I’ve already implemented this in Game::AI++ as it’s a pretty good starting point for creating game behaviors — even if it doesn’t involve the designers directly.
Macros or Templates
On Spore, it seems they make heavy use of macros to do this. These days, however, I try my best to avoid them, so I went for a template-based implementation to see how it would turn out. The results are quite encouraging! The idea is to get the C++ compiler to help build valid trees as much as possible, and try to provide a simple syntax.
Here’s what it looks like:
Node* behavior = TreeBuilder() .composite<Sequence>() .node<BehaviorSay>() .text("Going to get some food!") .end() .composite<ProbabilitySelector>() .node<BehaviorGoTo>() .destination("Kitchen") .style(Sneak) .end() .node<BehaviorGoTo>() .destination("Pandry") .style(Run) .end() .end() .end();
As you can see, it’s just a long sequence of function calls, like traditional C++ stream modifiers but for a tree structure. There are a few cool things about this:
You can only add nodes where it’s legal. The compiler will fail if you add leaf to a leaf, or add multiple nodes to a decorator.
Each leaf node takes named properties instead of arguments that are ordered in the constructor. It’s much more obvious what’s going on, and it’s less likely to require changes when the behaviors change.
When there are compilation problems with the tree syntax, they are exposed directly and not hidden inside macros.
So once you get used to the one or two common compiler errors when building trees, it’s a much easier workflow.
How It Works
The implementation, however, is certainly interesting (to say the least). I will be releasing my implementation in a few weeks with Game::AI++, but it’s barely over a hundred lines of code… so here’s a description in the meantime.
All the member functions like node() and composite() are template members. They return another tree builder that’s of the correct type, and only provides the valid functions in that context. Specifically:
The composite() function returns a CompositeBuilder, which has all the builder functions defined. It takes the parent type in the tree as a template parameter, and returns the parent of the exact type when you call .end()
The node() function returns a LeafBuilder, which inherits from the exact settings class for the behavior in question. This provides property setters like .destination(), or .style(). No builder functions are defined for these nodes since they are leaves! Calling .end() also returns a parent builder of the exact type in the tree.
The decorator() function returns a DecoratorBuilder which does the same as the composite. The only difference is that after building any node, it returns a LeafBuilder object which can’t accept anymore nodes.
I’m not entirely sure if it’s possible to implement this in fully standard C++. There’s a challenge for you! My understanding is, for it to work, you’d need to have a custom class created from templates for every call in the stream (rather than every level in the hierarchy). As far as I can tell, this requires mutually self-referential template inheritance — which won’t compile.
Back down to earth, you can implement this rather easily with reinterpret_cast though. It’s not ideal, but it’s fully safe. You’re not changing any types or casting any data, they stay exactly the same. You’re only casting to provide a different builder interface.
- Curiously Recurring Template Pattern
- You might need the CRTP to expose the node property setters that return the correct type. Use the access to the derived class type to cast your builder to the correct type.
- Mixin Builders
- Try to make each builder function in its own mixin class; it makes things easier to reuse when creating Builder classes that provide different options.
It’ll probably take a good C++ coder a few hours to figure this out, but it’s certainly worthwhile. It makes for very interesting language experiments if nothing else!
What about you, do you use macros to create your AI behaviors? Would you consider using templates?