Behavior Trees

What is a tree?

A behavior tree allows for a complex set of requirements and tasks to be defined in such a way that a decision can be made based on an infinite number of states. Behavior Trees are used in AI, robotics, mechanical control systems, etc. We use them with SyncAgent's for fine grain execution control.

An example, please?

Let's break that down to something we can all follow, like programming the AI of a video game.

The AI needs to do two things:

• Check for enemies in the area, If there are enemies in the area, then:

  • Check if they want to attack, or can attack

  • Only if the above statement is true, move into combat range

• Check for non combat activities after checking that there is no immediate danger in the area

  • Am I hungry?

  • Am I thirsty?

The two state checks (enemy check, non combat check) are known as a list of fallbacks. The reason for this is that every subsequent child node in a Fallback is executed in order until one succeeds.

As almost an opposite to Fallback nodes - Sequence nodes only execute their children in order if the previous one succeeds.

Use Fallback nodes for an ordered list of items to execute, where a failure moves onto the next node Use Sequence if the children need to succeed to proceed to the next node

The demo below uses simple bool variables to control state, but in a real scenario, these would be callback to check within a radius of the AI, or pull it's current hunger/thirst levels.

bool Enemies = true;
bool Attackable = true;

bool Hungry = false;
bool Thirsty = true;

