Creating an AI Behavior Tree in C# - How?

Question

I am attempting to create a "behavior tree" using C#.

For anyone who doesn't know, a behavior tree is basically a framework that you can construct an AI around. There are Sequencers, Selectors, Decorators, composite actions, and other things.

I have found a single library that has implimented a "behavior tree" in C#, located here (http://code.google.com/p/treesharp/) but I cannot understand how to actually use it since there is no example code I can draw from. Could anyone here perhaps make some simple example code that shows how to actually use this framework.. or perhaps you know of another way to impliment a behavior tree in C#?

Thanks so much!

Solution 1

I just looked at that implementation and I find myself wondering why so much code is needed for something relatively simple.

From what you say, you want a simple way of composing behaviours. A behaviour here, I presume, is a mapping from a state to zero or more actions by an agent. You can model this very easily using C# lambdas. For example:

Action Selector(Func<bool> cond, Action ifTrue, Action ifFalse) {
  return () => { if cond() then ifTrue() else ifFalse() };
}

Action Sequencer(Action a, Action b) {
  return () => { a(); b(); }
}

The leaves of your tree are simple Actions that do something appropriate to the state. You "run" a tree simply by executing it.

If you want to get fancy, you can parameterise this scheme to make the state explicit.

Hope this helps.

---- Addendum ----

Jason asked for an example of how you could use this approach, so here's a simple "AI" patrolling guard example (I assume WorldState corresponds to a description of the environment at the time the behaviour tree is evaluated):

Func<bool> ifPlayerIsInSight = () => ...true iff WorldState shows guard can see player...;

Action shootAtPlayer = () => { ...aim guard's weapon at player and fire... };

Func<bool> ifUnderFire = () => ...true iff WorldState shows guard hears player gunfire...;

Action takeCover = () => { ...guard runs for nearest shelter... };

Action walkBackAndForthGuardingDoorway = () => { ...default guard patrol behaviour... };

Action patrollingGuardBehaviour =
  Selector(ifPlayerIsInSight, shootAtPlayer,
    Selector(ifUnderFire, takeCover,
      walkBackAndForthGuardingDoorway));

To make the guard do something, just call patrollingGuardBehaviour(). Note that the various subactions and tests can be implemented as methods with the right signatures rather than inline as lambdas. You can add other combinators to Selector and Sequencer, e.g., for parallel activity.

Solution 2

It looks like one of the devs behind TreeSharp, apocdev, has some code that uses TreeSharp for some kind of spell-casting World of Warcraft player.

Here's a snippit:

public Composite CreateSpellCheckAndCast(string name)
{
    return new Decorator(
        ret => Spells.CanCast(name),
        new Action(ret => Spells.Cast(name)));
}

I'm not certain, but the usage here seems pretty simple: the Decorator class looks like it checks a predicate (Spells.CanCast) before trying to execute some action (Spells.Cast).

So a Composite is perhaps an Action that can do several things, e.g. check a predicate beforehand or execute several actions in sequence.

apocdev's blog mentions this overview of behavior trees, which links to more general descriptions of sequences, selectors, and decorators.

Solution 3

C# lambdas get expensive when they involve closures as this will cause allocations at every frame/iteration of your BT. You can avoid closures using a blackboard, but there is an easier approach.

You can implement behavior trees using the short-circuiting conditional operators && and ||. This approach is illustrated here: https://github.com/eelstork

Then the patrol example would look like:

Status Patrol()
    => (playerInSight && Shoot(player)) 
    || (underFire && TakeCover())
    || GuardDoorway();

Comments

[Jason]

Rafe... behavior trees are a bit more involved actually... let me try to simply explain them: The tree starts with a root.. and then it branches into seperate branches of logic from there. Each branch has a "filter" that decides whether or not the AI needs to take that branch or not. There are also "sequencers" that run a sequence of actions, returning upon the failure of any action, and "selectors" that run actions until a success is found (disregards failures). There are other things, but that is the core of it. Could we talk about this a bit more over chat somehow?

[Jason]

I'm just really confused at how I could actually impliment something like that in C#.. your example is really good but.. again I can't really understand it. Maybe for your implimentation you could write a little example that would show actually using the structure?

[ftt]

First you build the tree: you define actions and when (conditions) and how (in parallel, sequentially, etc.) they are executed. For simplicity, start with a tree that always starts execution from the root node and chooses its child(ren) depending on current conditions (sensory input). There are many implementation details and improvements, but that's the simplest workflow. Are you sure you understand BTs as a concept? If you're not, try aigamedev.com/insider/presentations/behavior-trees (free registration required) and their forums.

[Jason]

I understand the idea fairly well.. it's the C# that's getting in the way as I am still new to the language. :) The tree basically will have many branches and sub branches.. and sub sub branches etc.. so how can I actually construct that with C#? Nested If and for each loops = not a good idea right? haha :) Is there any example code out there I could actually look at? With other topics.. usually I learn by examining other people's code and seeing how things interact while reading about the topic at the same time.. some example text would be swell! :)

[Jason]

Rafe is there any way you could type a short example of a small "tree" of sorts created using lambda and your structure?

[Cerin]

Unless this library includes some mechanism to learn these trees, the whole idea seems indistinguishable to me from basic manually written procedural logic.

[Rafe]

Chris S - I agree, you could just write these as procedures. The compositional approach here does allow for on-the-fly generation of new behaviours. Regarding learning behaviours, that's a whole different kettle of fish.

[Jason]

Yes the whole idea of behavior trees is modularity. You use lookup tables for base goals to figure out what must be done to satisfy that goal instead of building an actual massive tree. :) Rafe, thank you so much for the extra code. Super helpful!

[Jason]

And just to get that straight rafe.. at the end of your code you made a selector.. inside of a selector, right? :)

[roundcrisis]

seems like most links on this answer are broken :(

[Nate Kohl]

@Miau: Yeah, it looks like apocdev's blog is down. I'll leave the links for now, in case it comes back up in the near future.