The Last Place You Look

When I was growing up, I always found it ironic how lost things were always found in the last place you looked for them. For some reason, whenever I was looking for a lost toy it was never in my bedroom or the play room. I'd find it outside underneath the deck, in the basement, or inside the sofa. It wasn't until I was older that I realized this wasn't coincidence; it was a mathematical truth. Put another way, when you're looking for something and you've found it, you stop looking. Things are guaranteed to be in the last place you look.

That's not the same as saying all places are equally likely to hold the lost object, of course. If I'm looking for the TV remote, it's less probable that the dog took it as a chew toy than that the remote fell between sofa cushions. And it's far less probable that the remote is now part of an exhibit in the Smithsonian Institute.

The general purpose search algorithm that humans use for locating lost objects involves prioritizing possible locations from most to least likely and searching them roughly in that order. The actual order will get rearranged to save travel time. For example, if an object is most likely to be on top of your dresser, second most likely to be on the bathroom counter, and least likely to be under the bed, you'll still probably check your dresser first and under the bed second before heading to the bathroom. But in general the search is from most likely to least likely. That also explains why the place you find an object is always the last place you'd think to look. The optimal searching algorithm stipulates that you search in the least likely places last.

So this brings me back to last week's topic of octrees. I described how to build the structure that BrainWorks uses to determine which item a player is nearest. But I haven't actually explained how BrainWorks uses the octree to do this. Consider this two dimensional tree (a quadtree):


Each item in the tree is one of the colored dots. The player is the black dot with the circles around it. Every rectangle refers to a particular subsection of the tree. In this example, the red dot is the root node of the tree. The lower left section of the tree is divided by the brown dot into four sub-regions, and the brown dot's lower left region is further subdivided because it contains another item (the purple dot). The circles represent the boundary of the potential search space as the algorithm progresses.

When the search algorithm first starts, it checks the distance from the root node to the player. This distance defines a circle around the player. If an item is closer to the player than the root node is, it must be inside that red circle. At this point the algorithm doesn't know that the green or blue dots are inside the circle. It doesn't even know that no items in the lower left quadrant are closer than the red (root) item is. But it can mathematically guarantee that nothing in the upper right quadrant could be closer, so that quadrant is ignored.

Because the player is in the lower left quadrant, the algorithm prioritizes search in that section first. This is the quadrant that contains the greatest area of the red circle. The next most likely place to look is the lower right quadrant, as the player is closer to the lower right quadrant than the upper left. The upper left quadrant is scheduled third. So the areas to check are, in order:

• Lower Left
• Lower Right
• Upper Left

Then the algorithm merely recurses. First it checks the brown item in the lower left. A quick distance check shows the brown item is too far away, but the search continues on the brown region's subquadrants of upper right, then upper left, then lower right. As none of these regions have any items, the search of the brown region terminates quickly. And at this point in time, the red item is still the closest object to the player.

When the algorithm starts checking the lower right quadrant of the red item, it notices the blue item is closer. So from now on, it compares all potential search areas against the blue circle instead of the red one. No further items exist in the lower right quadrant, so the blue item remains the closest item to the player.

Last, the algorithm wants to check the region to the upper left of the red (root) item. However, when compared to the new blue circle, the search algorithm realizes that the region does not intersect the circle. Since the circle is the area of potentially closer items, nothing in the upper left can be closer that the blue item, so the entire upper left region is ignored. And since all regions were prioritized by distance to the player (from closest to farthest), the search process is done. All potential items have been checked, so the blue item is the closest. The algorithm doesn't even need to check how close the green item is to the player because that entire upper left quadrant was skipped.

The octrees in BrainWorks function the same way, only in three dimensions instead of two, and using spheres instead of circles. That answers last week's question of why the algorithm might need to search up to 7 subregions to find the optimal solution. The closest item isn't necessarily in the same section of the octree as the player, but the diametrically opposed region can always be ignored. That leaves 7 of the 8 regions to check. In practice most regions are quickly pruned away when a closer item was found, in the same way the region containing the green item was ignored when the blue item was discovered. Even though the example tree contained seven items, only three of them needed to be checked (Red, Brown, then Blue) before the closest item could be found.

