On Friday 20th, Havok invited AiGameDev.com to its San Francisco headquarters for the first ever external preview of their new AI middleware component. I met with Principal Engineer Dave Gargan and Software Engineer Chris Elion who showed me the technology and demos they’ve been implementing over the past 18 months.
This article is an exclusive preview of Havok AI. The official unveiling will take place on on Wednesday, during the Expo at the Game Developers Conference ‘09 that takes place in San Francisco from the 23rd to the 27th. This announcement marks the opening round of AI announcements at the GDC; stay tuned for more coverage from the event in this increasingly exciting market.
Dealing With Destruction
According to Havok’s David Gargan, one of the growing challenges that game developers face, and are looking to for solutions to, is pathfinding in dynamic worlds. Indeed, not only are worlds in recent becoming larger but they also include destructible environments and numerous moving objects. Havok designed its AI middleware component with these requirements in mind to support this fully integrated dynamic pathfinding:
“As opposed to being a static pathfinding solution with an additional layered dynamic avoidance technology, Havok AI is built from the ground up to work with dynamic environments. Its unique, innovative solution handles thousands of moving obstacles in real-time with high fidelity.”
Obviously, a key challenge to supporting dynamic worlds is efficiently processing necessary changes. This is achieved in two ways:
The core navigation mesh building algorithm is very fast, capable of processing whole meshes in relatively short times. As a reference, it takes a few seconds to process the castle level that Havok uses for its demos, and demonstrated during our visit.
Based on Havok’s experiences with physics, they noticed that dynamic worlds tend to change locally in time and space. The algorithm is built to deal with dynamic changes as they happen to save time later.
The AI demos that Havok showed us are integrated with the whole suite of middleware, including Havok Physics and Havok Behavior. The AI component can be connected up to any physics simulation, however.
Screenshot 1: Navigation mesh updates happened dynamically in Havok’s demo when obstacles were added and removed in the level. Local steering also helps the characters avoid collisions better (large version).
Dynamic Navigation Meshes
Based on the observation that many modern games are bound more by memory than computation power, Havok made the decision to store only one navigation mesh per level, which then requires some runtime calculations to find paths for arbitrary actors. This decision is also supported by the fact that Havok optimized its pathfinding to run on separate processors like the PS3’s SPU. From the release that Havok sent along:
“Fully extensible and customizable pathfinding solution. The product includes a hierarchical pathfinder which is multithreaded and platform optimized for all of the key gaming platforms.”
These multi-threaded optimizations can often be difficult to achieve in practice when the pathfinder supports navigation links and smart objects that require integration with the high-level AI — which Havok provides also.
One of the demos that Havok showed included a building with a navigation link placed near a window, so soldiers could come vaulting out of the building using Havok Behavior to handle the animation. Of course, when the building is destroyed the AI deals with this so the link is no longer available.
This kind of situation, where the configurations of objects is roughly known during development (e.g. building parts are standing or destroyed) are handled particularly efficiently by the underlying system, using a variety of representation tricks.
Screenshot 2: Building windows include navigation links that allow the AI to jump through, similarly to a smart object that’s handled by Havok Behavior. Wall destructions also cause connections in the navmesh to be updated (large version).
Crowds and Moving Objects
Another aspect of Havok AI is that it can deal with dynamic moving objects within the world:
Pro-active and autonomous actors like soldiers or pedestrians.
Passive or physics-based entities like grenades or bombs.
The description that Havok sent us describes this as follows:
“Advanced predictive local steering module that complements the dynamic pathfinding capabilities. Characters predict the movement of obstacles and adapt accordingly, moving plausibly through the complex and often congested situations that arise when environments become dynamic.”
The full official press release will be made by Havok to the rest of the press within the next day.
Photo 3: AiGameDev.com at Havok’s San Francisco Headquarters. Alex Champandard, Dave Gargan and Chris Elion.