First Person Shooter AI Architecture

Preliminary Description and Basic Concepts

Introduction

The information in this article is adapted from a chapter in the recently published book, "AI Game Programming Wisdom", published 2002. It was written by Paul Tozour, and entitled, "First-Person Shooter AI Archtecture". The author prefaces the article with this statement:

This article describes a generic AI architecture for the typical first-person shooter ("FPS") game such as any of the titles associated with the Quake, Unreal, or Half-Life engines.

Overview:

Artificial Intelligence (AI) in First Person Shooter (FPS) game architectures tends be organized and controlled as seperate, individual agents, rather than coordinated teams that are synchronized to the same strategy playbook. The FPS Artificial Intelligence architecture is organized into a hierarchy with four major integrated components: Behavior, Movement, Animation, and Combat.

Principal Game AI Components:

The movement component is tasked with determining how the character should move in the game world. The movement AI is what makes the character avoid obstacles, follow navigation system nodes, and find paths through the complex environments to reach its destination. The movement subsystem never determines where to move, only how to do so. It simply receives commands from other components telling it where to move, and it is responsible for making sure the character moves to that point in an appropriate manner.

The animation component is responsible for controlling the game bot’s skeletal articulation and display appearance during gameplay. Its major role is selecting, parameterizing, and playing character animation sequences. It is also responsible for generating animations that cannot be played from pre-assembled animation sequences. Since we can’t tell in advance in what direction a character will face in a given scene, we need a method of integrated control over the real-time animation to ensure that the character behaves correctly.

The combat component is assigned the role of assessing the character’s current tactical situation, selecting tactics in combat, aiming and firing at opponents, deciding when to pick up a new weapon, and so on. Since combat is the core gameplay dynamic in most FPS games, the performance of this subsystem will be crucial to the player’s perception of the AI.

The behavior component is the integrating framework that determines the character’s current goal, orders, state, and immediate destination, and communicates with the other subsystems to coordinate physical motion towards a determined staging area. It is the highest-level AI subsystem and sits on top of all the other subsystems.

Pathfinding and the Bot Navigation System:

Fundamental to the movement AI system is the pathfinding component. This system is responsible for finding a Bot path from any coordinate location in the level to any other. Given a starting point, a state designation, and a goal or destination, it will find a series of waypoints that comprise an optimal path to some intermediate destination. It is possible that it will report that no path can be found, or will generate an apparent error in its repertoire of simulated human motion. The game AI pathfinder in Unreal Tournament uses a pre-computed data structure for guiding movement. This is a complex algorithm-controlled assemblage of linked lists, NavigationPoints, and Binary Space Partitioning (BSP) collision data. The FPS game world is relatively static, so it makes sense to pre-generate a database that is highly optimized for performing fast pathfinding in a particular section of the game world. At runtime, the pathfinding database is initialized and parameterized. The performance of this directed navigation system search is highly correlated with how appropriately the pathfinding database is optimized.

Realistic Interaction with Moving Objects and the Physics System:

The obvious weakness with the global pathfinding system is that it does not correctly interact with dynamic obstacles. Practical solutions to the problem of efficient in-game agent avoidance of moving obstacles are built on communication between the physics system and the local pathfinding system. Since dynamic obstacles can be moved at any time, the AI needs to continually query the physics system for the presence of dynamic obstacles in any area it intends to move through. This designated the local pathfinding system, and is an essential quality of any object capable of three dimensional movement in the level.

A local pathfinder does not replace a global pathfinder; the two are integrated and each subsystem is optimized for a different part of the problem. The local pathfinding system is built on top of the global pathfinder. When an AI needs to move from point A to point B, its movement AI first queries the global pathfinding system, and if it’s successful, the global pathfinder will return an ordered list of points that constitute a path from A to B. The AI can then use the global path as a guideline, and use the local pathfinding system to find a path to each successive waypoint in that global path, avoiding any obstacles that it might happen to interact with along the way.

Fundamentally, a local pathfinder needs to be based on a search algorithm which constrains possible initial directions to the immediate area near the origin of the search. This technique will ensure that the optimal path is found if such a path exists. A good way to do this is to perform sampling (for example, querying the physics system for the presence of obstacles) using a fixed size grid oriented toward the destination point. However, keep in mind that sampling can be computationally expensive if it’s performed too often, so it’s very important to take steps to minimize the amount of sampling that the system needs to perform in any given local search.

The Agent Movement Control Component:

The movement AI acts as the client of all the other parts of the AI; that is, it is a subsystem that performs arbitrary tasks assigned to it by higher-level components. Those tasks are issued in the form of discrete movement commands, such as, “move to point (X,Y,Z)”, “move to object B”, “turn to face point (X,Y,Z)”, or “stop moving”.

The movement AI will be executing exactly one of those movement commands at any given moment. We describe the movement component as the object that “owns” the current movement command.

Once we have done this, we can design the appropriate algorithms to execute the movement commands into the individual movement command objects themselves. A command such as, “move to (X,Y,Z)”, for example, will be responsible for using the global and local pathfinding systems to find and execute a path to (X,Y,Z), and making the appropriate engine calls to ensure that the character moves along the specified path. If no path is available, or when the AI entity reaches the end of its path, the movement command reports back to the movement controller so that it can be garbage-collected.

This technique is also useful for handling different types of movement. Different types of movement commands can handle tasks such as walking, running, swimming, and dying, with appropriate parameters to determine the AI agent’s acceleration, movement range, turn rate, animations, and other movement characteristics.

The Combat Control Component:

When an AI initiates combat, control for the majority of its behaviors is transferred to a combat control component. The combat controller is responsible for all combat-related tasks, such as selecting an opponent, selecting a weapon, maneuvering, firing, and searching for additional weapons and ammo.

The most difficult part of the combat problem is determining how to intelligently assess the current situation, and select and execute an appropriate tactic in response.

The challenge comes from the extraordinary difficulty of getting an AI entity to understand the significance of the spatial configuration of any given area. Any human can glance at his current surroundings and immediately form an assessment of the space.

Go on to the next part: FPS AI Architecture, Continued