Behaviour Trees

It’s been raining all day and night here.
I decided to spend some time playing with lezak’s BehaviorTree codebase.
After doing that for some time, I decided to find a decent editor I could use to create my trees, rather than using hardcode or handcrafting xml/json.

I came across “owl-bt” today. https://www.npmjs.com/package/owl-bt
I’ve fallen in love with its simple approach and engine-agnostic design.
Super easy to add new custom node types and even declare custom data types…
Saves to json. Hotloads your changes. Runs in your web browser.

I can see myself putting together code to load that json into lezak’s codebase, which is also highly flexible, and seems to be well thought out, other than one small issue… it’s a classical implementation of BT, and so there is no thought to data oriented design or re-use of existing subtrees…

Behaviour tree nodes that contain dynamic data are a no-no… (nodes that use constant or statically shared data are ok)…
If we do that, and by that, I mean store any dynamic values in our nodes, then we can’t easily reference entire subtrees at runtime, which means that every actor that needs a BT has to have a whole unique copy of said tree instantiated at runtime.

A perfect example is a repeater node, that holds a counter. We need to store that data outside the node, and pass it in our calling context, then we are “sweet”.

Just my two cents worth.

1 Like

Interesting find. I was searching for s.t. like it without the hassle of putting together an editor… Thx

1 Like

– referencebot

1 Like

Have started writing code to load the json saved by owl-bt
I thought I’d mention a couple of things I’ve noticed so far:

  1. Any node can have a Name - but the editor does not display them or let you set them.
  2. Node properties are not serialized if they bear the value we specified to be default (similar to Urho attributes).
  3. Manual editing of the owl-bt.json file usually (but not always) is hotloaded by the editor.
  4. Manual editing of mytree.json file is never hotloaded (refresh your browser to reload the tree)

I am still very happy with this editor because it is so easy to adapt to your custom bt node types.

Since I have access to class names, I’ve decided to let the parser attempt to construct node instances by name via class object factory method. Since I use scripting little if at all, I’ve been searching for a while for a good reason to register object factories, in a context where I could take advantage of name-based instantiation. It’s a shame we can’t register factory functions with arguments.

What is the proper way to cast a shared pointer in Urho? If I am using factory instantiation, then I get a SharedPtr, which is not really what my object type is.

@johnnycable, yeah, “something like it” was what I needed too - something that was not dedicated to an existing codebase or engine, and was easily configurable for my nefarious purposes.
I certainly wanted to avoid writing a full fledged editor, though there is some sourcecode floating around that I could have used to do so - it’s just not a good use of my time, for my project, to create custom editor solutions, when I can just rely on established stuff like xml and json, and deal with that at my end.

What I see in Urho (and what I often do) is cast the raw pointer. SharedPtr::Get() et al.

1 Like

[WARNING: WORKAROUND HACK CODE AHEAD! Also - this code is not complete…]

What I was looking for was Detach()…

Urho’s object factory implementation returns a shared pointer, but deep in my recursive json parser it was not necessary or even desirable to have my object pointers wrapped at all, let alone by the insidious shared pointer (hey - I DO use them, but I want to decide when and where something gets wrapped in one of those…)

