Jump to content
  • Advertisement
Sign in to follow this  
suranjith_e

Create Navigation Map

This topic is 3177 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I have an Object file that represent terrain(Map). By using this object file I want to create a navigation mesh for path planning. Can someone explain what are the steps I should follow to create Navigation mesh? Thank You, Suranjith

Share this post


Link to post
Share on other sites
Advertisement
Quote:
I have an Object file that represent terrain(Map). By using this object file I want to create a navigation mesh for path planning. Can someone explain what are the steps I should follow to create Navigation mesh?
You can do it manually, or you can automate it.

How best to automate it would probably depend on the nature of the input data. You mention terrain, but I'm guessing there's more to it than that. In order for there to be pathfinding, there have to be obstacles of some sort (impassable objects, steep grades, terrain that is difficult to traverse, etc.). What are the obstacles in your environment?

There are different ways to build a navigation mesh procedurally, including volumetric approaches, simple analysis of normal directions, etc., but again, what method will be most feasible will depend on the input data.

Share this post


Link to post
Share on other sites
Thank you for the reply.

Yes I want to do it automatically.

My object file that model the terrain contains obstacles like trees, steep grades that units cannot reach, buildings and I want to do path planning in such environment.

I need to know the process of creating navigation mesh from a given object file.

Your help will be greatly appreciated.

Share this post


Link to post
Share on other sites
Google for Mikko Mononens Recast software, its open source and generates a navmesh from any model file you give it, amazing stuff.

Share this post


Link to post
Share on other sites
http://aigamedev.com/premium/releases/recast-navigation/

I found the link but it needs a premium account to access it :(.

I want to know the common process used in game development for navigation mesh generation from a given object file. I think this one of fundamental need in game development process.

If some one can point out the steps which I should follow then I can google it and learn about the technique.

Share this post


Link to post
Share on other sites
http://digestingduck.blogspot.com/

That's Mikko's website, and:

http://code.google.com/p/recastnavigation/

Thats the SVN for recast, you should be able to find out how he does it by looking at those.

If you create an AIGameDev account and introduce yourself on the forum you can view the video on this page:

http://aigamedev.com/insider/presentations/recast-teaser/

Which is a 10 minute presentation explaining how recast works.

Share this post


Link to post
Share on other sites
Thank You for your resources. I will look into it immediately. Is it the normal process game developers follow when building navigation map from object file.

Share this post


Link to post
Share on other sites
Quote:
Is it the normal process game developers follow when building navigation map from object file.
I don't know if there's a 'normal' process for automating the building of navigation meshes. It's a non-trivial process, and is highly context-dependent.

Also, I think that historically navigation maps have been used less often than other methods (such as waypoint systems), so there hasn't been that great of a need for automation. In any case, the volumetric-based method linked to earlier looks very impressive and may be a good fit for what you're wanting to do, so I wouldn't worry too much about what the 'normal' way of doing it is, and just worry about what will give you the results that you're after.

Share this post


Link to post
Share on other sites
Ok. That is a good advice. If I'm going to use volumetric approach what will be the steps to create Navigation Mesh from given object file?

Share this post


Link to post
Share on other sites
Quote:
Ok. That is a good advice. If I'm going to use volumetric approach what will be the steps to create Navigation Mesh from given object file?
The steps are:

1. Use the library that was linked to earlier.

Unless you want to do it yourself that is :) In which case you've got some work ahead of you, because it's non-trivial.

I don't know what methods Recast uses, but it's open source (I believe), and is probably your best reference for the volumetric approach. (Maybe there are some papers on the subject available, but I don't know of any myself.)

If you need to do it yourself for some reason and are looking for other options, I imagine you could put together an ad hoc solution that would be somewhat simpler than the volumetric method. A good first step would probably be to apply a mesh simplification algorithm to the terrain to combine roughly co-planar areas into single large polygons. Then you would need to classify the polygons by the angle of their normals relative to the ground plane, and mark those with a sufficiently steep grade as impassable.

As for obstacles such as trees and buildings, you might be able to incorporate these by removing any terrain triangles that touched them prior to the mesh simplification stage; those areas would then appears as 'holes' in the navigation map.

This is all just speculative of course, but if I were given this task, that's probably where I'd start.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!