Have you ever gotten directions that included phrases like, "When you see the giant viking statue, go straight and curve left" or "If you pass a third Starbucks, you've gone too far"? People don't always give directions based on street names; sometimes the street names are largely irrelevant. Here in New England, if the street sign is even posted at all, it might not be readable until too late. Directions like "turn left at the Rite-Way Mart" are often easier to follow than "turn left at old route 293".
Believe it or not, bots have the same problem. We might conceptualize a level as rooms, hallways, and open areas, but these places have no names. Humans generally name these areas after a recognizable landmark. In Quake 3, that usually means items. You'd never tell a teammate, "I'm at (540, -973, 108)", which is how the computer records your position. But you would say, "I'm near the rocket launcher".
One requirement of item pickup that I glossed over in a previous post was this: Bots need to know how likely they are to encounter an enemy in a general area. That implies bots need a concept of what an area is. They need to think of enemies being "near the rocket launcher" not "at (540, -973, 108)".
Bots need to think of enemy location in human terms, not computer terms.
The obvious method of approaching this problem is to divide the level into regions, with each region being defined by one item. Technically each region is "the area of space that is closer to this item than any other item". Once you have the level conceptually divided into "near the red armor" and "near the plasma gun", whenever the bot sees an enemy it can say, "Ah, that player is near the red armor, not the plasma gun. I'm more likely to find enemies if I head for the red armor as well." Now whether or not it wants to enemies is a different question, one answered by item pickup. But at least it can track meaningful data about what other players on the level are likely to do.
However, just because it's possible to find out what item a player is nearest doesn't mean it's particularly fast or easy for the computer to determine that. The AI obviously can't spend half a second to calculate data it needs to save 10 times a second. It's okay to spend a bunch of time when the level loads to calculate the best set of regions, but once these calculations are done, bots need to do the location to region calculation very quickly.
I researched a number of different options, but eventually settled on the octree, briefly mentioned in a previous post. Conceptually an octree is a way to layout some number of points in 3-space. In BrainWorks, the item region octree contains the location of all items on the level. Rather than rewrite what has already been written on the subject, I recommend reading the wikipedia article on quadtrees (the two dimensional equivalent of octrees).
For the 99% of readers who don't care how to implement an octree, I'll just say that a well balanced octree will generally let you find which item is closest to any input location very quickly. The run time is O(log8 N) time, where N is the number of items on the level. That means that finding the nearest item on a level with 64 items will take twice as long as a level with 8 items, and a level with 512 items will take 3 times as long as a level with 8 items. Since even the largest levels rarely have more than 100 items, this calculation is really fast, and that in turn frees up more processor time to think about different AI problems. The bot makes a richer impression to the human playing the game and hopefully the player has more fun too. Sometimes making a game fun to play involves implementing mind-numbingly boring data structures, but the fun just wouldn't be there if they were missing.
Monday, March 10, 2008
Monday, March 3, 2008
Good Enough For Government Work
This might be a surprise if you've read my post on pragmatism, The Attitude of the Knife, but I'm actually an idealist. I don't want things to be good enough; I want them to be perfect, or at least as perfect as pragmatically possible. I use the attitude of the knife to temper my idealism.
Of course, there is tension between idealism and pragmatism when encountering very difficult problems. I don't just mean, "you'll have to be really smart to solve this problem." I mean, "it's mathematically impossible to solve this problem using the computer you have access to." The idealist wants 100% and the pragmatist wants 99% or even just 90%.
The classic example of a mathematically difficult problem is the Traveling Salesman Problem. If you're not familiar with the problem, it works like this: Suppose you have a salesman who wants to visit every city in a certain area exactly once, and he knows the distance between each pair of cities. What's the minimum distance he'll have to travel to visit all the cities and how do you determine it?
Mathematicians have been studying this problem for almost 200 years now. It turns out that determining the perfect solution is really, really hard, but it's possible. Worst case you can just check every possible ordering of cities. That worst case is unbelievably bad, however. If the salesman had 30 cities to visit and a computer could test one trillion options per second (current no single computer exists that is this fast), testing all these options would take much longer than the current age of the universe. Most of the studying mathematicians have done on this problem revolves around ways to get a "pretty good" answer without spending billions of years to do so.
I say I'm an idealist, which means I want things to be perfect. But I'm also ruthlessly pragmatic. These contrasting ideals intersect on the definition of perfect. If it takes 1 trillion years to find the traveling salesman route that takes 38 days but 1 hour to find the route that takes 42 days, then the 38 day solution isn't perfect. It's really 1 trillion years plus 38 days, which is definitively worse than 42 days, 1 hour. A "perfect" solution must take into account the constraints surrounding the problem and not just the problem itself. The mathematically optimal solution is not the perfect solution expressly because it's not practical enough to use.
What does this have to do with Artificial Intelligence, and specifically item pickup? Deciding what items to pickup is very similar to solving the traveling salesman problem, and that's bad news for me as the AI designer! If there are 20 items on a level, a bot wants to pickup between 0 and 20 different items on the way to its final destination. That's similar to a traveling salesman wanting to visit exactly 20 different cities. And since BrainWorks bots can't spend several trillion years to decide what items they're going to pickup, their item pickup code cuts a lot of corners to get a pretty good solution in a reasonable amount of time. This isn't the mathematically optimal solution, but it is a better choice overall.
Here are some of the tricks BrainWorks uses to reduce the computation time:
It's rare that thinking 10 item pickups ahead would really help the bot more than the first two or three choices. And usually the bot doesn't want to travel halfway across the map to pickup some random item. Only the nearby items are worth considering. For the one or two items that really might be that good, the bot specifically notes these items and includes them in the list of possible pickups, no matter how far away they might be. And as it turns out, these results are still "very good". Often the theoretically best solution isn't the best for the problem at hand. If you idealize the results and not the method, being idealistic involves selecting the most pragmatic solution.
Of course, there is tension between idealism and pragmatism when encountering very difficult problems. I don't just mean, "you'll have to be really smart to solve this problem." I mean, "it's mathematically impossible to solve this problem using the computer you have access to." The idealist wants 100% and the pragmatist wants 99% or even just 90%.
The classic example of a mathematically difficult problem is the Traveling Salesman Problem. If you're not familiar with the problem, it works like this: Suppose you have a salesman who wants to visit every city in a certain area exactly once, and he knows the distance between each pair of cities. What's the minimum distance he'll have to travel to visit all the cities and how do you determine it?
Mathematicians have been studying this problem for almost 200 years now. It turns out that determining the perfect solution is really, really hard, but it's possible. Worst case you can just check every possible ordering of cities. That worst case is unbelievably bad, however. If the salesman had 30 cities to visit and a computer could test one trillion options per second (current no single computer exists that is this fast), testing all these options would take much longer than the current age of the universe. Most of the studying mathematicians have done on this problem revolves around ways to get a "pretty good" answer without spending billions of years to do so.
I say I'm an idealist, which means I want things to be perfect. But I'm also ruthlessly pragmatic. These contrasting ideals intersect on the definition of perfect. If it takes 1 trillion years to find the traveling salesman route that takes 38 days but 1 hour to find the route that takes 42 days, then the 38 day solution isn't perfect. It's really 1 trillion years plus 38 days, which is definitively worse than 42 days, 1 hour. A "perfect" solution must take into account the constraints surrounding the problem and not just the problem itself. The mathematically optimal solution is not the perfect solution expressly because it's not practical enough to use.
What does this have to do with Artificial Intelligence, and specifically item pickup? Deciding what items to pickup is very similar to solving the traveling salesman problem, and that's bad news for me as the AI designer! If there are 20 items on a level, a bot wants to pickup between 0 and 20 different items on the way to its final destination. That's similar to a traveling salesman wanting to visit exactly 20 different cities. And since BrainWorks bots can't spend several trillion years to decide what items they're going to pickup, their item pickup code cuts a lot of corners to get a pretty good solution in a reasonable amount of time. This isn't the mathematically optimal solution, but it is a better choice overall.
Here are some of the tricks BrainWorks uses to reduce the computation time:
- Nearby items are grouped into a single cluster. Bots consider picking up the entire cluster at once. This reduces the effective number of things to consider.
- Bots do not consider picking up more than four items at once before going to their final goal.
- Bots only consider picking up the dozen or so items that are relatively near their current position, or not far off the path to their destination.
- When the bot is very near an item (less than a second away), it automatically picks it up rather than doing a full computation.
It's rare that thinking 10 item pickups ahead would really help the bot more than the first two or three choices. And usually the bot doesn't want to travel halfway across the map to pickup some random item. Only the nearby items are worth considering. For the one or two items that really might be that good, the bot specifically notes these items and includes them in the list of possible pickups, no matter how far away they might be. And as it turns out, these results are still "very good". Often the theoretically best solution isn't the best for the problem at hand. If you idealize the results and not the method, being idealistic involves selecting the most pragmatic solution.
Monday, February 25, 2008
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:
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:
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.
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)
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
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.
Monday, February 18, 2008
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.
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.
Tuesday, February 12, 2008
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 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.
Wednesday, February 6, 2008
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.
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.
Friday, February 1, 2008
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:
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.
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
- 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)
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.
Subscribe to:
Posts (Atom)