var btt = new BehaviorTree("AI").AddFallback("Activities",
    new Fallback("Check for enemies",
        new Sequence("Any enemies around?",
            new Leaf("Enemy Checker", (l) => { Console.WriteLine("Enemy Checker"); return Enemies ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Enemy Attackable?", (l) => { Console.WriteLine("Enemy Attackable?"); return Attackable ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Move in for combat", (l) => { Console.WriteLine("Move in for combat"); return NodeStatus.SUCCESS; }))),

     new Fallback("Non Combat Activities",
        new Sequence("Am I hungry?",
            new Leaf("Hungry test", (l) => { Console.WriteLine("Hungry test"); return Hungry ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Hungry - eat food", (l) => { Console.WriteLine("Hungry - eat food"); return NodeStatus.SUCCESS; })),
        new Sequence("Am I Thirsty?",
            new Leaf("Thirsty test", (l) => { Console.WriteLine("Thirsty test"); return Thirsty ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Thirsty - drink", (l) => { Console.WriteLine("Thirsty - drink"); return NodeStatus.SUCCESS; }))
    )
);

With that code in place, let's print and run our tree:

Console.WriteLine(btt.Print());
var status = BTTickEngine.RunOnce(btt);
Console.WriteLine($"Status: {Enum.GetName(status)}");

Results:

If you run the code as shown above, you'll notice the last node to be executed is: Move in for combat.

The reason for this is because "Check for Enemies" takes priority over "Non Combat Activities".

Change the results

Let's set bool Enemies = false; and run again. The last node to run this time is:

Thirsty - drink.

That's because our fallback node didn't have any enemies to check for, and our Thirsty bool is true.

This is what makes behavior trees so powerful. Simple state management changes the outcome of what it decides to do. Perigee has a built in SDK to make working with Behavior Trees quite easy.

SDK

The Print() Command

The print produces a nice breakdown of the tree itself. Showing nodes and their children

AI (BehaviorTree)
    Activities (Fallback)
        Check for enemies (Fallback)
            Any enemies around? (Sequence)
                Enemy Checker (Leaf)
                Enemy Attackable? (Leaf)
                Move in for combat (Leaf)
        Non Combat Activities (Fallback)
            Am I hungry? (Sequence)
                Hungry test (Leaf)
                Hungry - eat food (Leaf)
            Am I Thirsty? (Sequence)
                Thirsty test (Leaf)
                Thirsty - drink (Leaf)

The BTTickEngine

The tick engine runs a tree until success or failure. The run code is effectively processing the tree until it's no longer running:

//Use the built in TickEngine
var status = BTTickEngine.RunOnce(btt);

//Or run it manually
NodeStatus st = NodeStatus.RUNNING;
while (st == NodeStatus.RUNNING)
{
    st = btt.Process();
    Task.Delay(10).Wait();
}

Nodes and Types

The three main types are Fallback, Sequence, and Leaf. Leaf nodes are "special" nodes as they are the only nodes that contain a callback for code to be executed to determine the node state.

Node States

The three states are:

• Success - It's completed.

• Processing - It's still working on it, try again...

• Failure - It failed, stop.

Fallback

(Sometimes called a "Selector Node")

Fallback nodes process children nodes in order until a child node is a success, then fall out of the loop.

Sequence

Processes all children in order, if a child fails, it will return a failure and start back at the first child on next rerun (tick)

Leaf

Execute code to determine what status a node is in.

Node Operations

There are several special operations that can be performed on nodes.

Shuffle

You can shuffle a set of nodes by using this extension. The example below randomly shuffles whether the hunger check or the thirst check happens first

new Fallback("Non Combat Activities",
        new Sequence("Am I hungry?",
            new Leaf("Hungry test", (l) => { Console.WriteLine("Hungry test"); return Hungry ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Hungry - eat food", (l) => { Console.WriteLine("Hungry - eat food"); return NodeStatus.SUCCESS; })),
        new Sequence("Am I Thirsty?",
            new Leaf("Thirsty test", (l) => { Console.WriteLine("Thirsty test"); return Thirsty ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Thirsty - drink", (l) => { Console.WriteLine("Thirsty - drink"); return NodeStatus.SUCCESS; }))
    ).Shuffle()

Sort

Every node has a default SortOrder property. You can assign nodes a sort order or re-prioritize them at runtime/tree creation.

Sort orders these in ascending order. In this example, we sort Thirsty above Hungry.

new Fallback("Non Combat Activities",
        new Sequence("Am I hungry?", 2,
            new Leaf("Hungry test", (l) => { Console.WriteLine("Hungry test"); return Hungry ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Hungry - eat food", (l) => { Console.WriteLine("Hungry - eat food"); return NodeStatus.SUCCESS; })),
        new Sequence("Am I Thirsty?", 1,
            new Leaf("Thirsty test", (l) => { Console.WriteLine("Thirsty test"); return Thirsty ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Thirsty - drink", (l) => { Console.WriteLine("Thirsty - drink"); return NodeStatus.SUCCESS; }))
    ).Sort()

Invert

Invert reverses statuses. Success become failure, and failure become success.

Even though the bool Hungry = false; - the inversion node inverts the node status to be SUCCESS.

new Fallback("Non Combat Activities",
        new Sequence("Am I hungry?",
            new Leaf("Hungry test", (l) => { Console.WriteLine("Hungry test"); return Hungry ? NodeStatus.SUCCESS : NodeStatus.FAILURE; })
                .Invert(),
           
             new Leaf("Hungry - eat food", (l) => { Console.WriteLine("Hungry - eat food"); return NodeStatus.SUCCESS; })),
        new Sequence("Am I Thirsty?",
            new Leaf("Thirsty test", (l) => { Console.WriteLine("Thirsty test"); return Thirsty ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Thirsty - drink", (l) => { Console.WriteLine("Thirsty - drink"); return NodeStatus.SUCCESS; }))
    )

Retry

Retry does as it sounds, it retries the node X number of times if the node returns a FAILURE status:

You'll see "Hungry test" print 3 times (original + 2 retries).

new Fallback("Non Combat Activities",
        new Sequence("Am I hungry?",
            new Leaf("Hungry test", (l) => { Console.WriteLine("Hungry test"); return Hungry ? NodeStatus.SUCCESS : NodeStatus.FAILURE; })
                .Retry(2),
            new Leaf("Hungry - eat food", (l) => { Console.WriteLine("Hungry - eat food"); return NodeStatus.SUCCESS; })),
        new Sequence("Am I Thirsty?",
            new Leaf("Thirsty test", (l) => { Console.WriteLine("Thirsty test"); return Thirsty ? NodeStatus.SUCCESS : NodeStatus.FAILURE; }),
            new Leaf("Thirsty - drink", (l) => { Console.WriteLine("Thirsty - drink"); return NodeStatus.SUCCESS; }))
    )

Forces

There is both a ForceFailure and a ForceSuccess node. These are helpful when building certain trees that require a forceful response.

Prebuilt Leaf nodes and the fluent SDK

Fluent SDK

There are two handy built in methods for quickly creating the two kinds of trees:

BehaviorTree.NewSequence("Conditionals", 
    LeafNodes.NetworkAvailable, 
    LeafNodes.PingSuccess);

BehaviorTree.NewFallback("Conditionals", LeafNodes.NetworkAvailable);

LeafNodes

There are multiple pre-built leaf nodes available to use. They return a Leaf Node that is already pre-coded to return the correct Node Status.

Network

To check if the network is available

LeafNodes.NetworkAvailable;

PingSuccess

To check if a ping to 8.8.8.8 is available

LeafNodes.PingSuccess;

PingAddress

To check if the address responds positively to a ping

LeafNodes.PingAddress(new byte[] { 8,8,8,8});

SQLAvailable

To check if SQL Server can open a connection

LeafNodes.SQLAvailable("connectionString");

Agent Exists

To check if an Agent exists

LeafNodes.AgentExists("AgentName", treeHandler.AgentData);

Agent Data Expired

To check if an Agent has expired data. Returns SUCCESS if the data is NOT expired.

LeafNodes.AgentDataExpired("AgentName", treeHandler.AgentData);