The Environment and Space
Let's focus on the game world where movement takes place. The environment is planned by the designer, created with modeling tools by the graphics artist, and updated and displayed within the game by the programmer's engine. A wide variety of technologies can be used along this production pipeline, but it is mostly inconsequential from the AI's perspective.
What's important is the information contained implicitly within the world. Most environments are split into two components: structure and detail. After discussing them separately, this section looks at how they combine to define space.
Sum of Its Parts
The information about the environment provided to the players can be conceptually divided into two main components: structure and detail. This is more than just a theory, because most game engines strongly distinguish the two for efficiency reasons. The physics simulation handles the structure, and the detail is for graphics rendering. In the real world, of course, the boundaries between them are much more debatable, so we should consider ourselves lucky to be dealing with computer games!
There is one important omission to notice from the preceding definitions. What happens to living creatures and other mobile entities? Although not necessarily created with the same tools as the rest of the game world, they too are arguably part of the environment. We could argue that game characters have properties of both the structure and the detail. However, some developers (and robotics researchers) believe that they should be treated separately, as an entirely different set. Generally in games, the set of living creatures ends up being forced into one category or the other (for instance, players are detail that's ignored during movement, or players are part of the environment structure that movement takes into account).
Essentially, the problem is about combining these three components of the environment together to create an understanding of space. We want to understand space as best possible to develop high-quality movement. Considering moving creatures as either detail or structure can have a negative effect on the movement, especially when the problem has not been identified beforehand.
Fortunately, we have the luxury of being able to decide how to handle living creatures as we design the AI. In a deathmatch, for example, it's fine to ignore the other animats for movement; they can be blown up with a rocket if they get in the way! In cooperative mode, however, a separate category is needed for nonplayer characters (NPCs) so that they can ask each other to move. Finally, other players can be considered as obstacles in large crowds.
Fundamentally, the game world describes space. As the shape of the environment, the structure plays an important role; as far as the physics engine is concerned, all the movement is defined by the structure. However, both human players and AI characters cannot always match this physical knowledge of space; it will be extremely difficult, if not impossible, for them to understand the environment perfectly.
In some cases, when a simple world is stored in an explicit fashion (for instance, a 2D grid), understanding it can be a manageable task. As the design becomes more complex, many elements combine to define the environment in an intricate fashion (for example, a realistic 3D world). However, no matter how well the environment is defined or how accurate its physical rules are, it is not necessarily as clear to players and NPC.
For all intents and purposes, space is an abstract concept that cannot be fully understood. Different techniques will have varying degrees of precision, but all will be flawed. Don't see this as a problem, just accept it and embrace it; perfection is overrated! This lesson was learned in robotics thanks to the wave of nouvelle AI robots.
After space has been figured out, it's possible to determine which parts are free space and which can be considered solid. This implicitly defines all movement: what is possible and what isn't. Only then can intelligent movement be considered.