June 18, 2024
The following excerpt is from Game AI Uncovered Volume One, as edited by Paul Roberts. The book was published February 23, 2024 by CRC Press, a division of Taylor & Francis, a sister company of Game Developer and Informa Tech. Use our discount code GDTF20 at checkout on Routledge.com to receive a 20% discount on your purchase. Offer is valid through July 4, 2024.
7.1 INTRODUCTION
While working on a yet to be announced title, the AI team hit a snag. Behaviour trees were the decision-making architecture of choice, but they are not reactive. And for a tree to respond to an event, the response, and the conditions leading up to it, must be part of the tree. Reactive Behaviour Trees (RBT) were designed to solve this problem, but before delving too deeply into the problem this architecture aims to solve and why you would choose to implement this approach, we need to take a brief look at traditional behaviour trees.
7.2 BEHAVIOUR TREES
Behaviour trees have been around for a while. They were originally developed by Damian Isla as an improvement on Finite State Machines (FSM) in the development of Halo 2 (Isla, 2005). Since then, they have been used in a wide range of games and had numerous articles and had research papers written about them. Behaviour trees are now the preferred approach for AI behaviours across the industry. Epic’s Unreal Engine even has them built into the engine.
Traditionally, behaviour trees are graphs with a bunch of composite nodes that dictate the type of execution (branch nodes, in normal tree terminology), and behaviour/task nodes (leaf nodes), that execute some kind of logic, or more colloquially ‘do things’. They are almost always associated with a blackboard, which is essentially a common data store for trees to share data amongst one another. A blackboard has a one-to-many relationship with behaviour trees, meaning that a single blackboard can be associated to multiple behaviour trees but each behaviour tree can only ever be associated with the one blackboard. This greatly adds to the flexibility of the system because data can be set in one agent’s behaviour tree and then be used by another agent in a completely different behaviour tree.
On each update, the tree evaluates which task node is the best one to execute and goes through all the nodes in order, usually from top to bottom and left to right, until a particular task node returns true. The most commonly used composite nodes and a brief description of their purpose are as follows:
-
Sequence – These composite nodes execute each of their child nodes from left to right until all of them return success.
-
Selector/Fallback – These composite nodes execute each of their child nodes in any order until at least one of them returns success.
-
Parallel – These composite nodes execute the child nodes at the same time. These composite nodes return success when some number m of n number of child nodes succeed and returns false when all n child nodes fail. The term ‘parallel’ is used but the process is not usually true parallelism. It is more akin to a coroutine. For example: on each tick, each child class will individually tick in sequence from left to right and be suspended until the next tick.
In addition to the blackboard, there are decorator nodes that usually modify a child node with a unique policy, for example, using the Loop/Repeat decorator at the root of a subtree to repeat a certain subtree or using the Invert decorator to flip success to failure and vice-versa. There are others, but this is plenty to get the point across.
Combining all the nodes mentioned above, one can create a great looking AI agent quickly. So, let us do just that.
7.2.1 Patrolling Example with Traditional Behaviour Trees
Imagine you are developing a strategy game and have set up a group of units to patrol around the perimeter of your base camp. The group of units will, ideally, have a ‘leader’ who will be running a behaviour tree, with all other agents following their lead. The first thing we need to do is to set up the blackboard. In this case, our blackboard will have a couple of items – the current patrol location and a list of all patrol locations.
From the root of the tree, we add a selector, and its first leaf node could be a task node called ‘UpdatePatrolList’ that checks to see if the list of patrol points is empty, which on the very first iteration would be. This list will be populated with data from the world using some form of query system.
From the second iteration onwards the patrol list does not need updating, so a branch that allows our agent to enact the patrol is needed. Next, a sequence node can be added to the selector whose child nodes will be a task node to set the current patrol location. A task node named ‘MoveTo’ can then be added that will move the agent to the designated patrol location and a task node named
