Jump to content
  • Advertisement
Sign in to follow this  
Tangletail

How do you generate a Navigation Grid for 3D environments?

This topic is 1003 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 currently in the process of considering how I want to do navigation in my engine. Which follows suit for a Point and Click baulder's gate style game, with arbitrarily large, and seamless worlds. However the worlds do not exactly mean "Open", as they would still have passes and paths to follow to get to certain locations.

 

I already have planned a method to speed up Path finding, which is to do a several layers of navigation. So space is not that big of a concern. Yet anyways.

I needed something that had a high resolution, and can be marked as occupied on the fly. So my first thought came to a navigation grid similar to what was used in StarCraft, Warcraft, and Dragon Age Origins.

 

But my first problem was, how exactly would you generate something like this? And preferably axis aligned?

The Engine will be using a variety of meshes to populate a scene. The ones marked static would simply delete it's occupied squares from the grid. And the meshes that are dynamic would simply mark their squares as occupied as they can still be moved around by the player.

My first thought would be to use Rays at a fixed length fired downwards to generate this geometry, but this just seems terribly inefficient and error prone.

 

I tried looking into recast. Recast on it's own does generate squares, but not uniformly. And I can't quite figure out whats going on in it's generation phase (nor find it for that matter) to see whats going on.

Any ideas?

Share this post


Link to post
Share on other sites
Advertisement

Not exactly sure what you mean by squares, but Recast does indeed generate a voxel mold out of the geometry as a intermediate step when generating a nav mesh. I haven't used the voxel mold directly but I don't see why that wouldn't be possible. Try out the recast demo with some of your geometry to see if the results look like something you could use. The demo app can draw the voxels for you.

 

What exactly don't you understand about the generation phase? The samples that come with Recast are very well documented. Check out Sample_SoloMesh for example.

Share this post


Link to post
Share on other sites

Casting thick rays can work out okay, depending on your level geometry, you'll still run into issues if you set a building down that's not aligned to the squares, and having smaller squares tends to negate that effect, at the cost of performance.  The generation isn't a huge issue, since you can do it offline.

Share this post


Link to post
Share on other sites
I -can't- find the generation phase in the code nor do I have any idea on what's going on in it.

And by squares I mean that exactly, the navigation mesh as a grid of squares. If looked at from the top down, they would all appear to be the same size.

Share this post


Link to post
Share on other sites

Well they are hardly squares since we are talking about a 3D environment here. Anyway, the voxels produced by Recast should be exactly what you need.

 

If you cannot figure out where the generation is then you haven't looked very thoroughly at the code (in the file that I suggested earlier).

 

https://github.com/recastnavigation/recastnavigation/blob/master/RecastDemo/Source/Sample_SoloMesh.cpp

 

The complete navmesh generation is in Sample_SoloMesh::handleBuild(), but you don't necessarily need to do all steps 1-7. Step 2 is concerned with creating the voxel height field. Search for duDebugDrawHeightfieldSolid() to see how the demo app draws the voxels.

Share this post


Link to post
Share on other sites

Casting thick rays can work out okay, depending on your level geometry, you'll still run into issues if you set a building down that's not aligned to the squares, and having smaller squares tends to negate that effect, at the cost of performance.  The generation isn't a huge issue, since you can do it offline.

I've never heard of thick rays, nor can I find information about them. Do you mean something like a box cast?

 

 

Well they are hardly squares since we are talking about a 3D environment here. Anyway, the voxels produced by Recast should be exactly what you need.

 

If you cannot figure out where the generation is then you haven't looked very thoroughly at the code (in the file that I suggested earlier).

 

https://github.com/recastnavigation/recastnavigation/blob/master/RecastDemo/Source/Sample_SoloMesh.cpp

 

The complete navmesh generation is in Sample_SoloMesh::handleBuild(), but you don't necessarily need to do all steps 1-7. Step 2 is concerned with creating the voxel height field. Search for duDebugDrawHeightfieldSolid() to see how the demo app draws the voxels.

 

Eh, when flattened they would look like squares. And thanks, I'll take a look at that.

Share this post


Link to post
Share on other sites

Alright, I see what he's doing now. He's building triangles out of a convex shape using a very fine resolution.. From the outside in. then using a triangulization algorithm. Which is no good for me @_@; Though I suppose I can still use the height field. It's nothing but voxelized geometry, so theoretically if i lower the resolution so that everything is an equal sized box, I can do a square merge to find the largest square regions. And take that convex shape, and sub divide it. It will given a plane that roughly models the slope.

Anyone know any good algorithms for generating squares out of a convex hull? I'm sure someone has a speed algorithm

Share this post


Link to post
Share on other sites

I've never heard of thick rays, nor can I find information about them. Do you mean something like a box cast?

 

It's also called a Spherecast, which is basically a capsule check, it's not perfect, but it allows for a little wiggle in whether a square is considered entirely blocked.  Which is both good and bad, depending on your terrain& objects.  A telephone pole that is in between four tiles could be skipped, but so could a random small-ish rock that really shouldn't block four tiles.  (Though disallowing the placement of blocking terrain on a non-centered position would go a long way to avoiding the problems entirely)

 

EDIT:  I'm not sure how Aron Granberg does his gridgraphs, you might be able to email and ask him (especially if you're not using Unity, since then you're not trying to cheat him out of money)  I believe his pro/paid version does bridges and the like, but I forget.

 

EDIT2:  Ah, he has what he calls LayeredGridGraphs

Edited by ferrous

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!