I did need to perform an upcast from Urho3D::Object to my baseclass prior to calling Detach in order to ensure I was returned the correct object type.
Also, I think I’ll rename my classes to avoid the following ugly name-mangling… owl-bt calls its classes “Sequence”, “Selector” etc., while lezak’s classes are called “SequenceNode”, “SelectorNode”, and so on - and its the C++ class name that matters when instantiating class objects by name via factory.

    BehaviorTreeNode* BehaviorTree::ParseNodeFromJSON(const Urho3D::JSONValue& jvalue){
        String nodetype =jvalue.Get("type").GetString();
        String nodename =jvalue.Get("name").GetString();

        /// Instantiate the node by typename
        SharedPtr<BehaviorTreeNode> newNode(context_->CreateObject(nodetype+"Node")->Cast<BehaviorTreeNode>());

        /// If that failed, we probably forgot to register a node class with Urho!
        if(newNode==nullptr){
            URHO3D_LOGERROR("JSON PARSER - UNHANDLED NODE TYPE: "+nodetype);
            return nullptr;
        }

        /// Process node properties (if any)
        Urho3D::JSONArray props=jvalue.Get("properties").GetArray();
        for(auto it=props.Begin(); it!=props.End(); it++)
            ParseNodePropertyFromJSON(*it);

        /// Process node decorators (if any)
        Urho3D::JSONArray decorators=jvalue.Get("decorators").GetArray();
        for(auto it=decorators.Begin(); it!=decorators.End(); it++)
            ParseNodeDecoratorFromJSON(*it);

        /// If the node we just created is a Composite type?
        CompositeNode* n=newNode->Cast<CompositeNode>();
        if(n){
            /// Call initializer method on composite type
            n->OnFactoryConstruct(this, false, nodename);

            /// Process child nodes (only Composite Nodes should have children!)
            Urho3D::JSONArray children=jvalue.Get("childNodes").GetArray();
            for(auto it=children.Begin(); it!=children.End(); it++)
                n->AddChild(ParseNodeFromJSON(*it));
        }
        else
        {
            /// TODO:
            /// Node is some kind of Leaf node...
            /// Set a breakpoint here!
            int x=0;
        }

        /// HACK:
        /// Node Factory Function gave us a SharedPtr, but we did not really want one.
        /// We know there's no other "owners" of the shared pointer...
        /// Let's detach the raw pointer from the shared pointer :)
        return newNode.Detach();

    }

My code now returns raw pointers to the caller, who is in turn responsible for storing them in smart pointer objects. This is somewhat better than trying to pass / return shared pointers across call boundaries, and all the needless construction, copying and destruction that involves.
It would be nice if the Context class / Factory implementation provided a constructor that returned a raw pointer… is there something I missed?

1 Like

The reason that I have chosen to use factory instantiation is just this: once written, the same parser/loader code will still work, even if we register new node class types to Urho, with no further changes needed in the loader (99 percent of the time).

I tried to get my JSON parser to register new class attributes - this turned out to be a fizzer for several reasons, but I found an amicable workaround in the UIElement class - it implements a serializable attribute (variantmap type) called “Variables” (vars_ membername). I could easily add such an attribute to my base BT node class, so ANY node can potentially own an arbitrary list of properties / named and typed variables which would serialize easily.
I realized quickly that I could just add “node properties” as typed variants in a serialized map - this way, my classes did not need to express any details pertaining to properties.
Now dealing with some small issues involving an incomplete typemapping between JSON and Urho.

There are a bunch of “gotchas” when working with lezak’s behaviortree code.
I’ll try to put together some kind of documentation, as the owl-bt editor has very few limitations, while lezak’s code has a number of limitations where it comes to tree topology and execution.

One example is that the (owl-bt) editor will let you add multiple Decorators to any node in the tree, while the current codebase only allows one decorator per node.

It took me most of a day to completely implement and test the following node types:

Composites: Selector, Sequence, Parallel
Actions: LogAction, WaitStepsAction
Decorators: Invert, Loop, Success, Failure, IsBlackboardValueSet, IsBlackboardValueEqual

I found testing difficult, mainly because my understanding of how a BT works is fairly different to this (stack-based) re-entrant implementation. I am trying to cope, docs on the way (“it’s a man page”)

The first “gotcha” is that lezak’s BT nodes only support ONE Decorator. If you make more in the editor, they will not be loaded by my code (room to address this).

The second “gotcha” is that Decorators are only executed by nodes whose child reported that they completed (ie, not running).

The third, is that there are corner cases where Decorators won’t run at all.
I will try to elaborate on this as my understanding increases.

My next step is to implement something missing from lezak’s codebase: Service nodes… these basically execute a script… my first real foray into a reason to use script at all, coming right up…

Since decorators only “run late”, I may also introduce the notion of “guard node” - where one decorator node may prevent the execution of the node to which it is attached.

This is not immediately a good fit with the owl-bt editor, but I can work with it, given the flexibility in the editor, and possibly petition the author to extend their work.

Here’s a screenshot showing some customizing of Owl-BT … I can load and run this behaviortree, not that it does much yet - it’s just a testing ground to help me verify my custom node implementations and to help me to perform sanity-checking.

