Monday, August 18, 2008

Scouting for Trouble

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

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

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

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

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

No comments: