27
Looking for Trouble
Making NPCs Search Realistically
Rich Welsh

27.1 Introduction
27.2 Types of Searching
27.3 Triggering a Search

27.4 Phases of Searching
27.5 Conclusion
References

27.1 Introduction
Searching is so second nature to us that apart from the inconvenience of having misplaced
something, we’re naturally able to effectively track down missing items. What thoughtprocesses do we go through while we’re searching? How can we take these and apply themto our nonplayer characters (NPCs) in order to make them appear more realistic whenthey’re searching? If you’re searching for answers to these questions, then look no further!

27.2 Types of Searching
The main focus of this chapter is to outline the way in which NPCs search for hostiletargets in a title that I am unable to name. Since the target in this game is a player character, the target will be referred to as “the player”; however, in terms of implementation, this
could be any target that is hostile to the NPC. The assumption is also made that the player
is actively hiding from hostile NPCs. Despite these assumptions, a lot of the principles
described here are suitable for almost any type of search. With that in mind, there are twomain types of search that can occur in the game.
27.2.1 Cautious Search
A cautious style of searching is one in which the NPC has been alerted, but does not knowwhether their target is hostile. This style of searching is generally used when the NPC has

305been alerted by a stimulus without any knowledge of the source, for example, if a player
throws a bottle to draw attention and lure an NPC. While the NPC is aware of the noise,
they are unaware of whether the source is a friend or foe.
27.2.2 Aggressive Search
An aggressive search is one where the NPC knows about the target they are searchingfor and, at the very least, that their target is a hostile one. In most cases, the NPC will
have previously seen the player and the player will have successfully evaded the NPC.
However, any NPC that has knowledge of their target should employ this style of search—
this includes reinforcement NPCs who have just entered the engagement or NPCs who
have been informed of their hostile target by an ally.

27.3 Triggering a Search
The first key to making a search seem realistic is triggering it at the right time and telegraphing that transition to the player. Since the player is usually still nearby when the
search is triggered, it is likely that they are still able to see or hear the NPCs who are about
to hunt for them. Therefore, a poor decision on starting the search will be obvious to
the player.
While it may not seem as important as the search itself, telegraphing the transition into
a searching state to the player is vital to get right in order for players to be able to identify
what will and will not cause NPCs to react. In most games, this transition is signaled bysome dialogue and occasionally an accompanying animation.
27.3.1 Initial Stimulus-Based Trigger
An initial stimulus-based trigger is one in which the NPC goes from an unaware state into
a searching state due to an indirect stimulus such as a sound. If the NPC is able to see thetarget directly, then they would enter a combat state rather than search, so in this situation
the player must have created some kind of stimulus that was sensed without a direct lineof sight to the player.
Stimuli received by NPCs can be divided into two categories. Hostile stimuli, such as
gunfire and explosions, will trigger an aggressive search response. Although the target
isn’t known, it is assumed to be hostile from the type of stimulus received. Distraction
stimuli on the other hand, for example, a bottle being thrown or a prop being knocked
over, will trigger a cautious search.
27.3.2 Losing a Target
This method of triggering a search is one in which the NPCs had a direct line of sight tothe target at some point—whether the player just briefly dashed across the NPC’s fieldof view or ran away when spotted or actively engaged in combat. When losing sight of atarget, NPCs have knowledge of the last position and direction in which they were moving. Normally, if it were a person watching a target leave, they would be able to estimate
the location of the target after losing sight. Simply using the target’s last known velocity toestimate a current position after a time can cause problems however, as characters (especially players) don’t move in perfectly straight lines.
306

Tactics, Strategy, and Spatial AwarenessOne common problem with extrapolating a position in this manner arises when trying
to then map that extrapolated position to a navigable position. Without testing against
navigable surfaces (which can range from being a simple navmesh raycast through to afull-blown physics request), it is impossible to guarantee that such a naïve method won’t
have generated a position inside a prop or outside of the world. A far simpler solution tothis problem is to simply allow the NPC to “know” the position of their target for a few
seconds after losing sight of them—the exact number can be tweaked to suit the feel of thegame, but around 2–3 s gives a reasonably realistic feel. This is both a cheap and effective
way of giving the AI a human sense of “intuition” and has been used in a number of highprofile titles, including the Halo, Crysis, and Crackdown series of games.

