Outsmarting the Covenant

Building intelligent and engaging enemies to fight against in video games presents something of a conundrum for game developers.  In one sense, you are hoping to instil some evidence of strategy and reaction such that the player feels more engaged in each skirmish. Despite this, these non-player characters (NPCs) are typically built with the aim that we shoot and kill them within very small periods of time.  As such, there is a need to present whatever intelligent faculties these characters have within a very limited time-frame.

In this piece, we look at some of the challenges and solutions of the AI developers at Bungie during their time as custodians of the Halo franchise.  While the series has since transitioned to Microsoft-owned 343 Industries, there is an important journey that can be seen throughout the first three games as systems are refined and larger, more cohesive philosophies on AI  design are established.

Halo2007

The Halo Series

While the vast majority of gamers will be aware of the Halo series, it’s important we take time to establish these games in the context of this piece.  The original Halo was released in 2001 for the first Xbox console.  Halo is important largely in that it helped drive first-person-shooters (FPS) being released on games consoles.  While there were other FPS games being released on these systems, they were often poor conversions of PC titles – where FPS as a genre was well established – or simply not of the same calibre as their PC brethren. Halo was special in that it was not only a high-quality title, but also helped provide a ‘killer app’ for the original Xbox console.

TRIVIA: Given the success of Halo on the Xbox and its place in gaming history as the core IP for Microsoft’s foray in gaming, it’s easy to forget the game was originally headed for Mac!  The original Halo was first unveiled in 1999 as a title for Mac (by Steve Jobs no less) and the first teaser trailer still haunts the internet.  Not long after the announcement, Bungie were bought by Microsoft and Halo moved to the Xbox console.


Halo_Anniversary

The legacy of the Halo series is often considered in its technical achievements – which were further embellished by Halo 2, which became one of the first successful console-based online shooters – as well as the mechanics it helped establish for future generations of games.  As a result, gameplay trends such as recharging health meters, vehicular combat and the constraint of only wiedling two guns at any given time have since permeated throughout AAA shooters: there is certainly an idea or two that has been adopted by the Call of Duty series.

The Covenant

The Covenant is an alliance of numerous alien races who wage war upon the human race throughout the Halo series.  While from a game-design perspective this allows for a range of unique alien races to be fought against, it is also a catalyst for many of the plot elements throughout the original trilogy.  This is driven largely by the number of unique types of characters and their complex political structure, not to mention their religious worship of the halo device.

As far as we are concerned, we look at the Covenant army primarily by the types and their function.  A quick list of the typical Halo foes found throughout the series is given below:

  • Grunts: Small and rather harmless enemies when on their own.  Typically grouped in numbers alongside other, larger aliens to make them a real threat.
  • Jackals: Typically armed either with an energy shield and plasma weapon, which can proven difficult to fight against, or as snipers and attack long range.
  • Drones: Flying enemies who typically appear in the game in large numbers of 20 or more.  While typically armed with a plasma weapon, they do not pose that great a threat due to minimal health.  Once again, like grunts they benefit from strength in numbers.
  • Elites: The heavier armoured soldiers of the covenant, the Elites are more physically imposing than their brethren.  Equally smart and vicious, they can catch unaware as they wield a variety of different weapons.
  • Brutes: Larger and more imposing than Elites.  Typically carrying heavy armour and may be found wielding heavier weapons, including the gravity hammer.  The Brute class did not make an appearance in the series until Halo 2 but take on the gameplay role of the Elites in Halo 3 given they are not part of the invasion force.
  • Hunters: The largest and most deadly of the enemy classes: the Hunter is a large armoured enemy that wields a shield on one arm and a heavy cannon on the other.  Hunters can take serious punishment even on lower difficulties.

As we will learn later, each enemy type can carry their own AI behaviour.  This is actually a common trope exhibited in games, in that differing characters exhibit unique behaviours.  It provides a valuable means for players to understanding how to change their tactics based upon visual confirmation of the enemy.

The AI of Halo

One element of Halo that largely sets it apart from most other first-person shooters is the physical space of the environment.  Halo levels have a tendency to be very large.  As a result, in Halo the game is largely interested in creating encounters: periods where the player will discover multiple enemies that need to be defeated.  All of this space would be worthless if AI characters were merely dropped into the environment and started to attack. After all, large areas of physical space can provide for very interesting combat circumstances, particularly if enemy forces hold for example a beachhead or the entrance to a military structure.

In addition, as part of this larger and more open space, the game frequently jumps into periods of vehicle-based combat.  Unlike many other shooters where this would be a separate level or sequence – clearly separated by a checkpoint or animation sequence – in Halo there is no separation.  In addition, vehicle combat can easily be an asynchronous   event, meaning that Master Chief can be in a vehicle while his enemies are not and indeed vice versa.  As such, not only do NPCs need intelligent combat AI but it should adapt to vehicles too.

