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.
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:
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.
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.
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.
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!