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

Analyzing Terrain and Adapting Tactics

Terrain reasoning based on waypoint graphs, its value, and the concepts introduced here are best explained via an example.

This section discusses a concrete case, 'picking good sniping spots', in detail and illustrates how to translate tactics such as "sniping" to waypoint graph properties, how to create an algorithm that turns these properties into a waypoint sniping suitability score, how to improve the pre-computed sniping scores with sniping performance feedback collected in-game (thus learning), and how to adapt the algorithm to include game play experience in its tactical considerations (thus adapting to game tactics).

Problem: Picking Good Sniping Spots
Assume the following scenario (in a tactical 3D first person action game):

The player points to a building some one hundred meters in front of him, and summons the nearby AI actor: "get into position to snipe that building". The AI establishes the direction to the building.

The AI determines all waypoints that are within 2 seconds distance of him. He quickly ranks these spots for "sniping" suitability towards the target building. For the most promising spots, he checks if a clear line of fire is available.

Once a candidate spot has been found, the AI checks if it good enough for sniping purposes. The AI then reports back to the player whether he is able to execute the instruction. If so, he moves into position.

This example focuses on computing the waypoint's suitability for sniping.

The Terrain
A rather simple and small level serves to illustrate the terrain reasoning (whereas the reasoning can deal with any terrain size). The level consists of:

  • Two buildings on opposite ends of the terrain, each having two windows with a view to the bridge, and a rotating door
  • A creek separating the two sides
  • A bridge, providing a fast way to cross the creek, and offering some cover (half-height walls)
  • Two stairs, enabling players to leave the creek. Both stairs provide some cover (half-height walls)
  • Two full-height walls, providing additional cover.

In this example, assume that the AI sniper is in the northwest corner of the level, and is instructed to snipe towards the building in the northeast.



A simple, symmetric level, to demonstrate reasoning about sniping


The terrain is covered by some odd 480 waypoints.

Sniping Tactics and Good Sniping Spots
The suitability of a position for sniping depends on many qualities. Many of these qualities are easily identified when trying to describe the differences between an obviously good and an obviously bad sniping position.

The following qualities make for a good sniper spot in a tactical shooter game:
A. The sniper is inconspicuous at the spot
B. The sniper can overlook many distant locations from the spot
C. The spot is hard to reach from the overlooked locations
D. In the direct surroundings of the spot, the sniper can find cover from threats at overlooked locations
E. The overlooked locations do not provide nearby cover from observation and attack by the sniper (at his spot)
F. The spot overlooks many key locations (such as doors, windows)
G. Threats cannot easily approach the spot without being observed
H. The spot has focus, that is, it offers a great view in one single direction, in combination with one or more protected flanks
I. The spot allows the sniper to move freely, without requiring special movement skills, and without having to deal with obstacles such as doors
Relating Sniping Spot Qualities and Terrain
These sniping spot qualities are easily related to the following waypoint graph properties. For example, "the sniper is inconspicuous at the spot" can be expressed using a waypoint property: the (average) light level at the waypoint is below a minimum value.

A directional property (reflecting a relation between waypoints), "in the direct surroundings of the spot, the sniper can find cover from threats at overlooked locations," can be translated to "For all waypoints overlooked from the sniper spot waypoint: given a presumed threat at the overlooked waypoint, an easily reached waypoint that offers cover from such a threat is available near the sniper waypoint"

Even a complex property like focus can be easily tranlated: "The spot has focus, that is, it offers a great view in one single direction, in combination with one or more protected flanks" can be translated to "the ratio of waypoints visible in one direction vs. waypoints visible in other directions"

The following table lists the terrain properties used to express the sniping spot qualities:



Tactical properties for a sniping spot, and related terrain properties


Sniping Suitability: The Formula
With the sniping spot qualities expressed in terms of waypoint graph properties, a sniping spot suitability score can be computed, for each waypoint and every direction, as follows:

   sniping spot quality (w ,d ) =
   S properties ( w )
+ focus ( d ) ´ S directional properties ( w , w’ ),
      for all waypoints w’ in direction d from w

A directional property, such as, “b: overlooking many distant locations “ is computed as follows:


             Overlooking distant locations (w ,d ) =

k  ´ S ( line-of-sight-line-of-fire (w , w’ ) ´ fardistance (w , w’ )  )
_________________________________________________________


