You've Got My Attention

Everyone has had moments of deep concentration, only to be interrupted by someone's voice. Turning to see who spoke is the natural response. People naturally look at whatever thing has their attention, so a First Person Shooter bot should be no different. And because "looking" (aiming) is literally half of this AI problem, bots need a detailed mechanism for deciding what occupies their attention. Just figuring out what the bot wants to look at is complex enough.

Last post I described how bots become aware of different enemy targets and select one as the target to aim at. But just because the bot has an enemy to aim at doesn't mean there isn't something even more demanding of the bot's attention. And what happens when the bot can't find an enemy to look at? They have to look at something, presumably in the direction an enemy is most likely to appear.

The selection of where to look is handled by the aim engine (ai_aim.c). The selection algorithm uses a simple priority structure to arbitrate between conflicting things. For example, if the bot needs to jump over a pit while there is an enemy nearby, the bot will always look in the direction of the jump so it doesn't mess it up. While aiming at the enemy it might score the bot a kill, doing so makes the bot extremely likely to fall down the pit to its death. The bot can always aim at the enemy after landing the jump. Similarly if the bot hears a noise that might have been made by a player, the bot will only turn to inspect that area if the bot doesn't already have a known target. Aiming at enemies has a lower priority than getting air but a higher priority than finding additional targets.

Here is the list of typical aiming reasons, from most to least important, as taken from BotAimSelect():

• Jumping over pits
• Aiming at enemies
• Shooting destructible objects like mines
• Looking forward when swimming
• Face a non-hostile target that has the bot's attention
• Look at the item the bot is going to pick up
  
• Look in an area enemies are likely to be
• Look at the same thing as last time

Interestingly, this prioritization is analogous to Maslow's Need Pyramid. Maslow theorized that humans rank their needs according to priorities, with each need fitting into one of 5 categories:

• Physiological Needs (being free from short term danger)
  
• Safety (being free from long term danger)
  
• Love (being accepted)
  
• Esteem (being appreciated)
  
• Self Actualization (just being who you are)

People don't worry about getting love (level 3) when they need a job just to survive (level 2) or need food (level 1).

The base of Maslow's pyramid is comprised of immediate pressing needs, just like the top of the aiming priorities. Bots look forward when jumping because they will die if they don't. Bots don't look at items when there's an enemy nearby who wants to kill them. In this regard, bots are like humans. We are all programmed for survival as the greatest need.

Two Kinds of AI

There are two kinds of artificial intelligence problems. In both situations, the AI has data describing its world, but the two kinds of problems require vastly different solutions. In a video game, the AI can have perfect information about, well, everything. You can find out the exact location of anything, how fast it's moving, and pinpoint sound effects. The server can even give the AI perfect information about its enemies, like their current health and weapons.

Contrast this with AI in a real world setting, like creating an AI that drives cars:



Now the AI has a whole different set of problems. Your car might have a lot of sensors, but there still can be measurement errors. The data might not be in the ideal format-- in a game, the coordinates of all nearby objects are encoded in three dimensions. But an AI to drive a car would have to extract those coordinates from two dimensional camera images. And if game AI takes too long to think, the worst that happens is a slower server. If your car's AI thinks too long while driving on the freeway, it could get into an accident!

Of course, while writing AI for simulated environments like games is much easier than real world applications, it has a different set of challenges. A bot that always knows where you are and aims perfectly isn't much fun to play against. To make a fun bot, the AI should only use data a real player would have access to.

The challenge of real world AI is computing accurate data.
The challenge of simulated world AI is determining which pieces of data to use.

So when I tackled the problem of selecting which enemy a bot wants to attack, you can imagine the kind of challenge I faced. The simple and obvious solution-- considering each player in the game-- was simply incorrect because it used data the bot absolutely should not have access to. To solve this problem, I wrote an environment scanning engine for BrainWorks (ai_scan.c). Ironically, the purpose of this module is completely different from the scanning a car's AI would do. The BrainWorks scanning engine "fuzzes up" the data so it's less accurate, or simply ignores things the bot shouldn't know about. While it would be nice for bots to perform this task the same way humans do, in this case the bot approaches the problem in the exact opposite manner.

