They're Random, Baby!

Saved Films/AI Behavior - Interview with Max Dyckhoff

Longtime Bungie fans will remember that well over a decade ago, the original Marathon had a Saved Films option - the ability to replay the coolest moments of a game has been a part of Bungie tradition for almost as long as they've been making games. We were curious how it all worked, under the hood, however... so we talked to Bungie's Max Dyckhoff, one of the engineers at Bungie. Along the way, the conversation branched into a discussion of the AI that controls the non-player characters you interact with in the Campaign... and who were we to limit the sort of geeky goodness that could come out of this?

HBO: Saved films SEEM to work a lot like Marathon saved films worked; keystrokes, or button pushes, or whatever, are captured, along with a starting random seed... and when the film is played back, these are fed to the engine again. I realize Halo's system is WAY more complicated than Marathon's was - but is this at least the BASIC idea of how it works?

Max: You are absolutely correct, and no, it's not way more complicated than Marathon's.

HBO: So that random seed determines the actions of EVERY SINGLE ENEMY on the map, from the moment you start playing? (Well, given your own input, of course.)

Max: Not just every enemy, but every projectile, physics object, sound played, etc.

HBO: Those are the same things you need to keep track of to make online coop work too, - so they're inextricably linked, arent' they? I mean... if you can do online coop, you can do saved films?

Max: Basically that's correct, yes. (There are a couple of additional things like user interface (for both co-op and saved films) and extra design work for co-op.)

HBO: Someone has speculated that the reason Halo and Halo 2 had no online coop is because the AI algorithms for those games had some factor that was independent of the player - so that behavior could not be predicted across boxes. (This would also break films.) Is this true... or is it just as simple as "we couldn't get it polished?"

Max: I wasn't involved in either of those projects, but I can tell you that it isn't quite that simple. When dealing with network co-op you have to make sure that every operation inside the game is deterministic. This basically means that if you put in the same input (basically the random seed and the player input) then the system will always give you the same output.

Regrettably when it comes to coding, it is easy to make things non deterministic. Sharing data between multiple threads, updating data in the wrong place, failing to initialise data, and so on. We had some excellent engineers who worked really hard to polish out all these non deterministic pieces of code enabling us to announce that yes, we could do network co-op.

HBO: Can you explain how the system works?

Max: the first important thing to realise, which you probably do already but it's worth emphasising, is that random number generators are not random. You give the generator a seed number, and then ask the generator for random numbers. Given the same seed number, the generator will ALWAYS give the same sequence of numbers. (The seed changes whenever the game starts up.) The game engine will periodically request random numbers from the generator; for example if a Brute wants to choose between two equally good courses of action, he'll ask the random number generator which action it should choose. Because the game code is executed sequentially, given all other conditions being equal, the code will always request random numbers in the same order, from the same pieces of code (all other conditions meaning the input stream of player control). Because we're running on fixed hardware, the execution time of everything will be identical on subsequent playthroughs.

HBO: How many choices of action does an average AI character face in the course of an encounter? (You mentioned a case with two choices above - but is that normal, average, or were you just using a simple example?)

Max: There are probably very few choices which are based on a random number. Random AI isn't typically very fun; we like to make it so that a player's action will have a typical reaction. For example: "If I close to this distance from a berserking Brute, then he will melee me." The randomness is often used for big state changes, when we consider the AI to be operating somewhat on animal instincts. For example: when you take down a Brute's armour there is a probability that he will berserk and start charging at you; that is based off a random number, although he also takes into account other things first to keep him intelligent. (Other factors include "if the player is really far away then don't," "if the player is really close then don't," "if lots of people are berserking already then don't".) Similarly, kamikaze grunts operate on a random number.

HBO: So... in a battle like the last scarab battle (on The Covenant): how many AI characters are you typically keeping track of?

Max: Oh god, perhaps 40? 50? There are perhaps 10 marines, the two scarabs (they are actually AI characters) 6-10 guys on the back of each scarab, and then ghosts and choppers on the ground.

HBO: What about the banshees and hornets above the battle?

Max: Some banshees and hornets count as AI; I think there are a couple above the scarab battle. We also have the concept of flocks of banshees though; if you see a LOT of banshees/hornets, that is probably a flock. They will be far away, and are basically REALLY stupid. There are just a couple of rules that govern their movement and shooting. They are so simple they don't even feature in our performance calculations. I think the only place there are a lot of banshees that are AI is in the air battle on The Covenant.

HBO: How does the number of players affect the calculations? Is it a linear increase, or more than that? For example, a Brute is getting ready to go berserk because player 1 just shot his helmet off... and player 2 comes into range from the left. What does the Brute do?