# waypoints w’’ with a line-of-sight-line-of-fire (w , w’’ ) > 0

                for all waypoints w’, w’’  in direction d from w

with   line-of-sight-line-of-fire ( ) and fardistance ( ) returning values in [0..1]

And focus is computed (assuming 45 degrees directions), for example, as:

         focus (w ,d ) =

3 x value ( w, d ) + 1 x value ( w, d + 45°) + 1 x value ( w, d - 45°)
_________________________________________________________


S
value (w, d + a) for all a in {-135°, -90°, +90°, +135°, +180°}

with  value ( w, d ) = # waypoints w’’ with a line-of-sight-line-of-fire (w , w’’ ) > 0
for all waypoints w’, w’’  in direction d from w

Focus here is the ratio of forward interactions versus non-forward directions.The role of focus is best illustrated using the example terrain. Positions that have a strong eastbound focus are:

  • the positions at the western border, because they only have relations with waypoints to their west, and typically with a lot them;
  • the rooms in the southwestern building, and the small alley south of that building have a very strong focus, because their flanks are protected;
  • the positions in the northwest, west of the full height wall, the positions on the northern stairs from the creek, and the positions in western side of the creek also have a good eastbound focus, because their back (to the west) is covered.


Left: East-oriented focus (darker color is higher focus) for all locations, illustrated as a top view, along with terrain feature overlay Right: AI computed Sniping Spot preferences (darker is better) in the eastward direction, using static level data only


Ranking Sniping Spots using Static Info
The sniping spot quality formula, computed for each waypoint, in the east direction, generates the result as illustrated in Figure 5, right image, above. The results demonstrate that using the waypoint graph (and assumptions about game physics and weapon characteristics), the AI really can identify good sniping spots. It identifies as good spots the rooms and windows in southwest building, the western edge of the level, the northern stairs near the creek, and the spot between the northern stairs wall and the bridge wall.

Thus the AI, in the scenario sketched, is able to pick a good sniping spot from a list of automatically ranked sniping locations.Having an algorithm that identifies great sniping spots using just the annotated waypoint graph has several advantages. The AI no longer is dependent on the level designer to annotate terrain. The level designer himself can generate and inspect the AI's understanding of the terrain, which assists him in properly employing AI in the level.

However, it is also a disadvantage to use only these few inputs because locations not properly represented by a nearby waypoint are ignored and actual game play is ignored.

The first problem is easily addressed by adding more waypoints at and near key locations: with more waypoints, the AI is less likely not to detect a position offering cover.
The second problem shows in the rating of sniper spots on the western creek bank: these positions receive a rather high rating because they overlook spots in the creek from which it is hard to avoid the sniper. However, in most game scenarios, most activity will not occur in that creek. Consequently, the sniper spots on the creek bank are overrated.

Luckily, the lack of game play input is not only easily addressed, but also creates a great opportunity.

Using In-Game Sniping Feedback to Rate Sniping Spots

To improve the pre-computed sniper spot ratings, the AI needs to capture and analyze game play, and adjust the ratings accordingly. This sounds more complex than it really is, and even better, at can be done on the fly, at virtually no (CPU) costs.

Capturing and analyzing the required game play data for this case is done by
recording, at every way point, the time spent by the AI or player while static at that position and with sniping weapon active, the amount of damage caused by the sniping weapon from that position, and the amount of damage taken when sniping at that position.

After every game round or mission, aggregate this "experience" as follows:

      sniping experience at ( w, d ) =
      player sniping time in direction ( w, d ) + AI sniping time in direction ( w, d )
   + player directional damage issued ( w, d ) + AI directional damage issued ( w, d )
   - player directional damage taken ( w, d ) - AI directional damage taken ( w, d )


and adjust the pre-computed waypoint sniping rankings with the experience:
     sniping quality ( w, d ) =
     precomputed sniping quality ( w, d ) + sniping experience at ( w, d )


Collecting the game play data takes negligible time, especially since most games already determine the nearest waypoint for every actor at every game tick (for navigation purposes). Processing also takes little time, and typically can be done when presenting an intermission screen.

Because the AI can adapt its sniping spot rankings 'on-the-fly', it will display varying and adaptive sniping behavior. For this example, some 40 game rounds were run, with one or two snipers defending the western building, and three or four attackers storming that building from the east side of the level. The player, randomly, acted as a defending sniper or one of the attackers. The figures below illustrate the "sniping experience data" collected in-game, and the updated waypoint sniping ratings (in the east direction):



