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:
  • Conscious
  • Reflexive
  • Subconscious
A conscious action is something you choose to do, like going for a walk. You do it because your brain engages the activity. Reflexive actions are those that you don't think about doing, but you can bring to your consciousness and alter it. For example, breathing is reflexive. You just do it, but you can hold your breath if you want. A subconscious action is something you literally have no control over-- it just happens. Your heart beat is a good example. No matter how much muscular control you have, you cannot stop your heart from beating.

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.

No comments: