By meatshield — May 8, 2011

An Interesting Problem: The AI Director

For those who have never played Left 4 Dead and it’s sequel, one of the most interesting parts of the game is the fact that every time you play it’s different. There are different numbers of zombies in different locations, keeping the game fresh. This is handled by something Valve Software, who makes Left 4 Dead, called the AI Director. In this post I’ll go over how you could make a rudimentary AI Director of your own.

I’m going to put the caveat on this that I’m not a game designer or a specialist in AI. I’m just a programmer who thought I had a basic idea of how you could do this and wanted to share

While they won’t say how it works, they do mention that it scales the difficulty based on how well the team is doing, taking into account things like what items they have with them, their current health, and other various factors involved in that game. So basically to make an AI director for your game you need to have all these stats tracked. That’s the first step.

You also need a facility for dynamically spawning enemies. In other words, if your level is represented in a static state, such as an XML file, it becomes much more of a pain to spawn enemies in a “realistic” way since you run the risk of increasing the difficulty of the game too fast. So you have to make the game dynamic from the start.

Another thing that Left 4 Dead doesn’t do that I think it should is you shouldn’t put a cap on how hard it can get. I’m going to take Magicka (the game that gave me the idea) as an example. In Magicka, you don’t have any ammo or limitations on abilities, so to make the game more difficult, you have to spawn more and stronger enemies. And since you can use the most powerful spell in the game from the get go, that difficulty needs to rapidly increase if the players are good enough to tear through the game. Sadly Magicka doesn’t do this, but if they did, here’s how they might do it.

Here’s some basic psuedocode to show how we might go about the basics of spawning enemies purely at random. We’ll improve on this later, but this gives us the basics of what we’re trying to do:

First you need to put some constraints on your system. For instance, you can’t go from spawning low level creeps to suddenly spawning the unkillable boss. There has to be some progression. I’m a fan of normalizing data in these situations, so let’s assign a point value to any mob, and make this the “difficulty” of the mob. Then we’ll have an arbitrary amount we allow our difficulty to fluctuate so there’s some wiggle room in what difficulty we spawn.

Next, depending on the game type, we may need to change how we select our position to spawn. In games like Magicka and Left 4 Dead, the players are playing through a story, and are defeating waves of monsters in the way of their victory. As such, the constraint is that everything must spawn ahead of them. This is also efficient since spawning things behind them means the mob would have to play catch-up, meaning we waste resources on some enemies that might never actually be seen by the players.

So let’s add this in to our pseudocode:

[sourcecode language=”text”]//We assume we have some object representing all monsters as well as all the info on the players’ current state
get player states
if players are doing well
increase difficulty level
else if players are doing poorly
decrease difficulty level
//else if they are doing like we want them too, leave it the same
randomly generate a mob
calculate the mob’s difficulty rating
if the difficulty of the mob is beyond the difficulty wiggle room
make a new mob until you get one within the range we want to spawn.
find a position off screen in whatever parameter zone we set (in front, to the sides, etc.)
foreach monster in the mob
select a spot near your position that’s a valid spawn location (i.e. not in a wall, etc.)
if it’s a valid position and nothing is currently in that spot
spawn the monster
else select a new spot and keep trying until you spawn the monster
{optional} start the monster moving towards the players’ current position
end foreach[/sourcecode]

There’s one bit of extra stuff in there I added, which was to start moving the mob towards the players. This is a good practice so that the resources you have spent on the generation of this mob go into use. It’s no good doing all this work to spawn a random mob and the players never find them. So we want to send them towards the players.

With our basic design flow done, let’s start looking at some specifics. We’ll start with calculating how the players are doing. Again, we need a basic normalizing routine. Unfortunately this is going to depend on the game, but let’s take Magicka as an example. The game is unique in that the players are constantly able to heal and constantly able to attack, so going with a look at their health and their ammo count doesn’t really help us out. So let’s look at a few other unique aspects in the game. One of them is that death in the game is very common. So we can look at the number of dead players as an indication of how well the team is doing along with how many have low health from being recently resurrected. If they are all alive, they are probably alright, but a check of their health might show that it looks like two were recently resurrected, or are about to die because their health is low. This might show the team seeing some difficulty. Another factor might be the number of enemies nearby. How we can normalize this is to take every monster and calculate their distance from the players. Closer monsters are a bigger threat, so if there are a lot of monsters close to the player, you would hope the game is currently more difficult. We also have to take into account off-screen monsters as an indication of how the game may be progressing in the near future as those monsters come in to play. Naturally you would probably come up with a more advanced formula than this, but let’s go with this for the sake of illustration, assuming all we care about is the health of the monster in terms of the monster’s stats:

