Article

Type-Safe Behavior Tree Builders for C++

Alex J. Champandard on July 13, 2007

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:

  1. 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()

  2. 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.

  3. 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.

Practical Tips

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?

Discussion 12 Comments

gware on July 14th, 2007

I am a bit surprised by this implementation note :) It's very interesting to see this kind of approach. I'm eager to see how it will scale and be used. There's so much to say, I don't know where to start my comments :) First, my initial thought is : "is he creating an xml parser from c++ templates?" Correct me if I am wrong but using templates this way won't let you create new trees at runtime (because of the full template instanciation). Knowing that, I would say that you are describing "data" in C++. I'm not an XML fan, but I do not understand where is your gain to code and use such a tree structure. You could get the same type safe "data building" through the use of a schema file for your xml. Then you could create a binary file from your xml to avoid the cost of using xml at runtime. I'm not much a macro fan. It can be very usefull at times, but I try to avoid using them too much while designing such systems. If I were building this kind of system, I would try to extract behavior from code files, ask the developpers to use XSD files to describe the relations between behaviors, and use xml (possibly binarized ones) to create the tree. Cons : - you have to "extract" and maintain a list of behavior from the C++ side - ask your devs to use XSD files where they whould probably prefer using good old C++ - have a framework using xml - have a way to ensure sync between data and code. Pros : - validity is checked off-line, even before compile time (avoiding compile time for some "data-only" modifications) - you can use lots of tools to visualize behaviors relationships (a tool to show the xsd, visual is doing that for example). - XML files can also be graphically displayed (you'll be able to fully examine your behaviors without having to read any code, nor xml nor c++) - No run time cost if you use a binarized version of your xml. (using a model view controller pattern you can easily binarize your xml and use the data at runtime) - You still will be able to create (and save) behavior trees at runtime using a standard xml implementation (is it useful?). - No compiler related problem while using different toolchains. I'm not sure this is a good way to go, but from my experience it's working. Enough about this, I believe there's lots of different ways to do stuff. But I'd very much like to know what are your motivations for building this system using templates (is there run time possibilities I did not see ?). I can't wait for game::ai++ beta, reading your code ... and maybe comment it ;)

gware on July 14th, 2007

I am a bit surprised by this implementation note :) It's very interesting to see this kind of approach. I'm eager to see how it will scale and be used. There's so much to say, I don't know where to start my comments :) First, my initial thought is : "is he creating an xml parser from c++ templates?" Correct me if I am wrong but using templates this way won't let you create new trees at runtime (because of the full template instanciation). Knowing that, I would say that you are describing "data" in C++. I'm not an XML fan, but I do not understand where is your gain to code and use such a tree structure. You could get the same type safe "data building" through the use of a schema file for your xml. Then you could create a binary file from your xml to avoid the cost of using xml at runtime. I'm not much a macro fan. It can be very usefull at times, but I try to avoid using them too much while designing such systems. If I were building this kind of system, I would try to extract behavior from code files, ask the developpers to use XSD files to describe the relations between behaviors, and use xml (possibly binarized ones) to create the tree. Cons : - you have to "extract" and maintain a list of behavior from the C++ side - ask your devs to use XSD files where they whould probably prefer using good old C++ - have a framework using xml - have a way to ensure sync between data and code. Pros : - validity is checked off-line, even before compile time (avoiding compile time for some "data-only" modifications) - you can use lots of tools to visualize behaviors relationships (a tool to show the xsd, visual is doing that for example). - XML files can also be graphically displayed (you'll be able to fully examine your behaviors without having to read any code, nor xml nor c++) - No run time cost if you use a binarized version of your xml. (using a model view controller pattern you can easily binarize your xml and use the data at runtime) - You still will be able to create (and save) behavior trees at runtime using a standard xml implementation (is it useful?). - No compiler related problem while using different toolchains. I'm not sure this is a good way to go, but from my experience it's working. Enough about this, I believe there's lots of different ways to do stuff. But I'd very much like to know what are your motivations for building this system using templates (is there run time possibilities I did not see ?). I can't wait for game::ai++ beta, reading your code ... and maybe comment it ;)

alexjc on July 14th, 2007

Why use XML if you have the option of not using XML? :-) You're completely right about going data driven. It's typically the best approach in my opinion. But it takes a lot of work, a good tool chain, and if (like Spore) only programmers add new trees, then it's easier to just use C++ at first. The advantage of using C++ is that everything is self contained and easy to work with using existing editors and compilers. Then, using templates makes the whole thing easier to read and write, plus you get type safety for free. This solution indeed creates fixed tree types at compile time, but you can instantiate them in any way. To have more variation, you would: [LIST] [*]Build modular sections of trees and combine them together dynamically. (It's simple to do with a behavior lookup table.) [*]Call tree templates from parameterized functions that can change at runtime, so the data within the trees is easily changed per-actor. [/LIST] To be sure, for Game::AI++ there will be a data-driven tree format, but using this approach, many low-level behaviors can be assembled directly into the engine if necessary. Alex

alexjc on July 14th, 2007

Why use XML if you have the option of not using XML? :-) You're completely right about going data driven. It's typically the best approach in my opinion. But it takes a lot of work, a good tool chain, and if (like Spore) only programmers add new trees, then it's easier to just use C++ at first. The advantage of using C++ is that everything is self contained and easy to work with using existing editors and compilers. Then, using templates makes the whole thing easier to read and write, plus you get type safety for free. This solution indeed creates fixed tree types at compile time, but you can instantiate them in any way. To have more variation, you would: [LIST] [*]Build modular sections of trees and combine them together dynamically. (It's simple to do with a behavior lookup table.) [*]Call tree templates from parameterized functions that can change at runtime, so the data within the trees is easily changed per-actor. [/LIST] To be sure, for Game::AI++ there will be a data-driven tree format, but using this approach, many low-level behaviors can be assembled directly into the engine if necessary. Alex