Dude, Where's My Rocket Launcher?

Back in March I wrote about how the AI conceptualizes item placement. Rather than thinking of position in terms of raw coordinates, bots consider each item (or cluster of nearby items) to be a potential landmark. When statistical tracking is done for areas players are likely to be, for example, they are grouped by which item they are closest to. Statistical tracking is one of the most powerful tools available to AI if you have a sufficiently large and well organized data set. BrainWorks uses this data to analyze which areas of the level a player is most likely to be in, for example. Not only can this information help bots track down enemies; it also helps a hurt bot them avoid enemies. The more data it can track, the better. So by extension, the faster it can translate from raw coordinates to the nearest item, the better. However, this is not a simple request.

If a level has N items in it and a player is located at position (X, Y, Z), what's the fastest way to determine which item is closest to that player?

Well you can just check the distance to every item and use whichever item is closest. If you read last week's column, you'll remember that this search requires linear time. If you double the number of items on the level, it will take twice as long to find the closest. Certainly we can do better than linear time.

There are a number of data structures that can solve this problem. Some of them might require more setup time but give slightly faster search time. The structure I chose is an octree. It's a tree that holds some number of three dimensional locations. If you want to learn more, I recommend the Wikipedia article on quadtrees as well. A quadtree is the two dimensional analog of an octree, so it's a bit easier to visualize.

In the example I gave last week of a filing cabinet holding 100 pieces of paper, 1 cabinet held 10 folders and each folder held 10 papers. This is a total of 111 pieces of data stored (100 papers + 10 folders + 1 cabinet). In computer science terms, each data storage location in a tree is called a "node". The node where searching begins is called the "root node". In the filing cabinet example, the filing cabinet itself is the root node. The cabinet and folder nodes split 10 ways, and the pieces of paper do not contain any sub-nodes. Nodes that do not further branch are called "leaf nodes".

Getting back to the octree example, the BrainWorks AI code needs to store the spacial locations of 50 or even 200 items in a tree. Each node in the octree contains is one of the stored points, and the node branches 8 ways. Visually think of each node as dividing space into 8 octants-- upper north west, upper north east, upper south west, upper south east, and four more counterparts for lower sections. All points that are above, north, and west of the root node are stored underneath the upper north west node, and so on for all other octants.

For example, suppose there are 50 items on a level. One of them is stored in the root-- say it's a rocket launcher. Of the 49 remaining items, 6 of these item locations are above, north, and west of the rocket launcher. The root node will link to a node for one of these six items-- a megahealth. The other five items will be stored undernearth that megahealth.

Again, the octant division property applies to all nodes, not just the root. So the megahealth also divides its space into eight octants, and the five remaining items will be appropriately placed underneath it. Keep in mind that each of these items is guaranteed to be above, north, and west of the rocket launcher. But items that are above, north, and west of the megahealth will be stored in a different octant than those above, north, and east of the health. Given that there are eight possible areas and only five remaining items to store, chances are that these items will all be stored in one of the eight sub-nodes of the megahealth. (If two items happen to both be below, north, and east of the megahealth, then the first will be stored under the megahealth, and the second will be stored under the first.)

Searching a tree is generally proprortional to the depth of the tree-- the greatest distance from the root node to a leaf node. And for a tree of 50 items, the depth is usually 3 or 4. Going up to 100 items might push the depth to 5 for some level layouts. So the octree structure makes answering the question of "which item am I nearest?" much, much faster than checking all 50 or 100 items.

Given that items have fixed locations on the level, the octree needs to be created once when the level starts, but the tree will never modify during the game. (Ignore items that drop from dead players-- those are handled differently and not useful for statistical tracking anyway.) The actual algorithm is pretty simple, a bit slow, and very likely to produce a well balanced tree. Here's how it works.

Given a set of items:

• Average together all their positions to find the center
• Check each item to find which one is closest to the center
• Add that item as the dividing node
• Separate all remaining items into one of the eight octants this center divides
• Repeat the process on each octant that contains at least one item

By "not terribly fast", this algorithm could take up to half a second on a very, very large map. So still inconsequential, and well worth the one-time hit to produce a better tree.

Of course, there's still the question of how you search the tree to find the nearest item, and that I will be explaining next week. Here's some food for thought though: even if you identify which octant a point would reside in, you still need to search up to seven of the eight octants to guarantee you've found the closest item to your input point. Searching this tree is not done like most tree searches. For those of you who like thinking through these kinds of problems, try to figure out how the search algorithm actually works. I'll give the answer next week.

Given a set of item locations arranged in an octree and one player location, describe an algorithm to find the item nearest the player.

Good luck!

Needle In A Haystack

For a long time, I kept all my important documents in a single box. That would be stuff like my passport, car title, insurance information, and so on. After my wife and I bought a home, we had enough papers to file that our simple box wasn't sufficient. We bought large filing cabinet and it's served our needs ever since.

It's not that we needed to look up stuff any more frequently than before. But when we went from 100 pieces of paper to 1000, we didn't want it to take 10 times longer to find anything. To find stuff in the box, I riffled through it until I found the paper I needed, sometimes searching the entire thing. More stuff means the search takes longer.

A filing cabinet solves this problem by providing a natural structure for organizing the papers. For example, all the papers on the home can go in one file folder, all the car information in another, and all the identification documents like passports in a third. Then the lookup process becomes simpler, as I can ignore everything that's not part of the folder that keeps whatever I'm looking for.

This is a real savings in time. Imagine you have 100 different pieces of paper. You can either stuff them all in one box or you can organize them into 10 folders, each containing 10 papers. What's the average number of papers you'll have to look at to find any given piece, assuming you always know what folder should contain that piece of paper?

When looking through the box, you could look at anywhere between 1 and 100 pieces with equal probability. So you'll average (1 + 100) / 2 = 50.5 pieces before you find it. When looking through the folders, you have to find the correct folder from 10 options and then the correct paper of the 10 pieces in that folder. It will take between 1 and 10 tries to find the folder, or 5.5 on average. And similarly it takes on average 5.5 tries to find the paper in the folder. That's 11 tries total for the folder compared to 50.5 for the box. The filing system can be searched roughly five times faster!

Or is it really five times faster? What happens if you have 1000 pieces of paper instead of 100? When you have this much information, you could create folders and subfolders to further organize the papers. If you have 10 main folders, each of which contain 10 subfolders, and each of those contain 10 papers, then it will take 5.5 + 5.5 + 5.5 = 16.5 tries to find any one of the 1000 papers. It would take 500.5 tries if they were in a box. So in this case the filing system is about 30 times faster.

The more data there is to store, the more efficient the filing system is compared to the box. That's because the filing system is a whole order of magnitude more efficient. In mathematical terms, searching through the box takes linear time. When you add ten times as much stuff, it takes ten times as long. But searching the filing system takes logarithmic time. Adding ten times as much stuff just means it takes one more search step. Very roughly speaking, searching is proportionate to the number of zeros on the size of the data. Searching 100 things takes twice as long as 10 things, and searching 1000 things takes three times long. Want to search 1,000,000 things? That's six times longer than searching 10 things.

You might be wondering what all of this has to do with artificial intelligence. At the heart of almost all AI is data, and data doesn't mean anything if you can't find it when you need it. That means efficient data storage is the required foundation for artificial intelligence. An algorithm is only as good as the data it has access to, and good AI needs a lot of data. If all the data were just shoved in a box, there's no way the computer could run the AI's thought process fast enough. Indeed in almost all computer science, the way in which data is organized is just as important as the actual data being stored. After all, what good is information if you can't find it? Next week I'll give a concrete example of how BrainWorks puts this concept to use.

Sitting on the Fence