In order for this to prove useful, characters must be capable of a number of base behaviours:

  • Idle Behaviours: Naturally this will include idle animations, but may also include basic navigation patrols.
  • Combat Behaviours: Attacking a player if visible, searching for their target should they lose line of sight.
  • Defensive Behaviours: Running back to cover, falling back to more fortified positions, potentially fleeing if it appears all is lost.

Of course these base behaviours need to be fast and responsive.  In addition, they need to be flexible such that during a large and intense combat sequence, the AI can change goals for a character frequently and they respond in kind.  All the while, the player should not really be able to detect such changes are happening.  This occurs frequently throughout the series, given that as the Master Chief you will often alongside groups of AI  This becomes even more pertinent during the latter stages of Halo 2 where (SPOILER ALERT) a civil war among the Covenant results in sequences where different factions are fighting one another (and you if you interfere).

This brings us to the means by how this is achieved by the AI. Naturally for any game, there are a large number of design elements that bring it all together.  However, to begin we will look at one core element of the Halo AI infrastructure: behaviour trees.

Behaviour Trees

Behaviour Trees (BT) share many similarities with another popular game-AI technique: Finite State Machines.  This is largely due to their nature, in that they provide a symbolic and abstract means by which to identify both particular behaviours that you wish for a NPC to exhibit.  In addition, you can quite effectively model the decision logic that makes the transitions between behaviours occur.  Though despite their similarities, there are a number of differences, which we will discuss as we work through this piece.

EXTRA READING: If you’re new to Finite State Machines or fancy a refresher, check out our introduction to FSMs and their applications in the Batman: Arkham series entitled Arkham Intelligence (there’s also a feature-length lecture on this topic). In addition, the follow-up piece entitled Facing Your FEAR, which shows how FSMs are combined with planning technology in Goal Oriented Action Planning (GOAP).

Behaviour trees are, unsurprisingly, in the shape of a tree-structure.  This is not uncommon in computing, given we have data structures that are similar in nature.  What this does is ensure two key elements that make this distinct from traditional FSMs:

  1. A hierarchy in the actions that the NPC executes.  Such hierarchies help give complex behaviours greater shape.
  2. Control flow is more precise.  Typically, if we wish to manage how certain transitions occur in FSMs, we must become incredibly strict in its structure.  BT’s by default have precise control structure due to the top-down approach of their execution.

SIDE NOTE: Interestingly, behaviour trees bare a similarity to hierarchical finite state machines (HFSMs), given that they also dictate a hierarchy of knowledge modelling and subsequent execution. In some respects, it is actually hard to distinguish HFSMs from BTs. However for the sake of this article and our desire to discuss behaviour tree applications, we refrain from such associations.

A behaviour tree is comprised of nodes. A node will typically have multiple child nodes which subsequently have children of their own. This is how BTs grow: by starting with a single node and expanding outward from that point.  Each node can be used to either dictate a sequence of actions, one specific action or apply logical operations such as conditionals and negations.   A basic set of behaviour tree nodes are as follows:

  • Leaf: a node which has no children.  Typically a leaf node will be used to execute a specific action.
  • Selector: a node used to make decisions about which children (or entire sub-trees) should be executed.  Given their nature, it is expected that a selector will have numerous nodes as children.  A selector is akin to an if-statement in programming languages. Typically, the selector will use knowledge that exists somewhere in memory in order to make a decision based upon the state of the game.
  • Sequence: a node from which all children beneath it should be executed.  This allows for richer and more complex behaviours.

A simple example of a behaviour tree can be seen in the in the image below.  As we can see, we start with a root node an continue to move through the tree in an in-order traversal: i.e., we start at the top and move then visit every leaf node and its children from left to right.

A simple example of a behaviour tree with a number of selector nodes to allow for varied behaviour.  Retrieved from (Simpson, 2014)
A simple example of a behaviour tree with a number of selector nodes to allow for varied behaviour. Retrieved from (Simpson, 2014)

In the case of this behaviour tree, which is interested in moving between rooms using a doorway, it can be simplified as follows:

  • Walking towards the door.
  • Find a means to make the doorway accessible by either:
    • Opening the door.
    • Unlocking then opening the door.
    • Smashing the door down.
  • Walk through the doorway.
  • Close the door.

