Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

Pathfinding Navigation mesh generation on fairly large map?

Recommended Posts

When my program was generating navigation meshes for my geometry, and the extent is 5000x5000 (m), with a cell size of 5.0 meters, it has to generate 250,000 cells, which makes my computer halt, the target object is a truck, which has a radius of about 20 meters, should I give the cell size a value of 20, because I don't really want to use this navigation mesh on one type of vehicle only. I want to use it for vehicles like cars, which has only about 5 meters in radius... the generation speed is a problem while the memory consumption is another.

Any ideas how to improve this?

Thanks

Jack

Edited by lucky6969b

Share this post


Link to post
Share on other sites
Advertisement

First, I would double check whether a navmesh is the best solution in this scenario. They are really cool, but in a really large world, particularly with repeating assets (i.e. lots of clones of similar artwork), there might be other approaches that work well, such as simply bounding volumes around the obstacles. A lot depends on the details of your game though. Is it an RPG with trees to avoid, or a game like grand theft auto with joined buildings etc..

If you want to have such a large world, one options is to think whether you can devise a hierarchical system of navigation / pathfinding. As an example, with a building with multiple rooms, you can only travel between the rooms via doors, so you can have one system for finding the way between rooms (via doors) and one system for finding your way *within* the room, via a navmesh or whatever. If you apply this to a big world, you have a compact and fast way for doing the high level pathfinding, then you can load local navmeshes as required, presolve local navmesh A stars etc.

For the sizes, you can 'push' the navmesh walls at runtime and take into account agent size in the connections, but most people seem to recommend just keeping several navmeshes at several preset agent sizes. Obviously with a huge navmesh the first option could potentially become more attractive.

Share this post


Link to post
Share on other sites

Navmesh is a perfectly viable solution. Also, the hierarchical system is to speed up pathfinding, not navmesh generation.

Typically, the approach for mesh generation on large worlds is to split it into chunks. Not only does this keep your generation from choking your machine, it speeds things up during level changes since you only need to re-do the affected chunk(s).

What program are you using to generate your mesh?

Share this post


Link to post
Share on other sites

Hello Dave,

The library I am using to generate navmeshes is Recast.

https://github.com/recastnavigation/recastnavigation

However, as I need to generate a grid for vehicle navigation, I am taking back a look at something I already had... the hierarchical mover (pathfinder), in that pathfinder, I can have a series of large block and smaller ones which represent the walkable areas and unwalkable areas, I am thinking of a good solution to turn the hierarchical map into a road network map. It is very intuitive to just feed the geometrical data into the hierarchical pathfinder, currently I am just having some fancy looking map.... still thinking about it very hard, maybe I'll come up with a solution tomorrow when I get up from bed....

Thanks

Jack

Share this post


Link to post
Share on other sites

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  

  • 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!