Generating a navigation mesh in a static world.

[Crayder]

Let's say I have a rather large world. In fact, it's 6000 by 6000 units and has height (definitely not a 2D navmesh). I need to generate a navigation mesh with the following specifications:

- Walking slopes must be less than or equal to 63.5 degrees (been using acos of the ground normal for ground slope).
- Ceilings should be at least 2.1 units above the ground.
- Walkways need to be at least 2 units wide.
- Consider the players to be a 1 unit diameter round, 2 units high capsule.

Finding all of the valid points, connecting them, and everything else is going to be super complicated in such a large world.

The set of objects in this imgur album are within just a 125 by 125 sample area. The navmesh I need would be able to take any two surface points on this map and [if they are connectable] generate a path between them. As you can see, there are a lot of paths that can be taken. There are a lot of obstacles. And the terrain is very organic.

_________________


Is there any way Bullet can help me generate this navigation mesh? The world is completely static and I already have a database containing all of the objects' collisions (I already have a script that imports it to bullet). Any way Bullet could be helpful would be great.



Note: I have attempted this with a bunch of raycasts and surface normal stuff earlier. However, I do not know the internals of Bullet that well. I feel like I'm approaching this horribly wrong.

[Basroil]

3D navigation maps/pathing are a quite difficult thing, sure you can't just pre-render a 2D node map of the scene to traverse with standard techniques?

If you want to take the 3D route though, take a look at:
http://ri.cmu.edu/pub_files/pub4/carste ... 2006_1.pdf
https://www.diva-portal.org/smash/get/d ... TEXT01.pdf (actually closer to the above statement than 3D)
http://vbn.aau.dk/files/68652677/thesis.pdf

The last one can be done in bullet using the built in convex hull functions to traverse the surface of the hull. Add some smoothing and then make minor corrections based on the exact collision models.

[Crayder]

3D navigation maps/pathing are a quite difficult thing, sure you can't just pre-render a 2D node map of the scene to traverse with standard techniques?

Yes, it has to be 3D. We've (I and my community) been dealing with 2D pathfinding for a decade now. Our current takes are based on the heightmap of this large map. It's horrible since the map includes lot's of buildings (a lot of which are enterable), bridges, underpasses, tunnels, hills, cliffs, and everything else.

[Evan407]

yes this is a tricky thing to do but it can be accomplished with recursion and some cpu time. if you have to find the shortest possible path this will take a long time to compute. but if any old path will do it won't be so bad.

maybe this will give you an idea on how to do it

Code: Select all

Path theAnswer;
boolean done = false;
navigateToDestination(Path pathSoFar){
  if(done)
	return;
  if(reachedDestination){
	theAnswer = pathSoFar;
	done = true;
	return;
  }
  navigateToDestination(pathSoFar.add(firstChoicePathwayAddition));
  navigateToDestination(pathSoFar.add(secondChoicePathwayAddition));
  navigateToDestination(pathSoFar.add(thirdChoicePathwayAddition));
  navigateToDestination(pathSoFar.add(...));
  ...
}