Saturday, July 2, 2016

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
          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
          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;
            // 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;
       tick ); // not opened before

            // 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 );
            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 )
          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 )
          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 )
          runningChildIndex   : eInt;
          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;
            // 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
            result := eAI_BT_SUCCESS; // All children executed with SUCCESS
      end; // tick

{ eAI_BT_NodeMemSeq }

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

      function eAI_BT_NodeMemSeq.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
      var i       : eInt;
          child   : eInt;
            // 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

            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 )
          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 )
          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 );
            inherited initialize( parentNode );
            self.child    := nil;
      end; // initialize
      destructor eAI_BT_NodeDecorator.destroy();
            // 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;
            result := self.child;
      end; // getChild
      function eAI_BT_NodeDecorator.getChildrenCount() : eInt;
            if ( self.child = nil ) then
                result := 0 else
                result := 1;
      end; // getChildrenCount

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

{ eAI_BT_NodeInverter }

      function eAI_BT_NodeInverter.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
            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; // 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 )
      end; // eAI_BT_NodeCondition

      eAI_BT_Node_cEntInRange     = class( eAI_BT_NodeCondition )
            entity                : eES_EntityAbstract;
            entityIdName          : uString;
            distance           : eFloat;
          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 );
            inherited initialize( parentNode );
            self.distance := 5;
            self.entityIdName:= '';
            self.entity := nil;
      end; // initialize

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

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

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

                 if ( dist < self.distance ) then
                        result      := eAI_BT_SUCCESS else
                        result      := eAI_BT_FAIL;
      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 )
      end; // eAI_BT_NodeAction
eAI_BT_Node_aWait      = class( eAI_BT_NodeAction )
            elapsed          : eFloat;
            waitTime         : eFloat;
          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);
            inherited initialize( parentNode );
            self.elapsed := 0;
            self.waitTime:= 1;
      end; // initialize

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

      procedure peAI_BT_TickInfo);
            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;
            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
          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;
          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:
          procedure   loadFromStream_E22( str : TStream );  // Engine22 build-in format
      end; // eAI_BT_BehaviorTree

