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 
                       BehaviorResult.Failure;
                   // Exit the function
                   yield break;

               case BehaviorResult.Running:
                   // Notify parent that
                   // we're still running
                   yield return 
                       BehaviorResult.Running;
                   // Continue the loop
                   continue;
           }
       }
       NextChild:
       ;
   }
   // 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...