As you can see in this example, the basic actions – Walk to Door, Open Door, Unlock Door etc. – are all leaf nodes of the tree.  It is assumed that the NPC will then execute that particular behaviour and, upon completion, we will navigate to the next node in the tree. Meanwhile the Selector states are more readily apparent, given that it is clearly identified as such.  However, what is not apparent is that the Selector states will require access to some information held in memory to determine which of these actions to take.  In the case of the above example, it may well be that it simply opens the door, given that is permitted or would have smashed the door if it is locked.  In other cases, the ability to smash the door may not be allowed by that character, so they must find a key to open it. Meanwhile, you may have Hulk-like characters who are incapable of simply opening or unlocking a door and can only smash it.  How the Halo series addresses this type of flexibility is discussed later.

This is also the order in which the behaviour tree would be traversed when executed.  This would be achieved by calling the behaviour tree from the root node every frame of a game to find which node the NPC is currently in, which is rather memory intensive.  Alternatively, we can retain the current position within the BT in memory and then call back to that particular point on the next AI tick in the game logic.

It is arguably a better approach to build a behaviour tree as an asynchronous process; as particular behaviour can take numerous ticks to complete.  As such, if the BT is called almost every frame to see whether it is ready to transition is rather wasteful.  Since we often expect that behaviours will take time to complete.

Intelligent characters in games adopt AI methods, but what is used for entertainment versus scientific problems can differ drastically.
The Halo behaviour trees allow for a range of intelligent and engaging behaviours by different enemies found in the Covenant army.

Behaviour Trees in Halo

Behaviour trees have been applied in Halo extensively throughout the series, with a number of published works discussing their applications in both Halo 2 and Halo 3.  These are largely the focus of the remainder of this piece.

Let’s start by looking at the behaviour trees used in the Halo games.  As discussed earlier, the agency of a character in Halo (i.e. the range of different actions and decisions they can make) is very large in comparison to most other NPCs for first-person shooters.  As a result, the typical behaviour trees adopted in Halo, as shown in Figure 1, are fairly large.

The standard behaviour tree for an enemy in Halo 2.  Each subtree can openly compete for the next decision to take. Taken from (Isla, 2005).
Figure 1: The standard behaviour tree for an enemy in Halo 2. Each subtree can openly compete for the next decision to take. Taken from (Isla, 2005).

What is interesting about these behaviour trees is that each layer acts as a selector: dictating what particular action a NPC will commit at that particular point of time.  As we can see, this action range is very broad and encapsulates all of the different segments of combat that can take place in a Halo encounter (more on that in a bit).  The first layer dictates what particular type of action that the NPC will conduct, whether it is to engage the enemy, go into cover or attempt to flee.  However, as we move into the second layer we note that each of those ‘strategy sub-trees’ contain a number of individual behaviours.  For example, to engage against an enemy, be it the player or NPC, the AI can opt to attack by throwing a grenade, to charge the player (a behaviour typically exhibited by Elites, Hunters and Brutes) or conduct a gunfight.  Even then, it is quite easy to imagine that each of these actions, given they are represented so abstractly, is a behaviour tree in itself.

Action Context: Dictating Applicability

Naturally we are now spoiled with the range of actions we can commit live in gameplay, but what is important to remember is that – as mentioned earlier – particular actions will require some sort of assessment of whether they are applicable in that state.  While we may think about this on a enemy-class basis, it’s actually more about the current context the NPC finds itself in.  We will discuss this a bit more later on, but first let’s think about what that NPC is currently doing and what their role is.

If you consider the tree shown, some of these actions will not be applicable in certain contexts.  The easiest of these to appreciate is during vehicular-based combat: given that we are now constrained to the actions provided by that vehicle.  In addition, this can change depending on our role with that vehicle.  If we consider the collection of behaviour trees shown in Figure 2,  this shows which segments of the tree are active depending on the context and role.  The far left tree shows only what is applicable when the NPC acts as infantry.  As you can see, that encompasses a large proportion of the full range of actions.  The middle tree is in a vehicular context, but with that NPC assuming the role of the driver.  The far right tree is also in a vehicular context, but the NPC assumes the role of the passenger.  We can see that it becomes gradually more restrictive as a result of these changes.

The use of behaviour masks in Halo 3 allows for segments of the behaviour tree to be disallowed as a result of the 'emotional' state of the NPC.
The use of behaviour masks in Halo 3 allows for segments of the behaviour tree to be disallowed as a result of the ’emotional’ state of the NPC.

In addition, the type of character will have an impact on what actions can be executed.  In Halo 2 this was achieved by identifying areas of the tree as ‘disallowed’: meaning that the enemy can only achieve certain types of actions based upon who and what they are.  For example, Brutes do not aim for any sort of evasive or defensive tactics and act aggressively for the most part.  This idea evolved over time in Halo 3, with the introduction of behaviour masks, that would disallow certain portions of the tree depending on the ’emotional state’ of the NPC.  A given character could be normal, timid or aggressive and as a result, the range of available actions would change over time.   In addition, the behaviour trees adopted can have custom behaviours added in the pre-process stage of the AI ‘tick’, meaning that new temporary behaviours can be introduced.

