Open Tutorial
OccupancyZoom.medium

Occupancy Grids and Emergent Search Behavior for NPCs

Alex J. Champandard on April 28, 2011

Occupancy grids have been used in robotics for decades to help with navigation, and were recently applied by the MIT Media Lab make synthetic creatures more believable under Bruce Blumberg's supervision. Damian Isla, who originally worked on Duncan the Highland Terrier as part of his research there, popularized the concept for game developers in a demo at the AI Summit two years ago.

Here at AiGameDev.com, we're always keen to jump onto new bandwagons to see what all the fuss is about... In this article and accompanying video, you'll see our own occupancy grid implementation in action. It was implemented within the stealth game of The AI Sandbox™ by Quentin Pradet and Olivier Favre as part of their student project.

Executive Overview

Occupancy grids are a way to track the player's last known position in a more accurate fashion, by modelling probabilities in a graph-based data structure. These probabilities are calculated using the following steps:

  1. Visibility — When the player is visible, the probability for his/her current cell is set to one. Otherwise, all visible cells (without the player) have their probability reset to zero.

  2. Propagation — If the player is not visible, the probabilities from the previous occupancy grid are propagated along the edges of the graph to neigboring cells.

Using this resulting probability distribution map, it's possible to estimate how likely a player is to be found in a certain location. It allows an NPC in a stealth-like game to perform a methodical search by probability based on where player's predictions.

The Video

In Production?

At the Game Developer's Conference this year, I was discussing the topic of occupancy grids with Michael Dawe, AI Programmer at Big Huge Games, who's been implementing them within the MMO game he's working on. Michael pointed out that although the concept looks very simple, many optimizations and simplifications were necessary to get it working efficiently in production with real-time constraints. Guerrilla Games in particular uses the PS3's SPUs to perform accessibility calculations based on visibility.

These observations match with our experiences of occupancy grids so far. While our proof of concept (in the video above) has very convincing behaviors, its implementation wouldn't scale well to larger environments, or even multiple agents. In particular, here's what we'll be looking at over the next few moths:

  • Variable Grid Resolution — While it's clear that occupancy grids don't require the fine resolution of a pathfinding map (1m or more, rather than 25cm), there's also a solid case to be made that open space requires less detail than near obstacles. The search behavior looks more natural when attention is paid to space near walls and other potential hiding locations.

  • Hiding Location Probability — The probability in the occupancy grid spreads in a mathematically correct fashion, however, picking the highest probability point in the grid doesn't yield very good search behavior. In particular, locations that are poor places to hide but have accumulated a high probability are chosen over nearby locations (with lower probability) that would make better hiding locations. The occupancy grid needs to be combined with an automated analysis for visibilty, for example.

  • Hierarchical Occupancy — In most levels, there's only a small zone that's easily visible by line-of-sight. It only makes sense to have a high-quality occupancy grid for this area around the target, and falling back to a global area-based occupancy map otherwise. The challenge will be propagating the probabilities back and forth correctly between these two maps.

  • Line Of Sight Optimizations — The bulk of the occupancy algorithm is no more expensive than an influence map, but what costs the most processing power is the line-of-sight calculation. In the case of these 2D grids, the LoS calculations are simplified and done with line rasterization algorithms — similarly to path-smoothing calculations using string pulling. While we've optimized our algorithm with caching to avoid tracing N lines, there are better algorithms for this.

  • Emergent Glancing Around — The current search behavior simply follows a path towards the highest probability location repeatedly. This behavior only resets the probability of zones near the path in front of the NPC patrolling. Ideally, the behavior should include head movement to scan around the environment while searching. In fact, target points for the patrol could be picked based on how many hiding points (with high probability) are visible nearby.

Summary

Occupancy grids are a great way to improve the search behavior of the typical guard in a stealth game. They're relatively easy to get up and running too, but you'll run into a few issues as you try to get them production ready — in particular from the performance side of things, but also some behavioral issues too.

We're planning to implement a few features from our list and demonstrate the results at the Paris Game/AI Conference's demo and session on June 22nd. If you have any suggestions in the meantime, don't hesitate to post a comment or reply in the forum thread!

Discussion 5 Comments

Dil on May 2nd, 2011

Very interesting demonstration, I would guess a more realistic implementation would take in account the time to travel to the next most probable location, in order to prevent back and forth effect that you can see in the demonstration, it would then appear like a search guard more clever. Could this algorithm be combining distance cost and probability of player's location, or would you suggest another method to reach this effect?

memoni on May 2nd, 2011

I prototyped similar (but simpler) search behavior for Crysis1, where the AI would sweep the "dots" by looking around an moving the new are which was not inspected yet. Eventually we ditched it, though. The reason was that the player could not read it at all! It was cool to look at and the resulting motion felt clever when the debug draw was on, but in the context of the game it felt really random and it was impossible to guess when the search phase was over. Eventually we used similar "search a little bit past the last known position" as described in the Halo1 AI slides. It also was a better fit for the pacing of the game.

alexjc on May 3rd, 2011

The original PDF from the MIT Media Lab Synthetic Character's group by Isla, Blumberg & co. covers the process of predicting the new probabilities given a known velocity. It should be relatively easy to integrate! Mikko, that's very interesting to hear. I actually wasn't sure about integrating the prediction, it'd make the AI too good possibly. But I hadn't thought about it looking too random. We'll experiment and see how it turns out. Alex

kezza on May 8th, 2011

I think that player readability is an area that really needs to be explored for this technique, as it's very compelling with debug visualization and can create new gameplay. I'd hate to see occupancy grids fall into the "too hard basket". Off the top of my head I'd suggest that characters might telegraph where they're going and why. For example "He was headed this way... I'm going to check near that {nearby landmark}". The other suggestion I'd make is that the debug visualization perhaps can be shown subtly in game? Perhaps it's a stealth game and everywhere that's on an enemy's occupancy grid is lit up slightly, so that when a player is looking for shadows to hide in... those shadows are safe from searching enemies.

naimad on June 20th, 2011

Haha! I missed this article when it first came out, and I just happened across it in my google reader. Cool to see another implementation! Just a historical note: the terminology is, as always, a bit confusing, but the "Probabilistic Occupancy Maps" (as I called them) are quite different from the work you allude to in robotics, which I've heard referred to as "Occupancy Grids". The big difference being that the "probability" in question in the latter case is the probability of a particular grid-space being occupied [I]by anything[/I] (say, by wall, or furniture) whereas in the former (my work) the probability is the probability that the grid-space contains a particular target object. In the case of POMs all the probability in the world needs to sum to 1, where as in OGs, there is no such constraint (the probabilities are usually the result of some complex fusion of sensor data over time). POMs had much more in common with "Particle Filters", which solves many of the same problems in some of the same ways (in particular its incorporation of negative knowledge). Only instead of representing the distribution as a discrete grid over the entire world, particle filters represent it as a collection of gaussians. Clever stuff, and the real advantage to them is that you can scale your performance by scaling the number of particles you track (here a "particle" is a gaussian, essentially). Alex -- you should integrate a PF implementation into your sandbox as well! I'd love to see them running side-by-side! :) Agreed that any complex search behavior is almost always completely missed by the player in a first-person game. Third person and orthographic games, though, are much better in this regard.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!