For roughly the past month, I've been interviewing at a few different places looking for a new job. I've felt overqualified at my current place of employment and really wanted some more challenging work. At the end of the process I had two offers to choose from, both of which were really similar and far superior to my current job. I suppose most people might decide based on some simple, simple heuristic like "highest salary", "most attractive coworkers", or "did I flip heads?"

But I'm a compulsive optimizer. Naturally I agonized for two weeks over which offer I should. I was hoping one offer would be clearly better than the other, but both the corporate cultures and salary packages were similar. I analyzed every angle I could think of, from the commute times to little things my interviewers had said. I called friends I knew and got as much inside information about the places. I made risk estimates for the companies based on their respective industries. Talk about overkill! My opinion changed on a daily basis, but after two weeks I finally made my final decision.

This is, of course, the exact opposite of what good AI should do.

In most systems where a computer must analyze some data and make a decision, there's a problem when two choices are very similar. Sometimes the system can get caught in an oscillation state where working on either choice makes the other one better. For example, a Quake 3 bot might decide to pick up armor, but the act of moving towards the armor makes it decide that picking up some health is a better choice. So the bot instead moves towards the health, and on the way decides the armor is better. The bot can end up in a situation of indecision where it picks up neither of the two items, and clearly this is the worst of the three choices.

Item pickup isn't the only situation where this occurs. Target selection and weapon selection can have the same problems. A bot can try to chase down one target but on the way decide it would rather aim at a different one and waste valuable time aiming at neither. Or in theory a bot can switch to one weapon and change its range based on the new choice, but by the time it gets in position it decides another weapon is useful. If you've never seen a BrainWorks bot do this, that's great! I've worked hard to remove these indecisions from the AI, but it's neigh impossible to make AI that works in all situations. There are two basic tactics you can use to solve indecision oscillations, each with their own costs.

Most of the time I give the scoring estimate a bonus of between 10% and 25% for keeping the same decision. In other words, the AI won't change its mind unless the new option is at least 25% better than the old. The higher this factor is, the fewer oscillations will occur. However, the risk is that an option that's genuinely 8% better will be missed, even if it wouldn't cause an indecision loop. Additionally, it's rare but still possible that even with a 25% factor, the bot can get stuck in indecision. This method is best used for situations where the estimated value of one option over another doesn't change that rapidly. This is how general item pickup oscillations are handled, as well as enemy selection.

When a small buffer isn't sufficient, the other option is to prevent the bot from changing its mind until it completes its selection, or at least for a reasonably long duration (such as half a minute). This is guaranteed to solve the problem. But there are two drawbacks. Not only will the bot be more likely to make suboptimal decisions, but it could get caught in a situation where it's very predictable. As such, it's best to apply this tactic only when absolutely necessary and ideally when the action can be completed quickly.

This method is used in item pickup for items the bot is very nearby. If a bot can pickup an item in less than one second, it immediately overrides all other item pickups and grabs it no matter how useful some other item may be. It turns out that even with a bonus factor for keeping the same item selection, bots could still get stuck in indecision loops when they were very close to an item of low value. That's because the estimated points per second is the ratio of two very small numbers, so the estimation has a large margin of error. No bonus factor could stop the bot from switching between the bad nearby item and the good item that was far away. The code forces the bot to spend half second to grab the nearby item, thereby preventing the loop from occurring.

Regarding my new job, I was leaning towards the place that offered slightly less money but seemed to have higher job satisfaction. In the end they decided to beat the salary offered by the other company, so it was a no-brainer to pick the job that has both higher pay and happier workers.

Scouting for Trouble

One of the funny things about designing artificial intelligence is that you run into all kinds of problems you never even considered. For example, I spent a lot of time designing algorithms to handle realistic aiming. But what does the bot do when it's not trying to line up a shot? It has to look at something, even if there's no one else in the area. That's because the bot must either hear or see an enemy to become aware of it and start shooting back. Scouting around for likely areas an enemy might be is the best thing the bot can do when, well, it has nothing else to do.

