|
Features

Terrain
Reasoning for 3D Action Games
Other Terrain Reasoning
Applications
Terrain reasoning has many other applications, for example dealing with
dynamic situations. The following threat prediction case illustrates the
use of waypoint graph based reasoning for dynamic situations.
Predicting Out-of-sight Threats
Image the following scenario (with an AI actor, on defense, having spotted
a threat):
Upon seeing the AI actor, the threat turns and moves to the right, away
from the window and out of sight. The AI actor stays alert...
To be a useful team member or challenging opponent, the AI should understand
where threats are likely to appear and where threats are likely to move
to. Though it is often infeasible to fully model the presumed motives
and behavior of threats, it is possible to do a good job using the terrain
representation.
The following two-step, waypoint graph based approach works quite well.
First predict the threat's position using:
- the threat's
last observed position and movement;
- the viable
paths in the threat's surroundings;
- the (absence
of) lines-of-sight to the threat's presumed position.
Typically,
the threat's position is extrapolated, under the assumption that the threat
continues in the same direction and with the same speed. The resulting
position is tested against both the paths feasible, and the line-of-sight.
For example, the threat will not move through walls, and in the waypoint
graph, the absence of path indicates that. Similarly, if the AI does not
see the threat at a predicted location that is in full view, the extrapolation
is known to be incorrect. In these cases, the presumed threat position
can be corrected to reflect a (more) likely location, for example the
last valid extrapolated location.
Second, the AI needs to decide where to aim for. If the AI cannot fire
through obstacles, it solely has to consider the visible locations in
the immediate surroundings of the presumed threat position. One simple
way to pick a likely location for the threat to reappear (and thus a location
to aim for), is to construct the shortest path from the presumed threat
position to the AI actor. The first location on that path that is within
view of the AI, is a good location to aim for. The shorter the time the
threat needs to travel to that location, the more likely
If the threat's likely reappear location is quite close to the threat's
presumed location, the AI might consider to employ suppression fire or
launch a rocket towards that location.
Terrain Reasoning for Dynamic Situations
A large number of dynamic situations can be interpreted efficiently using
terrain reasoning, including locating nearby cover, planning concealed
paths, moving in formation, assessment of enemy positions, etc.
Even
non-trivial reasoning, such as determining the value of spending a hand
grenade to attack or flush out a threat, can be done efficiently provided
the data structures are designed to support such a query (Sterren).
Implementing
Terrain Reasoning
Terrain reasoning means reasoning about tens of thousands of polygons,
and millions of inter-waypoint relations. Implementing terrain reasoning
thus is a matter of carefully analyzing the AI requirements, the resource
constraints, making trade-offs, and executing some experiments.
This section briefly discusses the most important trade-offs to be made:
- waypoint
resolution, accuracy and performance
- CPU load,
lookup tables, and memory consumption
- Dynamics
and pre-processing
Waypoint
Resolution, Accuracy and Performance
Waypoints (and similar AI navigation aids) represent the accessible game
terrain. Many action games have their AI use as few waypoints as possible,
because:
- fewer
waypoints mean less work to the level designer (to place them);
- fewer
waypoints mean faster pathfinding and smaller shortest path lookup tables
However,
fewer waypoints mean also a coarser representation of the game terrain:
each waypoint (on average) describes a larger part of the terrain, and
the line-of-sight and travel time relations becomes less accurate.
The waypoint density required to sufficiently describe the terrain depends
on the game design and AI needs. For games featuring lethal weapons ("single
shot kills"), slow movement, many obstacles, and lack of respawns,
the terrain representation should describe as many covered and concealed
spots. This typically translates to a high waypoint density. In games
featuring respawns, fast movement, and weaker weapons, a low waypoint
density suffices, since terrain details are less important (but the tactics
still may be terrain driven, because of power-up and objectives positions).
Note that algorithm such as the one used for identifying good sniping
spots assumes a more or less uniform distribution of waypoints across
the terrain.
CPU Load, Lookup Tables, and Memory Consumption
Some terrain-related properties such as paths, and a bouncing grenade
trajectory take considerable time to compute. Other properties such as
lines-of-sight are inspected so frequently that in total they consume
a good amount of CPU.
Now consider the following simple AI query to locate nearby cover from
a number of threats:
Given three threats that have line of fire to the AI actor, is there a
spot within 3 seconds distance that provides cover?
To determine the result, the AI needs to construct numerous paths and
perform a good number of ray traces (taking into account different actor
postures, such as sitting and prone).
Today's CPUs and game engines handle in the order of 3,000 A* path searches
per second, and 50,000 trace lines per second, depending on level size
and geometry complexity. Given an AI budget of 10 percent, and 10 AI ticks
per second, the AI is allowed some 15 path searches and 250 trace lines
per tick, for all its actors (typically 4 to 30 of them), and as its sole
activity.
Storing part of the computations and looking up the (intermediate) results
typically is three orders of magnitude faster for path finding, and two
orders of magnitude faster for trace lines. Using lookup tables thus frees
up CPU time for more advanced AI or faster graphics.
However, lookup tables may consume a good amount of memory. Especially
for waypoint-pair relations, such as paths and line-of-sight, the straightforward
matrix implementation has O(N x N) space complexity. For N
³
1000, these lookup tables really start consuming megabytes.
For path lookup, a hierarchical or multi-level path structure in combination
with a cache for the most recently referred to paths (and travel times)
offers a smaller footprint while still being very efficient.
The average waypoint sees only a small subset of all other waypoints.
In that case, the line-of-sight matrix can be flattened: per waypoint,
record solely the waypoints actually seen by that waypoint, and the waypoints
able to see that waypoint.
Another concept that helps selecting the right content for look up tables
is the so-called "time horizon". Most of the AI decisions, especially
under the resource demanding "combat" conditions, have a limited
scope. The game world is so dynamic that planning beyond a horizon of
one to three seconds (depending on the game) has little value.
The AI queries therefor limit themselves to the surroundings accessible
within the time horizon (and upon arriving there, they will decide again).
A per waypoint look up table that contains the info for all waypoints
within that time horizon will be very efficient without being large.
Dynamics and Pre-Processing
Pre-processing the terrain can significantly off-load the in-game AI (as
is the case with pre-computing sniping spots). However, the game terrain
is not completely static. Dynamic environment such as doors, vehicles,
elevators, destructible walls, will change the paths, lines-of-sight,
etc.
Dynamic environment does not necessarily invalidate pre-processed terrain
information. Whether a distant door is open or closed does not really
affect the value of a sniping spot. However, a nearby door being closed
typically does invalidate a sniping spot (and is checked for in the sniping
scenario).
Apart from checking for changes in the environment, the AI can also try
to patch the pre-computed terrain description. The lines-of-sight affected
by a door can be pre-computed, and the changes can be applied on the fly
when the door changes state. Another option is to have a background threat
slowly update the information.
Implementing Reinforcement Learning
Waypoint based reinforcement learning is easy to implement. Just capture
the AI or player activity local to the waypoint, determine whether it
is positive or negative feedback for the intended task, and adjust the
waypoint value accordingly.
To create an AI that adapts quickly and tactically to the player's tricks,
pay some attention to issues like attaching more significance to feedback
from player activity than from AI activity because the player will be
more creative, and have a better tactical understanding of the game and
terrain. The player activity should be valued more than the combined AI
activities.
This policy also prevents the AI from honing into its own flaws (for example,
the AI repeatedly and unsuccessfully assaulting an area because the area
is known for the many frags scored there).
P eriodically, level all values to be more responsive to changes in tactics.
After re-computing sniping spots using game play data, the player might
see changes in the AI sniping and adapt his tactics. To be more responsive
to changes in the player's tactics, the aggregated game play activity
values should be leveled. Using a function such as log or sqrt, this can
be done while preserving the ordering.
Visualization and Feedback
The waypoint based terrain reasoning uses an approximation of the terrain,
and heuristics to interpret that approximation. Consequently, implementing
this kind of terrain reasoning requires tuning.
To efficiently develop and tune a terrain reasoning algorithm, the algorithm
is best created incrementally, and using feedback from visualizing its
results. Luckily, it is easy to visualize and interpret terrain and terrain
properties. Preferably, the results are visualized as an overlay in the
rendered 3D world. For tuning, an export facility to comma separated files
and a spread sheet package are recommended.
Summary
Terrain reasoning is the AI's ability to include terrain and related concepts
such cover, travel time, areas in its plans, decisions, actions and communication.
Notably in action games where AI and terrain play a big role, effective
terrain reasoning results in a richer game AI. Terrain reasoning involves
a terrain representation, and algorithms to create, manipulate and query
that representation. Waypoint graphs, until now primarily used for navigation,
are demonstrated to be a powerful means for terrain reasoning.
Many action game tactics use the terrain. These tactics then can be related
to properties of the waypoint graph. With formulas to express these waypoint
graph properties, the tactical concepts such as sniping spots, ambush
locations, and strongholds can be computed and identified by the AI.
The reasoning about tactical concepts is easily extended to include player
and AI game behavior local to the waypoint. This game activity data enables
the AI to adapt its tactics to actual game play. Adaptation occurs because
of re-enforcement learning, and because of improved understanding of the
role that various locations play in the game.
The waypoint based terrain reasoning can be used in-game, for example
to interpret threat positions and select the appropriate tactics. This
kind of terrain reasoning can also be used to pre-process terrain in order
to off-load and assist the run-time AI.
Acknowledgements
Jan Paul van Waveren (id software), Doug Reece (SAIC), and the numerous
talented bot developers in the Quake, Half-Life, and Unreal bot communities
for valuable discussions.
The Action Quake II community for their help in turning that "mod"
into a custom designed tactics testbed for AI experiments.
References
and Suggested Reading
Campbell, C.E., McCulley, G., "Terrain Reasoning Challenges in the
CCTT Dynamic Environment" in the 5th Annual Conference on AI, Simulation,
and Planning in High Autonomy Systems, IEEE, 1994
Laird, J.E., "It knows what you're going to do: Adding anticipation
to a Quakebot" in AAAI 2001 Spring Symposium Series: Artificial Intelligence
and Interactive Entertainment, March 2000, AAAI Technical Report SS-00-02
Pottinger, D.C., "Terrain Analysis in Realtime Strategy Games"
in Proceedings of Computer Game Developer Conference, 2000
Reece, D., Krauss, M., Dumanoir, P., "Tactical Movement Planning
for Individual Combatants", in Proceedings of the 9th Conference
on Computer Generated Forces and Behavioral Representation, 2000
Reich, A.J., "An Efficient Representation of Spatial Data For Terrain
Reasoning By Computer Generated Forces", in Proceedings of the ELECSIM95,
SCS, 1995
Snook, Greg, "Simplified 3D Movement and Pathfinding Using Navigation
Meshes" in Game Programming Gems I, Mark DeLoura (ed.), Charles
River Media, 2000
van der Sterren, W, AI for Tactical Grenade Handling, http://www.cgf?ai.com/docs/grenadehandling.pdf,
2000
______________________________________________________
|