A Gigantic AI Need

Gigantic is a 5-on-5 competitive multiplayer game in which each team is paired with a giant creature called a Guardian. The objective of the game is to destroy the enemy team's Guardian. This is done by building power for your team's Guardian by killing the enemy team's players and capturing strategic parts of the map by spawning creatures to guard those areas. This fast-paced competitive game involves both player-vs-player and player-vs-AI elements as key parts of the game. As such, AI is a major component of giving Gigantic its unique flavor.

There are a number of ways to implement AI systems for a game such as Gigantic. In the past, I've worked on data-driven solutions using state machines to custom-coded solutions backed by neural networks. For Gigantic, the primary mechanism through which AI is implemented is behavior trees.

State Machine Madness

While there are a number of ways to model game AI, it's often best to use a custom language to specify how an AI works, rather than using whatever language the game engine is written in. Using a simplified domain-specific programming language is important because the design of the AI is part of the overall design of the game. Since designers' work improves with iterations, allowing them to define AI behavior greatly improves productivity and quality because their ideas can be implemented immediately instead of waiting for an engineer to translate their idea into the game.

Finite State Machines (FSM) are a common and classic way to implement game AI. We can think of an AI character as being in various states of execution, and an FSM allows you to define these states, such as "guarding", "attacking", and "defending". We also need to specify the transitions between states, which are the rules for when we go from one state to another (for example, we can go from "guarding" to "attacking" but not from "guarding" to "defending").

Example Finite State Machine

This is pretty simple, and we can manage the growing complexity of transitions through hierarchical finite state machines. Unfortunately, game design often wants to reuse states in different contexts, and there's no way to do such a thing without at some level duplicating the state logic and transitions that are common between reused states.

For example, if I had an AI character that could parry with a sword when both attacking or defending, but after parrying would go back to either attacking or defending depending on what they were doing previously, we would have to create two parry states to encapsulate that difference in transition behavior.

Finite State Machine With Parry States

Even with great tools to help make things easier, managing states and transitions can become very quickly unwieldy, making complex logic difficult to maintain, let alone verify. Game design thrives on being able to reuse logic easily, improving modularity without increasing complexity.

Behavior Trees To the Rescue

Behavior trees superficially look like state machines, and indeed can capture all the complexity of states and transitions. However, instead of exposing AI logic at the state level (which answers "what am I doing and what can I do next?"), behavior trees make things more clear by describing the flow of logic. In other words, behavior trees try to structure more clearly "how should I figure out what to do?"

In Gigantic, behavior trees are created through a graph-based visual programming language. A behavior tree is composed of a hierarchy of nodes, with parent nodes linking to child nodes. Parent nodes typically make flow control decisions, deciding if and what order their child nodes should be run. Nodes with no further children are called leaf nodes, and typically contain the conditions to check in the game or actions to perform.

A Simple Behavior Tree For Eating Food

The logic of behavior trees is driven by the status of executing the logic of nodes. When a node is done executing, it passes the status of its execution back to its parent node.

Result	Description	Color/Arrow in Diagrams
SUCCESS	The result of running the node was a success
FAILURE	The result of running the node was a failure
RUNNING	This node is currently executing
READY	This node is ready to be executed

Types of Nodes

There are lots of different kinds of nodes, but common ones include condition nodes, which are leaf nodes that simply test some condition in the game such as "do I have more than 50% of my health?" Another type of leaf node is the action node, which tell the AI to do perform an in-game action, such as firing a weapon, and will return SUCCESS if the action completes successfully, FAILURE if it doesn't, and RUNNING while it is still executing and needs more time.

A common parent node is the sequence node which has multiple child nodes and will execute them in order. If any of these child nodes returns the status FAILURE, the sequence node will be set to FAILURE. Otherwise, if all the child nodes return SUCCESS, the sequence node will be set to the status SUCCESS. This is basically a short-circuit logical AND node.

To see how a node like this might actually execute its logic, let's start with a simple example of a sequence node that describes when an AI should attack an enemy. We shall assume that there is an enemy nearby, but that the AI is unarmed.

Logic for Attacking An Enemy

First, the sequence node will be in the RUNNING state, and will execute its first child node by putting it into a RUNNING state as well:

Sequence Node Testing the First Condition Node

This will ask the game engine if there is an enemy near this AI. Since there is indeed an enemy nearby, this condition node will return SUCCESS to its parent sequence node.

First Condition Node Evaluates as "Success"

The sequence node will then try to execute its second child node:

Sequence Node Testing the Second Condition Node

This condition node will check to see if the AI has a weapon. Since the AI is unarmed, this node will return a FAILURE status to its parent node.

Second Condition Node Evaluates as "Failure"

Because a sequence node will have its status set to FAILURE as soon as a child node returns a status of FAILURE, this sequence node will not execute its last child node that performs the action to attack the enemy.

Sequence Node Evaluates as "Failure"

A priority selector node will work much like a sequence node. It will execute its child nodes in order, and if any of them returns the status SUCCESS, the priority selector will be set to SUCCESS. Otherwise, if all the child nodes return FAILURE, the priority selector will be set the status FAILURE. In other words, this is a short-circuit logical OR node.

Here is an example of the final state of a priority selector node that determines if the AI should sleep:

