Game Bots and Movement

In most computer games, navigation is almost never achieved by sensing and interpreting the environment. As the world is virtual, it can be stored entirely in the computer's memory. Typically, an algorithm processes the world to extract the structural information from it. This can be done by dropping waypoints (as in Figure 6.1) or processing polygons. Once prepared, the bot receives compact knowledge of the terrain directly before the game starts.

Figure 6.1. Description of the environment using a set of waypoints, known as a terrain model. These are generally placed manually by the designers during the development of the game.

Because the bot is part of the simulation of the world, its position is known perfectly. The AI code will know this position, too. This makes it possible for the AI to decide where to go next. For this reason, bots are particular good at global movement, such as crossing the entire terrain. Given the knowledge of the environment, standard pathfinding algorithms, such as A*, are particularly efficient.

The A* Planning Algorithm

A* is a planning algorithm that searches through the terrain to find the shortest path to a single target. As a deliberative technique, A* is not discussed directly in this book. The web site at http://AiGameDev.com/ has a list of online resources freely available on the subject.

However, bots do not "sense" the world like humans or animals. This goes a long way toward explaining the common problems with game AI, such as bots bumping into walls, getting stuck in doorways, or ignoring dynamic obstacles. The problem is that the bots rely only on preprocessed knowledge of the environment. First, the terrain model is often based on erroneous assumptions, and second, it does not remain up-to-date in dynamic environments.