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!
Track us on ModDB (visit our page)
Please join us here too:
Pretty cool. Nice to see theres a free and reliable AI Pathfinding code in the internet.
Those links are extremely helpful, thanks for posting that. I've been looking into pathfinding solutions and its been doing my head in trying to find the right one.
Oh my, the foreground/ midground detail of that forest looks very nice. btw
Glad you like it :)
yeah some really beautiful screens on that kudos brah :)
Ty
Using awesome code, for such an awesome game.
Interesting.
I always like reading these. Keep up the good work over there!
Nice article, favorited it!
(buried)
This game is taking long bro
What did you expect? Excellent games can't be created in one day or even a few weeks.
first pic, its like a foto.
The forest looks amazing :)
The nav mesh for the buildings pic looks a bit dodgey, for example the stairs area. However if it's manually tweakable then it's still great cos you've saved time on the majority of the nav mesh graph :D
If you've used the demo of Recast you'll see that the pathfinding doesn't work on segregated meshes caused by elevation for some reason. As you can see in the pictures, most vertical geometry is left out, the demo I noticed does this and sometimes segregates the navmesh causing a heap of bugs to occur (where the nav mesh is 100% filled and the end of the path cannot be found this would probably cause the AI to move really oddly.) I'm wondering if they've done that in a way so that Vertical meshes are treated as "walls" so that it doesn't calculate them into the nav mesh. A work around would be to manually create a navmesh telling the AI where it can climb (as it'd ignore everywhere else- well at least on the wall). In the end I don't think you could use the pathfinder 100% automated, its still gonna need some help from a human. ;)
I've not looked at the code though so I have no idea what could be causing that to occur- But I noticed this in the demo and its also occurring in the examples here too.
Lucky you.
Wow! It's really nice, and good to see that you've found something really useful.
This was a very interesting news post. It always surprises me, how clever you manage to integrate feature by feature.