The issue is that a bot doesn't visualize the game the same way a human does. Technically stated, bots don't visualize anything at all. While we as humans see a brightly rendered three dimensional area, that's too much information for the artificial intelligence to process in a short amount of time. A Quake 3 bot actually uses something similar to sonar to "visualize" the world. It sends out a instantaneous pulse in a perfectly straight line and figures out where that pulse hits something. It can even tell what kind of thing the pulse hits, like a wall or some fleshy target. However, there isn't enough time to send pulses in all directions, so the bot needs to carefully spend its allotment. If it spends too much time figuring out what's nearby, it won't have enough time to think about other important things (such as where to run).

Getting back to the problem at hand, think about how a human player would decide where to look for new targets. In a hallway the solution is obvious-- look in both directions the hallway runs, but not towards the walls. In a large room you look towards the other side of the room, in doorways, and archways. As humans we quickly process the two dimensional rendering of the area and mentally create a three dimensional depth map. Then we look into the areas with the furthest line of sight, for the most part. That's because new targets come from far away.

While it's very hard for a bot to identify which areas are doors and hallways using its "sonar", it can at least determine which areas of the room are far away. To do this, the bot just sends out eight pulses around itself and finds the three that have furthest line-of-sight. It does some additional checking to find the ground below that point, so when the bot is on a ramp or staircase, it actually looks down the direction of the stairs. And then the bot randomly picks one of the three furthest directions. It's a pretty simple solution, and it does a great job of making sure the bot scouts in the areas where opponents will appear.

Now the interesting thing to note is that no human opponent ever actually sees the bot doing this for more than a fraction of a second. Once you're in the bot's field of view, it will start aiming at you rather than looking for more targets. But a human would notice the results of this code, in that the bots notice them and start responding in a realistic manner. An algorithm that no human actually sees is obviously less important than one they interact with all the time. But that's not the same thing as unimportant, and the relative simplicity of the scouting code reflects this.

Project Planning

As BrainWorks is a complete rewrite of the Quake 3 AI code, it was a relatively daunting project that required a lot of effort in many areas. First person shooter AI requires aiming and firing decisions (not the same thing!), item pickup, weapon selection, movement, visual and auditory awareness, and high level strategy to give a non-exhaustive list. Simply put, there's a lot of things to write and they all have to work together. When the project is this large, it's hard to even know where to begin. How do you prioritize such a wide list of features when, quite frankly, everything is required?

For BrainWorks, the secret is that I didn't start with plans of an entire rewrite. Rather my objective was to get the AI in a state where it was usable for another mod I had written, Art of War. (You can visit the Art of War website if you like, but it's horribly out of date.) The mod was a game designed similar to Natural Selection, although it was released years before Natural Selection even started development. Conceptually, think of each player in Art of War as a single unit in a real time strategy game. You can collect gold for your team's bank, then spend the gold to build buildings that unlock new units and powers. You can change to an assault based unit to attack the enemy base, be a defender, or play an assault support class. There are four unique factions in the game, each with their own basic play style and variations. Basically everyone who played it really enjoyed it. Some day I'll go into more detail about the design of it and post the source code for those who are into that kind of thing.

So if Art of War is so great, why have you never heard of it before?

Well if each player is on a team where you can pick one of four kinds of units, the game is well designed if a good strategy involves one player of each unit type and poorly designed if everyone wants to play the same kind of unit. As this was a well designed game, that means you are required to have 4 players per team to even get a feel for what the game play was like. With four players per side, that's a minimum of 8 players to even start a game. You could play with less, but a 2v2 match just wasn't that exciting. The mod required a strong player base to ramp up in popularity and it simply never got it.

The whole reason I started writing AI was to address this problem. If you could get three players on a server and have five bots filling in the gaps, you could get a semblance of a good game together while more people joined. Once enough people had joined the server, the bots would get kicked and people could play a real game. And so begins the tale of BrainWorks...

