CGF Terrain Specific AI - Terrain analysis

---

Last update: November 09, 1999, by William. List of changes here .

Terrain analysis is one part of the terrain understanding designed for and used by CGF (the teams of bots autonomously fighting in the Action Quake2 world employing realistic tactics, for those new to CGF).

As far as I know, similar techniques haven't been used in any other 3D first person tactical (real-time) game. The results obtained are promising and the approach and techniques seem to apply to most 3D fps games.

This page is organized as follows:

1. ranking locations for tactical value and human terrain understanding
2. static analysis: an off-line activity
3. analyzing terrain in terms of high level (terrain) concepts
4. the input: Quake2 terrain (and waypoints)
5. my CGF approach
6. running example and interpreting the graphs
7. intrinsic tactical value of a location
8. influence tactical value of a location
9. related work: influence maps
10. conclusions
11. change log

(Terrain analysis by CGF bots visualized by means of some staged shots with faked 'projected' slides. The AQ2 map, featuring conference facilities, is p1_lightbeam by Tristan 'P' Temple).

1. Ranking locations for tactical value and human terrain reasoning

• "this rooftop controls a good part of the street, and is hard to access"
• "this bright side of the map is almost without cover"
• "this ladder is in full view"
• "this room is hard to control because it can be accessed from four different directions"

2. Ranking locations: an 'off-line' activity saving CPU cycles for other AI

Though less accurate than considering the terrain with knowledge about specific threats and their positions, this (static) ranking of tactical locations is very important because:

• it enables the AI to take up good positions in advance of the engagement
• the analysis can be done in advance (thus before the combat starts) and leaves more CPU available for dynamic combat tactics
  this is especially important in games where the CPU power is too limited to do much terrain analysis during combat - the static terrain analysis results, obtained off-line, then are a worthwhile substitute

3. Terrain analysis using (higher level) concepts to reason about terrain

It's not the actual content of this document that matters here. Instead, it is important that the document is able to do 'generic' reasoning about terrain because it uses a number of (higher level) concepts:

• 'fields of fire'
• 'fields of observation'
• 'movement (restrictions)'
• 'cover/concealment'

• bottlenecks
• camping spots
• door handling

(Images above show (left) fields of fire explained in the FM90-10, (center) the CGF waypoints in the Urban map, and (right) a team spread out at urban using the tactical values computed).

4. Terrain input: CGF, Quake2 terrain and waypoints

Because Quake2 does not provide terrain information in a useful data structure via its API, CGF bases its terrain view on waypoints. Since waypoints reflect the reachable parts of the terrain (thus solely those locations where threats are likely to appear), and (in CGF) more or less overlay a uniform grid over the terrain, this abstraction of the real terrain works quite well.

More importantly, thinking about terrain in terms of waypoints (instead of brushes) also reduces the amount of data to be interpreted during terrain analysis.

The downside to this approach is the occurrence of sampling errors - not all relevant locations might be covered by waypoints.

The alternate approach, attractive because of its fully automated character, would be to parse the Q2 map itself (.bsp or .map files), and derive reachable areas from there. This area based approach was first implemented by the Q2 Gladiator bot, and Quake3Arena has been announced to utilize a similar mechanism.

As I understand the area based approach, the areas derived from the map file reflect the brush complexity - additional work would be required to obtain a uniform sized overlay structure.

5. CGF concepts for terrain analysis

The terrain ranking is constructed by assessing the tactical value of each location and ordering the locations accordingly. In game, that information is typically used queries like:

select the 10 tactically most promising positions
that overlook the tower window and
that are within 3 seconds distance
from the current position

• the location's intrinsic tactical value
• the location's potential influence on surrounding locations and v.v.

6. The example, and understanding the results

Urban is map covered by some 750 waypoints, in a pretty uniform grid.

To be able to 'read' the results, I've projected values in a terrain graph on the top view of the Urban map. Note that the terrain graph itself shows some artifacts near the edges.