{ eAI_BT_BehaviorTree }

      constructor eAI_BT_BehaviorTree.create();
            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();

            inherited destroy();
      end; // destroy

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

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

            // Init tick arguments
            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);
            self.root.copyFrom( otherTree.root );
      end; // copyFrom

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

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

      function  eAI_BT_BehaviorTree.getNode( const GUID : uString ) : eAI_BT_BaseNode;
      var i : eInt;
            for i:=0 to self.allNodes.count-1 do
                if ( eAI_BT_BaseNode( self.allNodes[i] ).GUIDequals( GUID ) ) then
                    result :=  eAI_BT_BaseNode( self.allNodes[i] );
            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
          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
          // 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 
          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:

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:

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;

        "90282381-684c-461e-b61c-11684778b0e5": {
            "id": "90282381-684c-461e-b61c-11684778b0e5",
            "name": "Priority",
            "title": "Priority",
            "description": "",
            "display": {
                "x": -320,
                "y": -160
            "parameters": {},
            "properties": {},
            "children": [
            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; // 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; // 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;

                      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; // 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];

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

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

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

            // 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
                    end else
                    if ( key = 'CHILDREN:') then begin
                        // Skip for now
                    end else

            // Repeat, now read children
            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 = '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 else
                if ( key = 'CHILDREN:') and ( cNode <> nil ) then begin
                    // Multiple children
                end else

            // Clean up crew
      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:

      _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 );

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.


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

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

      procedure _ES_RegisterBehaviorTreeNodeClass(  nodeIdName   : uString;
                                                    nodeClass    : TClass );
            if ( _ES_RegisteredBehaviorTreeNodesCnt > 255 ) then begin
                showMessage( 'ERROR: Cannot register more than 255 different BehaviorTree Node Classes!' );
            _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;
            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 );
            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.

Wednesday, June 22, 2016

Behavior Trees

One of the readers here (at least I hope you're still reading ;) ) hinted me quite a while ago about "Behavior Trees". No, that is not a tree where you learn your dog how to behave by punishing every time he lifts his paw. Although you could program such a scenario within a Behavior Tree. Like State-Machines, it's sort of a modelling method + programming guidance. Yet, quite difference than State-Machines. It wasn't until now I learned more about Behavior Trees -or "BT's" for short-, but I didn't forget about your advice, Sander!

I won't be telling how to code them in full defail, as there is enough detailed stuff out there:
I'll just show a simple but practical example, and have a chat about it. If you heard about BLT sandwiches, but never about BT's (like me), this may trigger you into reading the link I just posted. No pesky difficult algorithms, but fun stuff! All righty.

Artificial Fuzz

Let me begin explaining some pitfalls when trying to program A.I. in an ordinary, “on the fly” way. The way you would probably try the first 10 times, concluding things turned into a big mess as the IF's and BUT's stacked up. A.I. is complicated, even when your foes aren't supposed to be rocket scientists. A.I. is mostly about decision making, and executing those decisions in a “human way” (or Alien way, Horse way, whatever the character). Clear enough, but when to decide what? Depends on a lot of input signals and context.

Usually it starts pretty simple. A guy with a shotgun. He should shoot when he sees you, reload when out of ammo, and die when he gots hit. No fancy state machines or whatsoever required, right? Yeah, in that case... but this makes a boring enemy. How about walking? How about smoking cigarettes if there is nobody in sight? How about NOT cheating by killing you instantly as soon as he spots you? How about gently saying "AARH @SS F#CK SON OF A B!TCH!" when getting shot in the groin?

And we can keep on going. Getting hit by a BB-gun or flamethrower should result into different “behaviour”, and also picking positions to move over depends on a lot of context. When trying to attack, a foe should try find a partially covered spot with sight on the target. When trying to reload, a fully covered spot suits better, unless it's too far away maybe. And when trying to take a dump, a room with a toilet is probably an excellent good idea.

And now I'm only talking about simple shooter combatants. Imagine you're making The Sims. Or pedestrians that should act realistically (read not randomly crossing roads & ran over by a truck) in a GTA world. AI usually goes wrong -also in AAA titles- when a NPC (Non-Playable-Character) makes weird choices based on bad parameters, or keeps persistently trying to accomplish an impossible or totally unimportant goal. You must have seen guys running into a wall endlessly, or foes refusing to stop taking that dump even when a T-Rex is knocking on the door.

BT's (Behavior Trees) won't fix these issues by nature, but being a modelling method, sort of, you can at least clearly visualize the whole decision-making process - and see where they took a wrong turn, or ended up clueless. And more importantly, it's fairly easy to re-route the logic, or add branches/additional choices or conditions. In contrary to common code, that turns into a gigantic mess quickly as the exceptional cases, IF's and BUT's pile up relentlessly.

One more problem with regular code, is the actual execution. It takes a moment to prone, walk from A to B, to reload a weapon, or to take that dump (I'm sorry, can't resist). Timing man! Sequential code just tries to run everything ASAP by default, so you have to smear your execution over multiple cycles. Using (lot's of) timer variables, signal flags, waiters, and so on. Waiting X seconds before performing the next action isn't hard to code, but again the magnitude of things can become a problem quickly. Dozens of timers, eventually shared amongst multiple actions to make things worse. It's too easy to make mistakes, do 2 things at the same time, or screw up sequences with bad timing. Making your guy act as if he gets electrocuted all the time.

Usually you would make a list with tasks, and execute them one by one. But, now the real difficulty comes: our situation is Dynamic. As a computer foe, life is never certain. One moment you’re carrying cement bags, the next moment you’re fighting giant scorptions. Some tasks need to overrule other, but then again be careful not to mess up. You still need to walk –no run- over to the Player before you can slap him. 

Behavior Trees

BT's are there to help. Throw away all that messy A.I. code, and start modelling buddy. And no, I’m not talking about doodling some behaviour patterns on paper to code them later. The model(file) will actually replace the code! Doesn’t mean you don’t have to code anything anymore, but it will be limited to running the BT plus making small “building blocks” to construct that BT. I’ll explain.

Model made with this online tool:

Look at that picture, and tell yourself what happens here. It’s sort of a decision flow, starting at the left (although if you google BT's, they often to top-down). Probably you already figured, but basically it checks if it's hungry or tired, and if so, it executes a sequence of actions. Being placed higher, hungry gets priority over being tired. For starters, we can separate a BT in four types of nodes:

·         Composites (see the blue ones)
Elementary blocks to control the flow. They can run actions parallel or in a sequence, prioritize, or pick a random sub-node to execute. Composites do not actually actuate your NPC, but regulate the flow.

·         Conditions (see the green ones)
Basically the IF’s. Targer reached? Hunger more than 50%? Do we have the SkullKey item? Is Jack an asshole? That kind of questions. These (leaf)nodes are used to help prioritizing, or to interrupt a sequence at some point.

·         Actions (see the orange ones)
These (leaf)nodes actually actuate your NPC. Move over to X. Rotate, jump, salto-kick. Play a sound, do an animation, squeeze a fart.

·         Decorators (not visible in picture)
Used in combination with Conditions. Inverters (IF NOT x) or Delays to suspend actions.

Node that I just explained the very basic blocks. It’s up to you to add extra Composites, Conditions, Actions or Decorators, eventually with a list of parameters. For example, an action like “FindFridge” may require a maximum radius or zone, so we don’t loot the neighbors fridge. Now this where you programming skills shine; your engine/game/program has to offer a box of Lego bricks. A Shooter game would typically offer movement, aim, shoot and cover nodes, while The Sims is more about, ehm, looting fridges and making out in the bubble bath.

So, when implementing BT's, there are basically three components to deal with:
1.       The BT itself
Using a modeller program or even better –your own build-in editor-, producing BT files. Could be saved as XML for example.

2.       Set of Nodes provided by your engine
As explained above, you’ll need to code each type of node. In the end, you still need code to animate that robot, or to find a path through your maze.

3.       Engine that has to load BT & Run BT’s
Load a BT, and let your NPC’s make use of it. That involved logic that traverses the tree every cycle (sometimes referred as "Ticks"), executing the nodes that come accorss. Since a lot of actions may also rely on variable data, BT's are often accomponied by "Blackboards"; a (per entity, or global) storage space for custom values.

Johny Five routines

Now that BT is too simple, as usual with demo-models. A real game BT would have a lot more branches and nodes. So many, that you’re still having a hard time to comprehend. But that’s ok. Unless you’re a Jellyfish, you won’t able to model your own brain on a single paper, now would you? Still, using BT’s has a bunch of advantages.

First of all, the blocks you make are robust. Unlike on the fly/messy A.I. coding where you quickly end up taking dozens of scenario’s into account, smudging the “core business”, these Condition and Action nodes are really focussed on a single, simple task. A node that says “fart” just does that. Nothing more nothing less. It doesn’t check if your girlfriend is around, or if you had beans for diner. No! You –the A.I. designer- should do that prior to the action “Fart”, with other elementary nodes. That makes it fairly easy to code robust, proven, nodes. A simple node doesn’t do much, it’s all in making combo’s with others.

Although, nothing stops you from making more advanced nodes of course. Navigation and picking targets is a good example. It all sounds pretty simple, but there is a lot of logic behind that stroll from A to B. Why pick B? Can we reach it? What’s the shortest or best-quality route? And once the Nav-System has been set up, we still have to actually move our ass. Animate, rotate, climb stairs, and so on. We could spread that over many different micro-nodes, so we have FULL control over the entire procedure. But… it would be tedious. Instead we could compress all that action into a single, or fewer nodes, and use some additional parameters. For example, when picking a target, we could define parameters like “maximum distance”, or “what kind of target are we looking for?”. A fridge? A bed? Toilet? Human flesh maybe? And when we call “MoveToTarget”, we could define a speed, or pattern. Should we rush, sneak, or just chill out, not caring about a thing? Again, your engine decides what kind of parameters there are.

Long story short, lesser advanced blocks makes it easier and quicker to model behaviour, but limits your freedom. It’s up to you. Bear in mind though that Behavior Trees aren’t just limited to gunslingers and Johny-Five. Behavior Trees lend themselves well for robots, animated machinery, or puzzles. Check this door:
Yeah, even doors have a "Behavior". Of course we could hard-code all that stuff into the engine, but there will always be an exception. Especially if you're making weird puzzles, or want artists to use your engine to make their own stuff. And talking about artists, your art is to provide a toolset that is flexible, yet not too complicated. So, if well done, Behavior Trees allow non-programmers to create crazy scenario's without having to dive into the bits and bytes.

One last node I should make, is that you're not restricted to use a single HUGE BT. Of course different characters can load different BT files, but you could also chop it up into smaller modules. For example, a "Idle", "Walking", "Combat - weapons" and "Combat - fists" module. Monsters may use the same melee combat melee than people, but lack the Weapon module, and have different "Idle" behaviour. Where humans smoke cigarettes, chatter, scratch balls and take a dump, monsters eat flesh, fight each other, scratch balls, and also take dumps but without moving to a bathroom first. Apologies. Likely, a "combat" module can be split further into sections like weapon handling, finding cover, throwing grenades, and so on.

Seat-2D2 demo

Well, let's finish showing another model. Geared towards Engine22 this time. Disclaimer – I must admit I just started, so don’t expect rock solid awesomeness here. But as you can see in the little movie, it works J Without programming ANYTHING. Well, except for all the lower level engine stuff + a toolset of nodes to pick of course, but I mean nothing was programmed to make that “seat” chase me & make R2D2 sounds.
All these "PlaySound", "Rotate" and "Move" nodes have been implemented in Engine22, each with a bunch of parameters eventually.

So, what happened here? Every cycle the seat checks if it can see me(“Player”), by shooting a ray towards me. If the ray is interrupted or out of range, the seat will fall back to idle behavior, which results into either waiting, making noise, or moving short distances into a random direction. If it sees me –with a slight time delay, meaning it needs to see me at least a few seconds in a row- it will rotate towards me, then move forward, eventually correcting its angle a bit more as it slides. It keeps a minimum distance of 2 meters of me. It wants to move to me, not INSIDE me. And then it makes a cute sound.

Results? Here you go. Although Engine22 still lacks a tool to create and debug / visualize these trees (I imported the file export from ) it was quite easy to make this. It required a brain-reset to jump over from traditional programming to modeling, but once you're at it, it's fun to do.

As you may notice, the graphics aren't exactly what they used to be, compared to previous video's. That is partially because Engine22 has been re-programmed (thus a lot of shaders / effects / content is missing), and partially because these rooms simply didn't get a lot of love yet. Instead of pimping the graphics, I really try to focus more on making an actual playable game this time - hence the "working" player-physics and "A.I." you just saw. Of course, chasing seats won't make a thrilling game, but it's a start! 

And-yes-of-course, we will improve these rooms. But that requires artists, and last five years I learned it's very hard to find or keep artists if you're still far away from anything solid - a playable thing. Unfortunately, making a more robust engine, editors for the artist, pathfinding routines, or better physics to avoid falling through floors isn't the kind of stuff that generates awesome screenshots to show here. Which explains the lack of material lately here. But trust me, a lot of coding is going on. Hope you understand!

Sunday, April 24, 2016

Walk the line

Most programming-time on this project, disappears into improving graphics, making the editor a better man, or fixing bugs. Although engines, programming techniques and strategies get better and more robust every time you try, stuff still feels like a Jenga brick tower sometimes. Shove a new shader in here, and crap falls out at the other side - without you noticing until a week later, then wondering what the hell happened.

But I shouldn't forget, that we're making a game here. Or trying to at least. Making something you and me can *play*. So, once in a while, I step away from graphics and dive into game mechanics. A whole different area, I must say. Whatever game you're planning, the fun part is probably making your foes even smarter, designing puzzles, tweaking guns, testing what happens if you drive that race-car into garbage cans, et cetera. But... you're too far ahead maybe. Because a game begins with decent controls & basic physics.

Sure thing doc. But you know what? Making them Right, is pretty damn hard! Even if you have a proper physics library. Certainly because game-control-mechanics often have to cheat, overruling standard physics, collision and gravity rules, rather than using them. Getting a box tumbling down the stairs isn’t too hard. But getting a 200 pound guy moving upstairs is. It will bump, get stuck, rocket-jump into the sky, or more likely; stick on the ground like an Easter Island head.

Shoe laces thight
I take good controls for granted, 99% of the games have them right more or less, nowadays. Though the foul memoires of broken games haven’t faded completely. How many platform games fucked up, 30 years ago? Games didn't have too many problems stealing the ideas and visuals of Mario Bros. But copying the controls and mechanics was a whole different league. The player character being too fast, as if feeding an ADHD kid 200 red M&M's, six cola, and a line of speed before going to mcDonalds. Controls too slippery, as if ice-skating on olive oil the whole time. Too stiff, as if moving a 1 ton statue with the friction of a Thwomp. Too artificial, as if moving a rectangular sprite in horizontal or vertical patterns over the screen. Too sluggish, as in having a jump-button, but Arnold Schwarzenegger being too old to jump over a 30 cm obstacle, making it useless. Too unrealistic, as in total absence of any physical rules. Too realistic, as in having no control at all once you're airborne, realising you miscalculated the jump and heading into the abyss imminent.

Many old platform games failed miserably, because of unbalanced controls, or a level-design with impossible jumps. Or both. And not to mention the weird bugs. One thing I hated, was sprite-physics-anorexia. What I mean is that, even though the player sprite is 1 meter wide, its collision hull (an invisible shape used to test if it hits another shape) seems to be much thinner. Your feet would land on the edge of a platform, yet you would still fall down because the hitbox of your player missed the jump. It sucked, it seemed relative easy to fix, yet dozens of games screwed up. Also the opposite happened. A bumblebee would fly one feet over your head, yet still kill the player instantly because its oversized hitbox caught it.
Why L ?!! Well, I can tell you why. Again, because making physics is hard-core stuff, even for a platform game. I can tell, because I had the same weird shit in my 2D-hobby-games, where players would end up in the middle of the wall, raising upwards, straight out of the television. Detecting a "hit" isn't too bad (in 2D), but deciding what to do next, and making a 100% waterproof system is. Velocities, bouncing off, material frictions, taking the angles into account properly, and a big dose of magic numbers. 
Having a built-in jump-tester in the level editors would have saved dozens of broken joysticks and frustrated crying kids. But probably a lot of those shitty games didn't even have visual editors back then.

3D Crapdoll physics
The big transfer to 3D didn't really help either. Although a game like -of course- Mario 64 did remarkably well for one of the first serious 3D platform games with advanced moves, I couldn't count the number of awkward stunts on a hundred hands. Soldiers would drop through the deck of a moving boat, sink like a brick to the ocean bottom, then warp high into the sky to fall down to their deaths eventually (yes, I'm talking about Hidden & Dangerous here). Ragdolls would start spinning up to hyper speed, tearing their limbs apart, because they got hit by a closing door. Dead guys float in the air until I touch them with a fingertip, as they finally drop peacefully straight down (Fallout 4 + plenty of other modern games). Wrecked cars being launched to the moon after hitting that wall at the G-spot (GTA). Getting your head stuck through a wall, horrible clunky vehicle steering, flying in Limbo, …

Should I go on? Yeah, why not.  Giant dinosaurs worming through a 2 meter radius cave portal. Player not being able to proceed because required object used as a step-up fell through
the floor. Tough action hero’s that would drown instantly once being in 40 centimetres deep water. Cannot reach key of dead guard as his ass lays half inside a concrete wall. Being able to disable gravity and collisions by taking a wrong step somewhere in the corner of a map. Not able to get off the sofa after jumping on it because the ceiling is too low (Tower22). The list is endless, and if you look on Youtube, you quickly waste another few hours on watching this kind of stuff. Sometimes it works out well, like the Quake1 Rocket-jump ability, or having fun with flying cars in GTA. But most of the time it’s just, well... stupid.

That looks... painful. I think.

And at this point, T22 is still tormented with the same kind of bugs as well. But not the funny type of glitches. More the types where you want to smack the keyboard through a door, and decide to become a garbage man instead of a game-programmer for the rest of your life.  As you may know, Engine22/Tower22 uses "Newton" (not the guy, the code library) physics as a base layer. I'm not too sure about recent trends -to me it seems physics engines are a bit out of development last years-, but it’s free, and Newton was said to be quite accurate. Accurate my ass, when that stupid ball falls right through the floor again. Probably my fault somehow, though I often really can't explain the quirks. It works, works, works, then it suddenly goes wrong.

Role of a physics engine
Tower22 won't be a Prince of Persia game where you can climb walls upside down, take long jumps, or have to balance on ropes while riding the back of a tiger. But for starters, it would be nice if you can just walk in a straight line, rather than a drunk hobo who gets stuck behind doorsill.

Problem with game-physics, is that it's sort of a hack. Like with graphics, we'd like to found our physics on, well, real physics laws instead of (much simpler) programming abracadabra. Which is a good thing, but also complicates the situation at the same time. Rotating and moving an object forward with pure vector math is easy peasy. But the physics engine won't agree to do so, as your (player)object has friction with the floor, wants to spin like a vertical rolling-pin while sliding along a wall, get stuck in narrow passages, bounces you back when hitting an object, et cetera. Which is terribly annoying, because you're the MAN with the Controls. IF I say LEFT, go LEFT dammit.

But, if physics engines are so realistic... what exactly is the problem then? I mean, unless being on ice or having an epileptic seizure, you're in control. You stop when you want to stop, you can manoeuvre through a crowd without bouncing in the air, you can climb stairs and do a handstand while taking a piss, drunk. So again, the realistic physics engine can manage that for you as well, right?

No, it doesn't. Physics engines typically do 4 or 5 things:
  • Collision detection between primitives (spheres, cubes, cylinders,..), convex-hulls, and triangles (the world). Highly optimized, because doing this requires horsepower.
  • Collision response (friction between 2 surfaces, bouncing off, E=MC^2, ...)
  • Joint physics (ball & chain, hinge door, but also a ragdoll is basically a string puppet made of lots of primitives and joints)
  • Apply forces on bodies (gravity, spin, torque, movement, custom forces)
  • Special types like Fluids, Buoyancy or Cloth physics

Which covers a big important deal, but not everything. Player-physics for example are a black-art. Humans aren't boxes or capsules flying into all directions when you hit them. Or well, if a cement truck hits... Yet physics engines treat us just like that. Because *REAL* physics would be way too complex.

Obviously walking in real life isn't a matter of pushing us human-shapes forward. It's more a controlled form of tumbling forward, step by step. Push up, tilt forward, fall on the other foot. And repeat. No miracle it takes a baby some time to practice on his two legs (though I sometimes whish our youngest son never had legs, now that he learned how to climb onto practical everything). It's so difficult that God or Evolution gave most animals 4 or more legs, for Pete's sake. It's so difficult that hordes of scientists spend billions of dollars and hours into making robots that can do nothing but climbing stairs.

So having true human movement kinematics into games... better not. Even if it was available, it would probably beat the hell out the CPU. And then we have an alien character with 3 legs, or a crippled guy that walks on his hands... Got to start all over again. Just no. What we do have, is
either old fashioned homebrew fake-physics that are guaranteed to generate amazing stunts, or use the tools we get from a physics engine. Usually we do a hybrid; special rules for players, yet using an existing physics engine so it integrates with the other stuff in the game. Meaning it will bounce away a box if it was in your way, and meaning you can benefit from the same optimized collision detection systems.
Even the ED-209 hates stairs.

Jalapeno on a stick
Until recently, the Tower22 player was really just a capsule. On a stick. The tiny stick (cube) did some special stair stuff, and the somewhat wider capsule does the collision detection with other objects and of course the environment. Fortunately you can't see it (physic collision hulls are always invisible, the 3D mesh does not represent the actual physics shape), but man, it's a ridiculous model. Imagine everyone on street would look like Jalapeno on a stick, sliding forward by some invisible force. Because that is what happens, we push that thing forward, and use an up-constraint to prevent it from tumbling over. Like an invisible rope in the air that keeps us up.

Biggest problem is the sliding / pushing forward thing. What happens if you push a 80 kilogram washing-machine-box forward? Probably nothing, because it's fucking heavy. If you smear green soap on the floor, it may work though. So let's say we have green soap all over the place. Yeah, we're sliding now! Smooth as air-hockey! But crap, there is a little stump on the floor. Even though its 1 cm tall, it’s enough to block. Push harder, and the box tumbles, you landing on top. This is why a capsule-shape may work better, thanks to the rounding at the bottom, it has minimal contact with the ground, and it can lift up itself gradually. Over small obstacles at least. A 35 cm stair-step is either impossible, or requires an incredible amount of force. Increasing force is easy enough in a computer simulation, but hold your horses! Don't forget we also need to stop almost immediately when we release the forward button.

Oh dear, stairs. In the past that would mean you had to take 10 steps back, then charge like a raging bull, hoping your momentum would be enough to bring you upstairs.

Controlling the player like this, feels like manoeuvring the Bismarck. There is no direct control over it, you're at the mercy of physics. Which is exactly NOT what you want. I don't know how people do it in other physics engines, but Newton offers a bunch of "overrides", sort of. Rather than rocket-fueling force into the rear of my player, I can set its velocity. Sort of a PID-control will monitor the velocity and eventually correct it every cycle, in case it drifts off. Same stuff for controlling the spin force. If I say the player should be rotated 270 degrees, he'd better listen. The rotation is measured and guarded every cycle, meaning a correction spin will be applied as soon as the physics engine thinks otherwise (for example, when the player hits or gets hit by something). It works, but be careful that in some situation, you actually want the environment to have effect on our player. Well. Magical rules, overrides, different states... code quickly gets dirty for sure.

Scanning, Scanning, Error.
I didn't mention the stairs yet. The horror. As I tried to explain, we basically just push stuff forwards. But that's not how a human being climbs stairs! Lift a leg, place it one step higher, pull up. Well, we can't really simulate that with a stupid capsule on a stick. But we have some more David Copperfield magic up on our sleeves. If we can set forward-velocity, we can also set upward velocity. Obstacle in front of us? Add some "lift". Problem solved? Of course not.

How do hell do you know if there is an obstacle in front of you? And then I mean an obstacle you can pass, not a wall. Otherwise you would slowly lift yourself over the Chinese Wall, that's not how it should work. The player should scan its surroundings. For example, fire a ray forward from your toes, to see if there is something in front. If so, this *might* indicate a stair. But before rocketing up, do a second scan at balls-height. Still an obstacle? Then you can't simply step over it. You may need to leap over, if that's allowed in your game. But just sending some rays forward (like I did earlier) is prone to fail. Take a look at this picture:

That's a classy stair right? "Thanks" to its open gaps, my toe-sensors don't sense shit. So, no obstacle, no lifting. In other words, we're stuck. But wait a minute, there a are a billion other scenario's that can fool you. What if we were to climb to stairs while strafing or walking reverse? Toe-sensors have to measure into another direction, or it still fails. And what if we see the stairstep, but miss a metal pipe in front of our head? Head-bang. The most annoying are tiny obstacles (less than a CM tall), like rubble. Your sensor-rays may fly over them, but they are enough to stop or at least slow you down.

Scanning is one way to make decisions, but do not rely on a few rays only. Fortunately Newton provides convex-raycasting (like sending out a thicker volume, rather than a thin ray) which already does a better job, as it less likely slips through narrow holes or gaps. But a very different approach, is to simply flatten the stairs. And I'm quite sure older games did that a lot, and maybe even modern games still do so. In fact, due polygon limitations, old games actually had diagonal ramps rather than real block-shaped stairs. Yet, it feels a bit fake, as the player doesn't "hop up". Also the animation should change; you climb a stair, not run it. Idiot.

Looks like stairseps right? But look again, carefully at the edges. It's just a flat ramped polygon with a stairstep texture on it.

A third thing you can do, is making hints, or a context. And this sounds pretty logical. You could mark every "shape" as "floor", "wall", "ramp" or "stair". You decide what can be climbed, and what not. This at least avoids an automated scan to make mistakes, trying to climb stuff that shouldn't be. It also allows to make the player aware of more advanced manoeuvres on its path. Like "ladder", "rope" or "passable for AI only". Giving hints for players and NPC's. You would still have to scan forward, and as said, the level designer shouldn't forget to mark everything properly.

Yet at the same time, it feels as if this shouldn't be necessary. Can't remember having to do this for every possible obstacle in the Duke Nukem or Half life level editors. Also games with dynamic environments that can be altered by building or destructing stuff, probably don't have to mark everything. Obviously it would be nicer if the player-physics can figure out what to without hints.

So. How DID we do it?

As usual, I’m very good at showing a hundred and one failure situations. But more interesting, where is the cure? Well, I wasn’t exactly Newton’s best student back at school. Then again, as said, player physics is more about hacks anyway. In fact, the code is so… if there were Burqa’s for programming-code, this piece should definitely wear one. It’s the type of stuff you’re ashamed of. It’s not founded on rock-solid, robust, proven methods. But on numbers, case specific approaches, and cheap tricks. It feels as if it can collapse any moment. But reading Google, it seems this “Black Magic Code” just happens to be the norm. Okay… If you say so.

  • Skinny Capsule

So, first of all, I replaced “Jalapeno on a stick” with Jalapeno only; a Capsule. A relative thin capsule I must add, otherwise you’ll find your ass getting stuck in door portals. No Kim Kardashian collision hulls. This capsule has low friction and bounce settings. Basically we want as little contact with the environment as possible.

  • PID Controlled Velocity
As explained earlier, rather than just adding force into our desired direction, we measure the actual velocity (and spin), and add more or less if needed. This gives a more stabile speed, at surfaces with different friction settings.

  • Hover Shoes

Even though our capsule makes relative little contact, I still found myself getting stuck behind 5 millimetre floor height differences. A doorsill would be enough to keep me outside the room. Like Garlic hanging in front of Dracula’s nose, it just stopped moving. The solution? Sci-Fi hover shoes. I constantly apply upward force (or vice-versa, you could disable gravity while standing on the ground). Just a bit, to lift me off a few millimetres. Be careful not to add too much, or you will “wobble” like a flying space scooter.

  • Convex Cast ahead

No toe sensors, but we do a downward convex cast slightly ahead into our desired direction. I'm using a flat disc for this. Now we can compare our feet level with the obstacle height at the next step. If the difference is less than a defined “MAX_STEPHEIGHT”, we can engage our shoe thrusters further, giving upward velocity. Notice we can also do an upward scan. This is useful to signal NPC’s to start crouching, in case of an obstacle at head-height.

  • Downforce

We talked a lot about climbing stairs. But how about getting down, without flying through the air? By default, only gravity will pull you down. So you don’t really step down, you just fall. If you run fast enough, you won’t be touching the stair-steps at all, losing control while being airborne. What I did, is reversing my shoe thrusters to “press” you down rapidly. But only if the height difference isn’t too big. As shown in #4, the down-cast will get below the player feet. If less than “MAX_STEPHEIGHT”, downforce will be applied. In essence, it quickens the fall. Be careful not to apply downforce BEFORE you’re over the ledge, otherwise you get pinned to the ground just before taking a step down.
  • Baywatch

Just keep in mind you may walk through a wall, or fall through the floor for whatever reason. So you'd better have a lifeguard. Make a respawn point, or use some hard boundaries to prevent falling through. If the lowest point in a room is -2,5. then just disable gravity or even push up whenever the player threatens to get below that point. Yes, it's stupid and it shouldn't be necessary. But better safe than sorry.

Does this provide waterproof, fine controls? No, but at least it''s a step into the right direction. And moreover, I just wanted to give you an idea of things *can* be done. I still find myself in odd situations, like getting stuck in corners that are complex geometry-wise. Or flying up onto a steep ramped wall that shouldn't be climbed really. And for some reason I keep falling through that damn floor for no apparent reason. But at least its a lot better already.