• Advertisement
Sign in to follow this  

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
  • Advertisement
  • Popular Now

  • Advertisement
  • Similar Content

    • By lucky6969b

      Let's say, on abstract level, the path, namely, A->B->C->D->E is valid, but the agent must choose portal #1 to reach E.... Presumably the agent has chosen portal #2, and go to B, C and D and finally ending up finding itself getting stuck at D and cannot move over to E... The whole computation is wasted. How do I avoid this problem?
      thanks
      Jack
    • By ferreiradaselva
      There are a bunch of path finding implementations online. But, to be honest, I wasn't much satisfied with  most of them, for one of these reasons:
      Dynamic memory allocation in the middle of the algorithm Algorithm that does too much (more than what is needed) Too many files for just a single task So I made this two-files (`uastar.c` and `uastar.h`) library: https://github.com/ferreiradaselva/uastar
      No memory dynamic allocation. Straight to the point (the README.md explains how to use).
      It's nothing biggie, but certainly useful.
      Path finder at work:

      I'm leaving this in announcements, because I probably won't add more features (it's pretty much done).
    • By lucky6969b
      I am not sure I can ask questions about a specific library here, but if you haven't already. I'd like to tag some polys in a navigation mesh that correspond to grass or road etc, I can give an extent to do so, or in another way, I can directly feed a geometry in and the polys are tagged this way. But I am looking into alternative ways such as allowing the user to tag the polys using a text file or bitmap file (like the way heightfields are done).. If I define a area map which is a grayscale  image, and the values range from 0-255, and for example, if the value of the first char is 0, then I can map this index to certain place in the navigation mesh, and say this is a walkable ground etc, unlike heightfields, where you define an image and the resultant thing is some terrain, but when you start off with a bitmap for area map, you end up with what? you see, I had the geometry already, the area map probably doesn't make sense here, same way as the text file thing....
      Any ideas?
      Jack
    • By Luqman Ibrahim
      Hello guys, I just registered this site and heard from my lecturer that this a good site to talk about certain topics since my research topic are mostly programmer who are experienced with AI can answer the survey.
       
      The reason of the survey below is to understand which is suitable solution for 2d platformer pathfinding for AI and which one is easier to implement for 2D platformer. 
       
      I would appreciate if you guys give your responses for the survey link shared and thank you for spending time answering the survey. Sorry if the survey is a bit hard to understand, I tried to make it understandable as best as I can. Again, thank you!
       
      https://goo.gl/forms/S0etAlAAHL6S5kTI2
    • By baabaa
      Hello hello. I'm in the preliminary design phase for a space based game, and I need some advice on how to approach the AI side of things.
      Here's the situation in a nutshell. Say I'm a space explorer with a spaceship, and I am competing with other space explorers to be the first one to discover things. I have a procedurally generated 2D top-down solar system, and to make things a little simpler, let's say all the planets in the system are static, meaning they are not orbiting their sun. But they all have their gravity wells of varying strength. As a player I have to negotiate newtonian physics around these planets, using engine thrust at the right amounts and timing, to get to where I want. That part is not a problem. I'm also willing to assume non-newtonian rotation so that AI and player do not need to account for appyling torque to get a correct bearing.
      So far I have not mentioned whether this is real-time or turn-based and that's because of my uncertainty around AI.
      Problem is I'm not sure how to approach the AI side of things either way. Ideally I'd like to have an AI that can optimize trajectory for speed and/or fuel efficiency, but I have been able to find precious little on the topic on the interwebs. The best I've found so far is the following article from a decade ago, and it does not really point to a solution: http://playtechs.blogspot.ca/2007/05/pathfinding-in-space.html
      If I can find a good resource on how to pull this off in realtime, I'd like to go that route. At the moment my fallback is using a turn based system for exploration and visualizing the system as a hex grid. Then using A* I could get AI agents to naively assume use of thrust to come to a stand still each time they want to change trajectory, and then add extra thrust to move in the next direction, but I'm worried this would be extremely under-optimized in terms of fuel efficiency and the reach of rival ships as a result. I could also factor in the AI ship's current velocity into the graph search, which would likely greatly increase the search space for pathfinding, but I haven't experimented with it yet to be able to say whether it's viable.
      Any thoughts?
  • Advertisement