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.

Report article RSS Feed 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.

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.

Recast navigation mesh

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:

Recast navigation mesh

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:
Facebook icon ModDB icon Steam icon Twitter icon YouTube icon

Post comment Comments
Highmist
Highmist May 26 2010, 9:15pm says:

Pretty cool. Nice to see theres a free and reliable AI Pathfinding code in the internet.

+8 votes     reply to comment
formerlyknownasMrCP
formerlyknownasMrCP May 26 2010, 9:24pm says:

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.

+4 votes     reply to comment
aerozol
aerozol May 26 2010, 9:34pm says:

Oh my, the foreground/ midground detail of that forest looks very nice. btw

+6 votes     reply to comment
jeffr
jeffr May 26 2010, 9:48pm replied:

Glad you like it :)

+3 votes     reply to comment
MixWhelan
MixWhelan May 27 2010, 10:45am replied:

yeah some really beautiful screens on that kudos brah :)

+2 votes     reply to comment
hogan_skoll
hogan_skoll May 26 2010, 10:33pm says:

Ty

+2 votes     reply to comment
Nebcake
Nebcake May 26 2010, 11:38pm says:

Using awesome code, for such an awesome game.

+2 votes     reply to comment
NGS616
NGS616 May 26 2010, 11:41pm says:

Interesting.

I always like reading these. Keep up the good work over there!

+3 votes     reply to comment
NullSoldier
NullSoldier May 27 2010, 12:16am says:

Nice article, favorited it!

+2 votes     reply to comment
Anddos
Anddos May 27 2010, 1:33am buried:

(buried)

This game is taking long bro

-6 votes     reply to comment
feillyne
feillyne May 29 2010, 8:42am replied:

What did you expect? Excellent games can't be created in one day or even a few weeks.

+1 vote     reply to comment
SliderFF
SliderFF May 27 2010, 2:03am says:

first pic, its like a foto.

+2 votes     reply to comment
Blandr3ws
Blandr3ws May 27 2010, 4:16am says:

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

+2 votes     reply to comment
formerlyknownasMrCP
formerlyknownasMrCP May 27 2010, 6:37am replied:

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.

+2 votes     reply to comment
AlekZanDer
AlekZanDer May 27 2010, 4:24am says: Online

Lucky you.

+2 votes     reply to comment
xXMaNiAcXx
xXMaNiAcXx May 27 2010, 12:16pm says:

Wow! It's really nice, and good to see that you've found something really useful.

+3 votes     reply to comment
Dnst
Dnst May 27 2010, 4:22pm says:

This was a very interesting news post. It always surprises me, how clever you manage to integrate feature by feature.

+3 votes     reply to comment
Post a Comment
click to sign in

You are not logged in, your comment will be anonymous unless you join the community today (totally free - or sign in with your social account on the right) which we encourage all contributors to do.

2000 characters limit; HTML formatting and smileys are not supported - text only

Icon
Overgrowth
Platforms
Windows, Mac, Linux
Developer & Publisher
Wolfire Games
Contact
Send Message
Official Page
Wolfire.com
Release Date
TBD
Game Watch
Track this game
News
Browse
News
Report Abuse
Report article
Related Games
Overgrowth
Overgrowth Indie Single & Multiplayer Adventure
Related Engines
Phoenix Engine
Phoenix Engine Commercial TBD
Related Groups
Wolfire Games
Wolfire Games Developer & Publisher with 3 members