Max: In that case, the Brute will only be thinking about his immediate target. Each AI character has a single target; the person they are shooting, talking about, interacting with. You can distract him, but at that point you will become his target. They keep track of dozens of enemies, vehicles, projectiles, and so on, but only consider one to be their target, and most of the calculations they do are based off that one target.

HBO: Let's go back to something we started discussing earlier: are kamikaze grunts simply normal grunts who CHOOSE to go kamikaze - or are they put in at the start?

Max: Kamikaze grunts are just normal grunts who choose to kamikaze. We have the concept of leadership; a brute captain or chieftain is the "leader" for all the grunts and brutes around him. There's a very simple hiearachy, basically: Chieftain > Captain > (Brutes, Grunts, Jackals). The highest "ranking" guy around is considered to be the leader of that encounter (or section of the encounter; you can have more than one leader in some of the big battles). With a leader around, enemies are a lot more aggressive towards you, because they have him backing them up (or kicking their asses).

HBO: How smart are the underlings in terms of noticing the big guy's dead? Do they immediately look to Number Two, or can they get confused if Number One (the dead one) was in line-of-sight, and Number Two is around a corner?

Max: When the leader is killed, the group of enemies is "broken", and they all have what we call "broken behaviours" that trigger when this happens. Brutes: berserk or hide in cover. Jackals: huddle together, shields up. Grunts: flee or kamikaze.

HBO: I've seen the shield thing - looks almost like the E3 2003 trailer sometimes.

Max: YES! Mission accomplished. <grin> Actually, completely accidentally, marines will huddle too, if their leader is killed. (Well, we noticed the behavior, but left it in because it was cool.) Leadership was only intended for the enemy AI, but it just happens that one of the marines has a higher rank (I forget which one) and if he dies, then the other marines will huddle.

HBO: What's the percentage of leaderless grunts that go kamikaze, as opposed to fleeing?

Max: When we break, we tell each grunt that they are allowed to kamikaze. Each grunt will then check the conditions are ok (far enough away, not too close, etc), and then (importantly) check that not too many people are already kamikazing. We actually limit how many kamikazes are allowed per difficulty level; on normal I think you'll only get one, while on legendary I think you'll get three.

HBO: How does vehicle AI differ from AI for ground troops? How come some marines are perfectly happy to drive into a rock or a wall, but would never in a million years WALK into that wall?

Max: The behavioural AI for the two are virtually identical. We can enable or disable certain behaviours based on whether the character is in a vehicle or not, so for example there can be a custom behaviour which tells a vehicle driver to cover if his passenger is being damaged.

As far as movement goes, that's a much harder problem to solve. Ground troops can basically move and turn in any direction, which is a luxury vehicle drivers don't have. We therefore have two movement controllers for ground vehicles (and two for flying vehicles) that specify how they should drive.

Non directional vehicles such as the ghost or the wraith can move in any direction, and by and large operate like a ground troop would, with some extra code in there to make them look swooshy.

Directional vehicles like the scorpion or warthog are the hard one. If a character decides to move to a point perpendicular to his facing direction (that is, off to one side), he first has to orientate himself to face in that direction, and then move there. This means we have to calculate what sort of turn he should make, and then check if that turn will collide with anything like walls or crates or other vehicles.

Needless to say, this isn't completely elementary, and while I tried as hard as I could to make the directional vehicle driving perfect, there are still some... issues.

HBO: Why does the clip functionality work in Multiplayer, but not Campaign? (That is: the Saved Films How-To stated that "the feature did not function perfectly" in Campaign; why not? What's different?)

Max: I'm not entirely familiar with the clip functionality, but I suspect it is because the game state during a campaign game is far larger than that during a multiplayer game, and so multiple copies can't be stored as easily, which are necessary for saving clips. That's only a guess though...

HBO: In that same Saved Films How-To, it was stated that reloading a previously played area would "take ages" - this is because you'd not only have to load the map geometry - but you'd have to fast-forward through the film from the beginning to that save point? (Otherwise, there'd be no way to know what the state was just before the checkpoint.)

Max: The question about reloading a previously played area is really interesting. During a normal play through of the game, we are constantly caching the next section of the game. So while you are watching the "Arrival" cutscene, the first few encounters of Sierra 117 are being loaded in the background. While you are playing the Dam encounter at the end of the first level, we are loading the start of the second level. This means that we can have essentially seamless transitions between levels, and also has significant impact on the rewinding of saved films in Campaign. You can actually notice the impact of this if you speed through some of the areas really fast; you will hit a tiny two second loading screen that is annoying, however most players will never encounter this hold up.

I have to say hi to Mat Noguchi right now, because without him there would be loading screens all over the game and we would all be very sad. He did amazing and under appreciated work on caching :)

Thanks to nico, who inspired this interview in the first place.