When I first started BrainWorks, I didn't plan on doing a full rewrite. I just wanted some additional high level tactical decisions for Art of War. After looking at the initial code, however, I realized a better starting point was doing AI for the basic Quake 3 game, where you just need to run around and shoot things. My objective at this point was just better weapon selection.

Of course, having written better weapon selection code, I realized it was all meaningless unless the bots could pick up useful weapons, so I had to rework the item pickup code. And since weapon selection was based on statistical tracking of weapon accuracies, the selection code wasn't very useful until the bots had reasonable aiming, not inhumanly good aim.

Around six months into the project I took a step back and realized that none of the work would be that helpful unless I redid the entire code based. At this point I had a decision. I could have just thrown up my hands and walked away, declaring it too much work. But I decided to press on with a full rewrite.

I wish I could say I had some grand plan of how to prioritize everything in the project, but it started as a small project. So my plan of attack for solving this involved writing everything in chronological order. For example, bots must scan their surroundings for new enemies before deciding who they should shoot at. They need to pick an enemy before aiming their weapon, and they need to aim before firing. I tried to focus on the earlier steps first because that would define the exact information the bot could use to make its next decision. If you write it backwards, you'll often end up assuming you have data that you can't actually get in the format you need. When you have a truly large project, its often best just to dive in and start working on something, however. The sooner you get your feet wet, the sooner you'll have a feel for all the complexities and intricacies that need to be accounted for.

Mind Candy

If you haven't worked in the game industry, you might think of a game designer job as a dream job. You get to create your own toys and then play with them! Well it certainly has its moments, but it's important to realize that the job is still a job. There will always be boring parts that need to be done. And more often than not, the job involves creating your own toys and then figuring out why the won't work or aren't fun. In fact, it's a lot like every other programming job except you get to make toys rather than spreadsheets, word processors, or websites. While it's fun to design toys for a living, there's a pretty high cost to it. And I don't mean the "there's boring stuff too" cost that comes with every job. Here is the cost:

The more time you spend designing a game, the harder it is to enjoy playing it.

The problem is that over time, you have to think of the game in terms of its individual core mechanics. But the wonder and enjoyment comes from how those mechanics are organized into something greater. No game has infinite replayability. There always comes a point where you think, "That was fun, but I won't ever want to play this game again." A game might have 10 hours of good fun, or even 100 or 1000. But no game is fun after 10,000 hours. Why is that? Why can't games be fun forever?

Games are mind candy.

They are a thought treat. Personally I approach games as puzzles to solve. The very act of thinking is fun, at least for my mind. The challenge is learning how the make the best move in each novel situation the game presents. As you play a game more, you learn it better. And eventually you simply recognize the situation and can play on autopilot. At that point the game ceases to be fun because it is no longer challenging. It can still be entertaining to execute the actions, and in playing I can encounter a few new challenges, but in general the candy of the game no longer tastes sweet to my mind.

Unfortunately, my job as a game designer isn't done until I've solved the game and determined there are no degenerate solutions. The harder it is to determine a game's optimal solution, the more replayability it has. (Note that replayability just defines how long it takes for the game to cease being fun. It has nothing to do with whether or not the game is fun in the first place, or to what extent.) If it's too easy to solve the game due to an obvious dominant strategy, no one will have fun playing the game once they figure it out and all my design work is for nothing.

While I'm not an author, composer, or movie producer, I suspect this problem extends to all jobs designing entertainment. A really satisfying book is one where all the plot pieces fit together nicely and there are no obvious plot holes. The characters need to feel genuine and you need to understand how their development as people natural extends from their personalities and experiences. No author can convincingly do that without really getting into the minds and lives of these fictional people. To build the depth of a good book, the author must understand that depth before the final editing pass is done and the book is sent to print. They will never have the enjoyment and wonder of watching how the lives of their characters unfold. They sacrifice that potential joy so that other people can experience it too. It's just part of the creative process.

For my part, I find I don't enjoy playing first person shooters as much as I did many years ago. Maybe after a few years break I'll enjoy them again, but that's just the personal price I paid so that other people get more enjoyment from the games they play.