Background Review

Luckily, navigation is quite a common task. There are numerous existing projects on the topic, and plenty of experience to benefit from. In addition, because this is only the second part of the book, we would expect it to be a relatively straightforward task anyway:

• Robotics systems perceive their surroundings thanks to sonar or laser sensors, giving obstacles around them a sense of distance. Generally, this information is used directly—although more elaborate robots interpret the information with complex algorithms—to determine where to go next. Finally, navigation is performed by sending the chosen movement commands to the motors controlling the wheels (for instance, robots such as AuRA, Rhino, and SSS).

• Artificial life defines and studies the behavior of living synthetic creatures, usually as part of a group. A relatively important part of A-Life is movement, especially collective movement (for instance, flocking birds and swarming wasps). Some of this research—known as steering behavior [Reynolds89]—is applicable to individual creatures. Each agent is given artificial sensors, which can detect obstacles within range. This information is combined with the steering force using mathematical equations, and applied as linear and angular velocities.

• Other academic projects are too diverse to summarize briefly. Although most other academic (that is, not robotics) projects focus on 2D navigation as a practical application of an abstract algorithm (for instance, reinforcement problems), or small modular components of the whole system are developed (for instance, vision or localization).

• Game AI has historically simplified navigation as much as possible to reduce the computational overheads. This has involved precomputing the data structures necessary and passing them to the AI in the most optimal format possible. The position of each nonplayer character (NPC) can thereby be updated directly at runtime to achieve the illusion of conscious movement.

In the right circumstances, all of these approaches "work." It's just a matter of deciding which best matches our situation. Some of these methods disagree with our definition of embodiment listed in Chapter 2, "The Design of Intelligence." We'll need to decide which are convenient to develop game AI, and which have to be adapted.