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

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.

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.

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.

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.

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.

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?

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.