Bot Navigation: Design Philosophy
Alex J. Champandard
Alex J. Champandard
The game environment is the virtual world that you interact with. You can perceive it by sounds, joystick force-feedback, and the on-screen display. A.I. bots also have to deal with this environment, but they are not yet able of using visual perception: they must use the internal representation of the map to base their movement upon.
Currently, in-game agents are usually allowed information from any part of this environment, no matter how far away they are. This allows them to be omnipresent, which simplifies the design of the A.I. and spawns tougher opponents. Very soon, gamers will not tolerate such blatant cheating from the bots. Subjective perception, whereby only the part of the environment that is visible by the agent can be accessed, will become a standard. Even if this can be faked using global perception, an elegant solutions for subjective spatial awareness would shine through, creating a more convincing opponent.
For all games which are played on the scale of a normal person or animal, there are often two different kinds of environments: indoor levels and outdoor landscapes. This distinction has prevailed for a couple years, as very few games seamlessly blended the two. Things are now changing: outdoor scenes are no longer just simple height-fields, and one engine can usually handle the entire décor (potentially using slightly different rendering data-structures and algorithms). The navigation must, therefore, be able to handle both these types of environments without glitches.
A conventional environment can almost always be divided into two components.
Figure 1: Birds eye view of the Quake 2 level called Malediction (grdm1), revealing its overall structure.
This is the overall definition of the terrain, whether it's the inside of a building, or an outdoor landscape. It is a very simplistic representation of the environment, but contains all the important features: room connections, vague distance information, gross sub-area definitions, positioning. You could plan a military operation simply from this information.
In practice, for real-time games, this information is stored in the level structure on the hard disk: it can be extracted from the brushes used to design and create indoor levels.
Figure 2: Close-up screenshot of floor detail within the same level. The player can collide against it, but rarely pays attention to it.
This is made up of all the items, small objects, and other brushes the player can collide against. Plant pots, ornamental stones, and furniture often clutter everyday paths. Together with these more or less permanent features, temporary clutter may regularly impede movement: cleaning apparatus, fallen decorations, and even other resident wild-life.
In most games nowadays, a significant part of the detail is not taken into account during the collision detection. This will change in the near future, as the processing power dedicated to physics increases.
Before I lose you in further ponderings about bot navigation and spatial awareness in general, establishing a standard terminology seems like a good idea.
Remember you can visit the Message Store to discuss this essay. Comments are always welcome!. There are already replies in the thread, why not join in?