Sign in to follow this  

Pathfinding Navigation mesh generation on fairly large map?

Recommended Posts

lucky6969b    1330

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?



Edited by lucky6969b

Share this post

Link to post
Share on other sites
lawnjelly    1249

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
IADaveMark    3740

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
lucky6969b    1330

Hello Dave,

The library I am using to generate navmeshes is Recast.

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....



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  

  • Similar Content

    • By Crayz92
      Here are the two main files:
      A few things I've done to optimize the search:
      1. Rather than a dictionary to keep track of scores and parents, I use a 2d array of objects that are mapped to the grid i.e. [x,y] represents grid point (x,y).  Objects have F,G,H and Parent fields, these fields are reset to default values during each search.
      2. Cheap weighted heuristic
      3. Orthogonal neighbors (searching 4 neighbors rather than 8)
      Paths don't have to be beautiful because the point reduction smooths them out quite nice. 
      In Path.cs you can see the two functions to reduce points, Incremental and Stretch.  Stretch is much faster because it has the potential to reduce points all the way to the end right off the bat or early on thus reducing calls to the LineOfSight function, but it isn't so reliable around small areas/corners.  The incremental function is reliable but it calls to the LineOfSight function for each and every point along the path, this causes the path reduction to be just about as slow as calculating the path itself. 
      Line of Sight is determined by getting all points between 2 points and checking that they are all flagged as Walkable.
      My grid is dynamic and roughly 250x250.  I tried out Theta* and JPS, both were slower than my current A*.  I'm trying to avoid using a navmesh or worker thread, I suppose mostly just looking for ideas to tighten up my code
    • By Jesse "Chime" Collins
      3D Rigger Mixamo Is Making Some Changes
      Originally founded in 2008, Mixamo has been a go-to source for 3D animation and rigging for nearly a decade. On August 28th, 2013, Mixamo launched a platform called Face Plus. It was designed to allow developers or animators turn facial expressions recorded with even a webcam into top-notch 3D animation. This is not unlike what Holotech Studios’ “FaceRig” does for streamers and video creators as well.
      Back this past May 2017, Adobe (publishers of the Mixamo platform since 2015) announced the end of an era. Mixamo’s Face Plus will be removed on August 22nd, 2017, as well as several other free features.
      According to the Adobe post on the Mixamo website, they lay out what is changing and what is staying the same.

      Set out as bullet points in the post, they seem to be cleaning house on the “free” features. But, they are keeping a small handful of their main key points, such as:
      Select and use characters from Mixamo’s Character Collection
      Upload 3D characters to get them ready to animate using the Auto-Rigger
      Apply animations to characters
      Download as an .fbx or .dae
      Noticeably, the list that’s getting 86’ed includes major tools and the ability to save assets from their site:
      The ability to save and retrieve assets in “My Assets”.
      The Face Plus facial animation plugin
      The Decimator polygon reduction tool
      The ability to download Control-rig scripts
      Download types for .bvh and .biped that streamline integration with 3rd party applications
      Mixamo forums will close and all help articles will be moved to Adobe’s HelpX
      Don't Worry! There's still time!

      They’re allowing people to still download the tools and plug-ins until August 22nd, as well as utilizing their easy-to-download features of saving Assets directly. Those that use Mixamo, utilize Face Plus, or even just do animation are highly encouraged to take advantage and download the tools for the next week.
      To download, sign into your (free) Adobe account at the Mixamo website and start downloading. Developers have only one week left to grab as much as they can. For a complete FAQ and how-to for the Mixamo massacre, check out the Adobe post from their Customer Care Team.
      UPDATE (8/15/17): Adobe would like to stress that Mixamo, itself, is not going anywhere, just the Face Plus features, the tools mentioned above, and a couple other features to make the platform more "streamlined and a little modernized". Once the dust is cleared next week from the changes, I'll reach out to Adobe from a more guided tour of the new set-up. Additionally, I have changed the title of this article to reflect the clarification. Apologies for the inconvenience to those that have already read the article. 

    • By suliman
      I have a A* gridbased pathfind for a city builder I'm planning (think banished or stronghold).
      Units can walk in 8 directions from each tile. But I want more free movement. Look at the example pic below. The pathfind finds the path in step 0 to 19.
      But now I want to "simplify" the path so the unit goes straight from node marked 0 to 10 (and obviously also from 12 to 19; i forgot to mark this in the picture).
      Any good algoritm to "reduce" the path in this way? I understand I need to check if there is a unbroken "line of walk" between two nodes but if i start with checking 0 to 1, 0 to 2, 0 to 3 until i find that 0 to 12 doesnt work and stop there (so I throw away nodes marked 1 through 8) this would be VERY slow.
      Any idea?

    • By suliman
      In a game like stronghold with many workers going back and forth from a workplace to a dropoff-point for example, would I store the path and then use it backwards to not have to redo pathfinding all the time? If the moving units in the city doesnt block movement, very often I could just reuse the old path. Only if i run into a wall (if the player constructs a new building in the path of the old workers) will I recalculate the path.
      Workers in old age of empires for example, do they pathfind every time they go back to drop off gold in the storage?
  • Popular Now