So as detailed, depending on the context of battle and the type of character, the range of available actions will change dynamically throughout play..  With that in mind, how does the NPC then decide which action to take?

Figure 2: The accessibility of the same behaviour tree shown in Figure 1, depending on the role of the NPC in a vehicular context.
Figure 2: The accessibility of the same behaviour tree shown in Figure 1, depending on the role of the NPC.  The far left is infantry, the middle is vehicle drivers and the last is vehicle passengers.

Action Context: Dictating Priority

While this system largely suits our purposes, the big problem with so many different actions to choose from is how do you decide which is the right one to use?  This is achieved largely by using a priority-based list: where based on the priority of that action, the behaviour tree will select that particular path to execute.  Such priorities are calculated at runtime based upon what is transpiring in the game.  This means that priorities will gain and lose importance over the course of a battle; which is rather relevant given that priorities will shift during the period of an encounter. Notably since you, as the player, will continue to make your own decisions live in the battlefield, this will then dictate what the enemy does in response.  However, there is a small issue with this particular approach.

If we consider the idea of ‘action priority’, we’re assuming that these priorities are more or less fixed.  This does not hold when we consider how the tides of battle can often change based upon what’s going on.  As such, the selection layers of the behaviour tree continue to re-evaluate whether the current action being executed is the best one for that point in time.  This is achieved by re-evaluating the priority of each action, meaning they will change position in the aforementioned list.  As such, as a battle evolves over time, the NPCs will respond in kind and react to what’s happening around them.

An additional point tying into priority, is that once certain actions are completed, they carry a delay to prevent the action being executed again in quick succession.  An obvious example is throwing a grenade; otherwise the player would be continually dodging explosives as characters repeatedly thrown them at you.

Acting On Impulse

A final point to make about the Halo 2 behaviour trees is that our NPCs are acting based upon a priority system.  While these priorities are continually being re-evaluated throughout their lifespan, it means that these priorities are being scored using a pre-defined system.  This works fine in most cases, but there are circumstances where how these priorities are calculated don’t fit the context.  An example discussed in (Isla, 2005) is when a NPC is fighting the player and they are next to a vehicle.  The NPC will opt to stand their ground and fight.  Given that any attempt to get into the vehicle may be unwise, since the player could close the gap and attack while the NPC is too busy climbing into the vehicle.  However, should the player be in a vehicle, then getting into the empty Ghost or Wraith nearby is undoubtedly the best course of action.

To address this problem, Halo 2 adopts an event-driven approach called stimulus behaviours.  These behaviours force an impulse on the part of the NPC to give a particular action a priority at a given point in time.  While some of these impulses are rather small or specific, such as the vehicle example, there are cases when they are more encompassing.  A common squad behaviour is for lesser enemies to retreat in the event that the larger classes, such as Elites or Brutes, have been defeated.  This occurs courtesy of the death of the leader triggering a stimulus behaviour in the other characters.

Stimulus behaviours occur when an event in-game dictates an impulsive behaviour on the part of the NPC.
Stimulus behaviours occur when an event in-game dictates an impulsive behaviour on the part of the NPC.  This shows the ‘leader dead’ impulse, forcing the other NPCs to retreat.

Barely Scratching the Surface

This only scratches the surface of Bungie‘s rather substantial AI processes and design tools.  In this piece we have introduced the Halo series and discussed in particular their behaviour tree implementation adopted.  What has not been discussed is the rather extensive work that is put into creating each unique encounter that the player will work their way through. In addition, there are a number of optimisations that are achieved to ensure that Halo as a piece of software runs fast and efficiently.  It is rather easy for all of these systems to become very resource intensive.  We will discuss all this and more in a future piece as we return to the world of Halo.

References

Champandard, A. (2007) Teaming Up With Halo’s AI: 42 Tricks to Assist Your Game, AIGameDev.com, 2007

Islam, D. (2005) Handling Complexity in the Halo 2 AI.  GDC 2005 Proceedings, Hosted on Gamasutra, 2005

Islam, D. (2010) HALO Inspired Blackboard Architectures and Knowledge Representation. AIGameDev.com, 2010

Simpson, C. (2014) Behaviour Trees for AI: How They Work, Gamasutra, July 2014.

Enjoying AI and Games? Please support us on Patreon!
Tommy Thompson Written by:

Tommy is the writer and producer of AI and Games. He's a senior lecturer in computer science and researcher in artificial intelligence with applications in video games. He's also an indie video game developer with Table Flip Games. Because y'know... fella's gotta keep himself busy.