Tuesday, June 9, 2009

Behavior Tree & Navigation Meshes

Behavior Tree

Today i've been busy implementing a behavior tree in C#, which was suprisingly easy!

(In case you don't know what a behavior tree is, read this NOW!)
Update: Apparently i the link i provided is in a part of that website which requires (free) registration..
However, the same article is also available (oddly enough) in the publicly accessible part of the website, but split in 3 parts (go figure).
Here are the links.

One of the more complicated parts of the tree is that you don't run the entire tree each frame (which is a good thing!), so it has to be split into small pieces.

I realized that i could probably abuse the whole enumerator/yield construction in C#, and came up with the following solution:
public class Sequence : IBehaviorTransform
public IEnumerable<BehaviorResult> Process()
   foreach (var node in Children)
       foreach (BehaviorResult result 
                in node.Execute())
           switch (result)
               case BehaviorResult.Success:
                   // If child-node executes
                   // successfully, continue 
                   // to the next node
                   goto NextChild;

               case BehaviorResult.Failure:
                   // Notify parent that 
                   // we've failed ..
                   yield return 
                   // Exit the function
                   yield break;

               case BehaviorResult.Running:
                   // Notify parent that
                   // we're still running
                   yield return 
                   // Continue the loop
   // Finally, if all nodes are processed
   // without failing we return success
   yield return BehaviorResult.Success;

Every IBehaviorTransform implementation would return an IEnumerable of BehaviourResult, and as i enumerate my enumerable once each frame, it'll just magically work ;)

Navigation Meshes

Another rough idea of mine is about navigation meshes (Look here if you don't know what those are).

I haven't played with them yet, but it seems to me that it should be possible to simply perform A* on the traversable edges (that are wide enough for the current entity) to find a path.

One problem with navigation algorithms is that they're relatively expensive and either need to be stored and/or re-calculated every x frames..
So you really want to only calculate a rough high level path, and use some more refined (maybe completely different) algorithm at a lower level.

Suddenly i realized that quite often you'd end up with long paths in any navigation mesh where several connected cells/nodes form a chain.
Which means that you could basically just skip the whole chain during the high level path finding, and only check the nodes/cells where you need to make a decision!

You'd probably need to store some basic stuff like the minimum portal size so you can tell in advance if an entity will actually fit through that chain. And you'd need to be able to update the chain in case it's obstructed.

Maybe information about obstructions could be stored at an entity level?
(probably too memory heavy though)
Entities would then expect a pathway to be clear, but when they arrive it's blocked (useful for planning an ambush?), and then will either try to remove the obstruction (if possible and doesn't require too much time and energy) or try another route instead...


  1. That link for behavior trees description is behind some registered only section of that website. I found this helpful overview of behavior trees as implemented in Spore:


    That yield construction and continuations in general are awsome for easy state machine implementations. I wish certain ancient languages had built in support for that.

  2. Thanks for the heads up. I've added links to the same article but publically accessible, which oddly enough is also available but split in 3.

    Thanks for the link!

  3. It defintely makes sense to just find a rough path and then fine tune it.

    Detour[1] does just that. The path finder just finds a corridor of connected polygons and then the final string pulling is done every frame. The greatest advantage is that if the agent deviates from the path, say because it needed to avoid another agent, it does not matter. Also, you dont need to calculate the whole straight path, just the next few corners so you can calculate your steering velocity right.

    Another advantage of that is that if you are following another agent, you can do path finding once, and then adjust just the head and tail of the path as the agents move!

    (shameless plug) If you need to get started with navigation meshes, or just want some data to play around with, take a look at Recast and Detour[1] ;)

    You may also want to google for TRA*, it is a navmesh abstraction algorithm, similar than your skipping a chain idea.

    [1] http://code.google.com/p/recastnavigation/

  4. That looks very interesting, Thanks for the link!
    I'm definitely going to take a closer look at that project of yours :)