27.4 Phases of Searching
When performing the actual search in the game, both the cautious and aggressive searches
follow the same phases. The differences between the two come from the speed at which thecharacter moves, the animations that they play, and the rate at which they abandon the
search (see Table 27.1 for a summary of the differences).
27.4.1 Phase 1
When you’re searching for something, the most sensible place to start looking is the lastplace that you saw it. The same principle should be applied here when NPCs are searchingfor their target. Whether it’s a cautious or an aggressive search, the first phase should be tocheck the last known position in what can be described as a “narrow” search.
It is worth noting that while implementing phase 1, it is important to consider how
many NPCs should be able to simultaneously investigate the search location. This also
may vary between a cautious style and an aggressive style of searching.
27.4.1.1 Cautious

In the case of a stimulus that has drawn the NPC’s attention, the NPC should either move
up until they have line of sight with the stimulus position or move as close to the positionas possible. A suitable animation (such as an animation that makes the character lookaround or report the incident over a radio) can then be played. Often with a cautious
search, once the initial position of the stimulus has been investigated, there is no further
need to progress into the second search phase.
In a cautious first phase, limiting the number of NPCs who move to investigate candramatically change the feel of your game. By allowing only a single NPC, it gives theplayer the option to peel targets away from a group in order to take them out separately
Table 27.1 Differences between Cautious and Aggressive Searching Modes
Movement speed
Animations
Abandon search

Cautious

Aggressive

Walk
Slow, glancing around
After initial location searched (phase 1 only)Run
Weapon raised, more alert
After all locations searched or time limit
reached (phases 1 and 2)

Looking for Trouble307

or sneak past them more easily. This also makes it possible for emergent interactions
between the NPCs to take place—for example, the NPC going to investigate could play
an audio clip to any nearby allies saying that he’s going to check out the disturbance, andthey could reply with an acknowledgment. If that character doesn’t return within a certain time, a new stimulus could be generated at his position that attracts allies to see why
he hasn’t returned.
Any NPCs who weren’t allowed to investigate the source should lose interest in the
search and return to their standard behaviors.
27.4.1.2 Aggressive

When searching aggressively, NPCs know that they are engaging a hostile target; thus,
they should be much more alert as they approach and their movement should reflect that.
For example, they might run until they’re able to establish a line of sight with the target’s
estimated position and then slow to walk more cautiously up to that position. This gives
the appearance that while they are trying to track their target down, they are also aware of
the potential danger that they’re facing.
Unlike the cautious first phase, all NPCs who are involved in this search should stay inthe first phase until either the search is completed or phase 2 is started. These NPCs shouldlook as if they’re assisting without starting to sweep—this can be achieved by having themcover their colleagues by aiming their weapons, moving into cover or more tactical positions nearer to the search target’s last known position, or just playing suitable animations.
In the aggressive first phase, allowing multiple NPCs to all investigate simultaneously
can allow the characters to appear more coordinated—however, a limit should still beplaced to prevent every NPC from clustering at the same point (a limit of 2 or 3 characterssearching simultaneously works well). Upon reaching their target destination, suitableanimations and audio can be played, and all other NPCs who are participating in the
search should be informed that the phase will now be advanced.
27.4.2 Phase 2
The second phase is a much broader search, with characters sweeping the area to try andlocate the target after the first phase failed to locate them. This doesn’t really apply for thecautious search, as after investigating the initial position of the stimuli, the search should
finish (however, this is ultimately a design decision to be made to best suit your game).
It is important in this phase to have some kind of search coordinator that NPCs
register with, as the search needs to be performed as a group. Each participant in thesecond phase of a search will request a new search spot to investigate from the coordinator and move until either they reach that position or have a clear line of sight to it.
This behavior will be repeated until the search coordinator runs out of search spots orreaches a time limit.
27.4.2.1 Generation of Search Spots

