|
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.
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:
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
Overlooking
distant locations (w ,d ) =
for all waypoints w’, w’’ in direction d from w
focus (w ,d ) =
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.
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):
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).
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 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.
______________________________________________________
|