The bot starts by checking everything in the game and testing if it can see it, by testing that no walls are in the way, the bot is facing the thing, and the thing isn't too far away. The bot records all targets it sees in its awareness list (ai_aware.c). If the bot hasn't seen a target yet, there is a short delay before the target is "active" in the list, meaning the bot has officially spotted the target. This is analogous to time it takes humans to react to sudden changes. Furthermore, the bot will remain aware of this target for a few seconds even if they hide behind a corner. Just like a bot can't know about a target behind a corner it hasn't seen, the bot must know about that target if they have seen them. That enables the bot to chase after the enemy, should they run away.

And of course, there are other things the bot scans for. If it sees incoming missiles, it notes them as well so it can dodge out of the way. Sound effects help the bot identify enemies that can be heard but not seen, and so on. Once the bot has a list of enemies, it analyzes them to decide which it should attack. (Generally this is whichever enemy the bot has the easiest time shooting.)

All that work just to figure out who the bot wants to shoot at! The bot might have thought about the problem differently from humans, but it came to the same results. Sometimes good AI means making the AI play worse instead of better.

Taking Action

"Okay," I think. "Artificial intelligence. Just have to figure out what I'd do and teach a computer to do the same. Sounds easy enough. Only one problem..."

"Where do I start?"

There are so many decisions to be made when playing any sport or action game, many of them subconscious, and all the actions need to be executed at just the right time to feel natural. For example, imagine an opponent just enters your field of view. It will takes between .1 and .3 seconds for the typical human to notice and react to this. So if the bot only scans for new opponents twice a second, it could take up to half a second to respond, much worse than even a poor human player. And there are more problems than this: With only two scans per second, sometimes the bot happen to scan right after a player stepped into view, reacting much faster than .1 seconds to them. To solve this problem, bots need to scan constantly, but have their own simulated "reaction" delay to spotting the target.

On the other end of the spectrum, algorithms like deciding which item to pickup are genuinely hard. Humans can spend a second or more of thought on the problem, and if a bot recomputed item pickup as often as it rescanned, the computer run noticeably slower. Bad things will happen if scanning ran as infrequently as item pickup, or if item pickup ran as often as scanning. Every kind of thought that a bot might do needs to be properly scheduled. It can't think about the problem too much or too little.

To solve this problem, I wrote the ai_action.c file, which administrates all the thought a bot does. That code decides when certain engines run and when they get wait until later. At the core of the design is a model analogous to human thought and action. I classified all human responses into one of three categories:

• Conscious
• Reflexive
• Subconscious

A conscious action is something you choose to do, like going for a walk. You do it because your brain engages the activity. Reflexive actions are those that you don't think about doing, but you can bring to your consciousness and alter it. For example, breathing is reflexive. You just do it, but you can hold your breath if you want. A subconscious action is something you literally have no control over-- it just happens. Your heart beat is a good example. No matter how much muscular control you have, you cannot stop your heart from beating.

Each bot action is associated with one of these states. Anything that a human would spend a lot of time thinking about is automatically conscious. Chances are, the algorithm to do that thought will strain the computer, so it should be run as little as possible. These actions are labeled "Logical" and run whenever the logical processing should run (just a few times per second, or even less frequently).

Reflexive actions are things the mind doesn't think about unless something about the world changes. You might gasp and hold your breath if you suddenly smell something foul, for example, but otherwise you'd breath normally. So all bot actions that depends on the world state are labeled "Reflexive". These run every time the server updates anything on the level (once every 50 milliseconds, or 0.05 seconds).

Last, there are a handful of maintenance things that simply must run as often as possible so the data can be handled immediately, such as checking whether the bot died. These have no label because there's never a time you don't need to run them.

Sometimes there are dependencies between different sections of thought. For example, a bot needs to aim before it shoots, and it must select a target before before aiming. And before that, the bot must first scan for eligible targets. So if firing is a reflexive action, then everything it depends on must also be reflexive (or even faster).

This isn't a particularly novel algorithm-- operating system have used more advanced schedulers for years. But it's rare to see this level of design applied to artificial intelligence in games, and that's really a shame. There are whole categories of problems that are much easier to solve once you have a proper scheduler to organize everything the AI needs to do.

Care to Comment?

It seems that everyone has an opinion on programming style standards, and no two people have the same opinion. So rather than tell you what you should do, let me talk about what I did with the BrainWorks code base. In retrospect, I feel like I did three things well and two things poorly. While I'm sure there are well more successes and failures, no one really cares how good or bad your code is as long as maintenance isn't a complete nightmare. I don't code well for your sake-- I code well for my own.

