At the Heart of it All

As I outlined last week, the item pickup problem in First Person Shooter games is very difficult to solve, and that goes for humans as well. How do the truly advanced players approach this problem? At the heart of it all is one central question:

How will this benefit me?

If you want to know whether to pickup item A or B, you first must know how much item A benefits you, and how much it costs (in additional time to get the item). BrainWorks solves this problem using a customized resource prediction model, handled by ai_resource.c. Be warned, this code is not for the feign of heart. It's gratuitously well commented and documented, but there are so many bits and pieces it's very hard to get your head around everything at once. Think of it like opening the hood of your car, removing the engine block, and taking everything down to the nuts and bolts. Very interesting, but good luck assembling it into a working vehicle.

First, the AI's resource engine must encode the player's current state. This is handled by the resource_state_t structure (defined in ai_main.h). In brief, that information is:

• Health
• Armor
• Weapons
• Ammo per weapon
• Powerups (eg. Haste, Quad Damage)
• Activatable items (eg. Portable Teleporter)

It's easy to predict the results of picking up a specific item. If you want to imagine what happens when the bot grabs a rocket launcher, you'd just change the player state to have a rocket launcher and some rockets for ammo.

Determining how many points a given resource state is worth is significantly more complicated. Why is that? What other information does the bot need to estimate the points it would gain if it had this set of items? In short, it needs information about possible encounters with enemies:

• Chance of encountering an enemy near the bot
• How much damage the bot will deal with each weapon
• How much damage is required to score a kill
• How much damage an attacking enemy will deal to the bot
  

Once the bot has this information, it can estimate the points gained for any duration of time. The encounter rate can (and does) change based on where the bot is, of course. There will be higher traffic near popular items. As a result, the bot needs to remember when it does and doesn't see other players in different regions of the level. This is actually a complicated enough problem that I'll do a full post explaining how it works another day. For now, assume the bot magically knows how likely it is to find an enemy.

The three damage values should be independent of any changes to the resource states. The amount of damage a weapon deals depends on the bot's accuracy-- getting more ammo will let the bot deal that damage longer, but it won't ever make one weapon deal more damage per second than another. As a result, the bot sorts every possible weapon it could use in a priority list at the very start of prediction. The list might read something like, "Use the plasma gun until out of ammo, then the rocket launcher, then the shotgun, then ..." Now that might not be what the bot actually does when it gets in combat, but it uses this as a rough estimate of what might happen.

Naturally the estimated damage each weapon will deal is computed from the bot's historical data of previous weapon use. If in the past the bot had 30% machinegun accuracy and fired 90% of the time the machinegun was loaded, the machinegun's effective damage rate is 27% of it's maximum possible damage rate.

So when the bot needs to predict 20 seconds of time, it might say, "Well I'll get this many points from firing my rocket launcher for 8 seconds, until it's out of ammo. Then the next weapon is a railgun, which I shoot for the remaining 12 seconds and get this many extra points." There would be 2 distinct calculations in that situation. The code uses a similar system for powerups wearing off. In that example, if the bot had a quad damage that wore off after 15 seconds, it would break the time into three segments (0 to 8, 8 to 15, 15 to 20).

Of course this is all well and good if the bot survives, but what happens if the bot predicts its own death? Surely there must be a penalty if the bot needs health but considers options other than getting it. When the bot thinks its health will reach zero, the resource prediction engine stops giving points, and the bot takes a (1 / opponents) point penalty, since getting killed gives one opponent a point.

All that work just to figure out how many points the bot will gain, not even to select the best item for pickup! Next week I'll explain how exactly the item pickup algorithm uses this resource prediction engine to determine the best item to pickup.

A Journey of One Thousand Miles

There is a very old Chinese quotation that goes, "A journey of one thousand miles begins with a single step." More literally it reads, "A journey of one thousand miles begins beneath one's feet." Wherever you go, the first stage in any journey is the place you are in now. This might seem trite, but it's crucial, and all kinds of problems arise if you ignore it.

For example, suppose you take a cross-country trip from Chicago to Los Angeles:


View Larger Map

The basic plan is to take Interstate Highways 80, 76, 70, and 15 to cover most of the 2000 miles. But none of these directions are actually useful unless you can get on I-80 in the first place! If you zoom in on Chicago on the map, you'll see the directions start from outside the Chicago city hall. You'd use a totally different route to get on the highway if you started on the south side of Chicago or one of the suburbs. Understanding your current location is crucial to route planning.

Now last week I promised this post was about item pickup, not navigation. So what does route planning have to do with item pickup? Determining what items to pickup is a kind of of route planning. If a bot wants to go to a different area of the level, there might be three or four different routes it could take to get there, each with different items available on the way. There may be a good reason to take a longer route that has better items. Items define way points between where the bot's current location and where it wants to end up.

