AI: Search Behaviours

In intelAgent, whenever the player is seen, the guards will enter the “alert” phase. As long as the player is within a guards direct line of sight, guards will converge on that players position. Once the player is no longer visible and a guard has reached that last known location, the guards will be told to search the level. It’s important for this search behaviour to be semi-realistic but still beatable for the player. Too dumb and there’s no challenge, but too smart and it just gets frustrating. This is true for all AI behaviour, it needs to provide a challenge for the player and give them a sense of accomplishment when they overcome it.

Dumb Search

The first search behaviour implemented was basically just a placeholder action. It simply gave the guards a random target within a certain radius and sent them there. The randomness was nice as it makes it harder for the player to predict and evade but for the most part, it just made the guards wander aimlessly.

The second iteration of the search behaviour was adding predefined search locations within the level and guards would be assigned a location which hadn’t already been cleared. It’s a simple solution and gave the guards a nice systematic approach to sweep the level. The drawback to this was that it required more setup on our part when laying out the level. There’s also nothing intelligent about this behaviour.

Occupancy Grid

Over the last few days, I’ve been working on adding some emergent search behaviour by using an ‘occupancy grid’. The idea originated from this article I came across on AIGameDev. The basic concept is that probabilities are assigned to a graph to track where the player may have headed. These values represent the probability that the player is currently occupying that space.

Occupancy Grid start

Initial occupancy probabilities

When the guard reaches the players last known location (from the alert phase), the occupancy grid is refreshed and nodes are given a probability value (between 0 and 1). The node at the players last known location is given a probability of 1, and this value is propagated outwards to neighbouring nodes. When a guard can see that the player is not at a point, the graph is updated and probabilities propagated again. The graph is used to assign search locations to guards where there is the highest probability, leading to smarter search patterns that works anywhere on the map and doesn’t require explicit setup from us.

Occupancy Grid update

Propagation of probabilities

Here are examples of how the probabilities are propagated as certain points are cleared by the guard. (Screenshots were taken in the Unity scene view, so the guard is shown here as a flower gizmo that uLink uses). The short green lines are nodes that fall within the guards line of sight. The longer green line shows the guards current path as it is assigned the next best location using the graph probabilities.

Nodes with values below a certain threshold are ignored to limit the overall range and help with performance.

Occupancy Grid combined


There’s still work to be done on this. It works alright in it’s current state but it was just a first pass. There are always improvements that can be added and a couple of features I’d like to try out.

  • Update grid values over time: Try imitate the players movement. Right now, node values are only propagated when a guard sees some nodes and triggers an update.
  • Guide propagation in towards players direction: The probabilities are currently propagated outwards in all directions (to connected nodes), but if a guard had been chasing after the player and lost sight of him, it would make sense that the areas that the player had been heading in would have a higher occupancy probability.
  • Visual representation of occupancy grid in-game: It might be interesting to show the players how the graph is updated within the level, similar to the sound propagation
  • Integrate better with the predefined search locations: Currently, the guards will fall back to using that behaviour once the occupancy grid values have been cleared.
  • General optimisations


Leave a Reply

Your email address will not be published. Required fields are marked *