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.

Post news Report content 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 on

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

Comments
Highmist
Highmist

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

Reply Good karma Bad karma+8 votes
formerlyknownasMrCP
formerlyknownasMrCP

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.

Reply Good karma Bad karma+4 votes
aerozol
aerozol

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

Reply Good karma Bad karma+6 votes
jeffr Author
jeffr

Glad you like it :)

Reply Good karma+3 votes
MixWhelan
MixWhelan

yeah some really beautiful screens on that kudos brah :)

Reply Good karma Bad karma+2 votes
hogan_skoll
hogan_skoll

Ty

Reply Good karma Bad karma+2 votes
Nebcake
Nebcake

Using awesome code, for such an awesome game.

Reply Good karma Bad karma+2 votes
NGS616
NGS616

Interesting.

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

Reply Good karma Bad karma+3 votes
NullSoldier
NullSoldier

Nice article, favorited it!

Reply Good karma Bad karma+2 votes
Anddos
Anddos

(buried)

This game is taking long bro

Reply Good karma Bad karma-6 votes
feillyne StaffSubscriber
feillyne

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

Reply Good karma+1 vote
SliderFF
SliderFF

first pic, its like a foto.

Reply Good karma Bad karma+2 votes
Blandr3ws
Blandr3ws

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

Reply Good karma Bad karma+2 votes
formerlyknownasMrCP
formerlyknownasMrCP

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.

Reply Good karma Bad karma+2 votes
AlekZanDer
AlekZanDer

Lucky you.

Reply Good karma Bad karma+2 votes
xXMaNiAcXx
xXMaNiAcXx

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

Reply Good karma Bad karma+3 votes
Dnst
Dnst

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

Reply Good karma Bad karma+3 votes
Post a comment
Sign in or join with:

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.

Icon
Overgrowth
Platforms
Windows, Mac, Linux
Developer & Publisher
Wolfire Games
Contact
Send Message
Homepage
Wolfire.com
Release date
Game watch
Start tracking
News
Browse
News
New
Post news
Share
Related Games
Overgrowth
Overgrowth Adventure
Related Engines
Phoenix Engine
Phoenix Engine Commercial
Related Groups
Wolfire Games
Wolfire Games Developer & Publisher