Chapter 6. Decision Making

In this chapter, we will cover the following topics:

• Creating reusable actions for agent behaviors

• Building conditional evaluators for decision making

• Creating a decisions tree structure that builds autonomous agents

• Creating a finite state machine that handles state-based agents

• Creating behavior trees for reactive agents

Now that we have agents that can animate and maneuver through their environments, we'll add high-level decision making to our agents. These data structures will finally give our agents autonomy in how they interact with the world as well as other agents.

Creating userdata

So far we've been using global data to store information about our agents. As we're going to create decision structures that require information about our agents, we'll create a local userdata table variable that contains our specific agent data as well as the agent controller in order to manage animation handling:

local userData =
{
    alive, -- terminal flag
    agent, -- Sandbox agent
    ammo, -- current ammo
    controller, -- Agent animation controller
    enemy, -- current enemy, can be nil
    health, -- current health
    maxHealth -- max Health
};

Moving forward, we will encapsulate more and more data as a means of isolating our systems from global variables. A userData table is perfect for storing any arbitrary piece of agent data that the agent doesn't already possess and provides a common storage area for data structures to manipulate agent data. So far, the listed data members are some common pieces of information we'll be storing; when we start creating individual...

Agent actions

Ultimately, any decision logic or structure we create for our agents comes down to deciding what action our agent should perform. Actions themselves are isolated structures that will be constructed from three distinct states:

• Uninitialized

• Running

• Terminated

The typical lifespan of an action begins in uninitialized state and will then become initialized through a onetime initialization, and then, it is considered to be running. After an action completes the running phase, it moves to a terminated state where cleanup is performed. Once the cleanup of an action has been completed, actions are once again set to uninitialized until they wait to be reactivated.

We'll start defining an action by declaring the three different states in which actions can be as well as a type specifier, so our data structures will know that a specific Lua table should be treated as an action.

Note

Remember, even though we use Lua in an object-oriented manner, Lua itself merely creates each instance of an object...

Creating actions

With a basic action class out of the way, we can start implementing specific action logic that our agents can use. Each action will consist of three callback functions—initialization, update, and cleanup—that we'll use when we instantiate our action instances.

The idle action

The first action we'll create is the basic and default choice from our agents that are going forward. The idle action wraps the IDLE animation request to our soldier's animation controller. As the animation controller will continue looping our IDLE command until a new command is queued, we'll time our idle action to run for 2 seconds, and then terminate it to allow another action to run:

SoldierActions.lua:

function SoldierActions_IdleCleanUp(userData)
    -- No cleanup is required for idling.
end

function SoldierActions_IdleInitialize(userData)
    userData.controller:QueueCommand(
        userData.agent,
        SoldierController.Commands.IDLE);
        
    -- Since idle is a looping animation, cut...

Evaluators

Evaluators are the principal method of handling conditional checks in our decision structures. While actions perform the eventual behaviors that our agents exhibit, it's the responsibly of evaluators to determine which action is allowed to run at what time.

Creating an evaluator object simply wraps a function call that returns true or false when the userData table is passed into the function:

Evaluator.lua:

function Evaluator.Evaluate(self)
    return self.function_(self.userData_);
end

function Evaluator.new(name, evalFunction, userData)
    local evaluator = {};
    
    -- data members
    evaluator.function_ = evalFunction;
    evaluator.name_ = name or "";
    evaluator.type_ = Evaluator.Type;
    evaluator.userData_ = userData;
    
    -- object functions
    evaluator.evaluate_ = Evaluate;
    
    return evaluator;
end

Creating evaluators

Creating evaluators relies on simple functions that perform isolated operations on the agent's userData table. Typically, most evaluators will only perform calculations based on userData instead of modifying the data itself, although there is no limitation on doing this. As the same evaluator might appear within a decision structure, care must be taken to create consistent decision choices.

Tip

Evaluators that modify userData can easily become a source of bugs; try to avoid this if at all possible. Actions should modify the agent's state, when evaluators begin to modify the agent's state as a decision structure is processed; it becomes very difficult to tell how and why any eventual action was chosen, as the order of operations will affect the outcome.

Constant evaluators