The item pickup algorithm determines which items a bot should pick up while it goes somewhere else.

That might seem simple, but as best I can tell, it's a fundamental change in how item pickup AI has been done in every other first person shooter to date. Typically the problem is viewed as finding where the bot wants to go, and choices are picking up items, hunting down enemies, or guarding a specific location. I've approached the item pickup as what you do while you are also hunting down enemies or guarding a location.

There is one crucial difference between item pickup and traditional route planning problems, however. If I'm planning a cross country trip, I'm either trying to minimize travel time or travel distance. Item pickup isn't interested in either of these things. Why do players pick up items? To get more points in the game. Bots need to select the items to pickup between points A and B that will maximize their score, not minimize travel time. That's why it's often correct to take a longer route with better items. The better items will increase the player's score more than showing up at the destination completely unarmed. The item pickup algorithm I've implemented is completely focused on one thing: estimating the score gained from taking different items.

And because the journey of one thousand miles begins with the ground beneath your feet, bots need to know how effective they are at earning points in their current state (health, armor, weapons and ammo values). Then they estimate the value of a particular item by imagining how that item would modify their state and how that would change their rate of acquiring points. The overall item pickup algorithm involves estimating the points the bot gets going from point A to item X to point B, where X is any nearby item. But the actual meat of the algorithm is estimating how many points the bot gets given a specific amount of health, armor, weapons, and ammunition.

Next time we'll dive in and talk about exactly how this is done, and what other structures are necessary to make these computations possible.

Putting It All Together

I've received a number of requests from people who want to see the bots in action, but don't have Quake 3 installed. So I recorded a short demo of the bots in action, spectating from a bot's point of view. All the bots in this game are skill 4 out of 5, so they're intended to give an experienced player a run for their money. While there's a lot to be said about how each individual piece of code works, it's the entire package that matters. Weapon selection is meaningless without good aiming or item pickup, for example. Here's the video:



The biggest thing this demo shows is how realistic their aiming is. The bot's view changes as chaotically and accurately as a real person would, which is to say "generally pretty accurate, but fast enough to be a bit hard to follow". They quickly respond to changes in attention and their aim isn't instantly spot on, but they correct their aiming mistakes relatively rapidly. You can also see some good firing decisions. For example, early on Xaero fights Mynx in a narrow hallway. Xaero correctly chooses the rocket launcher and kills Mynx with two well placed blast hits.

You can also see how the bots do a pretty good job of picking up the crucial items. One of the first things they do when they respawn is grab a weapon, and they make sure to pickup health and armor when needed. It might not seem like a big deal that bots choose to pickup armor when they are near it, but it really is. The original Quake 3 bots were notorious for ignoring perfectly useful items.

This video also highlights areas where the bots could improve. Most notably, the navigation algorithm, which I could not change. Later in the demo, you can see Xaero dodge in place for maybe 10 seconds before Hunter arrives and Xaero kills her. In this situation, Xaero hears Hunter below him and wants to get to her, but he can't figure out how to jump down the ledge. So he dodges in place until she arrives. Once Xaero kills hunter, he goes on his way, picking up the megahealth and some armor.

So BrainWorks represents a lot of progress for First Person Shooter AI, but there's still a lot of room for improvement. As I said before, AI is hard! For those of you interested in more posts describing exactly how BrainWorks, uh, works, fear not! Next post we'll dive into one of the most complicated systems in the code, item pickup, and explain how the BrainWorks bots solve this difficult problem.

The Attitude of the Knife

When I was 15, I read one of the three books that shaped my early attitudes, perceptions, and thought process. That book was Frank Herbert's Dune. The book is about an extremely gifted 15 year old who rises to political power because of his talent and training. But he has trouble finding people who relate to him as a person because of how special he is. As another gifted 15 year old, the entire story resonated with me, and many sections of the book left their mark on my memory. My favorite quote isn't the popular "Fear is the mind killer..." quote, however. It's about finishing things:

Arrakis teaches the attitude of the knife--chopping what's off what's incomplete and saying: "Now, it's complete because it's ended here."

The attitude of the knife is an attitude of firm boundaries. It is the decision of royal fiat, the parent's "because I said so". The attitude of the knife is the act of will that sacrifices short term opportunities for long term gain by ensuring that things never grow beyond the size of usefulness.

Once you've embraced the attitude of the knife, you have significantly more peace in life. If you stain your favorite shirt, you might be able to wash the stain out, but you'll be stressed until you know one way or the other. If you accidentally rip that shirt in half, there's nothing you can do-- that's the end of the shirt. Certainly you'd rather have the shirt intact (and unstained) than not, but that's no longer an option. The shirt has met its end and your only option is to throw it out. The attitude of the knife reduces many choices to just one, even if it's not the "best" one. It is the recognition of when a problem is not solvable, at least by you, despite being a real problem.