To assist you in understanding the graphs, here are graphs representing the:

• height at each location (lighter color is higher) [center image below]
• darkness at lower locations (including streets and medium height buildings)
  (lighter color is less dark) [right image below]

In all graphs, blue areas represent unaccessible terrain. Notice that you can recognize the higher buildings and lower streets (in the center image), and (that in the right image) the open streets in general are brightly lit whereas various other locations provide better locations to hide.

All results were obtained from a (comma separated) spreadsheet file generated by CGF from within Quake2, which then were visualized and converted to .gif images in MsExcel using VB for Applications.
Computing the tactical values for each location takes about 2 minutes (Celeron300A @ 300Mhz).

7. The intrinsic tactual value of a location

Examples of intrinsic properties for a location are:

• amount of light at location (darkness reduces chances of being observed)
• movement speed at location (slow movement, such as in water, when required to crouch, etc. makes combat from this position less effective)
• movement restrictions (caused by the presence of ladders, doors, elevators, moving platforms) make combat from this location less effective

The center image above provides a light/dark map for the higher areas of the Urban map (lighter color is less dark). Only a few locations at the rooftops seem to provide some 'shelter' from observation.

The right image above shows differences in movement freedom at locations: locations featuring small ledges, ladders and doors hamper movement and therefor attack capabilities at those locations (much freedom is green via yellow to red is little freedom). You probably can recognize the single door in Urban (center), the ladders (right center side of the map, and left center) and the ledge (south center of the map). All other red areas are artifacts of the terrain graph.

CGF takes these intrinsic properties into account when assessing the value of a location, and combines them with the influence properties of that location. This is illustrated in the next section.

8. The 'influence' tactual value of a location

A single 'influence' is the 'interaction' of the location with one of its surrounding locations (typically, only those with a line-of-sight, a line-of-fire, or close-by locations). The 'influence' should be regarded as an abstraction of the key (combat) interactions players can have: weapon firing, observation, taking cover, and maneuvering.

Because the influence describes the relation between two locations, the influence has a direction. Since a human (or artificial) player cannot cover all directions at once (but typically focuses on one direction, occasionally checking another direction), I've chosen not to simply add up all influences originating from a location.

Instead, all influences are considered per sector (a 'slice of pie' of the surroundings). Then, the 90 degrees arc covering the highest influence is considered the primary axis. A secondary axis (being at least 90 degrees away from the primary axis) is computed as well. Finally, the influences are combined using a weighted sum with those influences along the primary or secondary axis receiving more weight.

This use of sectors is introduced to have locations that oversee a number of nodes in primarily one or two directions (center image) rank higher than other locations that oversee a similar number of nodes distributed over all directions. The former locations typically make for a good camping or sniping location, and the use of sectors (right image above) assist in assigning these locations their proper value.

Examples of influence characteristics for a location (with respect to surrounding locations) are:

• access advantage
  (the location is hard to reach from the locations it overlooks)
• cover advantage
  (the location has nearby cover available for threats from the locations it overlooks)
• visibility advantage
  (the location overlooks many other locations that would expose a threat because of sufficient lighting there)
• 'no cover' advantage
  (the location overlooks many locations where a threat cannot quickly move into cover as seen from this location)
• coverage of slow movement spots
  (the location overlooks (within useful weapon range) locations that cause threats to move slower or in a predictable way, such as ladders, doors, etc.)
• likeliness of being surprised
  (the number of access routes available to threats that bring the threat nearby without being observed)
• height advantage
  (it is easier to spot threats below you than to spot threats above you)

