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.