Overgrowth takes place in the savage world of Lugaru where rabbits, wolves and other animals are forced to use paws, claws and medieval weaponry to engage each other in battle. Combining 3rd person adventure platforming with intricate melee combat, Overgrowth achieves a unique feel. Overgrowth also benefits from Wolfire's brand new Phoenix Engine which has been built from the ground up to allow the use of cutting edge graphics, animation, and physics. Add to these exciting features Overgrowth’s realistic artificial intelligence and streamlined control system and the result is an astoundingly immersive experience.
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.
Posted by jeffr on May 26th, 2010
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!