Dom on July 20th, 2007

I am using Virtools, it's is a commercial authoring system for 3d apps. At it's core you have the "behavior" manager. A behavior is basically defined as a tree of ... let's say components. You can also attach sub trees (behavior subgraphs) to a behavior tree. A behavior tree can also be attached onto an entity - in that case it's called a "script". The interesting aspect is the way you create a tree: you compose them visually. There are not many screenshots of well formated examples online, but I found one from [URL=http://www.flashbangstudios.com/tests/schematicexample/pics/x__debug_shake.png]Matthew[/URL] This one contains many low-level elements, but using high level elements you can implement complex behaviors very fast. Especially if you reuse "sub"-trees. Information can be stored in parameters attached to the tree, or you can attach any number of "attributes" to entities. I am using the later intensively to define the state of an entity. The same behavior can act differently depending on which attributes it finds on his owner or their values. For example you can branch to a different sub-tree (or better for performance: activate another script). Unfortunately Virtools lacks some higher order elements to organize these behavior-scripts: FSMs etc. have to be created manually using the system. Great blog! Thx a lot for the very interesting articles.

Dom on July 20th, 2007

I am using Virtools, it's is a commercial authoring system for 3d apps. At it's core you have the "behavior" manager. A behavior is basically defined as a tree of ... let's say components. You can also attach sub trees (behavior subgraphs) to a behavior tree. A behavior tree can also be attached onto an entity - in that case it's called a "script". The interesting aspect is the way you create a tree: you compose them visually. There are not many screenshots of well formated examples online, but I found one from [URL=http://www.flashbangstudios.com/tests/schematicexample/pics/x__debug_shake.png]Matthew[/URL] This one contains many low-level elements, but using high level elements you can implement complex behaviors very fast. Especially if you reuse "sub"-trees. Information can be stored in parameters attached to the tree, or you can attach any number of "attributes" to entities. I am using the later intensively to define the state of an entity. The same behavior can act differently depending on which attributes it finds on his owner or their values. For example you can branch to a different sub-tree (or better for performance: activate another script). Unfortunately Virtools lacks some higher order elements to organize these behavior-scripts: FSMs etc. have to be created manually using the system. Great blog! Thx a lot for the very interesting articles.

alexjc on July 20th, 2007

Hi Dom, It's fascinating to hear how Virtools works. I've not really looked into it myself yet. From the image, it seems like the tree represents data flow. You connect things together and the interpreter takes care of passing data around, which results in computation. A lot like Maya's hypergraph, or even Unreal's Kismet. I'm sure this C++ builder would work for such data-flow trees also, but the behavior trees in Halo, Spore, or Game::AI++ are control flow trees. Parent nodes in the tree activate/search their child nodes... Data is only optionally passed around. Both achieve the same thing I think, but it's just a different way of looking at the solution! Anyway, thanks for the heads up. Alex

alexjc on July 20th, 2007

Hi Dom, It's fascinating to hear how Virtools works. I've not really looked into it myself yet. From the image, it seems like the tree represents data flow. You connect things together and the interpreter takes care of passing data around, which results in computation. A lot like Maya's hypergraph, or even Unreal's Kismet. I'm sure this C++ builder would work for such data-flow trees also, but the behavior trees in Halo, Spore, or Game::AI++ are control flow trees. Parent nodes in the tree activate/search their child nodes... Data is only optionally passed around. Both achieve the same thing I think, but it's just a different way of looking at the solution! Anyway, thanks for the heads up. Alex

pachanga on November 8th, 2007

This is a very fascinating approach and I can't wait to play with your Game::AI++. The only thing which worries me a bit is how to make this builder build trees dynamically using some sort of file descriptor(e.g XML) and if it's possible at all. Gabriel Ware mentions possible problems due to full template instantiation but, as you commented later, there are work arounds. And I'm just curious, what do you think about C++ code generation before the build stage using file descriptors? It's not that flexible as dynamic tree building yet should be easier to implement. And it can be very helpful on early stages of development for the game designer, since he would like to work with some sort of high level tree builder GUI rather than coding C++ himself.

alexjc on November 10th, 2007

Hi [B]Pavel[/B], Thanks for your comment. I see this tree builder as a compile time alternative, where as XML is runtime. If you want to mix the two ways of loading behavior trees, then it makes sense to integrate the two, otherwise just stick with XML if you use it. I've used code-generation before (on my FEAR project), and I'm still torn. I mean, meta-programming is great in a language that supports it elegantly, but with C++ it's often a dirty hack and codegen is a pain to manage in a build process. You really have to make sure that nobody edits the generated code, and make sure that you design the architecture so you can somehow override changes that are auto-generated. It's certainly a skill to get it right. But one thing I have used successfully is using code-gen to create behavior trees in [TT]Lua[/TT]. I used Lua both as at API to create nodes in an underlying C++ engine (essentially as a replacement for XML), and I've also used Lua to generate whole behavior trees. That's something I want to look into more; it's got promise. :-) Alex

pachanga on November 11th, 2007

Alex, thanks for replying! Am I right in thinking you want to make someday a high level Lua tree building interface for your Game::AI++ library? If so, I'm very much intrigued ;)

scypior on September 2nd, 2008

I know it's an old post, but I've just read it and I am astonished by cleverness of this idea. Being a C# guy lately(programmed in C++ before) I started to think about adapting this solution, that could be equipped in a visual editor very easily. All that would be needed is some kind of code generation(very simple in that case) plus some library like CSharpCompiler, and one will be able to create such trees in runtime:)

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!