Advanced AI for Games

Behaviour Trees and how they compare to other methods

There is a myriad of choices when it comes to designing artificial intelligence systems for use in games, certainly more than is discussed in this report. Nevertheless, this report aims to shed light on a few of them. Examining the differences between three in particular: The Hierarchal Task Network (HTN), Goal Oriented Action Planning (GOAP), and most importantly the Behaviour Tree (BT).  The latter, Behaviour Trees, being the primary focus of this report.

Behaviour trees are abstractions that can aid developers in creating complex frameworks for entities within games to use to simulating real behaviour patterns.  These abstractions consist of defined sets of modes  that are mapped to specific behaviours or operations within the AI system to achieve this.  This allows for the modelling of actions such as “open door”, “get weapon” and “reload gun”.

Control nodes control the flow of the behaviour tree, these can be sequence, fallback, parallel or decorator. Execution nodes however are responsible for defining actions for the entity to perform as well as analysing the world state of the scene that the entity is in to feed back to the tree.

The defined sets of control and execution nodes, which are represented as classes, are carried out in updates that are called “ticks”, which usually do so at a specific rate predetermined by the developer or developers of the system. When a behaviour tree ticks, all their child nodes do so as well repeatedly, based on the construction and structure of the behaviour tree in question. After this, one of three statuses are returned up the tree to the parent node, also represented as a class. The three statuses that can be returned to the parent class are “Success”, “Failure”, or “Running”.

In summary, the system travels from the root node, down, at its set tick rate, which is usually every frame, but can be different in certain situations when required f or more idiosyncratic systems that require a more unique approach to the AI system. Each node of the tree is tested to find which one is active, checking again all nodes along its path, reaching the currently active node for it to be ticked again.

The design of BT’s is that of a tree like data structure. This structure contains two main node types. The first of these being the control flow node, the internal nodes. The second being the execution nodes, the leaf nodes of the tree. The design of HTN’s models the task network itself as an objective to be achieved. This network has knowledge of both composite tasks, as well as primitive task. Finally, GOAP networks consist of preconditions and effects. These are used by the structure to create a queue of actions to fulfil a given goal.

As stated previously in this report, the implementation of BT’s involves the system traversing the tree starting from the root node usually each frame, testing nodes to see which is active, finally ticking said active node. The implementation of HTN’s is like that of BT’s. Tasks are performed according to the networks hierarchal structure, complying with required parameters when met, and executing required actions accordingly. Finally, GOAP networks utilise a planner manager which scans the data structure. It then creates a list of actions required to meet a desired goal, fulfilling a first in first out design structure, finally executing these actions in order.

When it comes to application it seems BTs are good tools for developers when a complex behaviour or set of complex behaviours are required to be modelled in relation to a single entity. For example, an enemy swordsman in a duelling game. The application of HTNs it seems is more fit for dealing with a larger group of entities that still need to be modelled with reasonably complex behaviours. For example, a group of NPC workers in a factory for a simulation game. Finally, the use and applications of GOAP structures is well suited to use cases in which there can be multiple ways to achieve the same goal, as well as cases where entities could have multiple complex goals which could potentially all be benefited from a single queue of actions compiled by the planner. For example, a sandbox game NPC that is given many ways to interact with the environment.

Finally, a word on the relative performance on each of these data structures. BTs retain reasonable performance; however, this can be compromised rather easily by designing complex trees that are not optimised properly which is being forced to tick every frame. HTNs retain a somewhat lower performance in the given context described above due to being computed for multiple entities at once. And, finally, GOAP data structures retain good performance also, because of its requirement to only check its surroundings and world data each time it has completed its previous list of actions.

The example behaviour tree shown above is that of the system developed for task 2 of this assignment. This tree begins first t a selector. This selector is specifically selecting from a sequence, and the PatrolTask node. The first of these two options is the sequence. This is connected to two tasks, these being CheckEnemyFOVRange and GoToTargetTask. When the sequence is ticked it runs the code for CheckEnemyFOVRange, specifically filling the “target” data structure if it can be, then the GoToTargetTask code is run in accordance with the sequence parent node above it, and the agent moves to a given location. Finally, the PatrolTask node is invoked while there is no player in sight of the agent, making the agent patrol between the 5 set patrol points.

To conclude; the different AI systems discussed in this report clearly have their own idiosyncrasies that are particularly relevant when one looks the different applications that they are used in, as well as the technical level of perceived intelligence each can give to game entities that a developer may implement it on. There is no one size fits all and careful consideration is to be undertaken when deciding on the approach that one may take when developing an AI system for a video game

Implementation of a simple behaviour tree

Source code:

Tests with console output:

Test	Expected outcome	Actual outcome
Patrol points	The Enemy AI agent patrols between a set of 5 points recursively.	The Enemy AI agent patrols between a set of 5 points recursively.
Chasing player	The Enemy AI agent chases the player when they enter range and view	The Enemy AI agent chases the player when they enter range and view
Returning to patrol	The Enemy AI agent returns to its patrol route when the player gets too far away from it	The Enemy AI agent returns to its patrol route when the player gets too far away from it