These searching behaviors were originally designed to work with the CryENGINE AI
system, which utilizes a tactical point system (TPS) [Jack 13]. The behaviors operate on
a set of discrete points. Although there are other systems that can be used to describe
search areas within the game (such as occupancy maps [Isla 06]), these data can always be
reduced to a set of points on which these behaviors will operate.
308

Tactics, Strategy, and Spatial AwarenessSource of coverTarget’s estimated position
Valid search spot location
Invalid search spot location

Figure 27.1
Search spot generation.

As soon as an aggressive style search is initiated, the search coordinator should startbuilding up a list of search spots. A search spot is a location that could potentially be hiding the player and as such will need to be investigated.
Commonly, a location that provides cover for a character also obscures that characterfrom sight. This allows cover positions to be used as a basis for generating search spots.
Similarly, a system such as a TPS could be used to generate locations in a radius around thetarget’s last known position that would obscure the target from view.
An example of search spot generation can be seen in Figure 27.1. In this example, coveris used as the basis for generating search spots. Any cover that is obscured from the target’s
estimated position is used to create a search spot. If there aren’t enough points generated by using cover, then random positions on the navigation mesh that are hidden fromthe estimated position can be used to increase the number of search spots, for example,
adding points that are around corners or in alleys.
27.4.2.2 Performing the Search

After the search spots have been generated and the search coordinator has a list of them,it’s time for the NPCs to begin their broad phase 2 search. This works as follows:
A new search spot should be requested from the search coordinator. If the coordinator
does not return a search spot (this could be because there are no more spots available or
because a time limit has been reached), then the character should return to their regularbehavior. If a spot is available, then the coordinator should calculate the best spot for the
search, mark that spot as being “in progress,” and return it to the NPC. The charactershould then move toward the spot with their weapon raised, playing alerted “glancing
around” animations.
As the NPC is moving, line of sight checks should be done to all unsearched spots thatare within its field of view (including the current target search spot). By having all searching NPCs test against all unsearched spots that they can potentially see, spots are quickly
removed from the coordinator. This prevents different characters from searching an areathat has already been swept, as in Figure 27.2.
Looking for Trouble

309

NPCs starting to move to a search spot
NPC

Searched spot

Search spots marked as searched as NPCs move
Unsearched spot

Cover

Figure 27.2
Search spots becoming marked as searched as NPCs move.

There are two issues with this approach that need to be addressed, however. First, raycasts are expensive. To address this issue, deferring or timeslicing these raycasts is a good
option. Unless the characters are moving extremely fast, a raycast every 1 or 2 s to each
unsearched spot will be enough to invalidate any that the character passively searches
while moving toward their target spot.
The second issue that can arise with this method is that the coordinator’s pool of search
spots can be depleted very quickly if a lot of spots are in areas visible to characters. Rather
than allow multiple NPCs to search the same spot, the best way to solve this problem isto ensure that the initial pool of spots is large enough to accommodate a suitably lengthy
search. Alternatively, if the search needs to continue but all spots have been marked as
searched, the coordinator could mark the oldest “searched” points as unsearched once
more and allow the search to continue or increase the search radius and rerun the generation step once more to provide a new, larger pool of search spots.
27.4.2.3 Selecting the Best Search Spot

When the coordinator is asked to select the best search spot to return for an NPC, it firstneeds to check whether any of the search spots that it has stored in the search list are currently free to be searched. Any spots that are in progress are no good, since that would leadto two NPCs moving to the same spot at the same time. Similarly, any spots that have beenmarked as already searched should be ignored.
Once the unavailable spots have been eliminated, the remaining spots should be scoredand the most suitable for the requesting NPC returned. This scoring of potential points isoften used in AI systems for tactical positioning in order to help determine which potential position will be the most attractive option for an AI. A good example of how to score
310

