Thursday, August 11, 2016

Status update: Playable Demo

Overall there is little visual progress, mainly because I'm pretty much alone on the project once again. And I won't be actively searching for artists (or funding) at this point. I could, but likely we end up as always; artist-X thinks T22 is interesting and has six-hundred hours a day available. He or she "joins", not really knowing what to expect (where is the office? where is the rest of the team? where is the game? where are the tools? where are the documents? where are the goals? where is the compensation?). Concluding: a bit of a bummer. And a few weeks later he or she claims to be "very busy".

Being very busy is the code-word for “screw it, I have better things to do”. School, work, moving into another house, dog died, computer crashed, et cetera. I've heard it all, and many times. After some months and three half-finished assets later, artist either just disappears, or says he has to quit because of circumstances. With two kids and two jobs, I consider myself pretty busy as well. I don’t believe in “too busy”, but I understand you won’t be spending those few free hours on something… vague.

Yeah, managing a team is much more than just telling them what you want, and giving some compliments or feedback time to time. Most people, including myself, want short-term results. A quick dose of fun. Modelling 3D seats that will be used not until two years later -maybe-, isn’t fun. Drawing concepts that never come alive, isn’t fun. Recording sound for non-existing monsters, isn’t fun. So before asking again, I feel the project must be much better prepared, being in a further stage. But how to get there in the first place? Chicken Egg story. Artists will be attracted to projects with potential. But to make a project look promising, you will need artists. Difficult situation.

Made half of the assets here. It doesn't look too well, but at least the viewer understands what's going on here. Besides, making kettles or kitchens instead of programming is nice for a change.

Make it, Work it, Fix it
But what I CAN do, in contrary to what happened before, is making an actual game as much as
possible. It doesn't have to look good, hence this is where artists can shine; feed them ideas
and let them work it out to something beautiful. So what I did last months/year, is just making
the game. You may have read about physics and AI(behaviour trees) in previous posts. If you forget
about graphics for a moment, these are also (if not more important) building-blocks for a game.
Walking a player, climbing stuff, picking up keys, solving a puzzle, showing an inventory, dealing with enemies, et cetera. Plus there needs to be an engine and editor part where we can script/program all that stuff in a robust and comfortable way.

Another thing I did, is making most maps that will be used in the Playable Demo. Corridors,
rooms, that kind of stuff mainly. Note Tower22 is basically one huge map, but made of smaller “sectors”. Being limited in skill, using a half-finished renderer, and having a small asset palette only (most Tower22 objects and textures made before were more industrial oriented, rather than old building / apartments / Soviet crap), these maps are empty and ugly. BUT, at least you can walk through them now, which hopefully gives future artists a much better understanding of the road ahead. And of course, artists can replace dummies and "play" their own stuff now.

I only have to finish a few more maps. Prototype maps, I must add. If an artist thinks corridor-X should look different, or proposes a slight different routing through the playable demo, of course we can change things, although the "Demo Walkthrough" has been written already. This document describes all the events and sequences in the demo (do this, go there, do that, bla bla). So I also started implementing actual game-scripts. For example, one of the very first “puzzles” is to do a couple of things in your apartment, before the front-door unlocks. Dress, prepare food, answer the phone. Sounds easy, but it triggered me to code quite a few additional things to make those puzzles work. An inventory system, a day/night cycle, combining or using items, door mechanics, semi-dynamic lightmaps that allow to turn lights on or off, affecting their indirect light. And a lot of API functions that can be called by LUA scripts or Behaviour Trees to play sequences, set the clock, unlock doors, switch lights, and so on. In short; facilitate engine functionality to make an actual playable game.
Now that is NOT a good looking inventory. Old fashioned really, now that most games have a quick-access ingame HUD spin-dial -whatever to call them-, or no inventory at all. But anyhow, point is that we have *something* that works, and giving the artist food for improvement. 

The bigger picture
Only coded the very first minutes of “GamePlay”, but eventually it will speed up, as the tools, API and library-of-whatever-is-needed grows. But other than describing these in-depth game-details, that Walkthrough Document also states the more overall goals. What is it, that we want to show? If the demo was finished tomorrow, and people would download it, what should they experience?

Of course, a horror game. But again that is easier said than done, as I think the horror-genre is an extreme difficult one. Why? Because it’s not about making a "fun" game. If you aim for a soccer game, the focus should be on soccer, super smooth controls, and realism. If you're making a shooter, the focus is on cool weapons, challenging A.I. and maps that lend themselves for addictive battle. If you're making a horror game, the focus is on scaring people, which contradicts the fun-part usually. Tower22 won't throw you into an arena with weapons. Smiles on your face won't cooperate with uncomfortable feelings. In general, games like Silent Hill or Resident Evil aren't much fun (and no, the later RE titles aren't true horror games in my opinion). But boy, we really want to know what happens next. From one wet pants to another, sadomachochism.

