Beneath all the higher ambitions for artificial intelligence in games, one basic, fundamental task remains: pathfinding. Simply telling a character how to get from A to B is a complex mathematical undertaking, and the perfect, foolproof solution remains elusive.

Here’s how several AI experts are struggling with the pathfinding problem…

Participants:
Remco Straatman: Lead AI programmer, Killzone 2
Sergio Garces Casao: Lead AI Programmer, Radical Entertainment
Nick Davies: AI Programmer, Wheelman, Midway Newcastle
Louis Gascoigne: Software Engineer, Dead Space, EA Redwood Shores
Owen O’Brien: Senior Producer, Mirror’s Edge, DICE

Remco Straatman: Pathfinding is more of a problem than ever before: game worlds are more dynamic, with physics objects moving around, things being destroyed and more actors running around on the battlefield. These things make both pathfinding and path following much more complex.

And at the same time, we want more realistic NPCs to use smarter paths, to use tactical knowledge of both the terrain and the state of battle. When moving, NPCs should avoid the lines of fire of their teammates, stay in cover from enemies, stay close to the player, etc. All these new requirements have made pathfinding more challenging, even with the extra CPU resources we now have.

Nick Davies: I think pathfinding will always be a bugbear for AI developers – especially with open world games. However, with AI middleware like Kynapse, the problems are getting easier to solve. With the auto-generated navigation meshes and hierarchical pathfinding available in Kynapse, we can concentrate more on developing fun and interesting behaviours, rather than the mechanics of A* [a commonly used pathfinding algorithm – more info here]. Additionally, the use of the Unreal Engine has made it a lot easier to create functionality, and with tools such as Unreal Ed and Kismet, scripting a sequence is relatively easy for designers.

Owen O’Brien: As the mechanics of games change and develop so do the requirements for things like pathfinding. Like most things, it’s different for different games. Battlefield Bad Company for example needs pathfinding that can take in to account the dynamic changes in the environment caused by destruction, whereas Mirror’s Edge requires enemies who can cope with a highly mobile character who can move very quickly in all three dimensions.

Sergio Garces Casao: The two main areas where Prototype is pushing boundaries for AI are density and integration with complex environments. We have created a densely populated world with hundreds of pedestrians and vehicles, and tons of enemies, which was impossible until now. Those enemies have to navigate and understand a fully dynamic urban environment that is not limited to the streets, but includes the vertical dimension as well. Having hunters and helicopters chase you as you run up a building and jump from rooftop to rooftop is a new experience.

In order to make all of this possible, we had to do research in level of detail techniques, not just limited to the graphical representation of characters, but also for their AI. On top of that, individual behavior is more challenging, as the traditional approach of having everything pre-computed falls down in heavily dynamic environments like Prototype’s. Being able to take advantage of this is another area where technology has advanced. For instance, some of our characters can use props they find in the world as weapons, much like the player can.

Louis Gascoigne: The biggest advancements are in handling dynamic changes to the environment. Previous solutions for visibility, light, and path-planning were static and could not deal with dynamic environments. With today’s hardware our players expect more.

As an example, in Dead Space nearly all of the lighting on the environment and characters is dynamic. Lights can be modified in real-time and work as expected. Any AI usage of lighting conditions has to be able to deal with this. [In other words, the AI characters in Dead Space need to know when a room is dark or light, so that they can, perhaps, navigate using shadowy areas…]

Pathfinding is expected to be able to handle situations like a player-caused building collapse. In the past both the destruction and its effect on the AI would likely have been scripted. Today there are pathfinding solutions which support dynamic terrain both for pathfinding and for strategic analysis although much of this work is still relatively new…

Come back tomorrow for more…