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!

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.

A Peculiar Bug

In my postmortem of BrainWorks, I mentioned one of the big things I did right was creating a powerful debugging infrastructure directly in the code base itself. In general, it's easiest to test and maintain software when as much of the testing is fully automated as possible. Now that's easy for a program like Excel, where you can create a battery of sheets with strange formulas that might cause errors, and then confirm that the numbers all match up. If the software creates something measurable, it can usually be automatically tested.

Naturally, this means automated testing is far harder for Artificial Intelligence than other areas of computer science. The goal of BrainWorks is "bots that appear to be human". How do you teach a computer to measure whether a player's decisions appear to be human? That's tantamount to writing a program that can judge a Turing test, which is as hard as passing one. Fully automated testing of the AI isn't an option, but there are certainly things that can assist testing. All you have to do is identify an measurable component and check if it meets the human expectations.

For aiming, BrainWorks already measures accuracies with each weapon in each combat situation. The bot knows that it scores perhaps 35% with the shotgun against an enemy a few feet away and 5% against an enemy a hundred feet away. But it doesn't know if those numbers are reasonable until I tell it what to expect. The vast majority of the testing I did with aiming involved forcing a bot to use a particular weapon, making it play for hours, and then checking if the numbers "looked good". Generally they didn't, and I had to figure out why they weren't matching my expectations. In this testing process, I uncovered a variety of interesting bugs. Large sections of the aiming algorithm were rewritten around a dozen times trying to get things right. I found several errors in how accuracy was even being measured. But the strangest error I encountered was something totally unexpected.

I was monitoring Railgun accuracy as way of testing the overall ability to aim. It's an instant hit weapon with no spread and infinite range, so it's a great initial test case. I loaded up eight bots on a wide open level and forced them all to have exactly the same skill, then ran them for several hours. Curiously when I checked the results, their accuracies weren't all the same. The best had an accuracy around 75% and the worst was around 65%. Moreover, their scores reflected this.

I activated some mechanics in the system to modify aiming behavior. First I turned off all errors, so the aiming should be flawless, like watching a human who doesn't make mistakes. Their accuracies were still stratified. Then I completely circumvented the entire aiming code, forcing the bots to aim directly where they wanted to. That gave the bots what most people think of as an aim hacking, so their aim should have been perfect. But even still, testing showed that some bots would get higher accuracies than others. Sure, there was one bot that would score 99.9% accuracy, but another bot would only score 97%. When a bot has perfect information and reflexes, it should not miss one in 30 shots.

Then one day I noticed that all eight bots were sorted in alphabetical order. The bot with the first name had the highest score (and accuracy) down to the bot with the last name having the lowest score. Since the odds of this are 1 in 8! = 40,320, I considered this curious but still possibly a coincidence. So I tested it again, and each time the bots were sorted alphabetically! That was the final clue I needed to isolate this bug.

The script I used to start testing adds the bots in alphabetical order, so I tried swapping the order different bots were added and their accuracies changed as a result. Each time, the most accurate bot was added to the game first and the least accurate bot was added last. For some reason, the internal numbering of bots was affecting their aim.

So why exactly was this the case? I'll let you puzzle over it for the week. Next week I'll explain why this happened and the extreme amount of work that went into solving it.

My Biggest Programming Fear

I have encountered some very strange bugs in my programming career. And most of them have been in BrainWorks, being by far the most complicated piece of software I've ever written. One of the worst involved a build that only crashed when run on someone else's system. On my system it was fine, but it would crash on my friend's system. It wouldn't crash right away, mind you. Sometimes it would take up to two minutes, so even testing to see if the bug was fixed took time. Oh, and his computer was in London while mine was in Los Angeles. Not exactly the easiest problem to solve.

I solved it by compiling in debug flags that would turn on or off entire sections of code and then had him run it. "Okay, load bots but turn off all movement, scanning, and aiming. Does it crash now? What about when Item Pickup is turned off?" Through the course of four builds that gradually narrowed in on particular blocks of code, we eventually found the offending bug.

(If you're curious what caused it, an uninitialized value was improperly being treated as an address, crashing the program whenever it was accessed. Because his machine's memory layout was different from mine, it would occasionally access invalid memory and the operating system would kill the program. For whatever reason, the uninitialized values that showed up on my system always happened to refer to memory BrainWorks was allowed to access, so it never crashed for me.)

It took about eight hours to do, but once you've solved a bug like that, you feel cabable of tackling any bug. Bugs bother me, but they don't frighten me. Know what my biggest programming fear is?

0 total errors

Any time I've spent over two hours working on a particular feature and attempt to rebuild the code base, I expect to see at least one error. I'm a good programmer, but that doesn't mean I'm perfect. I'm a good programmer because I know I'm not perfect. Good programmers assume they will make mistakes-- that's why they add all those safety error checks. If some other piece of code does the wrong thing, their error checks will contain it.

Last week I spent four hours tracking down the issues with bots overvaluing the shotgun. The problem was that the estimation of fire frequency wasn't precise enough. I spent another three hours analyzing the similarities between estimating the chance of hitting with a weapon (hits divided by attacks) and the chance of firing a weapon (attacks divided by potential attacks) and designing functionality that merged the two concepts. Actually writing the code took another 2 hours. Nine hours total including changes that could totally break the AI's ability to even attack, and here I am looking at the results from my very first recompile:

0 total errors

I haven't run it yet, but I'm terrified. Zero errors on the first try? That never happens. That's not even supposed to happen. Odds are the code I wrote has an error somewhere; I just don't know where.

At any rate, I plan to test it this upcoming week and get a new release out this weekend. Hope you enjoy it.

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.

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.