Most nodes can be annotated with comments, and composite nodes support random or ordered child execution. Owl-bt has no support for testing tree logic inside the editor, but I’ve never seen a BT editor that did - it has no idea how our implementation works!

My loader code attempts to automatically deal with new node types and node properties, which makes life pretty easy for the coder to support new node types should new requirements emerge.

I’ve implemented “SetVariable” and “IsSetVariable” as “action nodes” (aka leaf nodes).

SetVariable stores a named and typed value in the context of the owner tree (for now).
Currently supported types are string, number (evaluates to a float) or bool.
Unsupported types generate suitable debug spew.

IsSetVariable just tells us if some named variable has been set at all.

Action nodes can return Success, Failure or Running.
My “LogAction” node always returns Success - unless explicitly decorated to return something else.

“SetVariable” likewise, always succeeds, unless decorated.

But “IsSetVariable” can return Success (variable exists) or Failure (no such variable).

The variables of which I speak currently reside in a VariantMap (aka Blackboard) held by the BehaviorTree container object, but more correctly belong in a visiting Agent, or at least a Calling Context. These are not global variables, they represent the “knowledge” of the AI Agent who is the chief subject of the tree execution.

Today I extended lezak’s BT codebase to support Subtree recursion. The changes should allow us to do two important things:

  • be able to construct complex behaviors by referencing more simple ones … building blocks
  • be able to share one behaviortree instance across any number of actors … persistent data is not stored in the tree

The concept is that we have a special kind of Leaf node which holds a weak reference to another behaviortree, and acts as a proxy by executing the subtree and returning the result of the subtree execution to the parent node (of the proxy node) in the usual way (for behavior tree nodes).
One instance of such a node in a behaviortree is representative of an entire nested copy of some other tree. Of course, no such cloning of subtrees is actually done… instead, we can rely on a little logic: the execution-sensitive variables owned by the nodes in one subtree are safe for the entire execution of that subtree - and if we prevent subtree nesting, then they are safe across subtree executions, as they exist in a single “frame of tree execution”. In order to deliberately share data across subtrees, I chose a Blackboard approach…

I began by changing the return value of BehaviorTree::Process() to return the BTNodeState value from the root node execution all the way back to the caller of Process method.
This would allow a subtree to return its result to a caller node in a parent tree.

Secondly, I introduced the notion of a BehaviorTreeContext object which is passed down during subtree recursion - this acts as a “Blackboard” that nodes can read and write to, which contextually is “owned by the actor who is the subject of tree execution”. This mechanism allows data variables to persist and be shared by multiple subtrees, while remaining the property of the caller, and not the property of any individual node or subtree.

Thirdly, I added a guard stack to the BTContext object, so that it can remember which subtrees it has previously recursed during a single execution of the entire tree, and will trigger an error if an attempt is made to recurse a previously-visited subtree (to prevent the possibility of infinite recursion).

Fourthly, I added a static HashMap<String, SharedPtr> BehaviorTree::SubTreeLibrary and static methods to add your loaded behaviortree objects to the library, and to locate existing subtrees by name.
This mechanism will allow the JSON loader to locate previously-loaded behaviors by name alone.

The code all compiles and looks to be complete and logically sound… I’ll test it soon, need to modify owl-bt to support my new Subtree proxy node.

[EDIT]
All tested and working!
I’m loading two behaviortrees, and storing them as named behaviors. One of these two trees represents the root, and it contains a proxy node that references the other subtree. When that proxy node is reached, it executes the child tree, then returns the result from the child tree.

I’ve only tested a single depth-level of subtree recursion, but it works fine, and I can’t imagine why it would fail at deeper levels (ie, subtrees referencing even finer subtrees).
You just need to be mindful of a few things (time to write some docs?) - some are: subtrees must be loaded before attempting to load any higher behavior that references them, and we need to think more carefully about how the return value from a subtree is interpreted by the parent tree.

From now on, I don’t have to deal with large, sprawling, complex trees in the owl-bt editor - I can concentrate on one small sub-behavior at a time.