[sourcecode language=”text” light=”true”]current difficulty = (sum of player’s health[0 if they are dead]/some player average constant)
*(monster 1 health*distance from nearest player)+(monster 2 health*distance from nearest player)+…
+(monster N health*distance from nearest player)[/sourcecode]

That’s probably not the best formula, but it gives us an idea of how the players are doing. The player average constant would basically put either an increasing or decreasing value of the rest of the difficulty. So if all 4 players have 100 health and the constant is at 200, the player’s contribute X2 to the difficulty, meaning it’s going well for them. If all are dead but 1 who has 1 health, the number becomes the sum of all monsters/200, so it becomes small. Thus we can set a threshold of what is “doing good” and what is “doing bad” at the game. So say if the current difficulty is greater than 1000, the players are doing well, and if it’s less than 70 the players are doing poorly, and we can adjust the difficulty accordingly. This also means we can radically change the difficulty based on our thresholds, so if the players are significantly above our threshold for doing good, we need to increase the difficulty more than if they are just barely above it. Of course if you want to do that you probably want to track their progress and if they are consistently doing well up the difficulty rate considerably.

Next is mob generation. If we have a difficulty level we are aiming for, how do we know if we are matching that with the mobs we generate? Let’s say the current difficulty is set to 100. We want to create a random mob with a value of 100, or at least close to that. Computer Science students will recognize this as a nice application of the Knapsack Problem, where you try fit as much stuff of the highest value as you can into a fixed size “box”. The one difference is that we don’t necessarily want to maximize the “value” since we’ve normalized our monsters. So if we did it right spawning 100 monsters of a value 1 should have the same difficulty as one monster of value 100.

So here’s a nice pseudocode way do create a random mob assuming you have an array representing all your monsters:

[sourcecode language=”text”]int difficulty = whatever our difficulty is
while(true)//we break out below
randomly select a monster to try to insert
if difficulty – monster’s difficulty value > 0//we can insert
add the monster to an array of monsters to spawn
difficulty = difficulty – monster’s difficulty
endif
if difficulty < our wiggle room value//we can spawn this
break;
end while
go on to spawning our monsters[/sourcecode]

We have one final little bit to discuss, and that’s when to generate a mob. Your first instinct might be to spawn them either totally at random or at set intervals, but one thing I think you want to avoid is the idea that you can predict the flow of monsters, i.e. you kill a mob, move ten feet forward, kill another mob, move ten feet forward, etc. Nor do you want to spawn completely at random since you could spawn two difficult mobs on top of each other that would vastly ramp up the difficulty and might overwhelm the players. So we need to add in another component to difficulty, which is how often to spawn. So what we’ll do is put in a delay on the spawning where the spawning mechanism will hold for a randomish period when the game hits a certain difficulty. We also probably want to put a limit on how close two mobs can be to each other to prevent spawning on top of another mob. That’s up to you how to do, but it’s a nice way to keep the game very random.

And that’s really all the theory behind how you might go about creating random enemies. One thing I want to mention in implementation, which I’m not going to do since it’s too specific to your game, is that you should put all your constants and static data, such as monster attributes, in a text file. This makes it really easy to balance the game just by tweaking those values. If the game gets too hard too fast, increase one number and you can bring it back into line. I haven’t really deconstructed a game since Battlefield 2, but all the values for all their weapons and vehicles are in text files in that game, and they mentioned in at least one interview that they spent a lot of time in a text editor changing values slightly to balance the game.

And finally, here’s the complete pseudocode for our theoretical AI Director:

find a position off screen in whatever parameter zone we set (in front, to the sides, etc.)
foreach monster in the mob
select a spot near your position that’s a valid spawn location (i.e. not in a wall, etc.)
if it’s a valid position and nothing is currently in that spot
spawn the monster
else select a new spot and keep trying until you spawn the monster
{optional} start the monster moving towards the players’ current position
end foreach[/sourcecode]

Let me know in the comments if you guys have any thoughts on this. Is it good? Too basic? Tweak this and it’ll be better? Let me know!

Subscribe to Swimming in the Matrix