Behavior Trees - Implementation

Oh dear, the BehaviorTree article asked for some additional (coding) explanation. Normally I avoid code snippets as much as possible, for various reasons. First of all, it usually doesn't make a fun-article for non-programmers to begin with. We're here to fool around a bit, not to teach people :) And second, I'm not so sure if I'm a good teacher anyway. When it comes to programming, I know a bit about everything, in a lot of languages. But I don't have a true expertise. And certainly not in the BehaviorTree or A.I.-in-general area. Coding articles are inherently followed by wise guys asking why I'm not doing X, that I shouldn’t be doing Y, claiming Z is better, and telling I'm a douchebag.

Another reason is the size of the article. Even though my BehaviorTree code is still minimal -and I tend to keep all my code as small as possible (don't forget I'm doing this in my spare time)- it already covers about 3200 lines. Way too much for an article. Sure you don't have to see every bit to get a good understanding, but I find it difficult to make a compact comprehensible, yet "complete-enough" tutorial. Write too much and nobody will read and understand. Make it too short and people still know nothing. And of course there is the lazy type of programmer who just wants a download link with plug & play *working* code.

Last, writing coding articles is boring. For me at least. But ok ok ok. Here we go. Don't say I didn't warn you! And in case you missed it, it's Delphi/Pascal code, plus its written for Engine22 so mind the names and quirks here and there.

Oh, and one more reason - Syntax Highlighting never works properly for me on Blogspot. Managed to get it a few times, but each time they change something so the chain snaps again. If you're not seeing highlighting below, I'm trying to fix it.

1. Short refresh about BT's
2. Base Nodes - base code used for all nodes
3. Composite Nodes
4. Decorator Nodes
5. Condition Nodes
6. Action Nodes
7. Ticks - "Looping"
8. Blackboard - Custom memory storage container for trees
9. Loading a Tree
10. Registrating Node classes

1. Brain Refresh

Before starting, really read the first article again (and those others I linked to) to get a global understanding what a BT does. Grasp the "node" concept (composites, decorators, conditions, actions). But since those nodes are the core of everything, I'll repeat the four main types once again. A BT is made of nodes, which come in the following main flavours:

1. Composites

 "Flow regulator" nodes. They execute one or (usually) more child-nodes. This can be performed in a certain order (a "Sequence") or randomly. It can be done conditional, meaning it stops as soon a child-node FAILED or is still RUNNING. Or it just executes them all regardless.

               

2. Conditions

A check on something, returning SUCCESS or FAIL. Is it 12 o clock? Does player have the Blue-Key in his inventory? Are we within 5 meters from our target? Did we get hit by a flamethrower?

               

3. Actions

Stuff that actually does something in your game/program/robot. Pick a target, move to X,              rotate, animate, play sounds, give 10% health, perform a karate kick, et cetera.

               

4. Decorators

A couple of handy logic blocks that can be placed in front of Composites or Conditions to invert, delay or manipulate their results in some way. "NOT" Player-is-Cool.

               

And as told, nodes can return one of these three states:

• SUCCESS - Condition met or Action completed. Onto the next thing.
• FAIL - Condition not met, Action cannot complete.
• RUNNING - Task not done yet / pending. Still moving towards X, pie needs to be 10 more minutes in the oven.

Plus, for debugging purposes, you could add an ERROR result, for nodes that couldn't get executed because you gave them wrong parameters or something, or the code within raised an exception. Shouldn't happen, but it does happen when you develop things. Can help tracing faults.

It's up to us to implement these four types of nodes, and then to override them with our own stuff, because obviously, Conditions and Actions are very different for each application. Welding robots have rotate, coordinate, and well, welding actions, while a boxing games is more in terms of dodging and beating the shit out of that single opponent.

Right, got the basics? If not, go back to start and do not receive 20.000$. In Engine22, this is my basic file lay-out, for now:

                * E22_AI.BehaviorTrees.pas

                *** E22_AI.BehaviorTrees.Blackboard.pas

                *** E22_AI.BehaviorTrees.Nodes.pas

                ***** E22_AI.BehaviorTrees.Nodes.Composites.pas

                ***** E22_AI.BehaviorTrees.Nodes.Decorators.pas

                ***** E22_AI.BehaviorTrees.Nodes.Conditions.pas

                ***** E22_AI.BehaviorTrees.Nodes.Actions.pas

Since there will be a LOT of Conditions and Actions mainly, those files may branch further probably.

You could split into movement, combat, idle behaviour, et cetera. As for the "Blackboard", that's not a pirate name but a memory storage container we can use for our tree(s) to read/write custom data to. But let's begin coding them pesky nodes then.

2. Them pesky nodes – BASE NODE