First, we'll need to create the two most basic evaluators; one that always returns true, and another that always returns false. These evaluators come in handy as a means of enabling or disabling actions...

Decision structures

With actions and evaluators at our disposal, we'll begin to create different types of logic structures that use both of these primitive operators to build our agent's behaviors. While each decision structure uses different approaches and techniques, we'll create similar behaving agents based on the actions and evaluators we have.

Decision trees

Decision trees will be the first structure we'll implement and are, by far, the easiest way to understand how a decision was made. A decision tree is composed of branches and leaves. Each branch in the tree will wrap an evaluator, while each leaf will be composed of an action. Through a sequence of branch conditions, our decision tree will always result in a final action that our agent will perform.

To create a decision tree structure, we'll implement an update loop for our tree, which evaluates the root branch within the tree and then proceeds to process the resulting action. Once the action has been initialized, updated, and eventually, terminated, the decision tree will re-evaluate the tree from the root branch to determine the next action to be executed:

DecisionTree.lua:

require "Action"

DecisionTree = {};

function DecisionTree.SetBranch(self, branch)
    self.branch_ = branch;
end

function DecisionTree.Update(self, deltaTimeInMillis)
    -- Skip execution if the tree...

Building a decision tree

Building a decision tree starts with instantiating an instance of a decision tree, creating each branch within our tree, connecting the conditional branches, and adding actions:

SoldierLogic.lua:

function SoldierLogic_DecisionTree(userData)
    local tree = DecisionTree.new();
    return tree;
end

Creating branches

The tree we'll be creating combines each of the actions and evaluators we implemented previously and gives our agents the ability to pursue, flee, move, shoot, idle, reload, and die.

Critical health decision branch

First we'll create each branch instance that our decision tree will contain before adding any evaluators or actions.

SoldierLogic.lua:

function SoldierLogic_DecisionTree(userData)
    local tree = DecisionTree.new();

    local isAliveBranch = DecisionBranch.new();
    local criticalBranch = DecisionBranch.new();
    local moveFleeBranch = DecisionBranch.new();
    local enemyBranch = DecisionBranch.new();
    local ammoBranch = DecisionBranch.new...

Creating a decision tree agent

To create an agent whose logic is controlled by our decision tree, we'll modify our indirect soldier agent, as the initial setup of an animation state machine and soldier controller is already done for us.

We'll first create the userData table and associate the initial values so that our decision tree can interact with the agent. Once we've populated the userData table, we can instantiate our decision tree. We'll change the agent's update loop to process the decision tree as well as the soldier controller. As our decision tree expects that the execution will end when an agent dies, we'll add a conditional check that halts updates when this occurs:

IndirectSoldierAgent.lua:

local soldier;
local soldierController;
local soldierDecisionTree;
local soldierUserData;

function Agent_Initialize(agent)
    Soldier_InitializeAgent(agent);
    soldier = Soldier_CreateSoldier(agent);
    weapon = Soldier_CreateWeapon(agent);

    soldierController = SoldierController.new...

Finite state machines

Creating a finite state machine (FSM) for modeling logic will resemble the animation state machines we've created previously, except that transitioning to a new state within the state machine is handled automatically through the evaluation of transitions. Once one evaluator returns true, the state machine will transition to the new state and invoke the associated state's action.

States

States within an FSM are responsible for associating an action with the state. We create a state by passing an action and naming the state for debug convenience:

FiniteState.lua:

require "Action";
require "FiniteState";
require "FiniteStateTransition";

FiniteState = {};

function FiniteState.new(name, action)
    local state = {};
    
    -- The FiniteState's data members.
    state.name_ = name;
    state.action_ = action;
    
    return state;
end

Transitions

Transitions encapsulate the state to be transitioned to as well as the evaluator that determines whether the transition should...

Building a finite state machine

To build a finite state machine for our agent, we'll create the initial states that wrap each possible action. As the state machine needs a starting point, we'll set the state explicitly to the idle state to begin with. Once the idle state has finished, our state machine will automatically pick the most relevant action to execute afterward:

SoldierLogic.lua:

function SoldierLogic_FiniteStateMachine(userData)
    local fsm = FiniteStateMachine.new(userData);
    fsm:AddState("die", DieAction(userData));
    fsm:AddState("flee", FleeAction(userData));
    fsm:AddState("idle", IdleAction(userData));
    fsm:AddState("move", MoveAction(userData));
    fsm:AddState("pursue", PursueAction(userData));
    fsm:AddState("randomMove", RandomMoveAction(userData));
    fsm:AddState("reload", ReloadAction(userData));
    
    fsm:SetState("idle");
    return fsm;
end

The idle state

Creating the idle state consists of adding every possible transition from the idle, which also...

Creating a finite state machine agent

Now that we've created a finite state machine, we can simply replace the decision tree that powers our indirect soldier agent with a finite state machine. The initialization, updating, and termination of our FSM are identical to the decision tree.

With an abstract data structure, we can now create both decision-tree-based agents and finite state machine agents simultaneously:

IndirectSoldierAgent.lua:

local soldier;
local soldierController;
local soldierFSM;
local soldierUserData;

function Agent_Initialize(agent)

    ...
    
    soldierFSM = SoldierLogic_FiniteStateMachine(
        soldierUserData);
end

function Agent_Update(agent, deltaTimeInMillis)
    if (soldierUserData.alive) then
        soldierFSM:Update(deltaTimeInMillis);
    end

    soldierController:Update(agent, deltaTimeInMillis);
end

Strengths of finite state machines

The straightforwardness of a state machine relies heavily on large amounts of data. One of the key strengths with such a structure lies in the fact that the statefulness of an agent is inherent within the logical structure.

Compared to a decision tree, finite states isolate the amount of possible actions that can follow from another action. To create the same sort of flow in a decision tree would be inherently difficult and would require embedding some sort of userdata that maintains the statefulness we get for free with a finite state machine.

Pitfalls of finite state machines

The downside of state machines, though, are the exponential possible connections that come with the addition of each new state. To reduce latency or unexpected chains of actions, state machines need to be well connected so that agents can quickly select the best action.

Our implementation of state transitions is a simple, priority-based approach that might not fit all circumstances, in which case, a weighted or search-based approach might become necessary. This additional complexity can further complicate logic selection, where actions are chosen for reasons that aren't apparent.

Behavior trees

With decision trees focusing on the if…else style of action selection and state machines focusing on the statefulness of actions, behavior trees fill a nice middle ground with reaction-based decision making.

The behavior tree node

Behavior trees are composed solely of different types of nodes. Based on the node type, the behavior tree will interpret child nodes as actions and evaluators. As we'll need to distinguish each node instance type from one another, we can create an enumeration of all supported node types: actions, conditions, selectors, and sequences.

Creating an instance of a behavior tree node merely sets the node type and the name of the node:

BehaviorTreeNode.lua:

BehaviorTreeNode = {};

BehaviorTreeNode.Type = {
    ACTION = "ACTION",
    CONDITION = "CONDITION",
    SELECTOR = "SELECTOR",
    SEQUENCE = "SEQUENCE"
};

function BehaviorTreeNode.new(name, type)
    local node = {};
    
    -- The BehaviorTreeNode's data members.
    node.action_ = nil;
    node.children_...

Actions

The first node type is a basic action. We can create a wrapper function that will instantiate an action node and set the internal action accordingly. Actions are only designed to execute behaviors on an agent and shouldn't be assigned any children. They should be considered leaves in a behavior tree:

SoldierLogic.lua:

local function CreateAction(name, action)
    local node = BehaviorTreeNode.new(
        name, BehaviorTreeNode.Type.ACTION);
    node:SetAction(action);
    return node;
end

Conditions

Conditions are similar to actions and are also leaves in a behavior tree. Condition nodes will execute the evaluator assigned to them and return the result to the caller to determine how they should be processed.

SoldierLogic.lua:

local function CreateCondition(name, evaluator)
    local condition = BehaviorTreeNode.new(
        name, BehaviorTreeNode.Type.CONDITION);
    condition:SetEvaluator(evaluator);
    return condition;
end

Selectors