You might be wondering what this has to do with writing Artificial Intelligence. One of the bigger problems in software development is feature creep, the desire to add "just one more feature" or extend the usefulness of an existing feature. But things can easily grow out of control, beyond the ability of the project's developers. Often the features become so numerous that it's difficult for users to do what they want to do. All the features you don't care about get in the way. (Microsoft Office and Window's Vista, I'm looking at you.)

The attitude of the knife puts an end to feature creep. It says, "Sorry, that problem is out of my jurisdiction. I understand that's a real problem and you have to accept that it will continue to be a problem." Because Artificial Intelligence is so complicated, there's an awful lot of problems and it's very easy for a project to grow out of maintainability. You need to the attitude of the knife to write AI, or you'll never finish.

When I first started BrainWorks, I decided on two strict boundaries. First, every piece of source code has to be run on the game server alone, only running when the server requests AI processing. No changes to non-AI parts of the server were allowed. Second, no modifications to the core game engine were allowed either. The core engine that ships with Quake 3 runs the most complicated AI algorithms, such as navigation, motion prediction, and item pickup. If I found issues in the engine, I was allowed to write my own version but I could not modify the engine, even to fix bugs I found.

As fate would have it, all of the core engine algorithms for AI were dysfunctional. I did end up rewriting most of them-- weapon selection, item pickup, and motion prediction were all rewritten from scratch. But the one unsolvable problem was navigation. The core engine doesn't do a good job of navigating anything but a flat, two dimensional map. What's worse is the core engine doesn't even give the AI code enough map information for the AI to try a better job of making navigation decisions. The problem simply cannot be solved given the constraints of the system.

That's a real problem, but thankfully it wasn't my problem. There were enough other issues to tackle in writing BrainWorks. Many times it was a relief to find a bug that could immediately be ignored. Not because it wasn't a problem, but because nothing could be done about it anyway. And to be honest, most of the time the navigation decisions are actually correct. It only messes up in certain areas of certain levels. On the other hand, the core engine's item pickup and weapon selection decisions were universally wrong.

For those of you curious what two other books formed my life attitude, they are Godel, Escher, Bach: An Eternal Golden Braid and the Christian Bible. While I'm no longer a Christian, I've still taken to heart the positive humanitarian parts of the Bible. And I've not forgotten my promise to explain why I'm no longer a Christian and what part Artificial Intelligence played in that story.

Things in the Attic

Most every child has spent an afternoon rummaging through the attic at their parents or grandparents. Maybe it wasn't an attic for you. Maybe it was the basement or the garage, or just through some boxes shoved in a closet. But the basic experience is the same. You probably found a lot of mundane things and a few things whose existence is a mystery. "Dad, why do you have spare band saw belts in the basement? We don't own a band saw!" And if you were like me, you found one or two things where you couldn't even figure out what it was for. "Grandpa, what's this hunk of metal for?" "Oh, we used that to crank the windmill for water on days when it wasn't windy."

Of course... It seems so obvious now...

Programming can be like that attic too. You never know what things you'll find rummaging through the source code. For BrainWorks, the "attic" is ai_lib.c. Here's a partial list of the stand alone function:

• A bunch of functions that compare two values
• A function that returns the index of the first bit set of an integer
• A function that computer integer exponents of decimal numbers
• An assortment of semi-complicated vector math operations
• A function that tests ray intersections with a bounding box
• Binary search functions with optional insert on search failures

And there are some more complicated structures as well, such as:

• A rudimentary memory manager
  
• A hash table implementation (also known as a map)
• Timed Value Lists (a kind of priority queue)
• Octrees (a tree that organizes points in space for search)
• Index Subset Iterators (a highly specialized list iterator)

If you're not a programmer, you're probably thinking, "What on Earth is that stuff?" And if you are a programmer, you're probably wondering, "Why on Earth does he need that stuff?" From time to time, I'll come back to things on this list and explain how they were useful in designing AI.

But for now, I'll take a brief look at the memory manager and the hash table. The hash table is used to track dropped items and the memory manager handles the data in the table. Dropped items are things a player drops on the ground when they die, such as weapons and powerups they had. Without getting into too much detail, the AI code needs to track all dropped items so bots can consider them for pickup, and the code needs to know extremely quickly whether a dropped item is still there. That means the code needed the specialized storage structure of a hash map, since its so fast to read data from it.

One of the constraints of programming for Quake 3 is that the server absolutely cannot allocate any memory at run time, and there are generally no useful library functions. So if you need a widget_extractor() or a cog_spinner(), you have to make it yourself. While other languages have hash maps, Quake does not, so I had to write one. And writing the map required a memory allocator, or at least a good simulation of one.

All of that just so bots can pick up the quad damage someone dropped when they died! Good AI is worth that trouble.