Behaviours grow on trees

While taking a break from collision stuff and Swarms, I felt like getting a head-start on my AI plans. It seems I go on and on about how busy I am, but I still have time to make Kork fight himself:


[You can see I was using Jakob Dankovchik's awesome More Realistic First Person resource, which is why the bots shoot at their own feet while moving.]

What you see is a very, very simple combat AI battle using Behaviour Trees. In case you're not familiar with the concept, I'll outline the basic idea. In short, BTs are meant as a replacement for/upgrade of Finite State Machine AI, and though they do a similar job when you look at the end result, how you reach that result is a bit different. In addition, they allow far more advanced behaviour features than FSMs - for example, if you want the AI character to do a sequence of actions in a very specific order. It might be difficult to set up a sequence in an FSM, and handle failures, interruptions - but BTs make this relatively simple.

So here's what I wanted to achieve with my first combat AI:

Quote:
1. The AI waits for an enemy to come within sensing range
2. The AI aims at the enemy and moves closer, and when in range,
3. The AI fires at the enemy until dead
4. If the enemy moves out of range, follow them while firing

Not too ambitious at all.

As a BT, it looks like this:

Here's a quick run-down of what's happening here. As you can see, the Behaviour Tree is indeed a Tree, starting from Root and reaching all the way to leaves such as Single Shot and Find Target. The way the Tree works is by 'executing' it, which starts at the Root node and works down the tree until a decision is reached, and 'back-executing', which starts from a decision and works up the tree. These 'decisions' are represented by the Behaviour nodes, the leaves of the tree. The different sorts of nodes you can use to build a tree (colour coded) give different flow options to the tree when forwards or backwards execution happens.

The Parallel node type, which is used in the Root and Attack nodes, will simply execute all of its children. In the case of Root, there is only one child - but the Attack node has two children. Both of these will be executed when Attack is executed, so the decisions 'Approach Target' and 'Aim At Target' may be reached at the same time (so Kork can multi-task, in effect).

Sequencer nodes do just that: execute their child nodes, but in a distinct sequence. When a child node back-executes to a Sequencer reporting that it's completed, the Sequencer then forward-executes the next child. You can see a great example in the Firing Sequence. First, Kork aims at the target. When he has aimed, he pauses. When the pause has timed out, he fires, and the sequence is complete. The same can be seen on a larger scale in the Main Sequence. Kork first waits to find a target - then when that is complete, proceeds to attack the target. When this is complete, he will 'finish', which is where I would play a little victory animation or whatever. The Finish behaviour also executes the entire tree again, so that Kork can keep responding to targets even after killing the first one he engages.

Selector nodes, which I didn't use in this simple tree, will only execute one child, but you get to use a custonm function to pick which one. So if I wanted Kork to run away when his health was low, I might concievably insert a Selector into the tree at point X. Its children would be the Attack paralle, and a Flee branch. The function would decide which of these to execute based on whatever factors you wanted.

The Decorators are where it gets interesting. These nodes control the flow of execution in more complex ways - for now, I've used Decorators to loop behaviours, and pause a loop temporarily. The 'Loop While (target alive)' decorators are prety simple. When a back-execution hits them, from the Firing sequence or the Approach sequence, and the back-execution is reporting a success (i.e., we have successfully approached the target), then if the target is still alive, the Decorator will execute its child again. So Kork shoots me until I'm dead, at the same time as approaching me constantly.
The 'Hold While (target in range)' node was a little trick I worked up - astute readers might spot why. If Kork executed the 'Approach Target' behaviour and ran up to an enemy, then the Approach Target behaviour would return a success. The loop would then execute that behaviour again - but since we're already in range, the behaviour would immediately report success - and so on in an infinite loop that hangs the engine. So I inserted a Decorator to control forward-execution at that point. The 'Hold' decorator will check to see if the target is in range, and if so, will not pass on forward execution - so in effect, we 'pause' that branch of execution until the target is out of range, then the Decorator lets 'Approach Target' execute again.

Loop and Script (hold) Decorators are all I've implemented so far, but I'm planning on some more complicated types in the future.

So what does this look like in script? Couldn't be simpler:

function KraftyKorkBehaviourTree::createTree(%this)
{
   //Add a Parallel node named root, with no parent
   %this.addNode("root","","Parallel",true);
      //Add a Sequencer named mainSequence as a child of root
      %this.addNode("mainSequence","root","Sequencer");
         //Add a Behaviour specifying FindClosestTargetAction
         %this.addNode("findTarget","mainSequence","Behaviour",FindClosestTargetAction);
         %this.addNode("attackTarget","mainSequence","Parallel",false);
            %this.addNode("approachLoop","attackTarget","Decorator","Loop","0","ConditionTargetAlive","0");
               %this.addNode("loopBreak","approachLoop","Decorator","Script","ConditionTargetOutOfRange","1");
                  %this.addNode("approach","loopBreak","Behaviour",ApproachTargetAction);
            %this.addNode("firingLoop","attackTarget","Decorator","Loop","0","ConditionTargetAlive");
               %this.addNode("firingSequence","firingLoop","Sequencer");
                  %this.addNode("aim","firingSequence","Behaviour",AimAtTargetAction);
                  %this.addNode("wait","firingSequence","Behaviour",ShootingPauseAction);
                  %this.addNode("fire","firingSequence","Behaviour",ShootWeaponAction);
         %this.addNode("finishAttack","mainSequence","Behaviour",VictoryAction);
}

This method of creating trees was borrowed from James Ford's great blog. Basically, the BT object calls this method on itself when added, and you use it to add nodes to the tree. Some of the names are different from my diagram, but you should get the idea. Now, this tree seems too simple to be true. You're right! You can see that Behaviours refer out to Action objects. These are what makes all the magic happen. As an example, here's the implementation of the FindClosestTargetAction:

new Action(FindClosestTargetAction)
{
   //This controls how often the Action is evaluated to see if we're done yet: in this case, every 0.5 seconds
   tickPeriod = 0.5;
};

function FindClosestTargetAction::start(%this,%obj)
{
   if($BehaviourTree::scriptEcho) echo("starting find target!");
   //This is executed when the Action is chosen by the tree
   //%obj is the object executing the tree - in this case, Kork
   %obj.target = 0;
   return %this.evaluate(%obj,0);
}

function FindClosestTargetAction::evaluate(%this,%obj,%time)
{
   if($BehaviourTree::scriptEcho >= 2) echo("find target evaluated at time " @ %time);
   //Evaluate is called on a constant basis to see what the Action's status is: Completed, Working or Failed
   //%time here refers to the time (in seconds) the Action has been running for. This would allow me to 
   //time-out the target search and get Kork to do something else if nobody were around
   //Do a radius check to see if there are suitable targets
   %pos = %obj.getPosition();
   %radius = %obj.getDataBlock().attackRange;
   %closest = %radius;
   %target = 0;
   InitContainerRadiusSearch(%pos,%radius,$TypeMasks::PlayerObjectType);
   while((%search = ContainerSearchNext()) != 0)
   {
      if(%search.team $= %obj.team || %search.getDamageState() !$= "Enabled")
         continue;

      //Only work with the closest target
      %len = VectorLen(VectorSub(%search.getPosition(),%pos));
      if(%len < %closest)
      {
         %closest = %len;
         %obj.target = %search;
      }
   }
   if(%obj.target != 0)
      return "Completed";
   return "Working";
   //Note that we can't fail. If we don't find anything, we're just "Working", and we wait until we do
}

function FindClosestTargetAction::end(%this,%obj)
{
   if($BehaviourTree::scriptEcho) echo("ending find target!");
   //This is called when the Action is ended... there isn't really much to do here
}

So *there's* all the usual AI code.

The advantage of using this system is that Actions are completely modular. If I were to make a new BT for a different character who behaves entirely differently to Kork, but still needs to find nearby entities, I could use FindClosestTargetAction with no modification. You'll notice, though, that Actions do rely on a few things - for example, the object's datablock having an attackRange value. I make other assumptions in Actions because I know I'm working on a BT for AIPlayers, which means I can use the usual AIPlayer methods like setAimObject. My next goal is to abstract Actions completely, and have them set values (such as a move destination or aim object) on a dummy object, which gets callbacks and can then do what it needs to do to the entity is assigned to (whether an AIPlayer, or any other clas that needs AI, like a Projectile, Turret, etc.).

I'm thinking I'll release this as a resource when I've had enough time to tinker with it, flesh out features and make sure there are no bugs - but either way, it'll be part of the Horrible Places code pack. As soon as I get Swarms moving and detecting, you can expect some AI swarms.