Selectors are the first type of nodes that can have children within the behavior tree. A selector can have any number of children, but will only execute the first child that is available for execution. Essentially, selectors act as if, if…else, and else structures within behavior trees. A selector will return true if at least one child node is able to run; otherwise, the selector returns false:

SoldierLogic.lua:

local function CreateSelector()
    return BehaviorTreeNode.new(
        "selector", BehaviorTreeNode.Type.SELECTOR);
end

Sequences

Lastly, we have sequences, which act as sequential blocks of execution that will execute each of their children in an order until a condition, selector, or child sequence fails to execute. Sequences will return true if all their children run successfully; if any one of their children returns false, the sequence immediately exits and returns false in turn:

SoldierLogic.lua:

local function CreateSequence()
    return BehaviorTreeNode.new(
        "sequence", BehaviorTreeNode.Type.SEQUENCE);
end

Creating a behavior tree object

Creating a behavior tree object is simple, as it primarily consists of a root node, evaluation function, and update function:

BehaviorTree.lua:

require "BehaviorTreeNode"

BehaviorTree = {};

local _EvaluateSelector;
local _EvaluateSequence;

function BehaviorTree.SetNode(self, node)
    tree.node_ = node;
end

function BehaviorTree.new()
    local tree = {};
    
    -- The BehaviorTree's data members.
    tree.currentNode_ = nil;
    tree.node_ = nil;
    
    return tree;
end

Behavior tree helper functions

Four primary evaluators are used to process the behavior tree structure: selector evaluation, sequence evaluation, actual node evaluation, and finally, a continue evaluation function that continues where a sequence's child finishes:

BehaviorTree.lua:

local EvaluateSelector;
local EvaluateSequence;

Selector evaluation

As selectors only return false if all child nodes have executed without returning true, we can iterate over all children and return the first...

Building a behavior tree

Building a behavior tree is very similar to building a decision tree, except for the addition of selectors and sequence node types.

The soldier's behavior tree

We can start creating a behavior tree using a similarly wrapped function that instantiates a behavior tree and creates the first selector node for the tree:

SoldierLogic.lua:

function SoldierLogic_BehaviorTree(userData)
    local tree = BehaviorTree.new(userData);
    
    local node;
    local child;
    
    node = CreateSelector();
    tree:SetNode(node);
    
    return tree;
end

The death behavior

To add the first action, which is death, we add the required sequence, condition, and action nodes. As the behavior tree will completely re-evaluate once an action completes, we don't have to worry about other actions knowing about death. As prioritizing actions is based on how early in the tree they appear, we add death first, because it has the highest priority:

SoldierLogic.lua:

function SoldierLogic_BehaviorTree...

Creating a behavior tree agent

To use our behavior tree, we can replace the finite state machine and perform the same update loop on our behavior tree instead. Regardless, if our agent is using a decision tree, state machine, or behavior tree, its actions will be nearly identical, as the logic is merely translated from one decision structure to another:

IndirectSoldierAgent.lua:

local soldier;
local soldierController;
local soldierBT;
local soldierUserData;

function Agent_Initialize(agent)

    ...
    
    soldierBT = SoldierLogic_BehaviorTree(
        soldierUserData);
end

function Agent_Update(agent, deltaTimeInMillis)
    if (soldierUserData.alive) then
        soldierBT:Update(deltaTimeInMillis);
    end

    soldierController:Update(agent, deltaTimeInMillis);
end

Strengths of behavior trees

Compared to decision trees, behavior tree actions know very little about actions other than the priority they show up in the tree. This allows for actions to be modular in nature and can reduce the need to rebalance a complex tree when more actions are added.

Pitfalls of behavior trees

With reactive actions, behavior trees have shortcomings; they represent stateful logic very poorly. If statefulness needs to be preserved within a behavior tree, typically high-level conditions will dictate which branch is currently active. For instance, the noncombat and combat state of our agent isolates a lot of the behaviors that are available at any point in time.

Summary

With some rudimentary actions and decision-making logic controlling our agents, we can now begin to enhance how our agents see the world, as well as how they store information about the world.

In the next chapter, we'll create a data structure that can store knowledge as well as create senses for our agents to actually see and hear.