To make things even more difficult, T22 is a slow-suspense game. No buckets of blood in your face, no hideous creatures leaping at you every twelve seconds. The fear-element in this game should be much more subtle. Even though you don’t directly see it, you know things are messed up. Something bad is coming. Sure there will be some jump scares, and clichés, but all in all I try to make an unique setting, avoiding the tricks, scenery and plots you have seen too many times already. In other words, there is no real reference for this game, so I can’t really predict if this game will be fun, scary, or intriguing either.

Dummies for Dummies
So, how to make sure a short demo will accomplish this vibe? We got some issues here. First of all, resources and time are very limited, and even if I could make anything, you don’t pull out the big-guns for a (teaser)demo yet. It starts gentle. Second, having these maps modelled and loaded into the game now, it's still a far cry from anything scary. What I see, is mainly a buggy, clumsy, unfinished world. Plus I had those maps in mind for quite some years now, so they don't come as a surprise either. Yes, more than most puzzle or action games, horror games rely a lot on good sound and graphics.

And notice "good graphics" doesn't necessarily mean next-gen photo-realistic super graphics. But the contents have to consistently follow a certain style. Having re-programmed the whole engine, with a lot of features still disabled, I feel my re-newed rooms still miss that "personal touch" my previous results had. That engine wasn't perfect, but being a bit dark, blurry and noisy, rooms certainly had a certain vibe, in contrary to the cold fabricated renders I have now. But hey, let's not drift too far away into graphics again. My point was that I'm trying to setup an actual game now, following the locations and puzzles/scripts/events the documents describe.

Again I find this pretty hard though. One of the very first things that will happen, is you hearing an old phone ringing, and picking it up. But obviously pretty much all resources for even such a simple
event are still lacking. I actually do have a phone model, but no table or furniture to put it on. No ring-ring sound, no pickup animation, and definitely not a weird voice that speaks over the phone.
Since I can't wait for artists to make all that stuff (because I practically have none), my answer
should be in "dummies". Just make a simple ugly table. Pick up the mic and say "ring. ring.". Use
Microsoft Sam or deform your own voice for the conversation that follows. Of course it sucks, but the artist now knows exactly what to do, and it functions as a temporary place-holder so we can proceed with the next event.
So there you have your dummy telephone on a dummy table in a dummy room, accompanied by "Hints" that can show additional info, pictures, internet-links.

Only little problem is that I hate making ugly stuff or hearing my own voice. I'll quickly end-up putting way too much energy into trying doing it good (but probably with mediocre success only). So instead of making a boring desk object, I'd rather spend my energy on programming something else... like a day/night cycle skybox + cascaded shadowmaps for the sun like I did few weeks ago. Well, that's something I have to learn, and making a list of "stuff to finish" with relative simple jobs will probably help me doing it, no matter how silly or boring.

Too bad this drives me even further away from a scary game though. Picking up a fake phone and hearing Microsoft Sam isn't scary, it's ashaming. Of course an artists will polish it one day, hopefully, but with that thought still in the back of your mind, you just can't test and judge your own horror game. Somebody else needs to do that ;) 

Lost Fantasies
I also noticed making horror-scenario's requires constant training. As I'm getting older, I play less
games, and my fantasies are becoming more mature (read more boring). As a kid, your brain flies through space, candyland, naked girls, war-torn cities, silly jokes, hellish creations, castles and drunk nights. Or even better, a non-logical combination of all of that. As an adult, your brain flies through taxes, work, annoyances about the neighbours, making your kids eat broccoli, and how the garden should be restyled. I hate to say it, but creativity slowly drains away, and putting your mind 200% into an horrific Soviet style skyscraper gets more difficult. I should be reading more books, movies and play more games again (but Silent Hill with an 8 year old daughter...). But also, I should make time to fantasize again. Sounds childish, but really. I shouldn't have swapped my bicycle for a car few years ago, because those 60 minutes each day were great for drifting away into a T22 scenario or whatever fantasy, while cycling to work.

So we have a kitchen here. Next step; make it look better. Final step -and the real challenge; make it contribute to a terrifying horror atmosphere one way or another.

Well anyhow, that's my status update. So basically I'm making a simplistic, dummy variant of the
playable demo, and when I feel its "ready enough", I'll ask artists to replace those dummies with
cool stuff. And being a bit more finished programming-wise by then, I hopefully have more time to
direct them. Doing on-request engine features, improve the tools, review their work, compensate with a bit of money, ensuring the goals remain clear, et cetera. Not that artists wouldn’t be welcome today, but I just want to make sure I do a better job keeping them in, before asking again.

Final stage -when the demo is "beautified" and functional- is to poke some famous Youtube dude(s), to walk through it. A good way to reach far more people. If people like it and want to see more, that would be an appropriate time to launch a Kickstarter campaign. I could do the same now as well, but with only a few thousand people knowing about this project... Timing and patience, my friends.

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!