An old friend of mine was a former army drill sergeant. I was surprised to learn this, as he didn't fit the stereotypical personality at all. Thoughtful and friendly are not the first words that come to mind when you hear the phrase, "Drill Instructor". This former job came up when someone mentioned they were leaving for basic training (aka. "Boot Camp") in six weeks, and my friend immediately told the guy, "Start doing push-ups now." Apparently you do so many push-ups in boot camp that it's never to early to get in shape, and the better physical shape you are in, the easier it goes. Not that boot camp is ever easy.
Intrigued by learning that my friend had been a drill sergeant, I asked him about basic training from the sergeant's perspective. According to him, the most important thing you can do to survive boot camp is to be practically invisible. You need to blend into the crowd and never even be noticed by the drill instructors. The instructor's job is to spot recruits that don't fix the mix and make them fit in.
"The instructors don't hate you," he said. "It's just that nothing you've learned in civilian life is of any use in the army, and they need to beat that crap out of you."
The typical civilian doesn't take order very well. Generally orders are considered "loose guidelines". They're likely to ignore orders outright, only do the parts they want, or do things differently based on their preferences. That kind of attitude is acceptable (although not optimal) in real world business settings. In the army though, the lives of thousands if not millions of people are at stake, and defying orders can have large consequences that the enlisted units can't possibly be aware of.
If your army company controls a bridge, but your officer tells you to march one mile down a river and swim across at midnight, then that's exactly what you do. The option of taking the bridge across and walking down the other shore shouldn't even enter your mind, even though your officer never told you why he gave you your orders. Soldiers who disobey orders either get killed or get other people killed. That's why the number one objective of a drill instructor is to teach privates to follow orders.
There's a similar issue for AI in team play video games. If your team contains some bots or possibly "side kicks", the game designers generally give you some way to give them orders. No game designer considers making your minions sometimes ignore orders, of course. Rather, the problem is this: Just as most people aren't used to following order precisely, they also aren't used to giving them precisely. There's a whole set of problems determining what the player even intends when they say something as simple as, "go back through the door". Which door? How far back? So much of language depends on context and it's just hard to determining meaning from a small snippet of words.
The second issue is that no matter what order a player gives, they almost never want the bot to perform that task indefinitely and precisely. When you say "go guard the red armor", it's just until they spot an enemy. When the bot spots an enemy, you don't want it to let them get away if that enemy leaves the red armor spot. The bot should stop guarding and start attacking in that case. Similarly, if no one goes by the red armor for a while, the bot should stop guarding and find something useful to do. When the player says, "Guard the red armor", the bot needs to understand that as "Guard the red armor until you see an enemy or until you've been there for three minutes".
This is the basic strategy BrainWorks uses for its message processing, which is largely unchanged from the original Quake 3 message code. It does the best job to determine what the player means and treats that instruction as a relatively important high level task. But it's still just a guideline. Stuff like combat takes precedence, and the bot will forget about the order after a few minutes. Ironically the bots need to function like civilians rather than soldiers, or the person playing the game wouldn't be happy with how the bots would follow orders.
Showing posts with label scheduling. Show all posts
Showing posts with label scheduling. Show all posts
Monday, November 24, 2008
Monday, August 11, 2008
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.
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.
Monday, July 7, 2008
A Simple Solution
As the story ended last week, I had uncovered a very strange bug in BrainWorks. There was up to a 10% accuracy difference between the first bot added to the game and the last bot. No one guessed the correct cause, but this one from cyrri was the closest:
The real culprit was the mechanism through which the server processes client commands. The server processes each human player's inputs as soon as it receives them (as fast as 3 milliseconds for a human), but the inputs for bots are processed exactly once every 50 milliseconds. In turn, each bot handles its attacks and then moves. Then the next bot is processed, and they do this in the order they were added to the game. See the problem?
Every bot made its decisions based on where the other bots were currently located at the end of the last server frame, but only the first bot will actually attack against targets in those positions. By the time the last bot aims, every target had already spent 50 milliseconds moving. The first bot had 0 ms of latency and the last bot had 50 ms. Now 50 milliseconds isn't too bad, except the last bot was playing as if its latency was 0. That's why it missed around 10% more.
Since one of my original project constraints was that nothing would change in the server code, that meant that at least some bots had to play with 50 milliseconds of latency. There were no changes I could make to reduce this problem. So the solution was to add latency to all the bots. I wrote a feature into the AI core that tracked the positions of all players in the game for the last half second worth of updates or so, for all bots and all humans. Then if a bot needed to know where a target was, it looked up the properly lagged position and did basic extrapolation to guess where the target would be at the exact moment of attack.
Implementing this system gave all the bots very similar accuracies (within 1% due to the issue cyrri pointed out). But now the problem was that all bots the same accuracy as the worst bot, when they should have had the accuracy of the best bot. It turned out this "basic extrapolation" wasn't good enough. The original Quake 3 AI code used linear trajectories to estimate where a target would end up, nothing more sophisticated than that. So if a bot aimed at a target running to the bottom of a staircase, the bot would keep aiming up into the ground for a while, even though a human would know the target would move straight.
I tried some slightly more advanced solutions, doing basic collision checking against walls, but that didn't solve the problem of running down a ledge. I eventually concluded that humans have a learned sense of physics they take into account, and the bots would need that same sense if they were to play like humans. Solving this problem was both straightforward and time consuming.
I made an exact duplicate of the entire physics engine, modified it for prediction, and placed it in the AI code.
Every detail needed to be modeled-- friction, gravity, climbing up and down ledges, movement into and out of water. Even the force of gravity acting on a player on an inclined ledge. Everything had to be duplicated so that the bots could get that extra 10% accuracy in a human-like manner. It was not easy, and I learned far more than I wanted to know about modeling physics in a 3D environment. But in the end, it was worth it to see bots that could aim like humans.
bots occupy client slots in the same order as they are added.This actually does happen, but it only accounts for a 1% to 2% accuracy change between the first and last bots. Also, this value increases as bot accuracy increases, since it's more likely that two bots will be lined up for a good shot at the same time.
in the very rare cases of two clients killing a third one simultaneously, it is allways the one with the lower slot id that gets the frag, becuase his usercommands are processed first. the other one gets a missed shot.
The real culprit was the mechanism through which the server processes client commands. The server processes each human player's inputs as soon as it receives them (as fast as 3 milliseconds for a human), but the inputs for bots are processed exactly once every 50 milliseconds. In turn, each bot handles its attacks and then moves. Then the next bot is processed, and they do this in the order they were added to the game. See the problem?
Every bot made its decisions based on where the other bots were currently located at the end of the last server frame, but only the first bot will actually attack against targets in those positions. By the time the last bot aims, every target had already spent 50 milliseconds moving. The first bot had 0 ms of latency and the last bot had 50 ms. Now 50 milliseconds isn't too bad, except the last bot was playing as if its latency was 0. That's why it missed around 10% more.
Since one of my original project constraints was that nothing would change in the server code, that meant that at least some bots had to play with 50 milliseconds of latency. There were no changes I could make to reduce this problem. So the solution was to add latency to all the bots. I wrote a feature into the AI core that tracked the positions of all players in the game for the last half second worth of updates or so, for all bots and all humans. Then if a bot needed to know where a target was, it looked up the properly lagged position and did basic extrapolation to guess where the target would be at the exact moment of attack.
Implementing this system gave all the bots very similar accuracies (within 1% due to the issue cyrri pointed out). But now the problem was that all bots the same accuracy as the worst bot, when they should have had the accuracy of the best bot. It turned out this "basic extrapolation" wasn't good enough. The original Quake 3 AI code used linear trajectories to estimate where a target would end up, nothing more sophisticated than that. So if a bot aimed at a target running to the bottom of a staircase, the bot would keep aiming up into the ground for a while, even though a human would know the target would move straight.
I tried some slightly more advanced solutions, doing basic collision checking against walls, but that didn't solve the problem of running down a ledge. I eventually concluded that humans have a learned sense of physics they take into account, and the bots would need that same sense if they were to play like humans. Solving this problem was both straightforward and time consuming.
I made an exact duplicate of the entire physics engine, modified it for prediction, and placed it in the AI code.
Every detail needed to be modeled-- friction, gravity, climbing up and down ledges, movement into and out of water. Even the force of gravity acting on a player on an inclined ledge. Everything had to be duplicated so that the bots could get that extra 10% accuracy in a human-like manner. It was not easy, and I learned far more than I wanted to know about modeling physics in a 3D environment. But in the end, it was worth it to see bots that could aim like humans.
Friday, January 18, 2008
Taking Action
"Okay," I think. "Artificial intelligence. Just have to figure out what I'd do and teach a computer to do the same. Sounds easy enough. Only one problem..."
"Where do I start?"
There are so many decisions to be made when playing any sport or action game, many of them subconscious, and all the actions need to be executed at just the right time to feel natural. For example, imagine an opponent just enters your field of view. It will takes between .1 and .3 seconds for the typical human to notice and react to this. So if the bot only scans for new opponents twice a second, it could take up to half a second to respond, much worse than even a poor human player. And there are more problems than this: With only two scans per second, sometimes the bot happen to scan right after a player stepped into view, reacting much faster than .1 seconds to them. To solve this problem, bots need to scan constantly, but have their own simulated "reaction" delay to spotting the target.
On the other end of the spectrum, algorithms like deciding which item to pickup are genuinely hard. Humans can spend a second or more of thought on the problem, and if a bot recomputed item pickup as often as it rescanned, the computer run noticeably slower. Bad things will happen if scanning ran as infrequently as item pickup, or if item pickup ran as often as scanning. Every kind of thought that a bot might do needs to be properly scheduled. It can't think about the problem too much or too little.
To solve this problem, I wrote the ai_action.c file, which administrates all the thought a bot does. That code decides when certain engines run and when they get wait until later. At the core of the design is a model analogous to human thought and action. I classified all human responses into one of three categories:
Each bot action is associated with one of these states. Anything that a human would spend a lot of time thinking about is automatically conscious. Chances are, the algorithm to do that thought will strain the computer, so it should be run as little as possible. These actions are labeled "Logical" and run whenever the logical processing should run (just a few times per second, or even less frequently).
Reflexive actions are things the mind doesn't think about unless something about the world changes. You might gasp and hold your breath if you suddenly smell something foul, for example, but otherwise you'd breath normally. So all bot actions that depends on the world state are labeled "Reflexive". These run every time the server updates anything on the level (once every 50 milliseconds, or 0.05 seconds).
Last, there are a handful of maintenance things that simply must run as often as possible so the data can be handled immediately, such as checking whether the bot died. These have no label because there's never a time you don't need to run them.
Sometimes there are dependencies between different sections of thought. For example, a bot needs to aim before it shoots, and it must select a target before before aiming. And before that, the bot must first scan for eligible targets. So if firing is a reflexive action, then everything it depends on must also be reflexive (or even faster).
This isn't a particularly novel algorithm-- operating system have used more advanced schedulers for years. But it's rare to see this level of design applied to artificial intelligence in games, and that's really a shame. There are whole categories of problems that are much easier to solve once you have a proper scheduler to organize everything the AI needs to do.
"Where do I start?"
There are so many decisions to be made when playing any sport or action game, many of them subconscious, and all the actions need to be executed at just the right time to feel natural. For example, imagine an opponent just enters your field of view. It will takes between .1 and .3 seconds for the typical human to notice and react to this. So if the bot only scans for new opponents twice a second, it could take up to half a second to respond, much worse than even a poor human player. And there are more problems than this: With only two scans per second, sometimes the bot happen to scan right after a player stepped into view, reacting much faster than .1 seconds to them. To solve this problem, bots need to scan constantly, but have their own simulated "reaction" delay to spotting the target.
On the other end of the spectrum, algorithms like deciding which item to pickup are genuinely hard. Humans can spend a second or more of thought on the problem, and if a bot recomputed item pickup as often as it rescanned, the computer run noticeably slower. Bad things will happen if scanning ran as infrequently as item pickup, or if item pickup ran as often as scanning. Every kind of thought that a bot might do needs to be properly scheduled. It can't think about the problem too much or too little.
To solve this problem, I wrote the ai_action.c file, which administrates all the thought a bot does. That code decides when certain engines run and when they get wait until later. At the core of the design is a model analogous to human thought and action. I classified all human responses into one of three categories:
- Conscious
- Reflexive
- Subconscious
Each bot action is associated with one of these states. Anything that a human would spend a lot of time thinking about is automatically conscious. Chances are, the algorithm to do that thought will strain the computer, so it should be run as little as possible. These actions are labeled "Logical" and run whenever the logical processing should run (just a few times per second, or even less frequently).
Reflexive actions are things the mind doesn't think about unless something about the world changes. You might gasp and hold your breath if you suddenly smell something foul, for example, but otherwise you'd breath normally. So all bot actions that depends on the world state are labeled "Reflexive". These run every time the server updates anything on the level (once every 50 milliseconds, or 0.05 seconds).
Last, there are a handful of maintenance things that simply must run as often as possible so the data can be handled immediately, such as checking whether the bot died. These have no label because there's never a time you don't need to run them.
Sometimes there are dependencies between different sections of thought. For example, a bot needs to aim before it shoots, and it must select a target before before aiming. And before that, the bot must first scan for eligible targets. So if firing is a reflexive action, then everything it depends on must also be reflexive (or even faster).
This isn't a particularly novel algorithm-- operating system have used more advanced schedulers for years. But it's rare to see this level of design applied to artificial intelligence in games, and that's really a shame. There are whole categories of problems that are much easier to solve once you have a proper scheduler to organize everything the AI needs to do.
Subscribe to:
Posts (Atom)