By the way, keep in mind that the Quake 3 code was written in C, so as a language it lacks some fundamental modern concepts such as "constructors" (a way to initialize information), "member functions" (a way to tie information to things the it can do), and a whole host of other things. Check out ai_lib.c for a reimplementation of things like binary search, memory management and hash tables-- things other languages can (and should) take for granted. I tried hard to keep things organized, but the choice of language made it difficult at times.

Success #1: Commenting

If you've looked at any of the BrainWorks code, it will be apparent that I'm a commenting Nazi. While sometimes I go a bit overboard, I cannot tell you how much time I saved by writing good comments. The purpose of commenting is to explain why, in human language, a block of code is doing things. Sometimes this means one line of comment can describe ten lines of code and sometimes you need the reverse. There's no magic ratio since a complicated thought process can be simple to explain to a computer or vice versa. For an extreme example of this, check out the comments for DataPerceiveCorrect() and ViewAxisModify() in ai_view.c. These functions are the very core of BrainWorks' vision algorithms, and both have header comments far longer than the actual code they contain. In both cases, I had to go back to these functions and I'm so glad I wrote down my thoughts. Without explaining why the code was doing things, it would have been much harder to figure out why it was doing the wrong things.

Commenting isn't just for maintenance. I actually write my comments before my code. If I can't explain in English why my code is doing the whatever it's doing, then I don't understand what I should even write.

Success #2: /ai_debug command

When the project doesn't come with a debugger, you can either litter the code with print statements or you can write your own debug interface. While I had to do a lot of the first, the development process was really helped by creating the /ai_debug command. This command lets you modify the behavior of any bot in real time, as well as force it the bot to give data describing what it's doing. For most of the weapon testing, I used this command to give one specific bot a weapon with infinite ammo and then had him output his accuracy with that weapon. I could see how the rates changed when I removed all error from his aim, or when I told his target to stop dodging (or even stop moving). For item pickup, I could make the bots tell me what items they chose to pickup and why they thought it was the best choice. A good test interface made it possible to analyze the vast sets of data a bot uses to make it's choices

Success #3: Overall Architecture

The top level architecture is handled by ai_action.c, and despite some issues with how some things must be written in the C programming language, I believe it's the best designed file in the whole project. It's a birds-eye view of everything a bot needs to do in a given processing frame. If you want to learn more about the BrainWorks code base, this file is the place to start. The comment in BotActions() explains how and when the bot decides to do things. Some bits of code must execute all the time while others must only run every so often. Structuring the bot's outer processing loop in this manner gave me excellent context whenever I needed to add a new feature. It was easy to look at this file and see exactly which other engines the new feature would need to interact with.

Of course, there are a few problems as well.

Failure #1: Lack of const correctness

This is just an inexcusable mistake on my part. I should have used the const keyword more (restricting a value from being accidentally changed) literally hundreds of times. It hasn't been a big part of my programming background, but doing so can prevent bugs from occurring. It also forces me to thing about function interfaces more. When I got to the end of the project and realized it should have been there, I felt like it wasn't worth the time. Everything already worked, but it should have been there from the beginning.

Failure #2: Lack of external data files

There are a few places where data structures are inlined directly in the code, and they should be stored in an external file and processed on startup. In particular, I'm thinking of ai_weapon.c which contains a description of the characteristics of every weapon. While this data shouldn't change, putting it in another format means non-programmers could read and edit it without rebuilding the project. The less you make someone else deal with your code, the better, no matter how well written it is. I suppose I could blame this on the annoyance of text processing in C versus some modern language, but the fault is really mine. If I'm willing to write memory managers in C, text processing shouldn't bother me at all.

It's a Hit!

In my last post, I explained how it's easy to decide what weapon a player wants to use given some simple data and one magic value: the player's accuracy with a weapon. It makes perfect sense-- if two weapons deal similar damage and you'll hit twice as often with one of them, then of course that's the weapon you want to use!

There's just two problems with writing AI for this. First, there's no innate concept of "weapon accuracy" like there is for weapon damage or weapon reload. A player's ability to use a weapon well is emergent behavior based on their reaction speed, mental estimation, and muscle precision. Bots don't magically know how accurate they are with a weapon-- they must be taught.

