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.
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.
- Short refresh about BT's
- Base Nodes - base code used for all nodes
- Composite Nodes
- Decorator Nodes
- Condition Nodes
- Action Nodes
- Ticks - "Looping"
- Blackboard - Custom memory storage container for trees
- Loading a Tree
- Registrating Node classes
1. Brain Refresh
Before
starting, really read the first article again (and those others I linked to) to
get a global understanding what a BT does. Grasp the "node" concept (composites, decorators, conditions, actions). But since those nodes
are the core of everything, I'll repeat the four main types once again. A BT is
made of nodes, which come in the following main flavours:
1. Composites
"Flow regulator"
nodes. They execute one or (usually) more child-nodes. This can be performed in a certain
order (a "Sequence") or randomly. It can be done conditional, meaning it stops as soon a
child-node FAILED or is still RUNNING. Or it just executes them all regardless.
2. Conditions
A check on something, returning
SUCCESS or FAIL. Is it 12 o clock? Does player have the Blue-Key in his inventory? Are
we within 5 meters from our target? Did we get hit by a flamethrower?
3. Actions
Stuff that actually does something in your game/program/robot. Pick a target, move to X, rotate, animate, play sounds,
give 10% health, perform a karate kick, et cetera.
4. Decorators
A couple of handy logic blocks
that can be placed in front of Composites or Conditions to invert, delay or manipulate
their results in some way. "NOT" Player-is-Cool.
And as told,
nodes can return one of these three states:
- SUCCESS - Condition met or Action completed. Onto the next thing.
- FAIL - Condition not met, Action cannot complete.
- RUNNING - Task not done yet / pending. Still moving towards X, pie needs to be 10 more minutes in the oven.
Plus, for
debugging purposes, you could add an ERROR
result, for nodes that couldn't get executed because you gave them wrong
parameters or something, or the code within raised an exception. Shouldn't
happen, but it does happen when you develop things. Can help tracing faults.
It's up
to us to implement these four types of nodes, and then to override them with
our own stuff, because obviously, Conditions and Actions are very different for
each application. Welding robots have rotate, coordinate, and well, welding actions,
while a boxing games is more in terms of dodging and beating the shit out of
that single opponent.
Right,
got the basics? If not, go back to start and do not receive 20.000$. In
Engine22, this is my basic file lay-out,
for now:
* E22_AI.BehaviorTrees.pas
***
E22_AI.BehaviorTrees.Blackboard.pas
***
E22_AI.BehaviorTrees.Nodes.pas
*****
E22_AI.BehaviorTrees.Nodes.Composites.pas
*****
E22_AI.BehaviorTrees.Nodes.Decorators.pas
*****
E22_AI.BehaviorTrees.Nodes.Conditions.pas
*****
E22_AI.BehaviorTrees.Nodes.Actions.pas
Since
there will be a LOT of Conditions and Actions mainly, those files may branch
further probably.
You
could split into movement, combat, idle behaviour, et cetera. As for the "Blackboard",
that's not a pirate name but a memory storage container we can use for our
tree(s) to read/write custom data to. But let's begin coding them pesky nodes
then.
2. Them pesky nodes – BASE NODE
Delphi being
OOP, we should start with an abstract "base-node" that can be used by all other nodes that will follow. Here, bang, Turbo Pascal time:
eAI_BT_BaseNode = class
private
isOpen : eBool; // Node has been evaluated this tick, or in a previous tick & still running
// Information
nodeTitle : aString32; // Custom title
nodeDescription : aString128; // Custom description, by artist
nodeCoords : eVec2; // X Y, for editor views
nodeGUID : aString48; // Unique ID
public
parentNode : eAI_BT_BaseNode; // Decorator or Composite node that links to us
procedure initialize( parentNode : eAI_BT_BaseNode ); virtual; // Set initial vars and such
destructor destroy(); virtual;
// Execution
function _execute( tick : peAI_BT_TickInfo ) : eAI_BT_Result;
procedure enter( tick : peAI_BT_TickInfo ); virtual; // called every time a node is executed
procedure open( tick : peAI_BT_TickInfo ); virtual; // called only when the node is opened (when a node returns RUNNING, it will keep opened until it returns other value or the tree forces the closing);
function tick( tick : peAI_BT_TickInfo ) : eAI_BT_Result; virtual;
procedure close( tick : peAI_BT_TickInfo ); virtual; // called when a node return SUCCESS, FAILURE or ERROR, or when the tree forces the node to close;
procedure exitNode( tick : peAI_BT_TickInfo ); virtual; // called every time at the end of the node execution.
// Editing
function getTitle() : uString;
procedure settitle( const title : uString );
function getGUID() : uString;
procedure setGUID( const GUID : uString );
function GUIDequals( GUID : uString ) : eBool;
function getDescription() : uString;
procedure setDescription( const desc : uString );
function getCoords() : eVec2;
procedure setCoords( const x,y : eFloat ); overload;
procedure setCoords( const v : eVec2 ); overload;
// Child management
procedure addChild( node : eAI_BT_BaseNode ); virtual;
procedure removeChild( node : eAI_BT_BaseNode ); virtual;
function getChildrenCount() : eInt; virtual;
function getChild( const index : eInt ) : eAI_BT_BaseNode; virtual;
// Property management
function getPropertyCount() : eInt; virtual;
function getProperty( const index : eInt ) : eAI_BT_NodeProperty; virtual;
procedure setProperty( const index : eInt; const value : uString ); overload; virtual;
procedure setProperty( propName : uString; const value : uString ); overload; virtual;
procedure copyFrom( otherNode : eAI_BT_BaseNode ); // Copy props from another node
// Visualizer (editor)
procedure draw(); virtual;
end; // eAI_BT_BaseNode
I hope
this header-code is somewhat self-explanatory. Plus you can forget about 75%,
as most methods are for (future)editing purpose. If you use an external editor,
you don’t have to define coordinates, descriptions or drawing functions. More
important are the Execute, Open, Tick, and Close functions:
·
Tick This runs the
actual node evaluation code.
·
Open Called when the node is called for
the first time since closed last time
·
Close Called when the node is “done”
(SUCCEEDED or FAILED, not RUNNING)
·
_execute Calls all the enter/open/tick/close/exit
functions in the right order
function eAI_BT_BaseNode._execute( tick : peAI_BT_TickInfo ) : eAI_BT_Result;
var status : eAI_BT_Result;
listIndex : eInt;
begin
// Add to "Entered" list
tick.evaluatedNodeCnt := tick.evaluatedNodeCnt + 1;
listIndex := tick.openedNodes.count;
tick.openedNodes.Add( self ); // Keep track of the evaluated nodes.
// Can be intreesting for debugging, visualizing,
// or optimizing later on.
// Open
self.enter( tick );
if not ( self.isOpen ) then begin
self.isOpen := true;
self.open( tick ); // not opened before
end;
// Execute logic
status := self.tick( tick );
// Close
if ( status <> eAI_BT_RUNNING ) then begin
self.close( tick );
// Remove ourselves & children nodes
while ( tick.openedNodes.count > listIndex ) do begin
eAI_BT_BaseNode( tick.openedNodes[tick.openedNodes.count-1] ).isOpen := false;
tick.openedNodes.Delete( tick.openedNodes.count-1 );
end;
end;
self.exitNode( tick );
result := status; // Report our result to our parent node
end; // _execute
Note
that this “execute” function is potentially called every cycle, for every node
(in the worst case). Games or Realtime robotic applications tend to cycle
through their program many times per second, evaluating their logic.
BehaviorTrees refer to this as “ticks”. More about that later.
2.2 Custom Node Properties
The
nodes that we’ll make later, will mainly override the Tick and Open functions,
doing your magic. Also not unimportant, are the “Property” functions. In many
cases you want to feed your Actions or Conditions with some background info. A
“setTarget” action also wants to know “WHAT TARGET?!”. The player? The closest
foe? The toilet bowl? And a “check clock” function should know what time to
check in terms of hours and minutes. Each node has a fixed number of
properties, each with a name, type (int, bool, float, string,
vector(coordinate)), unit and default value. When loading trees from files
later on, those names are important for matching. Other info is mainly
interesting if you plan to make your own editor.
eAI_BT_NodePropertyType = ( eAI_BT_PropBOOL = 0,
eAI_BT_PropINT = 1,
eAI_BT_PropFLOAT = 2,
eAI_BT_PropVEC3 = 3,
eAI_BT_PropVEC4 = 4,
eAI_BT_PropCOL3 = 5,
eAI_BT_PropCOL4 = 6,
eAI_BT_PropSTRING = 7,
eAI_BT_PropENTITY = 8,
eAI_BT_PropSOUND = 9 );
eAI_BT_NodeProperty = record
idName : aString16;
value : aString128;
defaultValue : aString128;
unitName : aString8;
propType : eAI_BT_NodePropertyType;
procedure make( name : string; value, defaultValue : eInt; const unitName : string ); overload;
procedure make( name : string; value, defaultValue : eFloat; const unitName : string ); overload;
procedure make( name : string; value, defaultValue : eBool ); overload;
procedure make( name : string; value, defaultValue : uString; const typ : eAI_BT_NodePropertyType ); overload;
procedure make( name : string; value, defaultValue : eVec3 ); overload;
procedure make( name : string; value : eES_EntityID ); overload;
end; // eAI_BT_NodeProperty
3. Composite Nodes
So far,
abstract meaningless code. Let’s override that abstract node and turn it into a
real node we could use, starting with composites. There aren’t many types of
composites, and although you are completely free in giving them names and
logic, you should try to follow the standard types of composites. Some very
common ones are:
·
(Memorized)
Sequence
Loop through children, until one returns
SUCCESS or FAIL (abort the sequence). If it’s a memorized sequence, resume the
child-node we evaluated previous tick.
·
Priority
or Selector
Basically the IF THEN ELSE. Stop looping though
the children as soon as one returns SUCCESS or RUNNING.
·
Parallel
Executes all children, regardless their
outcome. Eventually return SUCCESS if more than X children succeeded.
And then
there is the START or ENTRY node. Which doesn’t do shit, but connected to a
single child. This where the tree starts. Keep in mind a Tree could execute sub-trees,
starting at their entry points (and eventually returning an overall result as
well).
Probably
you will be using Sequence to begin with. We can code them as follow:
eAI_BT_NodeComposite = class( eAI_BT_BaseNode )
public
children : TList;
procedure initialize( parentNode : eAI_BT_BaseNode ); override;
destructor destroy(); override;
procedure addChild( node : eAI_BT_BaseNode ); override;
procedure removeChild( node : eAI_BT_BaseNode ); override;
function getChildrenCount() : eInt; override;
function getChild( const index : eInt ) : eAI_BT_BaseNode; override;
end; // eAI_BT_NodeSequence
// Execute all children until one NOT returns SUCCESS
// Return SCCUESS if all childen succeeded, FAIL if any of the children FAILED
eAI_BT_NodeSequence = class( eAI_BT_NodeComposite )
public
function tick( tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
end; // eAI_BT_NodeSequence
// Same as Sequence, but keep track of the position so earlier succeeded children
// won't be re-executed until the parent node was closed.
// Return SCCUESS if the last child succeeded, FAIL if any of the children FAILED
eAI_BT_NodeMemSeq = class( eAI_BT_NodeComposite )
private
runningChildIndex : eInt;
public
procedure open( tick : peAI_BT_TickInfo ); override;
function tick( tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
end; // eAI_BT_NodeMemSeq
{ eAI_BT_NodeSequence }
function eAI_BT_NodeSequence.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
var i : eInt;
begin
// Loop through children until one FAILED or RUNS
for i:=0 to self.children.count-1 do begin
result := eAI_BT_BaseNode( self.children[i] )._execute( tick );
if ( result <> eAI_BT_SUCCESS ) then
exit; // FAIL or RUN
end;
result := eAI_BT_SUCCESS; // All children executed with SUCCESS
end; // tick
{ eAI_BT_NodeMemSeq }
procedure eAI_BT_NodeMemSeq.open( tick : peAI_BT_TickInfo );
begin
self.runningChildIndex := 0;
end; // open
function eAI_BT_NodeMemSeq.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
var i : eInt;
child : eInt;
begin
// Start where we ended last time (was running previously)
child := self.runningChildIndex;
// Loop through children until one FAILED or RUNS
for i:=child to self.children.count-1 do begin
result := eAI_BT_BaseNode( self.children[i] )._execute( tick );
// Wait until current child finished
if ( result <> eAI_BT_SUCCESS ) then begin
if ( result = eAI_BT_RUNNING ) then
self.runningChildIndex := i; // For next Tick
exit; // FAIL or RUN
end;
end;
result := eAI_BT_SUCCESS; // All children executed with SUCCESS
end; // tick
So here
we showed how a (memorized) sequence can be implemented. As you see, it still
doesn’t do much other than executing children. Those children could be other
Composites, Decorators, or eventually Conditions and Actions. Quite often a
sequence will first check one or more Conditions:
Sequence à IF
health < 25 (condition)
Find
medkit (action)
Move
to medkit (action)
Pick
up medkit (action)
Boedha
time (action)
If those
first conditions aren’t met, there is often no need in executing any further
actions. Be aware with Memorized Sequences though, that those conditions aren’t
re-checked every tick. If the dog eats the medkit in the meanwhile, our NPC
still continues his procedure, unless there is some exit strategy implemented.
4. Decorator Nodes
A very
basic, but useful decorator is the Invertor or “NOT” node. Decorators always
have a single child, and manipulate their results. The invertor turns SUCCESS
into FAIL, or vice-versa.
eAI_BT_NodeDecorator = class( eAI_BT_BaseNode )
public
child : eAI_BT_BaseNode;
procedure initialize( parentNode : eAI_BT_BaseNode ); override;
destructor destroy(); override;
procedure addChild( node : eAI_BT_BaseNode ); override;
procedure removeChild( node : eAI_BT_BaseNode ); override;
function getChildrenCount() : eInt; override;
function getChild( const index : eInt ) : eAI_BT_BaseNode; override;
end; // eAI_BT_NodeDecorator
eAI_BT_NodeInverter = class( eAI_BT_NodeDecorator )
public
function tick( tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
end; // eAI_BT_NodeInverter
{ eAI_BT_NodeDecorator }
procedure eAI_BT_NodeDecorator.initialize( parentNode : eAI_BT_BaseNode );
begin
inherited initialize( parentNode );
self.child := nil;
end; // initialize
destructor eAI_BT_NodeDecorator.destroy();
begin
// Do not destroy children, must be done by owner tree
inherited destroy();
end; // destroy
function eAI_BT_NodeDecorator.getChild(const index: eInt): eAI_BT_BaseNode;
begin
result := self.child;
end; // getChild
function eAI_BT_NodeDecorator.getChildrenCount() : eInt;
begin
if ( self.child = nil ) then
result := 0 else
result := 1;
end; // getChildrenCount
procedure eAI_BT_NodeDecorator.addChild( node : eAI_BT_BaseNode );
begin
self.child := node;
end; // addChild
procedure eAI_BT_NodeDecorator.removeChild( node : eAI_BT_BaseNode );
begin
self.child := nil;
end; // removeChild
{ eAI_BT_NodeInverter }
function eAI_BT_NodeInverter.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
begin
if ( self.child = nil ) then
result := eAI_BT_ERROR
else begin
result := self.child._execute( tick );
if ( result = eAI_BT_SUCCESS ) then
result := eAI_BT_FAIL else
if ( result = eAI_BT_FAIL ) then
result := eAI_BT_SUCCESS;
end;
end; // tick
Got
that? Fine, onto the real interesting nodes: Conditions and Actions.
5. Condition Nodes
There
are no default Condition nodes, as they really depend on your needs. But let’s
come up with something practical; a node that checks if a certain entity (could
be the player, but also a hamburger) is within range. We will also provide some
custom properties to this node. The desired distance in meters, and an entity
idName – the target to check. Note by the way that Condition (or Action) nodes
do not have children, so their “getChildrenCount()” should always return 0.
eAI_BT_NodeCondition = class( eAI_BT_BaseNode )
public
end; // eAI_BT_NodeCondition
eAI_BT_Node_cEntInRange = class( eAI_BT_NodeCondition )
private
entity : eES_EntityAbstract;
entityIdName : uString;
distance : eFloat;
public
procedure initialize( parentNode : eAI_BT_BaseNode ); override;
procedure open( tick : peAI_BT_TickInfo ); override;
function tick( tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
function getPropertyCount() : eInt; override;
function getProperty( const index : eInt ) : eAI_BT_NodeProperty; override;
procedure setProperty( const index : eInt; const value : uString ); override;
end; // eAI_BT_Node_cEntInRange
{ eAI_BT_Node_cEntInRange }
procedure eAI_BT_Node_cEntInRange.initialize( parentNode : eAI_BT_BaseNode );
begin
inherited initialize( parentNode );
self.distance := 5;
self.entityIdName:= '';
self.entity := nil;
end; // initialize
function eAI_BT_Node_cEntInRange.getPropertyCount() : eInt;
begin
result := 2;
end; // getPropertyCount
function eAI_BT_Node_cEntInRange.getProperty( const index : eInt ) : eAI_BT_NodeProperty;
begin
case (index) of
0: result.make( 'entity' , self. entityIdName, ‘Player’, eAI_BT_PropENTITY );
1: result.make( ‘distance’ , self.distance , 5, 'meters' );
end;
end; // getProperty
procedure eAI_BT_Node_cEntInRange.setProperty( const index : eInt; const value : uString );
var id : eUInt64;
begin
case (index) of
0: self.entityIdName := value;
1: self.distance := strToFloat( value );
end;
end; // setProperty
procedure eAI_BT_Node_cEntInRange.open(tick: peAI_BT_TickInfo);
begin
if ( self.entity = nil ) then begin
// Find our target
self.entity := _ES.getManager().getEntityByName( self.entityIdName );
end;
end; // open
function eAI_BT_Node_cEntInRange.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
var dist : eFloat;
begin
if ( self.entity = nil ) then begin
result := eAI_BT_FAIL;
end else begin
try
// Get distance between our parent entity, and our target
dist := self.entity.getPos().distanceTo( tick.myEntity.getPos() );
except
result := eAI_BT_FAIL; // Maybe entity got unloaded in the meanwhile
exit;
end;
if ( dist < self.distance ) then
result := eAI_BT_SUCCESS else
result := eAI_BT_FAIL;
end;
end; // tick
Be aware
that this node is sensitive for some faults. Maybe the entityName was spelled
wrong. Maybe we found the entity, but it get destructed later on. Also, when
setting properties, you may want some exception checking on top of that, in
case we give invalid numbers. The whole purpose of BehaviorTrees is to provide
(the artist / mapper / designer) a robust tool to create A.I.. And people make
mistakes, so be prepared.
6. Action Nodes
The last
type of node we show; Action-Man. Actions actuate something. We could use them
to write some custom data into our memory “Blackboard”, to pick a target, to
throw grenades, and so on. Typically we want to split up into simple actions
that can be reused for a lot of different procedures. Moving is an excellent
example, though a difficult one because movement contains a ton of deeper
(engine) logic. Picking a target, moving to it, physics, gravity, collision
detection, animation, inverse kinematics while climbing a stair, and so on. You
could deal with each of those sub-actions via your BehaviorTree, but it might
be easier for the A.I. designer to let the engine take care of that
automatically.
For demo
purposes, I picked a simpler action: doing nothing. A delay. After an
adjustable amount of seconds, it will return SUCCESS. But as with many actions,
this takes a while. In the meanwhile the node turns “RUNNING”. This affects the
way how parent composites deal with it. Memorized Sequences will remember the
current action, so it can be called again next tick, proceeding.
eAI_BT_NodeAction = class( eAI_BT_BaseNode )
public
end; // eAI_BT_NodeAction
eAI_BT_Node_aWait = class( eAI_BT_NodeAction )
private
elapsed : eFloat;
waitTime : eFloat;
public
procedure initialize( parentNode : eAI_BT_BaseNode ); override;
function getPropertyCount(): eInt; override;
function getProperty(const index: eInt): eAI_BT_NodeProperty; override;
procedure setProperty(const index: eInt; const value: uString); override;
procedure open( tick : peAI_BT_TickInfo ); override;
function tick( tick : peAI_BT_TickInfo ) : eAI_BT_Result; override;
end; // eAI_BT_Node_aWait
{ eAI_BT_Node_aWait }
procedure eAI_BT_Node_aWait.initialize(parentNode: eAI_BT_BaseNode);
begin
inherited initialize( parentNode );
self.elapsed := 0;
self.waitTime:= 1;
end; // initialize
function eAI_BT_Node_aWait.getPropertyCount(): eInt;
begin
result := 1;
end;// getPropertyCount
function eAI_BT_Node_aWait.getProperty(const index: eInt): eAI_BT_NodeProperty;
begin
result.make( 'time' , self.waitTime , 1, 'sec' );
end; // getProperty
procedure eAI_BT_Node_aWait.setProperty(const index: eInt; const value: uString);
begin
case ( index ) of
0: self.waitTime := strToFloat( value );
end;
end; // setProperty
procedure eAI_BT_Node_aWait.open(tick: peAI_BT_TickInfo);
begin
self.elapsed := 0; // Reset timer when we got re-opened
end; // open
function eAI_BT_Node_aWait.tick(tick: peAI_BT_TickInfo): eAI_BT_Result;
begin
self.elapsed := self.elapsed + tick.deltaSecs;
if ( self.elapsed >= self.waitTime ) then
result := eAI_BT_SUCCESS else
result := eAI_BT_RUNNING;
end; // eAI_BT_NodeWait
7. Watch out for Ticks
All right, so far the nodes. The only way to really get comfortable with them, is just by doing. My advice, start with a simple scenario, like the “Seat-2D2” video showed, and model it in a free tool, just to get a hang on it. As you goi, you’ll figure out what kind of nodes you’ll be needing, and what kind of parameters they should use. And very likely, you will rethink your whole node toolset at some point, generating a more logical, easier to use set. Don’t be afraid to take some missteps. The beauty is that you can relative easily remove and introduce new nodes to your package; the code above it – that runs the tree- won’t be affected.The next thing to do, is making a “Tree” class. The BT itself is a collection of nodes, and provides the logic to run them.
eAI_BT_TickInfo = record
deltaSecs : eFloat; // Elapsed time between 2 cycles
entity : eES_Entity; // Parent entity (NPC)
blackboard : eAI_BT_Blackboard; // Custom Read/Write Memory
navigator : eAI_Navigator; // For movement, pathfinding
// Evaluation
evaluatedNodeCnt : eInt;
openedNodes : TList; // Tracker of evaluated nodes
end; // eAI_BT_TickInfo
peAI_BT_TickInfo = ^eAI_BT_TickInfo;
eAI_BT_BehaviorTree = class
private
tick : eAI_BT_TickInfo; // Arguments to pass to the nodes when executing a tick
blackboard : eAI_BT_Blackboard;// Memory container
navigator : eAI_Navigator; // For movement
inUse : eBool;
instanceGroup : eAI_BT_BehaviorTreeInstanceGroup;
public
root : eAI_BT_BaseNode; // Start evaluation here
allNodes : TList; // All (sub)node instances used in this tree
constructor create();
destructor destroy();
procedure clear();
procedure execute( entity : eES_Entity; const deltaSecs : eFloat );
function addNode( const nodeClassIdName : uString;
parentNode : eAI_BT_BaseNode ) : eAI_BT_BaseNode;
function getNode( const GUID : uString ) : eAI_BT_BaseNode;
procedure removeNode( node : eAI_BT_BaseNode );
// Loader
procedure copyFrom( otherTree : eAI_BT_BehaviorTree );
procedure loadFromFile_B3JS( const filename : uString ); // Online editor: http://behavior3js.guineashots.com/editor/
procedure loadFromStream_E22( str : TStream ); // Engine22 build-in format
end; // eAI_BT_BehaviorTree
{ eAI_BT_BehaviorTree }
constructor eAI_BT_BehaviorTree.create();
begin
inherited create();
// Blackboard
self.blackboard := eAI_BT_Blackboard.create();
// Navigator
self.navigator := eAI_Navigator.create();
self.allNodes := TList.Create();
self.inUse := false;
self.instanceGroup := nil;
// Root
self.root := eAI_BT_NodeRoot.create( );
self.root.setTitle( 'root' );
self.root.initialize( nil );
end; // create
destructor eAI_BT_BehaviorTree.destroy();
begin
self.root.destroy();
self.clear();
self.allNodes.destroy();
self.blackboard.destroy();
self.navigator.destroy();
inherited destroy();
end; // destroy
procedure eAI_BT_BehaviorTree.clear();
var i : eInt;
begin
for i:=0 to self.allNodes.count-1 do begin
eAI_BT_BaseNode( self.allNodes[i] ).destroy();
end;
self.allNodes.clear();
self.navigator.reset();
end; // clear
procedure eAI_BT_BehaviorTree.execute( entity : eES_Entity; const deltaSecs : eFloat );
begin
self.navigator.update( entity, deltaSecs );
// Init tick arguments
self.tick.openedNodes.clear();
self.tick.entity := entity;
self.tick.deltaSecs := deltaSecs;
self.tick.blackboard := self.blackboard;
self.tick.navigator := self.navigator;
// Tick root-node, and everything beyond...
self.root._execute( @tick );
end; // tick
procedure eAI_BT_BehaviorTree.copyFrom(otherTree: eAI_BT_BehaviorTree);
begin
self.root.copyFrom( otherTree.root );
end; // copyFrom
function eAI_BT_BehaviorTree.addNode( const nodeClassIdName : uString;
parentNode : eAI_BT_BaseNode ) : eAI_BT_BaseNode;
begin
result := _ES_MakeBehaviorTreeNodeInstance( nodeClassIdName, parentNode );
self.allNodes.add( result );
end; // addNode
procedure eAI_BT_BehaviorTree.removeNode( node : eAI_BT_BaseNode );
begin
// Detach
if ( node.parentNode <> nil ) then begin
node.parentNode.removeChild( node );
end;
self.allNodes.remove( node );
node.destroy();
end; // removeNode
function eAI_BT_BehaviorTree.getNode( const GUID : uString ) : eAI_BT_BaseNode;
var i : eInt;
begin
for i:=0 to self.allNodes.count-1 do
if ( eAI_BT_BaseNode( self.allNodes[i] ).GUIDequals( GUID ) ) then
begin
result := eAI_BT_BaseNode( self.allNodes[i] );
exit;
end;
result := nil;
end; // getNode
Typically
each Entity / Agent / NPC has its own Tree. This brings a slight difficulty… What if we
have 200 soldiers, all using the same tree? You can’t directly share the same
tree-instance, because internal variables like delay-timers, target coordinates
or the actual node states (running, failed, …) can be different for each
soldier.
The
tutorial I linked to in my previous post solves this by NOT storing any
instance-dependant variable into the node objects. Instead, everything is
written to a “Blackboard”. This blackboard contains the run-state of each and
every NPC that uses the tree, as well as a global section so variables can be
shared amongst multiple NPC’s. This can be useful in particular when your army
or squads share tactical info. A commander NPC could set global goals for a
whole group of soliders.
However,
I chose not to do it like that. Because adding, overwriting, removing and
getting all those variables via lists is slow and painful, I’d say. Instead, I’ll
make a copy of the entire tree for each instance. Now, Tower22 won’t have 200
enemies. Yet it doesn’t sound like a very performance-friendly method either.
To partially fix that, Engine22 does a lot of recycling. Yes, we are very
green. If a tree is released (entity went to Hell), it will be available for
another instance.
So, when
I need a tree of typeX, (say file “monkey_BT.txt”), a manager will first check
if there is an unused tree available. Ifso, give that one –and reset it before
usage. If there is no tree available, a new one will be created. But instead of
loading the whole file again, it copies its content from another tree. Engine22
does this for a lot of memory-eating resources by the way.
7.2 Even-Driven?
One more
thing I should mention about Ticks & Tricks, are events. Right now, a NPC
has a single tree and just checks everything, always. That introduces a few
problems. How about high priority stuff like getting killed? It would suck
pretty much if your opponent doesn’t die because his faulty BT skipped the
“Die-Hard” section, as the “eating cookies” branch got a higher priority. And
also in general, polling if something happened (every cycle) just isn’t very
performance friendly.
You
could decide to run different trees instead, based on events. “OnHitByBullet”,
“OnCollision”, “OnPlayerInSight”, “OnTargetReached” or “OnClicked” are
beautiful examples of that. It will result into multiple, but smaller
“to-the-point” behaviortrees. It may run more efficiently, and reduces
modelling faults. Then again it will also reduce flexibility, as your model
relies on the available engine events. Yet I’m seriously considering this for
Engine22.
8. Captain Blackboard
Blackboards
are memory containers. Although BehaviorTrees do not store each and every state
value into a Blackboard, we still use them for custom variables. Those are
either per-NPC variables. Like “hunger” which could be different for each
instance. But there is also a global Blackboard, containing shared variables
that can be accessed by all NPC’s. We all want to know who the player is. And
for a soccer team, we could write the score as a single number, rather than
maintaining the score number for each NPC individually.
From an
engine design perspective, custom data is always tricky. We’re trying to make
Tower22 in Engine22, but we could just as well make Pac-Man with it. Both games
have very different BehaviorTrees, and thus also very different data behind
them. In other words, the engine should not make a whole list of “expected”
variables. It doesn’t know which variables there will be, neither should it
care about. Game specific code, which includes BehaviorTrees should manage
that.
Yet for
performance reasons, the E22 Blackboard does have some pre-defined variables,
like a “PrimaryTarget”. Whether it’s a Pac-Man ghost, Tower22 monster,
Black-Ops trooper or racing car, they (almost) always have a goal; something to
engage, pick-up or move over to. So, there are some Set/Get primaryTarget
functions. But other than that, custom variables are simple tuples with a
key(id name) and a value.
eAI_BT_BlackboardVar= class
public
key : uString;
value : uString;
defaultValue : uString; // Reset
end; // eAI_BT_BlackboardVar
// Use a blackboard to Read/Write data via a BehaviorTree
// One board assigned per Tree - thus per NPC
eAI_BT_Blackboard = class
private
// Primary target
targetEntity : eES_EntityAbstract; // Primary target
targetLocation : eVec3; // Fixed target location - if there is no entity
targetAssigned : eBool; // True whenever set. Set false once reached or lost.
// Custom values
variables : TStringList; // Sorted list of
public
constructor create();
destructor destroy();
procedure reset();
// Primary target
procedure setPrimaryTarget( targetEntity : eES_EntityAbstract ); overload;
procedure setPrimaryTarget( targetLocation : eVec3 ); overload;
procedure setPrimaryTargetNone( );
function primaryTargetIsEntity() : eBool;
function hasPrimaryTarget() : eBool;
function getPrimaryTargetEntity( ) : eES_EntityAbstract;
function getPrimaryTargetPos( var targetLost : eBool ) : eVec3;
// Custom values
procedure writeVar( const key : uString; const value : eInt ); overload;
procedure writeVar( const key : uString; const value : eFloat ); overload;
procedure writeVar( const key : uString; const value : eBool ); overload;
procedure writeVar( const key : uString; const value : eVec3 ); overload;
procedure writeVar( const key : uString; const value : uString ); overload;
function readVar( const key : uString ) : uString;
end; // eAI_BT_Blackboard
In order
to Write those variables, you could make an Action node for that: “writeVar”.
Either pick a global or NPC blackboard as a target, and give it a name + value.
Reading
and using them is a bit more tricky. Of course you can read, write and do math
internally in your overrided Node code, using the functions above. But it would
also be interesting if we can replace fixed values with variable references,
when defining properties in our BT modeller. I didn’t code anything for this
(yet), so I won’t dive into this further, but it can be something to keep in
the back of your mind, when coding your BT engine.
9. Plant and Load a Tree
As
promised, we close this article with some code that reads the JSON file, produced
by this online BT editor:
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;
(* EXAMPLE
"90282381-684c-461e-b61c-11684778b0e5": {
"id": "90282381-684c-461e-b61c-11684778b0e5",
"name": "Priority",
"title": "Priority",
"description": "",
"display": {
"x": -320,
"y": -160
},
"parameters": {},
"properties": {},
"children": [
"88e3cb42-bb69-4774-ba9f-411a2b6db4ed",
"08a6f505-2184-478b-b56b-d527f1d8ff60"
]
},
*)
procedure trimValueString();
begin // Remove tail comma, if there is one
if ( length(val) > 1 ) then
if ( val[ length(val) ] = ',' ) then begin
val := val.subString( 0, length(val)-1 );
end;
end; // trimValueString
procedure trimKeyString();
begin // Remove tail comma or :, if there is one
if ( length(key) > 1 ) then
if ( key[ length(key) ] = ':' ) or ( key[ length(key) ] = ',' ) then begin
key := key.subString( 0, length(key)-1 );
end;
end; // trimKeyString
procedure readChildren();
begin // Read node "children" references (GUIDs) sub-block
while ( sFile.readRawLine(line)) do begin
strReadLine( line, key, values );
if ( key = ']' ) then exit;
trimKeyString();
child := self.getNode( key ); // Get node from list via GUID
if ( child <> nil ) then begin
cNode.addChild( child ); // Fill children list
child.parentNode := child;
end;
end; // while
end; // readChildren
procedure readProperties();
begin // Read node "properties" sub-block
while ( sFile.readRawLine(line)) do begin
strReadLine( line, key, values );
key := upperCase(key);
if ( key = 'PROPERTIES:' ) then exit;
if ( key = '},' ) then exit;
if ( values.count < 1 ) then continue;
val := values[0];
trimKeyString();
trimValueString();
try
cNode.setProperty( key, val );
except
// No such property
showMessage( 'Warning: cannot set property '+key+' = '+val );
end;
end; // while
end; // readProperties
begin
self.clear(); // Clean up old crap first
values := TStringList.create();
try
sFile := strTextFileReader.create( filename, 'eAI_BT_BehaviorTree.loadFromFile_B3JS' );
except
sFile.destroy(); // Cant open file, fuck you
exit;
end;
// Loop through file, create all nodes
// BUT DO NOT LINKED THEM WITH EACH OTHER YET (nodes can refer to uncreated subnodes)
cNode := nil;
while ( sFile.readRawLine(line)) do begin
strReadLine( line, key, values );
key := upperCase(key);
if ( values.count < 1 ) then continue;
val := values[0];
trimValueString(); // Remove tail character from string
if ( key = 'CUSTOM_NODES:' ) then break;
if ( key = 'ID:') then cGUID := val else
if ( key = 'NAME:') then begin
cNode := _ES_MakeBehaviorTreeNodeInstance( val, nil );
if ( cNode = nil ) then continue;
cNode.setGUID( cGUID );
self.allNodes.add( cNode );
// don't know the parent yet - do that later
end else
if ( cNode <> nil ) then begin
if ( key = 'TITLE:') then cNode.setTitle( val ) else
if ( key = 'DESCRIPTION:') then cNode.setDescription( val ) else
if ( key = 'X:') then cNode.setCoords( strToInt(val), cNode.getCoords().y ) else
if ( key = 'Y:') then cNode.setCoords( cNode.getCoords().x, strToInt(val) ) else
if ( key = 'PROPERTIES:') then begin
end else
if ( key = 'PARAMETERS:') then begin
readProperties();
end else
if ( key = 'CHILDREN:') then begin
// Skip for now
end else
end;
end;
// Repeat, now read children
cNode := nil;
sFile.restart();
while ( sFile.readRawLine(line)) do begin
strReadLine( line, key, values );
key := upperCase(key);
if ( values.count < 1 ) then continue;
val := values[0];
trimValueString(); // Remove tail character from string
if ( key = 'ROOT:') then self.root.addchild( self.getNode(val) ) else
if ( key = 'CUSTOM_NODES:' ) then break;
if ( key = 'ID:') then cNode := self.getNode( val ) else
if ( key = 'CHILD:' ) and ( cNode <> nil ) then begin
// Single child
trimValueString(); // Remove tail character from string
child := self.getNode(val); // Get via GUID
if ( child <> nil ) then begin
cNode.addChild( child );
child.parentNode := cNode;
end;
end else
if ( key = 'CHILDREN:') and ( cNode <> nil ) then begin
// Multiple children
readChildren();
end else
end;
// Clean up crew
values.destroy();
sFile.destroy();
end; // loadFromFile_B3JS
This
code won’t run straight away, because it uses quite a lot Engine22 string
functions, but hopefully you get the point. One important aspect here though,
is the “_ES_MakeBehaviorTreeNodeInstance” function. Given a Node classname
(such as “Sequence” or “aMoveToTarget”), it will create a node instance from
that class.
10. Registrate node classes for usage
Each
node class is registered during startup, like this:
begin
_ES_RegisterBehaviorTreeNodeClass( 'cEntInRange' , eAI_BT_Node_cEntInRange );
_ES_RegisterBehaviorTreeNodeClass( 'cHasTarget' , eAI_BT_Node_cHasTarget );
_ES_RegisterBehaviorTreeNodeClass( 'cTargetRaycast' , eAI_BT_Node_cTargetRaycast );
_ES_RegisterBehaviorTreeNodeClass( 'cRaycast' , eAI_BT_Node_cRaycast );
_ES_RegisterBehaviorTreeNodeClass( 'cClockLaterThan', eAI_BT_Node_cClockLaterThan );
_ES_RegisterBehaviorTreeNodeClass( 'cClockBetween' , eAI_BT_Node_cClockBetween );
_ES_RegisterBehaviorTreeNodeClass( 'cClockLaterThan', eAI_BT_Node_cCalenderCheckDay );
end.
Note
that code is placed at the bottom section, and will be executed right away when
the program starts. The _ES_RegisterBehaviorTreeNodeClass function maintains a
list of nodes and classes, so we can create an instance of those classes later
on, giving the name of the class.
//******************************************************************************
// BEHAVIOR REGISTRATION
type
eES_BehaviorTreeNodeSpecs = record
nodeClass : TClass;
idName : uString;
end; // eES_BehaviorSpecs
var
_ES_RegisteredBehaviorTreeNode : array[0..255] of eES_BehaviorTreeNodeSpecs;
_ES_RegisteredBehaviorTreeNodesCnt : eInt = 0;
procedure _ES_RegisterBehaviorTreeNodeClass( nodeIdName : uString;
nodeClass : TClass );
begin
if ( _ES_RegisteredBehaviorTreeNodesCnt > 255 ) then begin
showMessage( 'ERROR: Cannot register more than 255 different BehaviorTree Node Classes!' );
exit;
end;
_ES_RegisteredBehaviorTreeNode[ _ES_RegisteredBehaviorTreeNodesCnt ].nodeClass := nodeClass;
_ES_RegisteredBehaviorTreeNode[ _ES_RegisteredBehaviorTreeNodesCnt ].idName := nodeIdName;
inc( _ES_RegisteredBehaviorTreeNodesCnt );
end; // _ES_RegisterBehaviorTreeNodeClass
function _ES_MakeBehaviorTreeNodeInstance( nodeIdName : uString;
parentNode : eAI_BT_BaseNode ) : eAI_BT_BaseNode;
var i : eInt;
begin
for i:=0 to _ES_RegisteredBehaviorTreeNodesCnt-1 do begin
if ( nodeIdName = _ES_RegisteredBehaviorTreeNode[i].idName ) then begin
result := eAI_BT_BaseNode( _ES_RegisteredBehaviorTreeNode[ i ].nodeClass.Create() );
result.initialize( parentNode );
exit;
end;
end;
showMessage( 'WARNING: BehaviorTree Node Class "'+ nodeIdName +'" does not exists!' );
result := nil;
end; // _ES_MakeBehaviorInstance
Well, I
hope this LOOONG-ASS article suited your BT needs boys and girls. Hopefully the
code snippets were somewhat readable and understandable. Next time we talk
about boobs, beer and games again, easier for me.
