I am attempting to find a solution to this problem. I'm trying to build a navigation mesh in the format of a grid of vertices locked to x, y floored coordinates in the shape of squares for 3D space. But I'm having problems trying to figure out a way to go about it.

I tried looking into the Recast library. It's a pretty robust method, but it apparently slows down with larger maps and open space. I also don't know how they generate vertices and edges for the world space with the height map.

My next thought was to do what Unreal Engine 3 used to do.

<https://udn.epicgames.com/Three/NavigationMeshReference.html>

Which was to use raycasts to generate the mesh. I couldn't figure out how to have the raycasts stop.

So... my next option was box, possibly a box cast. Create a subdivided volume with a size that's a power of 2. Align the box to the grid, and shoot rectangular prisms downwards as a ray. If it lands on a piece of geometry that's part of the ground and the rectangle is not being intersected, leave a square there. And continue down until the bounds of the volume is reached. To check if edges need to be linked, I suppose I could check to see if the slope between two pairs of vertices is within the walkable slope, merge them if this is true.

My main problems are... this doesn't seem to be very optimal. Without thinking of it, at estimation the process is O(N^3) for a multilayered level. Which can get pretty nasty.

And the last bit is for automatically creating rectangular groups of these squares. I'm not entirely sure how to do this. The Unreal implementation separates them by slopes. However, I'm trying to keep the grid format. So that's not entirely necessary. The trouble still remains on creating large rectangular tiles to split up the path finding process into a per tile basis. The tiles can't be too large, nor too small.

So the questions are...

What would be an efficient way to generate this girded navmesh? And what would be a good way to create the tiles?