Selector Node Evaluating "Should I Sleep" Logic

The priority selector first checked the condition "Am I tired?" which returned FAILURE. It then checked the condition "Am I lazy?" which also returned FAILURE. Lastly it checked the condition "Is it nap time?" which returned SUCCESS, so the priority selector returned SUCCESS.

A combination of sequences and priority selectors in addition to a few other logical nodes is all we need to let a behavior tree decide what an AI should do and how it should do it.

By composing logic through modular nodes, behavior trees implicitly capture a modular programming paradigm, which allows for creating complex behaviors without incurring the penalty of transition management inherent in complex FSMs.

For further examples of how behavior trees work, Chris Simpson provides some great examples based on Java Behavior Trees.

Implementation Challenges

Making a complex system for a game like this necessarily requires some careful technical considerations. Naturally, an exploration of these considerations benefits from a background in computer engineering.

Executing the Logic of a Node

Games typically operate on the concept of "ticks", which take care of the logic that happens between rendering frames of the game. Because some actions will take time to accomplish (such as moving from one point to another), behavior tree nodes also each implement a "tick" function.

How we implement the tick functions for nodes has a big impact on how easy it is to debug the logic implemented with behavior trees. A naive approach would be to have each parent node's tick function directly call its child node's tick function. However, now the execution stack-depth is driven by the depth of the tree, which is something designers shouldn't have to worry about.

Alternatively, a tree could be implemented using a polling model, where for each frame of the game, each node of the behavior tree is ticked in depth-first order. While this model makes it incredibly easy to step-debug logic, it's also very inefficient, since parent nodes are being ticked even when they have nothing to do but wait for a child node to finish executing.

When polling is a poor choice, we often turn to an event-driven model. In this model, a parent node tells its child node to execute, then waits for the child node to fire an event when it's done. Because only actively executing nodes are running, we guarantee the highest execution efficiency. However, this model makes following the underlying behavior tree engine code difficult because execution doesn't happen procedurally through code, but rather jumps around functions as events are fired.

Gigantic's implementation employs a hybrid solution. First, we maintain a custom execution stack on the heap to store which nodes should be run. When a parent node wants to execute its child node, it pushes its child node on this execution stack, and sets the child node's state to "running". The execution engine will run the tick function for the top node on the stack until that child node's status is either "success" or "failure." Then the node is popped from the stack, and the next top-most node (the parent node) is notified of the child's status.

For example, this simple tree that determines if we should sleep:

Selector Node Evaluating "Should I Sleep" Logic

Would have the following execution stack:

Stack Structure for Active Nodes in "Should I Sleep" Logic

The actively running node is the conditional that is determining if we're lazy, while its parent nodes are on the stack waiting for a response before they can continue execution.

Sometimes parent nodes need to run to monitor some other game process or prematurely end execution of their child nodes. These nodes are marked as "always tick" and will be executed before their children on the stack. This model gives us the best of all worlds, with a highly efficient execution process that's easy to step-through and debug.

Concurrent Execution of Tasks

Another difficult technical concept to encapsulate in behavior trees is capturing concurrent logic. For example, a designer may want to implement a behavior where an AI is running towards a location on the map while simultaneously firing a gun at the enemy. Because it's common for an AI to execute multiple tasks at the same time, a natural approach to solving this problem would be to introduce parallelism and break tasks into threads. Of course, multithreading can be a challenging concept for even senior engineers to wrangle, let alone designers with little engineering experience. Avoiding race conditions can become a severe impediment to changing the logic in the tree.

For Gigantic, we didn't want to burden designers with such complex and esoteric technical details. While threads typically imply a preemptive model of parallel execution, we're really only interested in the concurrency of tasks (in that they execute in order and in the same frame). Thus, we opted to use a cooperative multitasking model. This is implemented using a "parallel" node, which can have several child nodes that branch off of it (the name "parallel node" is somewhat misleading to engineers, but easier to identify with for non-engineers).

Behavior Tree with a Parallel Node

In addition to the execution stack the parallel node was originally on, a parallel node adds an execution stack per child branch. When the execution engine ticks nodes, we simply tick the nodes on the top of each stack in order.

Execution Stack for Behavior Tree with Parallel Node

This model is similar to languages that use coroutines, and gives the structural illusion of multiple threads while executing strictly serially by waiting for each child branch to yield upon completing a single tick of execution. As a parallel node iterates over its children, it changes the currently active stack to use. This way, child nodes don't have to know whether they are parented to a parallel node. For example, a sequence node parented to a parallel node can simply push its child to the currently active stack. All the active nodes are ticked between frames of the game, allowing for an easy way to execute concurrent logic.

Scratching the Surface

This is only the tip of the iceberg when it comes to behavior tree architecture details. For example, other technical challenges we addressed include subroutine support for improved modularity of code, and scalability of the behavior tree engine through a carefully crafted lockless design. In addition, behavior trees can be extended in many surprisingly powerful ways, integrating other AI constructs such as Goal-Oriented Action Planning (GOAP), cloud-based machine-learning algorithms, or user-interactive RTS-style AI command systems. Behavior trees cleanly integrate decision-making logic with their subsequent actions, empowering designers to present unique challenges and opportunities to the player, allowing the AI to become an integral part of the Gigantic experience.