Second, even if bots knew their overall accuracy, that wouldn't be enough. Some weapons are much more effective in some situations than others. The shotgun is good at close range because the shot spread makes it ineffective at long ranges. Rockets are good when you are above your target because you can blast the rocket against the floor, making your target take blast damage even if they dodge the missile, and so on.

To get truly human-like weapon selection, bots need a relatively accurate answer to the following question:

How likely am I hit to hit my target from my current position?

The goal of the accuracy engine (ai_accuracy.c) is to answer this question. Bots solve this question by tracking the results of their attacks in game and modifying their behavior accordingly. If a bot starts scoring a lot of hits with one particular weapon in a certain situation, then it will naturally favor that weapon whenever it's in a that situation again.

Tracking accuracy against actual shots also lets the bots react to differences in player skill. Some weapons are particularly good against players who dodge poorly. If the bot encounters a player like this, their accuracy will increase and they'll know to use weapons that player has trouble with.

The accuracy data is reset every level to prevent bias. For example, if one level is wide open (favoring instant hit weapons) and the next level has many narrow hallways (favoring missile weapons), the bot will notice its higher accuracy on the second level and show a preference for missile weapons.

To differentiate the different combat situations a bot could be in, the bot analyzes both the distance to the target (whether it's near or far) and the bot's pitch view angle (whether the bot has to look up or down to aim at the target). These two values define a "Combat Zone". For example, 500 units away and 15 degrees down is one possible combat zone.

There are a total of 12 "reference" combat zones, forming a 4x3 grid of four distances (close, mid-range, far, very far) and three pitches (high, level, low). When the bot scores a hit (or miss) in a zone, the data is split between the four nearest combat zones. For example, one zone might split its data as:

• 10% (close, low)
  
• 40% (close, level)
  
• 10% (mid, low)
  
• 40% (mid, level)
  

But if the enemy moved further back, the accuracy data could get split as:

• 5% (close, low)
  
• 20% (close, level)
  
• 15% (mid, low)
  
• 60% (mid, level)
  

Similarly, whenever the bot wants to read data for a new combat zone situation, it simply averages together the data from the four nearest reference points. So even if the bot has never been in the exact combat situation of 682 units away, 4.3 degrees down, it has a very solid estimate of accuracy with all weapons.

The bot doesn't even need to know why rockets are better when it aims down at a target. Maybe it's the opponent, maybe it's the level, or maybe it's the bot's aiming algorithm. The reason really doesn't matter. The historical data will tell the bot that the rocket launcher is good in that situation, and that's enough for the bot to select that weapon.

The Rambo Problem

So imagine you're armed like Rambo. With a machine gun, shotgun, enough grenades to blow up a tank, and a missile launcher, you're a one man army. (Forget for a moment how you're carrying all this stuff; that's why it's a game!) There's just one problem. You only have two hands. So what weapon do you use? If you were one of the original Quake 3 bots, you would use whatever you felt like, as described by some randomly assigned weapon preference values. Unfortunately, that doesn't produce very good results. Shooting a rocket at a moving target far in the distance is bound to miss. What good players do is choose the best weapon to attack the selected target, and that's what BrainWorks bots do as well.

Of course, the devil is in the details: what makes a weapon "best" for the current situation? Well why do players attack targets anyway? To kill them, of course, since each kill is worth one point. The best weapon is whichever weapon will kill the target fastest. Mathematically estimating "Time to Death" (TTD) is an easy enough problem, given the following input variables for each weapon:

• D = Damage per hit
• R = Reload between shots
• A = Bot's accuracy with this weapon
• P = Percent of time the bot attacks with this weapon

And the all important:

• H = Target's current health

If you'd like to follow along with the source code, it's located in ai_weapon.c in the BotTargetWeapon() function.

The bot will average one hit every R*A/P = T seconds with whatever weapon it's considering, and it will kill the target in H/D = K hits, with a minimum of 1 hit. In other words, a weapon that deals 100 damage will require 1 hit against a target with 20 health, not .2 hits. This bounding ensures that the bot properly penalizes itself for "overkill" on the last hit. Against a target with 120 health, the bot might continue using the 100 damage/hit weapon until it scores a hit, and then switch to something else when the target is at 20 health.

This tiny little bit of code creates the crucial bit of emergent behavior known as "weapon combos". BrainWorks bots can and do attack bots with some high damage, slow reload weapons, and then switch to a spray-and-pray weapon like the machine gun or shotgun to finish off wounded opponents. It's something every good human player does and I never wrote a bit of code that says, "switch to the machine gun if the target has less than 30 health." This emergent behavior is the payoff from properly designing the algorithm, and it handles far more situations than the one described.

At any rate, if the bot averages one hit every T seconds and needs H hits to kill the target, the estimated time to death with a given weapon is T*K... Right? Well yes, but for reasons more complicated than they first appear. The real time to death is the sum of a geometric series defined as, "Chance to kill in 1 shot multiplied by time to fire 1 shot plus chance to kill in 2 shots multiplied by time to fire 2 shots plus ..." But this value turns out to be T*K.

There are a few other caveats well. No reload time is incurred for the last shot required to kill a target, so the code deducts R/P seconds from time to death for that. And if the weapon being considered isn't the currently equipped weapon, there's a reload penalty for switching which increases the time to death. The weapon switch reload penalty is automatically incurred (possibly a second time) if the considered weapon doesn't have ammo to kill the target, since the bot will be forced to change once it runs out. But that's the algorithm in a nutshell:

Search all weapons available, find the one that kills the target fastest, and use it.

If you've been reading closely, there are still two details I've glossed over: Estimating target health and estimating weapon accuracy. For health, bad players don't even think about it, good players estimate based on sounds (wounded players sound different), and great players keep a running total of the health value based on the hits the score and the items they see their target pickup. Attempting to model this, the average and low skill BrainWorks bots assume everyone has a fixed health total. The above average bots roughly know their target's health to the nearest 25 health points. And the best bots will flat out cheat and look up the exact health value. That last part is a bit unrealistic, but the information is used in a realistic manner. You don't have to use strict causality and emergent behavior for every problem to get good results.

Estimating accuracy is much harder, hard enough that there is an entire ai_accuracy.c file devoted to tracking it, so I will cover that topic at a later date.

Artificial Causality

Previously I said that causality was the foundation for BrainWorks. Since the objective of the AI was to produce bots that seemed human-like, the bots needed to do things humans would do at the same times humans would do them. That "at the same time" restriction is particularly important. A human player will pickup health, armor, weapons, and ammo during a game, and it's not enough to make a bot that also picks up those four kinds of things. If the bot decides to pickup an extra weapon when they are low on health, or armor when they are healthy but low on ammo, then they aren't playing very effectively. It will be obvious to their human opponents that the bots are making mistakes when they die so easily or just don't have weapons to put up a good assault.

When a player picks up health, they do it for a reason: they don't want to die. The proper time is to pickup health is when the player is in danger of dieing. So if a bot is going to do the same things players do at the same times, then:

Bots must do things for the same reasons players do them.

That means making great bots for a first person shooter game comes down to understanding why human players do the things they do. Why do players miss more often against dodging players? Why do players time the respawns of armor but not health or ammo? Why do players choose to fight with a rocket launcher sometimes and a machine gun other times? You have to understand how you play the game before teaching someone else how to play. If only the external details match but not the internal decision process, it's very easy for the bot to appear inhuman, picking up ammo when its low on health and so on.

This intense focus on well understood focus causality automatically disqualify some important AI tools however: genetic algorithms and neural networks. You can think of these things as black boxes with fixed inputs (eg. your location, what enemies are nearby) and outputs (eg. where to aim, whether to shoot). The boxes try things at random and their effectiveness is graded. Then the most successful ones are mixed together and the process repeats. Eventually you get one black box that does a good job of solving a particular problem with well defined inputs and outputs. For many applications, genetic algorithms are great. You can get 90% or better effectiveness without really knowing how the AI works. In practice that means that 9 times the AI does the right thing and 1 time they do something stupid, but it all washes out in the end.

The problem with using genetic algorithms in BrainWorks is that humans notice a flaws much more than correct decisions. As the ultimate objective is bots that feel human, a bot that does ten things 90% well meets that objective. But a bot that does nine things perfectly and one really stupid thing doesn't.

In effect, writing BrainWorks was teaching a computer how I, Ted Vessenes, play first person shooter games. And the teaching required me to learn for myself why I make certain subconscious decisions. In the upcoming posts, I'll dive into a few specific applications. Up next week: Weapon Selection.