It's free to join Gamasutra!|Have a question? Want to know who runs this site? Here you go.|Targeting the game development market with your product or service? Get info on advertising here.||For altering your contact information or changing email subscription preferences.
Registered members can log in here.Back to th e home page.    
Latest game industry news.|Articles about game development.||||Searchable databases of game development companies, products, and web sites.|Purchase stuff from Gamasutra, Game Developer magazine, the GDC, and more.
Search articles, jobs, buyers guide, and more.

By William van der Sterren
Gamasutra
[Author's Bio]
September 12, 2001

Terrain Reasoning

Waypoint Graphs

Analyzing Terrain and Adapting Tactics

Other Terrain Reasoning Applications

Printer Friendly Version


This feature originally appeared in the Game Developers Conference 2001 Proceedings.

 

Letters to the Editor:
Write a letter
View all letters

Letters to the Editor:
Write a letter
View all letters


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

______________________________________________________

[Back to] Terrain Reasoning


join | contact us | advertise | write | my profile
news | features | contract work | jobs | resumes | product guide | store



Copyright © 2001 CMP Media LLC. All rights reserved.
privacy policy | terms of service