Automatic navigation meshes

One of the hardest parts of developing character AI in 3D games is pathfinding -- making sure that they can figure out how to move from point A to point B in a believable way. This is almost impossible to do using raw rendering data (often referred to as "polygon soup"), because it has both too little and too much information. Too little in that it doesn't encode which surfaces can be navigated and which are obstacles, and too much in that it includes tiny surface details which are not relevant to pathfinding. So, to efficiently find paths, we need to create a more informative representation of the scene.

Many modern games use navigation meshes for pathfinding instead of the old waypoint and grid methods -- you can read Paul Tozour's detailed post on the subject to find out why. A navigation mesh is a set of connected polygons which define where characters can walk in the scene. Here is an example of a navigation mesh for a detailed scene in Overgrowth: the light blue areas represent navigation surfaces.

These navigation meshes are often created by hand, or using expensive middleware packages. However, the lead AI programmer for Crysis (Mikko Mononen) recently released an open-source navigation mesh library called Recast, along with a companion pathfinding library called Detour. You can find the Google Code project here. "Automatic" and "open-source" are magic words for me when looking for tech to include in Overgrowth, so I decided to try it out. So far it seems to work well -- it can even handle stairs and other small climbs:

There is still a lot of tricky pathfinding work to do, such as incorporating alternate navigation such as jumps and slides. However, Recast and Detour look like they can give us a decent head start!