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.