The Artificial Intelligence of Halo 2

Are you tired of getting whipped by the Covenant? Learn how they think from the man who created the artificial intelligence for "Halo 2." In this exclusive Stuffo interview, Chris Butcher of Bungie Studios enlightens us.

11/17/04

So here I am ... surrounded by pizza boxes, soft taco wrappers, and soda cans and controllers. I'm tired, and I smell bad. I've finally beaten "Halo 2." I've been ambushed, sniped, flushed out, cornered and just plain beat down by the Covenant more times than I care to remember. In both "Halo" and "Halo 2," the enemy's battlefield savvy is one of the most impressive aspects of the game. The enemies are so much more than just an onslaught of fodder. This is not your daddy's shooter. If you think that a quick trigger finger is going to let you plow through the Covenant in "Halo 2," then there is a body bag with your name on it.

**"The AI lives in a simulated world."**
Photo courtesy Bungie Studios

The enemy characters in "Halo," as with all video games, are driven by artificial intelligence or AI. The complexity of the AI can often make or break a game's level of fun, realism and replay value. Halo is at the top of list when it comes to AI. The enemies react, respond and adapt to the player like real combatants on a battlefield.

If you're amazed by just how "dirty" the Covenant's "dirty pool" can get in the heat of battle, then you will be interested to hear what Chris Butcher had to say about the artificial intelligence of "Halo 2." Chris is one of four Engineering Leads at Bungie Studios, who are each responsible for certain sections of Halo's creation. Chris created the AI for the original "Halo" and got to expand his work in "Halo 2." Stuffo got a chance to sit down with Chris a few days before "Halo 2" launched and talk about the artificial intelligence of "Halo 2."

The Basics

"I wrote the artificial intelligence for Halo 1," Chris explains. "Basically, it is a very specialized type of intelligence. There was a custom piece of code for each character." In "Halo 2," Chris broadened the AI he built for the first game. The first thing to understand about the AI characters in Halo is this: "The AI lives in a simulated world."

Most first person shooter games, such as Quake or Unreal, are built on a graphical engine. The player is essentially a stationary "camera," and the engine creates the sensation of moving through a world by rendering graphics that create that effect. Halo is different, Chris explains. "Halo is a simulation engine. The engine creates the world, then puts the player and the AI in it ... [The] characters and their code are isolated from the world."

Each character is written to do certain things, but despite their individual roles, they all function in the same way. It breaks down like this:

The character uses its AI "senses" to perceive the world -- to detect what's going on around it.
The AI takes the raw information that it gets based on its perception and interprets the data.
The AI turns that interpreted data into more processed information
The AI makes decisions about what its actions should be based on that information.
Then the AI figures out how it can best perform those actions to achieve the desired result based on the physical state of the world around it.

"That all works through the same capabilities the player has," Chris explains. This is a key point in how the Halo AI works: Because the characters are forced to perceive the world around them, they are, in many ways, limited like the player by their senses -- in their overall awareness of what is going on around them. This limitation creates more lifelike behavior for the AI characters, as they can be surprised, make mistakes and decisions based on their perceptions of what's going on around them. As Chris puts it, "there is really very little difference between a player and an artificial intelligence character in Halo."

AI Perception

Chris goes on:

"If we were writing artificial intelligence for a robot, we would have to write all kinds of computer vision and analysis of the images to figure out what it was seeing. But because [the Halo characters] live in a simulated world, the characters can directly perceive that world. We chose to do that through simulated senses, because that way, the characters perceive the world in a way that players can reason about, because the player understands how their senses work in that world. We made simulated senses [for the AI].

So we have simulated vision, hearing and also a little bit of tactile knowledge. Where the player has five senses to deal with, and they're well developed, the AI in Halo really primarily only responds to visual input and sound input. That's because the two ways the player generally makes himself known to the AI is: The AI sees the player or they make a noise, like shooting someone."

Chris continues:

"So we have simulated vision and sound. We take that information about what the AI can see right now and we turn that into a memory structure. So [the AI] is able to say, 'At this moment in time, I'm able to see [a woman] sitting right there. I see a woman wearing a black sweater right there.' You then turn that into more processed information by saying, 'I have a memory there that is [a woman] who is in this particular state at this time.' If [that woman] were to walk out of the room and go around that corner, I wouldn't see her anymore. But the AI would keep a memory of that character and the fact that they last saw her there, and when she left, she was moving in that direction.

So they have memory models that are what they know about the world. They take that memory model and turn it into more specific combat information. For instance, if I have memory of seven characters in this room and one of them is my friend and the other six are my enemies, I will have the knowledge that says, 'I am in a battle in close quarters with an overwhelming force. There are six enemies and only two friends in here.' That is an example of more processed information that is used to create a more persistent knowledge about what is the state of the battle or what is the state of the world and how should I react to it?"

The Decision Making

The AI in Halo each take turns "thinking". These turns occur very quickly, which gives the impression that each AI is constantly thinking. When it is its turn, each AI makes decisions based on the data they have processed. This is the AI behavior system. Chris explains:

The four states of the combat cycle are:

Idle
Guard/Patrol
Attack/Defend
Retreat

That's the decision making. Behind it all is a basic combat cycle of seeing enemies, engaging enemies retreating and going back into another combat state. Now those are all combat-specific behaviors because ... our AI doesn't drink, it doesn't eat, it doesn't sleep. All it really does is stand around and then fight when enemies are nearby, but we try to make those behaviors be as life-like as possible."

Chris continues:

"So at every level of the hierarchical tree, those decisions about what the most appropriate thing to do is made based on the knowledge of what is going on in the world and knowledge about the type of character the AI is. For example, at that top-most level, it should say, 'If there are enemies I can see, then I should be engaging them in combat.' But if the AI is a cowardly character, it might say, 'If I am faced with overwhelming force, then I will retreat.' That is the level where our game designers come into play. They have access to all this game information and to all the numerical quantities that control the behavior of the AI.

We don't do things by random chance very much. The goal is not to create something that is unpredictable. What you want is an artificial intelligence that is consistent so that the player can give it certain inputs. The player can do things and expect the AI will react in a certain way. For example, if I sneak up behind a Grunt and surprise him, I expect him to run away. It would be bad if they only ran away half of the time, because then the player can build a plan that will only work half of the time. We try to go for predictable actions but unpredictable consequences. The Grunt will always run away, but you don't necessarily know where he'll run away to. That is where the re-playability comes from."

Pathfinding

Chris continues:

"If I'm an AI, fighting with enemies around me, one of the decisions I have to make is where is the most advantageous position for me to be standing? In each environment, there are hundreds of points specified by the level designer -- these are possible places an AI might like to be. That is how they control the flow of the game. They take AI and move them from one point to another, based on what's occurring. You feed all that into the really low-level intelligence. Like, if I am here and I want to get there, how do I get there? That's called pathfinding and really, I like to say that almost all AI is about pathfinding.

In encounters, there are rules. The Covenant will be here on top of the building. If the player kills three of them, then the Covenant goes to a set of points that are inside the building. What's really happening is the Covenant is following quite simple rules that the player perceives ... as the flow of battle. It seems like the Covenant thinks they have been weakened, so they retreat to a more defensive position. In fact, they are actually just following quite specific rules that have been laid out for them in that space."

Chris works with the level designers to analyze each point in the allowable area for the AI. In a way, the thinking is done for them. Each point is assigned a value, based on its characteristics in the space. For instance, a high spot may be a good location if you are on the offensive but not so good if you are being attacked. A spot behind a wall may be a good place to hide, but not to shoot. The AI knows these values and picks the location that offers the value it needs for the current situation.

The real challenge of pathfinding is getting to that point in a way that makes sense. Chris elaborates:

"If you have a character that can't navigate in an environment, that character will do things that are perceived by the player as stupid, like running into a wall or standing still and being dumb. That's because they want to go somewhere, but they don't know how to do it. We invested a lot of time in pathfinding in our game. Our AI knows that there are objects in the world that we have tagged with properties; this is a small object or a large object or a huge object. The AI will know, 'I can run through small objects' when pathfinding. They will kick them aside. But they have to run around larger objects. Certain larger characters know they can barge through objects that small characters will avoid or run around. "