Left: Waypoint sniping experience data (non-directional, darker is better)
Right: Eastward sniping ratings adjusted with the experience (darker is better)


Note that the sniping experience data in the images above (left) largely corresponds with (and thus confirms) the sniper ratings computed from the waypoint graph. However, the experience data also emphasizes several highly successful sniper spots over other potential sniper spots.

Adjusting the waypoint sniping ratings results in new ratings. These ratings show a decreased importance for the southwestern creek bank, and increased importance for a few northwestern spots partially covered by the full height wall there.

Better Tactical Understanding From Game Play Experience
Further improvements of the sniping ratings are possible using the game play data. In the previous section, the sniping spot ratings have been adjusted by more or less copying "best sniping practices", without giving the data gathered further thought. Giving the data some thought, that is, using the game play data in our reasoning is exactly what needs to be done to improve the sniping ratings.

Game play does not occur evenly across the map. Some locations are more frequently visited than other locations. And sniping spots overlooking many of these "traffic" locations thus are more important. Again, it is easy and cheap to record actor and player movement per waypoint. The formula for sniping rating needs to be extended with yet another factor, the ability of the sniper to overlook much of the traffic (preferably at some distance from its spot, because then the sniper has an advantage).



Left: Traffic data per location (non-directional, darker is more traffic)
Right: Sniping ratings now also taking into account traffic and sniping experience (darker is better)


Re-running the algorithm, now taking into account both sniping experience, and traffic data results in the following output as is shown above (right).

The new results again show reduced sniping ratings of the spots on the southwestern bank near the creek. They also show increased ratings for the whole western edge of the map (because these positions overlook many traffic spots).

Processing Steps
The AI need for the waypoint sniping ratings, as discussed in the scenario above, has been addressed with:

  • tactics based algorithm to rate sniping spots using the waypoint graph;
  • an on-the-fly procedure to adapt the sniping ratings to game-play feedback;
  • (optionally), a re-run of the algorithm to put more tactical understanding of the game play in the ratings


The terrain analysis cycle, with pre-game and in-game processing

The in-game memory consumption can be as small as two tables containing, for each waypoint and each relevant direction, the sniping rating and player and AI activities respectively. The in-game CPU consumption consists of tracking player and AI activity per waypoint, and a brief computation to adjust sniping ratings (typically done when presenting an intermission screen). To preprocess a level, the memory and CPU requirements are more demanding. The tables for shortest paths, line-of-sight, line-of-fire easily consume a few MB, and the algorithm takes a few tens of seconds to execute.

There are several alternatives to create good waypoint sniper rankings, as is shown in Figure 8 above.The approach presented enables the game developer to ship his game with an "experienced" AI that has gained some tactical understanding of the game's levels.Optionally, the gamer can be allowed to run the algorithm using on his game play data, so the AI adapt to his style of playing.

Similar Terrain Reasoning Applications
A problem similar to picking sniper positions is finding appropriate ambush positions. The ambush position typically is hidden from observation in all but a few directions. The ambush position typically overlooks a number of nearby locations, thus providing targets little time to respond. The direction of traffic near the ambush position typically is perpendicular to or away from the attack direction.

Again, these properties can be mapped onto waypoint related properties. For ambush positions, it is also simple to capture 'ambush' related game play data, and use that to adjust ambush ratings on-the-fly, or with a re-run of the algorithm.

Another problem that is very similar is identifying good positions to position sentry guns.
A more generic waypoint 'combat suitability' rating is also valuable. Such a rating will help the AI distinguish between threats that occupy strong or weak positions. If the game AI implements flocking behavior, that waypoint 'combat suitability' rating can be used to stimulate tactical movement.

In a flocking algorithm, squad members determine their position based on attracting forces (for example, stay near the team members) and repulsing forces (stay away from walls, do not get too close to team members). Often, tactical considerations are ignored. By using the generic 'combat' rating as additional force (attracting or repulsing the squad member), concepts such as nearby cover, good overview, and flank protection can be handled as part of the flocking. As a result, the squad will be more likely to move along walls than to move in the open.
In combination with areas and portals, the combat rating of areas and portals can be determined. To do so, for each area, the combat ratings for waypoints are determined using solely the interactions with other waypoints outside the area. This enables the AI to detect strongholds.

______________________________________________________

Additional Terrain Reasoning Applications


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