Tactics, Strategy, and Spatial Awarenesspoints can be seen in Killzone’s Tactical Positioning system [Straatman 05]. If no spots areavailable or if the search has exceeded it’s time limit, then the system returns NULL and
the NPC should abandon the search.
When scoring the spots, the most important two weights should be the distance of the
spot from the target’s estimated position and the distance of the spot from the NPC’s current location. However, as several NPCs will be drawing from the same pool of points, thisleads to characters favoring search spots in areas localized around themselves. By adding
an extra weight for the distance of the search spot from the player’s actual current position, it gives the AI the illusion of human intuition and shapes the search pattern gently inthe correct direction. The weighting for distance to target actual location should be quite
subtle compared to the other two weights, so as not to make the NPCs all immediately
flock to the target. This would both break the illusion of intuition and make the game feel
unfairly stacked against the player.
27.4.3 Improving Phase 2 Search: Gap Detection
While moving toward their target search spot, it is important to keep the characters animated in order to keep them looking as if they are actively searching an area—not justmindlessly pathing from point to point.
The obvious way to handle this is simply to layer sweeping or glancing animations on
top of the movement. This can result in glances that seem random or unmotivated, however. The realism of the NPCs and the effectiveness of their search can both be increased
by adding gap or corner detection to their searching movement, as shown in Figure 27.3.
By using long raycasts both perpendicular to the character’s path direction and slightly
ahead of the character, upcoming gaps can be detected on either side of the path. The character then has the option to turn and look into the gap, which will potentially invalidate
search spots that would otherwise require further investigation. The character can pick

NPC starts to path
toward search point

Both raycasts areblocked by obstracles

One raycast returns nohits—gap has been detected

Character has theoption to glance into a
gap as they pass

Figure 27.3
Gap detection.

Looking for Trouble311

randomly between going over to look, an animated turn, and a head-only glance, so that
not every character passing by a gap will react in the same way.
27.4.4 Ending the Search
There are two ways that a search can end: either the target is successfully located by an
NPC or the search is called off and the target is considered lost. With the latter, it will
ultimately be the decision of the search coordinator as to whether the search should stop.
When either no more search spots are valid to be searched or a time limit is reached, NPCs
should naturally filter back to their regular behaviors in their own time. Although they
are operating as a group, stopping all NPCs simultaneously looks very strange, giving theimpression that they are operating under one hive mind.

27.5 Conclusion
This chapter examined the subtleties of NPC searching. First, the type of searching must
be determined, either as a cautious search or an aggressive search, based on the triggering event. Then the search proceeds in two phases. The first phase attempts to find thesource of the triggering event directly by going to its last known position. Once successfully investigated, a cautious search will complete, while an aggressive search will proceedto phase 2. In phase 2, new search spots will be generated and investigated, with NPCs
sharing information over recently searched spots. If the player was not uncovered during
these searches, then the NPCs should naturally return back to their previous tasks.
As a practical matter of effectiveness, there were several key tricks introduced thatmake the search behavior look more natural. First, if the NPC loses sight of the target, it
should cheat and continue to know the target’s position for 2–3 s, as if continuing to pursue by intuition. Second, within phase 2, it’s important to generate enough search spots
so that the search doesn’t end prematurely. Lastly, the search behavior will appear much
more natural if you implement gap detection and have the NPCs exhibit various glancing
animations.

References[Isla 06] Isla, D. 2006. Probabilistic target tracking and search using occupancy maps. In
AI Game Programming Wisdom 3, ed. S. Rabin. Hingham, MA: Charles River Media.
[Jack 13] Jack, M. 2013. Tactical position selection: An architecture and query language.
In Game AI Pro: Collected Wisdom of Game AI Professionals, ed. S. Rabin. New York:A K Peters/CRC Press.
[Straatman 05] Straatman, R. and Beij, A. 2005. Killzone’s AI: Dynamic procedural tactics.
http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf (accessed September
10, 2014).

312

Tactics, Strategy, and Spatial Awareness