In order to create even more realism in how AI interacts with objects in the world, the team uses animation to smooth out the look of the pathfinding. "We also tag objects with animation points," Chris explains. "A crate may have a tag that tells the AI, 'You can jump on top of this if you want to.' So when pathfinding the AI can decide to make a path over tagged objects. In combat, if the AI knows an enemy is hiding behind that tagged object, they may choose to jump on top of it and say something scary, or if they have lost sight of the enemy they may decide to jump up on an object to get a better look."

Object tags are also used to keep the AI aware of changes in their environments and indicate places that an AI can use as cover. But if these cover objects are destroyed or moved, the tag changes. This is how the AI knows they can no longer seek cover at that point in space. The cover tag is attached to the object, not the space.

Working Together

"Halo 1" offered players a level of a AI coordination and cooperation rarely seen in FPS games. By creating a series of built-in responses in each individual AI, the creators made the AI appear to be working together. Chris explains, "one of the most interesting things about Halo is that we have a lot of tools to make the AI work together as a coordinated force... [The AI] make individual decisions based on what's happening around them with their friends. For example, a Grunt would make the individual decision, 'The Elite I was just with got killed. So I am going to run away.'"

The Grunts are programmed to always react in that way. What appears to the player as an emotional or tactical response is, in fact, a simple "if/then" statement.

AI were also issued commands to move individually with guidelines that made them appear as if they were a team. Chris used the Marines as an example: "'I like to stand with my friends, but not too close.' That is how the Marines work. The Marines tend to move together as a unit but they won't stand in each others field of fire."

But that was the first Halo. "In 'Halo 2,' we have new tools for them to work together," Chris explains. His team added a joint behavior system to the AI that allows them to work together on much more complicated tasks. "The AI will say, 'I'm considering this joint behavior, and I notice there are people around me who are my friends.' So they post a request to the other AI to say, 'I would like to do this behavior with you. Will you accept it?' and the other AIs, when it is their turn to think, will either accept it or reject it and tell the originator. We used these new developments for various subtle and obvious improvements. The most obvious is the characters talking to each other. The AI posts a joint behavior, 'I notice both of us are looking for the same guy. I want to tell you something about him and I want you to respond to me.' or, 'We're both looking for the same guy. Let's work together to find him so that we can jump out and surprise him together.'"

Getting into a vehicle is another group behavior. If an AI can see a moving vehicle, it cam post a request to the AI driving that vehicle, asking for a ride. The AI driver, if he accepts the post, will stop, turn around and pick him up.

And the dialogue isn't just for flavor, Chris explains. "The talking is important because the AIs behavior and communication wouldn't be obvious to the player without the AI saying something and declaring their motives to the player."

The Uncanny Valley

As the interview started to wind down, Chris and I discussed some of the challenges facing AI.

"Are you familiar with the 'Uncanny Valley' theory from computer animated film?" he asked. I wasn't, so Chris explained it:

"As characters become more photo-realistic, you start to believe in them more and more. With humans characters, you get to a certain point of realism. What happens is there are characters that are so realistic you want to believe they are actually human. Then you notice their deficiencies. They have very plastic skin or very wooden eyes. All of the sudden they just become creepy. They are like zombie people, rather than appealing computer people. The appeal of the character rises, then drops dramatically, then rises again as you approach photo-realism."

Chris continues:

"In our game, we're not trying to be photo-realistic. Our characters are what they are in terms of visuals. The problem is that we are starting to approach that 'uncanny valley' point with behavior. We have all these characters that say all of these interesting things, that are very rich and meaningful about their environment. They have all of these interesting combat capabilities, but you can do something that they are not programmed to respond to, and they don't know how to react. Then all of the sudden they become dumb, like a zombie. They don't have any lines for, 'Hey Chief, you just made that soda machine do a complete flip. That was awesome!'

They have all this interesting stuff they do and say in combat and after combat and at certain points in the mission, but if you just hang around and observe them, they don't really do anything. The game industry is fast approaching this point where we are building characters who are really lifelike in their specific modes of operation, but when you take them out of those modes of operation, they really start to fall apart.

The challenge with AI in games right now is, 'What are the boundaries of AI? How do we hide those boundaries from the player? And how do we go beyond them?' That is what artificial intelligence is all about. It's about tricking the player into believing that there is something intelligent there."