Sign in to follow this  

Building a navigation system

This topic is 3668 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

I'm planning for the construction of a navigation system to my game, and I have a few questions: 1. How do I perform efficient path finding in a nav mesh without colliding with obstacles? If the player is contained entirely within a single triangle in the nav mesh in xz coordinates (where y is up), he is obviously not colliding with anything. Things get worse when there's a triangle that is smaller than the size of a character, or the player is on the edge between two triangles. Then simply ensuring containment within the nearest triangle isn't possible. How do I in general solve this difficult problem in a correct and efficient manner? 2. Simplification of navmesh while still being able to handle multiple floors. A lot of issues with navmesh can be solved by removing the capability of handling multiple floors. For example, in an outdoor environment, most of the terrain will be passable, so I would like to optimize by merging navmesh triangles, since after all, it's probable that in a 100*100 heightmap mesh, maybe 20-100 triangles would actually be enough to describe what is passable and what isn't (in extreme cases, with all passable, 2 would be enough, as opposed to 10,000 in the unoptimized case. However, the terrain isn't of the same height everywhere outdoors, so some of the navmesh will then end up below ground in this optimized, compressed version. One way to allow for this is to remove the y coordinate altogether from the nav mesh, but that removes the ability to handle multiple story buildings, doesn't it? One suggestion I've heard is to have two different navigation systems. But that would restrict me and prevent me from, for example, adding certain multifloor structures that are outside - for example a platform, a tree house, and so on... What solutions do you know about for this problem?

Share this post


Link to post
Share on other sites
The solution for both your problems is to efficiently merge the triangles in convex polygons, starting with the smaller ones. Ideally, the edge of each polygon should be larger than your agent size to be navigable, altough that is not always true, like on a ridge. For outdoors, you can still merge polygons that are not stricly co-planar. As you said, the resulting polygon might end up slightly underground, but you should be able to support a certain margin without any adverse effect.

Building a navmesh in a complex level is a difficult problem (I tackled it myself last winter, lots of fun, had to re-learn computational geometry). Check out this article in AI Programming Wisdom 3: "Improving on near-optimality: more techniques for building navigation meshes" by Fredrik Farnstrom from Rockstar San Diego. It'll clarify a lot of things (better than I can), and probably save you a lot of time with problems you dont know you'll have yet.

Share this post


Link to post
Share on other sites

This topic is 3668 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this