The center image above provides a large (green) - medium (yellow) - little (red) map expressing the 'hard to access advantage'. In the green areas the attacker typically overlooks (and can fire into) many locations from where a threat has to go a long way to to reach the attacker. In red areas, this advantage is absent - the attacker can be easily reached from most location he is able to cover.
Especially the locations surrounding the AQ2 sign (northwest) are very promising in this aspect, as is the rooftop of the lower north building (actually, it cannot be accessed from the lower parts of the maps). The high (sniper) towers in the center and right side of the map provide advantages as well.
Note that the input data for the graph contains more detail - there are many (subtle) differences within the individual locations in the red areas.

The right image above shows the amount of cover an attacking locations has with respect to the locations it is able to attack (for the high areas in the Urban map) (green is better than yellow than red). Simultaneous sufficient cover and influence over many locations can be found near the AQ2 sign (northwest), near the sniper room (northeast), near the top ladder position (northeast) and around the air vents and Coke sign (southeast resp. south).

The center image above illustrates the chances of being 'surprised' by an attacker (small (green) - medium (yellow) - large (red) chance). The chances of being surprised decrease when a location is able to overlook many of its nearby locations - threats thus have fewer ways to approach the location without being observed.

Many of the indoor locations (the stairs center north, the area around the door (center), the narrow alleys in the center as well as the small sniper room (south east) aren't very strong positions from this perspective.

The image to the right illustrates the average height advantage a location has (advantage (green) - neutral (yellow) - disadvantage (red)). The height advantage is largest when a large proportion of the locations observed is significantly lower than the location itself. Attractive locations typically can be found near the edges of high roofs, whereas many of the central street locations are at a disadvantage.

The center and right images below illustrate aggregated influence values for the lower resp. higher areas at Urban.

9. Related Work: Influence Maps

Influence mapping is technique frequently employed in hex-based (turn-based) war games. In general, those games feature large scale units (batallions, divisions), and the influence of terrain, when compared with influence of these units, is limited: some locations might be time-consuming to enter, reduce visibility, or reduce the damage taken.
The influence of those combat units typically is large: the presence of a unit often prohibits movement in neighboring hexes, and initial unsuspected contact may stall the planned progress of a unit.

Influence mapping, primarily dealing with 'projected' force by combat units, makes a lot of sense in those games. However, in its form as described above, it does not work for 3D action games.

Current 3D action games typically display small unit combat. The influence exercised by the small units or individuals typically is far smaller than the role of terrain. Populated with many obstacles, the terrain blocks and directs movement to large extent. Even a thin wall can block the threat originating from an enemy unit.

The world simulated by the game is typically is smaller than the world of turn-based games. As a consequence, in 3D action games, weapon ranges are as large as the terrain dimensions, and cover thus becomes very important. Unlike the hex based games, the presence of a small unit at a location does not really interdict nearby movements of opposing units - rushing past a defender is easily done.

Though traditional influence maps don't work well for 3D action games, because of the big role of terrain in the 3D action 'tactics', it is well possible and useful to determine the strong and weak positions influence map solely based on the terrain.
A very important aspect is also that off-line (a priori) computation of the terrain position rankings is possible - this saves a good deal all-important CPU cycles for the run-time AI.

Mark Eversons also has coined up ideas of AI players obtaining a 'functional grasp of geography', including focus on the (more important) road and rail junctions and mountain passes.

10. Conclusions

The images above show the 'total' (intrinsic and influence combined) tactical values for each location in the lower (center image) and higher (right image) areas of Urban. As far as my actual experience goes, most of the essential locations have been issued high values.

Without this understanding of the terrain, exact manual positioning (as is done for Quake2 and Half-Life) of teams would be required. CGF, instead, is able to have the teams autonomously position themselves.

More importantly, these waypoint based algorithms can easily be extended (read: improved and corrected) by taking into account (location) based recordings of 'combat' events: movements along locations, occupation of locations, (successful) attacks from locations. Using that kind of information in the algorithm enables some learning from and some 'adaptability' towards successful tactics employed by the player.

This use of dynamic combat information has been implemented (for CGF 0.80) and will be discussed in an upcoming document.

11. CGF Terrain Static Ranking Change Log