Delphi being OOP, we should start with an abstract "base-node" that can be used by all other nodes that will follow. Here, bang, Turbo Pascal time:

      eAI_BT_BaseNode     = class
        private
          isOpen          : eBool;        // Node has been evaluated this tick, or in a previous tick & still running
          // Information
          nodeTitle       : aString32;    // Custom title
          nodeDescription : aString128;   // Custom description, by artist
          nodeCoords      : eVec2;        // X Y, for editor views
          nodeGUID        : aString48;    // Unique ID
        public
          parentNode      : eAI_BT_BaseNode;  // Decorator or Composite node that links to us

          procedure   initialize( parentNode : eAI_BT_BaseNode );  virtual; // Set initial vars and such
          destructor  destroy(); virtual;

          // Execution
          function   _execute(  tick : peAI_BT_TickInfo ) : eAI_BT_Result;
          procedure   enter(    tick : peAI_BT_TickInfo ); virtual; // called every time a node is executed
          procedure   open(     tick : peAI_BT_TickInfo ); virtual; // called only when the node is opened (when a node returns RUNNING, it will keep opened until it returns other value or the tree forces the closing);
          function    tick(     tick : peAI_BT_TickInfo ) : eAI_BT_Result; virtual;
          procedure   close(    tick : peAI_BT_TickInfo ); virtual; // called when a node return SUCCESS, FAILURE or ERROR, or when the tree forces the node to close;
          procedure   exitNode( tick : peAI_BT_TickInfo ); virtual; // called every time at the end of the node execution.

          // Editing
          function    getTitle() : uString;
          procedure   settitle( const title : uString );
          function    getGUID() : uString;
          procedure   setGUID( const GUID : uString );
          function    GUIDequals( GUID : uString ) : eBool;
          function    getDescription() : uString;
          procedure   setDescription( const desc : uString );
          function    getCoords() : eVec2;
          procedure   setCoords( const x,y : eFloat ); overload;
          procedure   setCoords( const v : eVec2 ); overload;

          // Child management
          procedure   addChild( node : eAI_BT_BaseNode ); virtual;
          procedure   removeChild( node : eAI_BT_BaseNode ); virtual;
          function    getChildrenCount() : eInt; virtual;
          function    getChild( const index : eInt ) : eAI_BT_BaseNode; virtual;

          // Property management
          function    getPropertyCount() : eInt; virtual;
          function    getProperty( const index : eInt ) : eAI_BT_NodeProperty; virtual;
          procedure   setProperty( const index : eInt; const value : uString ); overload; virtual;
          procedure   setProperty( propName : uString; const value : uString ); overload; virtual;
          procedure   copyFrom( otherNode : eAI_BT_BaseNode );  // Copy props from another node

          // Visualizer (editor)
          procedure   draw(); virtual;
      end; // eAI_BT_BaseNode

I hope this header-code is somewhat self-explanatory. Plus you can forget about 75%, as most methods are for (future)editing purpose. If you use an external editor, you don’t have to define coordinates, descriptions or drawing functions. More important are the Execute, Open, Tick, and Close functions:

·         Tick          This runs the actual node evaluation code.

·         Open         Called when the node is called for the first time since closed last time

·         Close        Called when the node is “done” (SUCCEEDED or FAILED, not RUNNING)

·         _execute   Calls all the enter/open/tick/close/exit functions in the right order

      function eAI_BT_BaseNode._execute( tick : peAI_BT_TickInfo ) : eAI_BT_Result;
      var status    : eAI_BT_Result;
          listIndex : eInt;
      begin
            // Add to "Entered" list
            tick.evaluatedNodeCnt := tick.evaluatedNodeCnt + 1;
            listIndex             := tick.openedNodes.count;
            tick.openedNodes.Add( self );  // Keep track of the evaluated nodes.
                                           // Can be intreesting for debugging, visualizing,
                                           // or optimizing later on.
            // Open
            self.enter( tick );
            if not ( self.isOpen ) then begin
                self.isOpen := true;
                self.open( tick ); // not opened before
            end;

            // Execute logic
            status := self.tick( tick );

            // Close
            if ( status <> eAI_BT_RUNNING ) then begin
                self.close( tick );
                // Remove ourselves & children nodes
                while ( tick.openedNodes.count > listIndex ) do begin
                    eAI_BT_BaseNode( tick.openedNodes[tick.openedNodes.count-1] ).isOpen := false;
                    tick.openedNodes.Delete( tick.openedNodes.count-1 );
                end;
            end;
            self.exitNode( tick );

            result := status; // Report our result to our parent node
      end; // _execute

Note that this “execute” function is potentially called every cycle, for every node (in the worst case). Games or Realtime robotic applications tend to cycle through their program many times per second, evaluating their logic. BehaviorTrees refer to this as “ticks”. More about that later.

2.2 Custom Node Properties

The nodes that we’ll make later, will mainly override the Tick and Open functions, doing your magic. Also not unimportant, are the “Property” functions. In many cases you want to feed your Actions or Conditions with some background info. A “setTarget” action also wants to know “WHAT TARGET?!”. The player? The closest foe? The toilet bowl? And a “check clock” function should know what time to check in terms of hours and minutes. Each node has a fixed number of properties, each with a name, type (int, bool, float, string, vector(coordinate)), unit and default value. When loading trees from files later on, those names are important for matching. Other info is mainly interesting if you plan to make your own editor.

      eAI_BT_NodePropertyType = ( eAI_BT_PropBOOL   = 0,
                                  eAI_BT_PropINT    = 1,
                                  eAI_BT_PropFLOAT  = 2,
                                  eAI_BT_PropVEC3   = 3,
                                  eAI_BT_PropVEC4   = 4,
                                  eAI_BT_PropCOL3   = 5,
                                  eAI_BT_PropCOL4   = 6,
                                  eAI_BT_PropSTRING = 7,
                                  eAI_BT_PropENTITY = 8,
                                  eAI_BT_PropSOUND  = 9 );
      
eAI_BT_NodeProperty = record
          idName          : aString16;
          value           : aString128;
          defaultValue    : aString128;
          unitName        : aString8;
          propType        : eAI_BT_NodePropertyType;

          procedure make( name : string; value, defaultValue : eInt; const unitName : string ); overload;
          procedure make( name : string; value, defaultValue : eFloat; const unitName : string ); overload;
          procedure make( name : string; value, defaultValue : eBool );   overload;
          procedure make( name : string; value, defaultValue : uString; const typ : eAI_BT_NodePropertyType ); overload;
          procedure make( name : string; value, defaultValue : eVec3   ); overload;
          procedure make( name : string; value : eES_EntityID ); overload;
      end; // eAI_BT_NodeProperty

