It's time we return to the Halo franchise with Bungie's 2007 release Halo 3. One of the earliest entries in AI and Games was an overview of the behaviour tree AI in Halo 2 and how it accommodated for a variety of combat situations. This time around we're looking at how new combat systems were built atop this framework to better control and manage the AI characters seen in Halo 3's large-scale encounters.
2004's Halo 2 for the original Xbox was the first step towards the proliferation of an AI technique now known as behaviour trees. Behaviour Tree's adopt a trickle-down approach to decision making where a tree comprised of all possible behaviours for a given character is constructed with conditions that dictate when to execute them. Based upon the current circumstances within the game, a particular sub-section of the tree will then be executed. This was ideal given the range of circumstances both ally and enemy AI characters could find themselves in, from Halo's variation in combat arena size to the ability for characters to jump in and out of vehicles at any time. Bungie's behaviour tree system made this process manageable by enabling or disabling specific sub-sections of the trees based upon the context of combat. In addition to this, Bungie adopted a principle referred to as 'stimulus behaviours', which were event-driven overrides that would force characters to dynamically respond to events in the world. This included being alerted to opposing forces being spotted, grenades being thrown in proximity, to nearby commanding officers being defeated by the player.
But in order for all this to work, each character needs to be given goals to complete that fit the story of combat: having every character set their goal as 'Kill Player' would result in a compromised and unbalanced mess. To achieve this, Halo 2 adopts an encounter logic system whereby the goals of a given character, be it hold a position, rush the player or enter a vehicle are managed by a handful of task generators set by designers. Each generator satisfies specific designer needs by identifying goals for specific characters in combat at a given point in time.
However, whilst this worked out fine for Halo 2, it would easily explode in scale and become difficult to manage. This would prove unsuitable for what Bungie sought to achieve in Halo 3. As such, a new suite of systems were required to balance and manage the objectives being set for characters, how they could achieve them and the knowledge base they could use to make intelligent decisions, so let's take a look at how that came about.
Halo 3 launched on the Xbox 360 in 2007 showcasing a scale of conflict not yet seen in console shooters: with dozens of friendly and enemy characters filling the screen at once not to mention vehicle combat with a more epic scope. To pull this off Halo 3 expands the combat management systems, but makes one sweeping change. Instead of adopting an imperative approach - that dictates what AI characters should be doing and how they can do it - it uses a declarative method that simply states that tasks need to be completed; squads of units then assign themselves to these tasks and can figure out how to complete them on their own.
Halo 3's mission designers build tasks that tell AI characters - be they UNSC, Covenant or Flood - what they should be doing at particular stages of combat. This includes territory they need to maintain, vehicles that should be manned or targets that need attacked. In addition, each task carries filters - conditions that dictate how they can be executed (such as the type of character or whether they need to be in a vehicle) and parameters that dictate how they're executed - like whether they should follow the player throughout or increase their level of aggression in combat. Tasks are typically broken down into smaller sub-tasks that can allow for more granular detail of what needs done and where.
Each major combat sequence has sets of tasks that are made active at different points of the battle, this encounter logic gives the combat a more natural feeling as fighting begins, followed by the player and supporting forces beginning to control the flow of conflict, right up to the last enemies taking their last stand against you. But also these tasks can help structure combat - such as having Brute Chieftans dictate the coordination of Covenant squads - or even shorten downtime in battle - with UNSC troops driving over to the player to pick them up during vehicle sequences. The task management and objectives system is hooked into the HaloScript tool used by level designers such that they can specify tasks, their priority, conditions and much more.
So how are tasks structured and how are non-player characters assigned to them? Tasks are built into the task-tree: whereby a collection of tasks are listed by priority and dictate what conditions are required for them to activate, when in the pacing of given battle they can occur and how many NPCs can be assigned to it. This is achieved by bundling NPCs into squads.
As Damian Isla explained in his 2008 GDC, the system operates much like a Plinko machine whereby squads trickles-down through the squad tree and begin to assign themselves to tasks with the highest priority that have yet to be filled. This squad and task allocation is an ongoing and dynamic process, with task allocation being activated frequently as the task-tree changes or tasks are completed. Should a task be deactivated given it's been completed by the squad or it's no longer relevant, the squad will trickle down to the next available lower-priority task. However, should a new higher-priority task be enabled, one or more squads will be filtered back down through the tree to ensure it is satisfied quickly and efficiently.
The criteria for how a squad is assigned to a task varies, but often the focus is ensuring that the selected squads don't have to travel far to execute it, will ensure they move closer to the player for the fight and that the selected squads will appear coordinated in doing so.
Now to wrap this up, I want to talk about how squads operate. Squads are - as the name implies - groups of NPCs that are of a similar faction. However their makeup is rather freeform, given that they can move around and due to the chaotic nature of battle, get broken up from one another. As such a characters assignment to a particular squad is governed simply by whichever one is closest to it.
The real reason that squads are put together beyond executing specific tasks required by designers, is to minimise the amount of times a specific NPC is requesting information about the game world that it needs to make decisions. Given there can be so many characters in Halo 3 on screen at once, this could kill performance. As such, each squad maintains a knowledge base known as a clump - which represents all actors in the game such as allied or enemy characters or props like vehicles and thrown grenades that are within region of the squad.
The squad then shares this information for making decisions but it ensures only relevant data is sought and calculations are kept to a minimum and only updated when necessary. So it works two-fold, as squads are now more coordinated and intelligent, but they also didn't cause your Xbox 360 to overheat, or at least not for that reason anyway.
Whilst the Halo franchise has since gone on to make spin-offs, prequels and sequels, the significance of Halo 2 and 3's technical achievements can't be understated, and helped innovate the game AI space at around the same time First Encounter Assault Recon did with the Goal Oriented Action Planning method. With 343 industries now caretakers of the Halo franchise, but also Bungie working on the Destiny franchise, you can be sure many of these systems and tools have since proliferated to not just those studios, but many of your other favourite shooters dominating the AAA marketplace.