Here’s what the code looks like now for proxy-execution of a Subtree… We can see the implementation of the new signature for the execution entrypoint … BTNodeState BehaviorTree::Process(float, BehaviorTreeContext*)

    BTNodeState SubTree::HandleStep(){
        if(tree_->btContext_==nullptr)
        {
            URHO3D_LOGERROR("Behavior Subtree cannot execute with no Context!");
            return NS_ERROR;
        }
        return subTreeRef_->Process(tree_->timeStep_, tree_->btContext_);

    }

It is vital to note the use of a cascading execution context argument, this is our “persistent data container, per calling agent”. It’s the blackboard which allows us to share both subtrees and entire trees across multiple game entities, and it also implements my safety code to prevent problems associated with subtree nesting.

Each behaviortree has members to hold the calling BTContext and the deltatime - these values are set when a subtree is about to be processed, and so become available to all nodes in that tree, including those belonging to subtrees, since these values are passed from parent tree to child subtree in the Process() entrypoint call. These values are NOT passed during node-stepping within a single subtree, including the root subtree - they are simply retained and shared for the duration of the frame of execution.

Here’s what the class definition looks like for SubTree node.

    class SubTree:public LeafNode
    {
        /// All BehaviorTree nodes derive from Urho3D::Serializable
        /// The reason is that we support full serialization (to file) of node-local properties.
        URHO3D_OBJECT(SubTree, LeafNode)
        
    public:
    
        /// Registers this class with Urho3D (required for factory-based instantiation)
        static void RegisterObject(Context* context);

        /// Called by JSON Loader to "unpack Properties" associated with this class
        /// The only property for this Node that matters is the SubTreeName string.
        /// It will never change again for this object instance, so this is a good place for Loader to set that member
        virtual void OnFactoryConstruct();

        /// Factory Constructor: This is what the JSON Loader uses
        SubTree(Context*);

        /// Set this node's subtree reference to the given BehaviorTree instance
        void SetSubTree(BehaviorTree* subtree){ subTreeRef_ = subtree; }

        /// Set this node's subtree reference from Behavior Library, according to the subTreeName_ member
        void SetSubTree();

    protected:
        /// We redefine the execution behavior for this node.
        /// Basically we just execute this node's subtree reference, and return what it gives back to us.
        virtual BTNodeState HandleStep() override;

        /// Set by JSON Loader
        /// Unique Name of the Behavior that this node will attempt to execute
        String subTreeName_;
        
        /// See SetSubTree methods
        /// Holds reference to a BehaviorTree
        WeakPtr<BehaviorTree> subTreeRef_;

    };

Love to hear your thoughts, though it’s probably ready to upload somewhere for proper evaluation.

For the sake of completion, and sorry if this is a lot to take in!

    /// Execution Context for processing a BehaviorTree:
    /// The calling AI Agent should implement this class!
    ///
    class BehaviorTreeContext{
    public:
        /// Used to store variables during tree execution
        VariantMap blackboard_;

        /// Used to guard against subtree re-entrancy (infinite recursion)
        /// BehaviorTree::Process() is responsible for this safety mechanism
        Vector<WeakPtr<BehaviorTree>> subtreeStack_;
    };

Here is the per-game-actor container we hand in when we execute our root ai behavior.
It has two members: one is the blackboard of shared variables for this agent, representing what this agent “knows” about the game world, and the other is a guard stack, used to stop bad things happening due to re-entrancy.

This guy should probably be a struct, but thus far, my code is still only in the testing phase, so I am not too worried about the fact there’s no code in this class.

Sorry for belated thanks, your reply
helped me get back on track

1 Like

For anyone who is experimenting with owl-bt, or is interested in doing so, here is the json I use to modify the editor for my purposes so far. Maybe you will see something in here you can use too.
This replaces the “owl-bt.json” configuration file… you’ll figure it out if you haven’t already :slight_smile:

{
    "nodes": [
        {
            "name": "Selector",
            "icon": "question",
            "isComposite": true,
            "description": "{{Name}}: isRandom = {{isRandom}}",
            "properties": [
                {
                    "name": "isRandom",
                    "type": "bool",
                    "value": false,
                    "default":false
                },
                {
                    "name": "Name",
                    "value":"SelectorNode",
                    "default":"[nameless]"
                }
            ]

        },
        {
            "name": "Sequence",
            "icon": "arrow-right",
            "isComposite": true,
            "description": "{{Name}}: isRandom = {{isRandom}}",
            "properties": [
                {
                    "name": "isRandom",
                    "type": "bool",
                    "value": false,
                    "default":false
                },
                {
                    "name": "Name",
                    "value":"SequenceNode",
                    "default":"[nameless]"
                }
            ]
        },
        {
            "name": "Something",
            "icon": "question",
            "isComposite":true,
            "description": "Is blackboard value \"{{Field}}\" set",
            "properties": [
                {
                    "name": "Field",
                    "type": "string",
                    "default":"set me"
                }
            ]
        },{
            "name": "LogAction",
            "icon": "arrow-up",
            "isComposite": false,
            "description": "Log << \"{{Text}}\"",
            "properties": [
                {
                    "name": "Text",
                    "type": "string",
                    "default":"set me",
                    "value": "something"
                }
            ]
        },
        {
            "name": "WaitStepsAction",
            "icon": "arrow-",
            "isComposite":false,
            "description" : "Wait for \"{{Counter}}\" ticks",
            "properties": [
                {
                    "name": "Counter",
                    "type" : "number",   
                    "default":0,                 
                    "value": 2                    
                }
            ]        
        },
        {
            "name": "SetVariable",
            "icon": "arrow-down",
            "isComposite":false,
            "description" : "Set \"{{VarName}}\" to {{Type}}  \"{{Value}}\"",
            "properties": [
                {
                    "name": "VarName",
                    "default":"[not set]",                 
                    "value": "varName"           
                },
                {
                    "name": "Value",
                    "default":"[not set]",                 
                    "value": "value"           
                },
                {
                      "name": "Type",
                      "default": "None",
                      "type": "enum",
                      "values": [
                        "string",
                        "number",
                        "bool",
                        "Panic"
                      ]
                }
            ]        
        },
        {
            "name":"IsSetVariable",
            "icon": "arrow-up",
            "isComposite":false,
            "description" : "Does \"{{VarName}}\" exist?",
            "properties": [
                {
                    "name": "VarName",
                    "default":"[not set]",                 
                    "value": "varName"           
                }
            ]
        },{
            "name":"SubTree",
            "icon":"cog",
            "isComposite":false,
            "description":"Runs Behavior: \"{{SubTreeName}}\" ... Please Note, {{description}}",
            "properties": [
                {
                    "name": "SubTreeName",
                    "default":"[not set]",                 
                    "value": "subTree"           
                },{
                    "name": "description",
                    "default":"[not set]",
                    "value":"description"
                }
            ]
        }
    ],
    "decorators": [
        {
            "name": "Failure",
            "icon": "thumbs-o-down"
        },
        {
            "name": "Invert",
            "icon": "exchange"
        },
        {
            "name": "Success",
            "icon": "thumbs-o-up"
        },
        {
            "name": "RepeatUntilFailure",
            "icon": "arrow-up",
            "description":"Execute child until Failure"
        }

    ],
    "services": [
        {
            "name": "Sample service",
            "icon": "cog",
            "description": "sample service",
            "properties": [
                {
                    "name": "BlackboardKey",
                    "default": "Target",
                    "type": "string"
                },
                {
                    "name": "BlackboardKey2",
                    "default": "1",
                    "type": "string"
                }
            ]
        },
        {
            "name": "ScriptFunction",
            "icon": "cog",
            "description": "Execute a scripted function \"{{FunctionName}}\" with arg1=BBKey \"{{BlackboardKey}}\" and arg2=BBKey \"{{BlackboardKey2}}\" and arg3=number  \"{{ConstantNumber}}\"",
            "properties": [
                {
                    "name": "FunctionName",
                    "default": "TakeDamage",
                    "type": "string"
                },
                {
                    "name": "BlackboardKey",
                    "default": "Target",
                    "type": "string"
                },
                {
                    "name": "BlackboardKey2",
                    "default": "SomeArg2",
                    "type": "string"
                },
                {
                    "name": "ConstantNumber",
                    "default": "1",
                    "type": "number"                
                }
            ]
        }
    ]
}