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?

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.

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

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.

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.

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

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