3. Composite Nodes

So far, abstract meaningless code. Let’s override that abstract node and turn it into a real node we could use, starting with composites. There aren’t many types of composites, and although you are completely free in giving them names and logic, you should try to follow the standard types of composites. Some very common ones are:

·         (Memorized) Sequence

Loop through children, until one returns SUCCESS or FAIL (abort the sequence). If it’s a memorized sequence, resume the child-node we evaluated previous tick.

·         Priority or Selector

Basically the IF THEN ELSE. Stop looping though the children as soon as one returns SUCCESS or RUNNING.

·         Parallel

Executes all children, regardless their outcome. Eventually return SUCCESS if more than X children succeeded.

And then there is the START or ENTRY node. Which doesn’t do shit, but connected to a single child. This where the tree starts. Keep in mind a Tree could execute sub-trees, starting at their entry points (and eventually returning an overall result as well).

Probably you will be using Sequence to begin with. We can code them as follow:

      eAI_BT_NodeComposite    = class( eAI_BT_BaseNode )
        public
          children            : TList;

          procedure   initialize( parentNode : eAI_BT_BaseNode ); override;
          destructor  destroy(); override;
          procedure   addChild( node : eAI_BT_BaseNode ); override;
          procedure   removeChild( node : eAI_BT_BaseNode ); override;
          function    getChildrenCount() : eInt; override;
          function    getChild( const index : eInt ) : eAI_BT_BaseNode; override;
      end; // eAI_BT_NodeSequence

      // Execute all children until one NOT returns SUCCESS
      // Return SCCUESS if all childen succeeded, FAIL if any of the children FAILED
      eAI_BT_NodeSequence     = class( eAI_BT_NodeComposite )
        public
          function  tick(  tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
      end; // eAI_BT_NodeSequence


      // Same as Sequence, but keep track of the position so earlier succeeded children
      // won't be re-executed until the parent node was closed.
      // Return SCCUESS if the last child succeeded, FAIL if any of the children FAILED
      eAI_BT_NodeMemSeq       = class( eAI_BT_NodeComposite )
        private
          runningChildIndex   : eInt;
        public
          procedure open(  tick : peAI_BT_TickInfo ); override;
          function  tick(  tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
      end; // eAI_BT_NodeMemSeq

{ eAI_BT_NodeSequence }

      function eAI_BT_NodeSequence.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
      var i : eInt;
      begin
            // Loop through children until one FAILED or RUNS
            for i:=0 to self.children.count-1 do begin
                result := eAI_BT_BaseNode( self.children[i] )._execute( tick );
                if ( result <> eAI_BT_SUCCESS ) then
                    exit;  // FAIL or RUN
            end;
            result := eAI_BT_SUCCESS; // All children executed with SUCCESS
      end; // tick


{ eAI_BT_NodeMemSeq }

      procedure eAI_BT_NodeMemSeq.open(  tick : peAI_BT_TickInfo );
      begin
            self.runningChildIndex := 0;
      end; // open



      function eAI_BT_NodeMemSeq.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
      var i       : eInt;
          child   : eInt;
      begin
            // Start where we ended last time (was running previously)
            child := self.runningChildIndex;

            // Loop through children until one FAILED or RUNS
            for i:=child to self.children.count-1 do begin
                result := eAI_BT_BaseNode( self.children[i] )._execute( tick );

                // Wait until current child finished
                if ( result <> eAI_BT_SUCCESS ) then begin
                    if ( result = eAI_BT_RUNNING ) then
                        self.runningChildIndex := i;  // For next Tick
                    exit; // FAIL or RUN
                end;

            end;
            result := eAI_BT_SUCCESS; // All children executed with SUCCESS
      end; // tick

So here we showed how a (memorized) sequence can be implemented. As you see, it still doesn’t do much other than executing children. Those children could be other Composites, Decorators, or eventually Conditions and Actions. Quite often a sequence will first check one or more Conditions:

                Sequence           à           IF health < 25                    (condition)

                                                               Find medkit                       (action)

                                                               Move to medkit              (action)

                                                               Pick up medkit                 (action)

                                                               Boedha time                     (action)

If those first conditions aren’t met, there is often no need in executing any further actions. Be aware with Memorized Sequences though, that those conditions aren’t re-checked every tick. If the dog eats the medkit in the meanwhile, our NPC still continues his procedure, unless there is some exit strategy implemented.

4. Decorator Nodes

A very basic, but useful decorator is the Invertor or “NOT” node. Decorators always have a single child, and manipulate their results. The invertor turns SUCCESS into FAIL, or vice-versa.

      eAI_BT_NodeDecorator    = class( eAI_BT_BaseNode )
        public
          child               : eAI_BT_BaseNode;

          procedure   initialize( parentNode : eAI_BT_BaseNode );  override;
          destructor  destroy(); override;
          procedure   addChild( node : eAI_BT_BaseNode ); override;
          procedure   removeChild( node : eAI_BT_BaseNode ); override;
          function    getChildrenCount() : eInt; override;
          function    getChild( const index : eInt ) : eAI_BT_BaseNode; override;
      end; // eAI_BT_NodeDecorator



      eAI_BT_NodeInverter     = class( eAI_BT_NodeDecorator )
        public
          function  tick(  tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
      end; // eAI_BT_NodeInverter

{ eAI_BT_NodeDecorator }

      procedure eAI_BT_NodeDecorator.initialize( parentNode : eAI_BT_BaseNode );
      begin
            inherited initialize( parentNode );
            self.child    := nil;
      end; // initialize
      destructor eAI_BT_NodeDecorator.destroy();
      begin
            // Do not destroy children, must be done by owner tree
            inherited destroy();
      end; // destroy



      function eAI_BT_NodeDecorator.getChild(const index: eInt): eAI_BT_BaseNode;
      begin
            result := self.child;
      end; // getChild
      function eAI_BT_NodeDecorator.getChildrenCount() : eInt;
      begin
            if ( self.child = nil ) then
                result := 0 else
                result := 1;
      end; // getChildrenCount



      procedure eAI_BT_NodeDecorator.addChild( node : eAI_BT_BaseNode );
      begin
            self.child := node;
      end; // addChild
      procedure eAI_BT_NodeDecorator.removeChild( node : eAI_BT_BaseNode );
      begin
            self.child := nil;
      end; // removeChild



{ eAI_BT_NodeInverter }

      function eAI_BT_NodeInverter.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
      begin
            if ( self.child = nil ) then
                result := eAI_BT_ERROR
            else begin
                result := self.child._execute( tick );
                if ( result = eAI_BT_SUCCESS ) then
                    result := eAI_BT_FAIL else
                if ( result = eAI_BT_FAIL ) then
                    result := eAI_BT_SUCCESS;
            end;
      end; // tick

Got that? Fine, onto the real interesting nodes: Conditions and Actions.

5. Condition Nodes

There are no default Condition nodes, as they really depend on your needs. But let’s come up with something practical; a node that checks if a certain entity (could be the player, but also a hamburger) is within range. We will also provide some custom properties to this node. The desired distance in meters, and an entity idName – the target to check. Note by the way that Condition (or Action) nodes do not have children, so their “getChildrenCount()” should always return 0.

      eAI_BT_NodeCondition        = class( eAI_BT_BaseNode )
        public
      end; // eAI_BT_NodeCondition


      eAI_BT_Node_cEntInRange     = class( eAI_BT_NodeCondition )
        private
            entity                : eES_EntityAbstract;
            entityIdName          : uString;
            distance           : eFloat;
        public
          procedure   initialize( parentNode : eAI_BT_BaseNode ); override;
          procedure   open(  tick : peAI_BT_TickInfo ); override;
          function    tick(  tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;

          function    getPropertyCount() : eInt; override;
          function    getProperty( const index : eInt ) : eAI_BT_NodeProperty; override;
          procedure   setProperty( const index : eInt; const value : uString ); override;
      end; // eAI_BT_Node_cEntInRange

{ eAI_BT_Node_cEntInRange }

      procedure eAI_BT_Node_cEntInRange.initialize( parentNode : eAI_BT_BaseNode );
      begin
            inherited initialize( parentNode );
            self.distance := 5;
            self.entityIdName:= '';
            self.entity := nil;
      end; // initialize



      function  eAI_BT_Node_cEntInRange.getPropertyCount() : eInt;
      begin
            result := 2;
      end; // getPropertyCount
      function  eAI_BT_Node_cEntInRange.getProperty( const index : eInt ) : eAI_BT_NodeProperty;
      begin
            case (index) of
                0: result.make( 'entity' , self. entityIdName, ‘Player’, eAI_BT_PropENTITY );
                1: result.make( ‘distance’ , self.distance , 5, 'meters' );
            end;
      end; // getProperty
      procedure eAI_BT_Node_cEntInRange.setProperty( const index : eInt; const value : uString );
      var id : eUInt64;
      begin
            case (index) of
                0: self.entityIdName := value;
                1: self.distance := strToFloat( value );
            end;
      end; // setProperty



      procedure eAI_BT_Node_cEntInRange.open(tick: peAI_BT_TickInfo);
      begin
            if ( self.entity = nil ) then begin
                // Find our target
                self.entity := _ES.getManager().getEntityByName( self.entityIdName );
            end;
      end; // open


      function  eAI_BT_Node_cEntInRange.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
      var dist : eFloat;
      begin
            if ( self.entity = nil ) then begin
                result := eAI_BT_FAIL;
            end else begin
                try
                    // Get distance between our parent entity, and our target
                    dist   := self.entity.getPos().distanceTo( tick.myEntity.getPos() );
                except
                    result := eAI_BT_FAIL;  // Maybe entity got unloaded in the meanwhile
                    exit;
                end;

                 if ( dist < self.distance ) then
                        result      := eAI_BT_SUCCESS else
                        result      := eAI_BT_FAIL;
            end;
      end; // tick

Be aware that this node is sensitive for some faults. Maybe the entityName was spelled wrong. Maybe we found the entity, but it get destructed later on. Also, when setting properties, you may want some exception checking on top of that, in case we give invalid numbers. The whole purpose of BehaviorTrees is to provide (the artist / mapper / designer) a robust tool to create A.I.. And people make mistakes, so be prepared.

6. Action Nodes

The last type of node we show; Action-Man. Actions actuate something. We could use them to write some custom data into our memory “Blackboard”, to pick a target, to throw grenades, and so on. Typically we want to split up into simple actions that can be reused for a lot of different procedures. Moving is an excellent example, though a difficult one because movement contains a ton of deeper (engine) logic. Picking a target, moving to it, physics, gravity, collision detection, animation, inverse kinematics while climbing a stair, and so on. You could deal with each of those sub-actions via your BehaviorTree, but it might be easier for the A.I. designer to let the engine take care of that automatically.

For demo purposes, I picked a simpler action: doing nothing. A delay. After an adjustable amount of seconds, it will return SUCCESS. But as with many actions, this takes a while. In the meanwhile the node turns “RUNNING”. This affects the way how parent composites deal with it. Memorized Sequences will remember the current action, so it can be called again next tick, proceeding.

      eAI_BT_NodeAction       = class( eAI_BT_BaseNode )
        public
      end; // eAI_BT_NodeAction
      
eAI_BT_Node_aWait      = class( eAI_BT_NodeAction )
        private
            elapsed          : eFloat;
            waitTime         : eFloat;
        public
          procedure initialize( parentNode : eAI_BT_BaseNode ); override;
          function  getPropertyCount(): eInt; override;
          function  getProperty(const index: eInt): eAI_BT_NodeProperty; override;
          procedure setProperty(const index: eInt; const value: uString); override;

          procedure open(  tick : peAI_BT_TickInfo ); override;
          function  tick(  tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
      end; // eAI_BT_Node_aWait

{ eAI_BT_Node_aWait }

      procedure eAI_BT_Node_aWait.initialize(parentNode: eAI_BT_BaseNode);
      begin
            inherited initialize( parentNode );
            self.elapsed := 0;
            self.waitTime:= 1;
      end; // initialize


      function  eAI_BT_Node_aWait.getPropertyCount(): eInt;
      begin
            result := 1;
      end;// getPropertyCount
      function  eAI_BT_Node_aWait.getProperty(const index: eInt): eAI_BT_NodeProperty;
      begin
            result.make( 'time' , self.waitTime  , 1, 'sec' );
      end; // getProperty
      procedure eAI_BT_Node_aWait.setProperty(const index: eInt; const value: uString);
      begin
            case ( index ) of
                0: self.waitTime  := strToFloat( value );
            end;
      end; // setProperty


      procedure eAI_BT_Node_aWait.open(tick: peAI_BT_TickInfo);
      begin
            self.elapsed := 0; // Reset timer when we got re-opened
      end; // open


      function eAI_BT_Node_aWait.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
      begin
            self.elapsed := self.elapsed + tick.deltaSecs;
            if ( self.elapsed >= self.waitTime ) then
                result := eAI_BT_SUCCESS else
                result := eAI_BT_RUNNING;
      end; // eAI_BT_NodeWait

7. Watch out for Ticks

All right, so far the nodes. The only way to really get comfortable with them, is just by doing. My advice, start with a simple scenario, like the “Seat-2D2” video showed, and model it in a free tool, just to get a hang on it. As you goi, you’ll figure out what kind of nodes you’ll be needing, and what kind of parameters they should use. And very likely, you will rethink your whole node toolset at some point, generating a more logical, easier to use set. Don’t be afraid to take some missteps. The beauty is that you can relative easily remove and introduce new nodes to your package; the code above it – that runs the tree- won’t be affected.

The next thing to do, is making a “Tree” class. The BT itself is a collection of nodes, and provides the logic to run them.

      eAI_BT_TickInfo       = record
          deltaSecs         : eFloat;             // Elapsed time between 2 cycles
          entity            : eES_Entity;         // Parent entity (NPC)
          blackboard        : eAI_BT_Blackboard;  // Custom Read/Write Memory
          navigator         : eAI_Navigator;      // For movement, pathfinding

          // Evaluation
          evaluatedNodeCnt  : eInt;
          openedNodes       : TList;              // Tracker of evaluated nodes
      end; // eAI_BT_TickInfo
      peAI_BT_TickInfo  = ^eAI_BT_TickInfo;


      eAI_BT_BehaviorTree  = class
        private
          tick          : eAI_BT_TickInfo;  // Arguments to pass to the nodes when executing a tick
          blackboard    : eAI_BT_Blackboard;// Memory container
          navigator     : eAI_Navigator;    // For movement

          inUse         : eBool;
          instanceGroup : eAI_BT_BehaviorTreeInstanceGroup;
        public
          root          : eAI_BT_BaseNode;  // Start evaluation here
          allNodes      : TList;            // All (sub)node instances used in this tree

          constructor create();
          destructor  destroy();
          procedure   clear();

          procedure   execute( entity : eES_Entity; const deltaSecs : eFloat );
          function    addNode( const nodeClassIdName : uString;
                                     parentNode      : eAI_BT_BaseNode ) : eAI_BT_BaseNode;
          function    getNode( const GUID : uString ) : eAI_BT_BaseNode;
          procedure   removeNode( node : eAI_BT_BaseNode );

          // Loader
          procedure   copyFrom( otherTree : eAI_BT_BehaviorTree );
          procedure   loadFromFile_B3JS( const filename : uString );  // Online editor: http://behavior3js.guineashots.com/editor/
          procedure   loadFromStream_E22( str : TStream );  // Engine22 build-in format
      end; // eAI_BT_BehaviorTree

{ eAI_BT_BehaviorTree }

      constructor eAI_BT_BehaviorTree.create();
      begin
            inherited create();

            // Blackboard
            self.blackboard     := eAI_BT_Blackboard.create();

            // Navigator
            self.navigator      := eAI_Navigator.create();

            self.allNodes       := TList.Create();
            self.inUse          := false;
            self.instanceGroup  := nil;

            // Root
            self.root           := eAI_BT_NodeRoot.create( );
            self.root.setTitle( 'root' );
            self.root.initialize( nil );
      end; // create


      destructor eAI_BT_BehaviorTree.destroy();
      begin
            self.root.destroy();
            self.clear();
            self.allNodes.destroy();
            self.blackboard.destroy();
            self.navigator.destroy();

            inherited destroy();
      end; // destroy


      procedure   eAI_BT_BehaviorTree.clear();
      var i : eInt;
      begin
            for i:=0 to self.allNodes.count-1 do begin
                eAI_BT_BaseNode( self.allNodes[i] ).destroy();
            end;
            self.allNodes.clear();
            self.navigator.reset();
      end; // clear



      procedure eAI_BT_BehaviorTree.execute( entity : eES_Entity; const deltaSecs : eFloat );
      begin
            self.navigator.update( entity, deltaSecs );

            // Init tick arguments
            self.tick.openedNodes.clear();
            self.tick.entity     := entity;
            self.tick.deltaSecs  := deltaSecs;
            self.tick.blackboard := self.blackboard;
            self.tick.navigator  := self.navigator;

            // Tick root-node, and everything beyond...
            self.root._execute( @tick );
      end; // tick



      procedure eAI_BT_BehaviorTree.copyFrom(otherTree: eAI_BT_BehaviorTree);
      begin
            self.root.copyFrom( otherTree.root );
      end; // copyFrom



      function  eAI_BT_BehaviorTree.addNode( const nodeClassIdName : uString;
                                                   parentNode      : eAI_BT_BaseNode  ) : eAI_BT_BaseNode;
      begin
            result := _ES_MakeBehaviorTreeNodeInstance( nodeClassIdName, parentNode );
            self.allNodes.add( result );
      end; // addNode
      procedure eAI_BT_BehaviorTree.removeNode( node : eAI_BT_BaseNode );
      begin
            // Detach
            if ( node.parentNode <> nil ) then begin
                node.parentNode.removeChild( node );
            end;

            self.allNodes.remove( node );
            node.destroy();
      end; // removeNode



      function  eAI_BT_BehaviorTree.getNode( const GUID : uString ) : eAI_BT_BaseNode;
      var i : eInt;
      begin
            for i:=0 to self.allNodes.count-1 do
                if ( eAI_BT_BaseNode( self.allNodes[i] ).GUIDequals( GUID ) ) then
                begin
                    result :=  eAI_BT_BaseNode( self.allNodes[i] );
                    exit;
                end;
            result := nil;
      end; // getNode

Typically each Entity / Agent / NPC has its own Tree. This brings a slight difficulty… What if we have 200 soldiers, all using the same tree? You can’t directly share the same tree-instance, because internal variables like delay-timers, target coordinates or the actual node states (running, failed, …) can be different for each soldier.

The tutorial I linked to in my previous post solves this by NOT storing any instance-dependant variable into the node objects. Instead, everything is written to a “Blackboard”. This blackboard contains the run-state of each and every NPC that uses the tree, as well as a global section so variables can be shared amongst multiple NPC’s. This can be useful in particular when your army or squads share tactical info. A commander NPC could set global goals for a whole group of soliders.

However, I chose not to do it like that. Because adding, overwriting, removing and getting all those variables via lists is slow and painful, I’d say. Instead, I’ll make a copy of the entire tree for each instance. Now, Tower22 won’t have 200 enemies. Yet it doesn’t sound like a very performance-friendly method either. To partially fix that, Engine22 does a lot of recycling. Yes, we are very green. If a tree is released (entity went to Hell), it will be available for another instance.

So, when I need a tree of typeX, (say file “monkey_BT.txt”), a manager will first check if there is an unused tree available. Ifso, give that one –and reset it before usage. If there is no tree available, a new one will be created. But instead of loading the whole file again, it copies its content from another tree. Engine22 does this for a lot of memory-eating resources by the way.

7.2 Even-Driven?

One more thing I should mention about Ticks & Tricks, are events. Right now, a NPC has a single tree and just checks everything, always. That introduces a few problems. How about high priority stuff like getting killed? It would suck pretty much if your opponent doesn’t die because his faulty BT skipped the “Die-Hard” section, as the “eating cookies” branch got a higher priority. And also in general, polling if something happened (every cycle) just isn’t very performance friendly.

You could decide to run different trees instead, based on events. “OnHitByBullet”, “OnCollision”, “OnPlayerInSight”, “OnTargetReached” or “OnClicked” are beautiful examples of that. It will result into multiple, but smaller “to-the-point” behaviortrees. It may run more efficiently, and reduces modelling faults. Then again it will also reduce flexibility, as your model relies on the available engine events. Yet I’m seriously considering this for Engine22.

8. Captain Blackboard

Blackboards are memory containers. Although BehaviorTrees do not store each and every state value into a Blackboard, we still use them for custom variables. Those are either per-NPC variables. Like “hunger” which could be different for each instance. But there is also a global Blackboard, containing shared variables that can be accessed by all NPC’s. We all want to know who the player is. And for a soccer team, we could write the score as a single number, rather than maintaining the score number for each NPC individually.

From an engine design perspective, custom data is always tricky. We’re trying to make Tower22 in Engine22, but we could just as well make Pac-Man with it. Both games have very different BehaviorTrees, and thus also very different data behind them. In other words, the engine should not make a whole list of “expected” variables. It doesn’t know which variables there will be, neither should it care about. Game specific code, which includes BehaviorTrees should manage that.

Yet for performance reasons, the E22 Blackboard does have some pre-defined variables, like a “PrimaryTarget”. Whether it’s a Pac-Man ghost, Tower22 monster, Black-Ops trooper or racing car, they (almost) always have a goal; something to engage, pick-up or move over to. So, there are some Set/Get primaryTarget functions. But other than that, custom variables are simple tuples with a key(id name) and a value.

      eAI_BT_BlackboardVar= class
        public
          key             : uString;
          value           : uString;
          defaultValue    : uString;  // Reset
      end; // eAI_BT_BlackboardVar



      // Use a blackboard to Read/Write data via a BehaviorTree
      // One board assigned per Tree - thus per NPC
      eAI_BT_Blackboard   = class
        private
          // Primary target
          targetEntity    : eES_EntityAbstract;   // Primary target
          targetLocation  : eVec3;                // Fixed target location - if there is no entity
          targetAssigned  : eBool;                // True whenever set. Set false once reached or lost.

          // Custom values
          variables       : TStringList;          // Sorted list of 
        public
          constructor create();
          destructor  destroy();
          procedure   reset();

          // Primary target
          procedure   setPrimaryTarget( targetEntity    : eES_EntityAbstract ); overload;
          procedure   setPrimaryTarget( targetLocation  : eVec3 ); overload;
          procedure   setPrimaryTargetNone(  );
          function    primaryTargetIsEntity() : eBool;
          function    hasPrimaryTarget() : eBool;
          function    getPrimaryTargetEntity( ) : eES_EntityAbstract;
          function    getPrimaryTargetPos( var targetLost : eBool ) : eVec3;

          // Custom values
          procedure   writeVar( const key : uString; const value : eInt    ); overload;
          procedure   writeVar( const key : uString; const value : eFloat  ); overload;
          procedure   writeVar( const key : uString; const value : eBool   ); overload;
          procedure   writeVar( const key : uString; const value : eVec3   ); overload;
          procedure   writeVar( const key : uString; const value : uString ); overload;
          function    readVar(  const key : uString ) : uString;
      end; // eAI_BT_Blackboard

In order to Write those variables, you could make an Action node for that: “writeVar”. Either pick a global or NPC blackboard as a target, and give it a name + value.

Reading and using them is a bit more tricky. Of course you can read, write and do math internally in your overrided Node code, using the functions above. But it would also be interesting if we can replace fixed values with variable references, when defining properties in our BT modeller. I didn’t code anything for this (yet), so I won’t dive into this further, but it can be something to keep in the back of your mind, when coding your BT engine.

9. Plant and Load a Tree

As promised, we close this article with some code that reads the JSON file, produced by this online BT editor:

http://behavior3js.guineashots.com/editor/#

And, let me just warn you, the code below doesn’t do anything truly smart. No JSON libraries or whatsoever used, just good old dumb string parsing. You see, I want to have an editor build into the engine (so you can check & change stuff on the fly, and automatically access all the available nodes plus their parameter information). But since that will be quite beefy, I used an external editor to begin with, and made a quick & dirty reader. If you need something more fancy for Delphi, commenter Dennis gave us a link to his work:

https://github.com/Dennis1000/behavior3delphi

All right:

      procedure eAI_BT_BehaviorTree.loadFromFile_B3JS(const filename: uString);
      var sFile       : strTextFileReader;
          line        : uString;
          values      : TStringList;
          key,val     : uString;

          cGUID       : uString;
          cNode       : eAI_BT_BaseNode;
          child       : eAI_BT_BaseNode;

(* EXAMPLE
        "90282381-684c-461e-b61c-11684778b0e5": {
            "id": "90282381-684c-461e-b61c-11684778b0e5",
            "name": "Priority",
            "title": "Priority",
            "description": "",
            "display": {
                "x": -320,
                "y": -160
            },
            "parameters": {},
            "properties": {},
            "children": [
                "88e3cb42-bb69-4774-ba9f-411a2b6db4ed",
                "08a6f505-2184-478b-b56b-d527f1d8ff60"
            ]
        },
*)
            procedure trimValueString();
            begin // Remove tail comma, if there is one
                  if ( length(val) > 1 ) then
                  if ( val[ length(val) ] = ',' ) then begin
                      val := val.subString( 0, length(val)-1 );
                  end;
            end; // trimValueString
            procedure trimKeyString();
            begin // Remove tail comma or :, if there is one
                  if ( length(key) > 1 ) then
                  if ( key[ length(key) ] = ':' ) or ( key[ length(key) ] = ',' ) then begin
                      key := key.subString( 0, length(key)-1 );
                  end;
            end; // trimKeyString


            procedure readChildren();
            begin // Read node "children" references (GUIDs) sub-block
                  while ( sFile.readRawLine(line)) do begin
                      strReadLine( line, key, values );
                      if ( key = ']' ) then exit;
                      trimKeyString();

                      child := self.getNode( key ); // Get node from list via GUID
                      if ( child <> nil ) then begin
                          cNode.addChild( child );  // Fill children list
                          child.parentNode := child;
                      end;
                  end; // while
            end; // readChildren


            procedure readProperties();
            begin // Read node "properties" sub-block
                  while ( sFile.readRawLine(line)) do begin
                      strReadLine( line, key, values );
                      key := upperCase(key);
                      if ( key = 'PROPERTIES:' ) then exit;
                      if ( key = '},' ) then exit;
                      if ( values.count < 1 ) then continue;
                      val := values[0];
                      trimKeyString();
                      trimValueString();

                      try
                          cNode.setProperty( key, val );
                      except
                          // No such property
                          showMessage( 'Warning: cannot set property '+key+' = '+val );
                      end;
                  end; // while
            end; // readProperties

      begin
            self.clear(); // Clean up old crap first
            values := TStringList.create();

            try
                sFile := strTextFileReader.create( filename, 'eAI_BT_BehaviorTree.loadFromFile_B3JS' );
            except
                sFile.destroy();  // Cant open file, fuck you
                exit;
            end;

            // Loop through file, create all nodes
            // BUT DO NOT LINKED THEM WITH EACH OTHER YET (nodes can refer to uncreated subnodes)
            cNode := nil;
            while ( sFile.readRawLine(line)) do begin
                strReadLine( line, key, values );
                key := upperCase(key);
                if ( values.count < 1 ) then continue;
                val := values[0];
                trimValueString();    // Remove tail character from string

                if ( key = 'CUSTOM_NODES:' ) then break;
                if ( key = 'ID:') then cGUID := val else
                if ( key = 'NAME:') then begin
                    cNode := _ES_MakeBehaviorTreeNodeInstance( val, nil );
                    if ( cNode = nil ) then continue;
                    cNode.setGUID( cGUID );
                    self.allNodes.add( cNode );
                    // don't know the parent yet - do that later
                end else
                if ( cNode <> nil ) then begin
                    if ( key = 'TITLE:') then cNode.setTitle( val ) else
                    if ( key = 'DESCRIPTION:') then cNode.setDescription( val ) else
                    if ( key = 'X:') then cNode.setCoords( strToInt(val), cNode.getCoords().y ) else
                    if ( key = 'Y:') then cNode.setCoords( cNode.getCoords().x, strToInt(val) ) else
                    if ( key = 'PROPERTIES:') then begin

                    end else
                    if ( key = 'PARAMETERS:') then begin
                        readProperties();
                    end else
                    if ( key = 'CHILDREN:') then begin
                        // Skip for now
                    end else
                end;
            end;


            // Repeat, now read children
            cNode := nil;
            sFile.restart();

            while ( sFile.readRawLine(line)) do begin
                strReadLine( line, key, values );
                key := upperCase(key);
                if ( values.count < 1 ) then continue;
                val := values[0];
                trimValueString();    // Remove tail character from string

                if ( key = 'ROOT:') then self.root.addchild( self.getNode(val) ) else
                if ( key = 'CUSTOM_NODES:' ) then break;
                if ( key = 'ID:') then cNode := self.getNode( val ) else
                if ( key = 'CHILD:'   ) and ( cNode <> nil ) then begin
                    // Single child
                    trimValueString();          // Remove tail character from string
                    child := self.getNode(val); // Get via GUID
                    if ( child <> nil ) then begin
                        cNode.addChild( child );
                        child.parentNode := cNode;
                    end;
                end else
                if ( key = 'CHILDREN:') and ( cNode <> nil ) then begin
                    // Multiple children
                    readChildren();
                end else
            end;

            // Clean up crew
            values.destroy();
            sFile.destroy();
      end; // loadFromFile_B3JS

This code won’t run straight away, because it uses quite a lot Engine22 string functions, but hopefully you get the point. One important aspect here though, is the “_ES_MakeBehaviorTreeNodeInstance” function. Given a Node classname (such as “Sequence” or “aMoveToTarget”), it will create a node instance from that class.

10. Registrate node classes for usage

Each node class is registered during startup, like this:

begin
      _ES_RegisterBehaviorTreeNodeClass( 'cEntInRange'    , eAI_BT_Node_cEntInRange );
      _ES_RegisterBehaviorTreeNodeClass( 'cHasTarget'     , eAI_BT_Node_cHasTarget );
      _ES_RegisterBehaviorTreeNodeClass( 'cTargetRaycast' , eAI_BT_Node_cTargetRaycast );
      _ES_RegisterBehaviorTreeNodeClass( 'cRaycast'       , eAI_BT_Node_cRaycast );

      _ES_RegisterBehaviorTreeNodeClass( 'cClockLaterThan', eAI_BT_Node_cClockLaterThan );
      _ES_RegisterBehaviorTreeNodeClass( 'cClockBetween'  , eAI_BT_Node_cClockBetween );
      _ES_RegisterBehaviorTreeNodeClass( 'cClockLaterThan', eAI_BT_Node_cCalenderCheckDay );
end.

Note that code is placed at the bottom section, and will be executed right away when the program starts. The _ES_RegisterBehaviorTreeNodeClass function maintains a list of nodes and classes, so we can create an instance of those classes later on, giving the name of the class.

//******************************************************************************
//    BEHAVIOR REGISTRATION
type

      eES_BehaviorTreeNodeSpecs = record
          nodeClass             : TClass;
          idName                : uString;
      end; // eES_BehaviorSpecs


var
      _ES_RegisteredBehaviorTreeNode      : array[0..255] of eES_BehaviorTreeNodeSpecs;
      _ES_RegisteredBehaviorTreeNodesCnt  : eInt  = 0;



      procedure _ES_RegisterBehaviorTreeNodeClass(  nodeIdName   : uString;
                                                    nodeClass    : TClass );
      begin
            if ( _ES_RegisteredBehaviorTreeNodesCnt > 255 ) then begin
                showMessage( 'ERROR: Cannot register more than 255 different BehaviorTree Node Classes!' );
                exit;
            end;
            _ES_RegisteredBehaviorTreeNode[ _ES_RegisteredBehaviorTreeNodesCnt ].nodeClass := nodeClass;
            _ES_RegisteredBehaviorTreeNode[ _ES_RegisteredBehaviorTreeNodesCnt ].idName    := nodeIdName;
            inc( _ES_RegisteredBehaviorTreeNodesCnt );
      end; // _ES_RegisterBehaviorTreeNodeClass



      function  _ES_MakeBehaviorTreeNodeInstance(   nodeIdName  : uString;
                                                    parentNode  : eAI_BT_BaseNode ) : eAI_BT_BaseNode;
      var i : eInt;
      begin
            for i:=0 to _ES_RegisteredBehaviorTreeNodesCnt-1 do begin
                if ( nodeIdName = _ES_RegisteredBehaviorTreeNode[i].idName ) then begin
                    result := eAI_BT_BaseNode( _ES_RegisteredBehaviorTreeNode[ i ].nodeClass.Create() );
                    result.initialize( parentNode );
                    exit;
                end;
            end;
            showMessage( 'WARNING: BehaviorTree Node Class "'+ nodeIdName +'" does not exists!' );
            result := nil;
      end; // _ES_MakeBehaviorInstance

Well, I hope this LOOONG-ASS article suited your BT needs boys and girls. Hopefully the code snippets were somewhat readable and understandable. Next time we talk about boobs, beer and games again, easier for me.