How would one generate a Navigation Grid for a 3D world?

Question

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?

Answer 1

A basic 3D world could be represented by a navigational mesh that can be conveniently built in most game engines. The Actor can travel along edges of polygons.

That would be a simple solution. There are many algorithms for path-finding and generating a navmesh.

I would like to share something i read a while ago.

This describes a possible solution where we can break our game world into square tiles. whenever a square tile is added into game(when player gets near an area/ procedural terrain), a square tile is added. However, we dont have to calculate the entire navmesh anymore. we just calculate it for that tile and add it into existing graph. Significant performance gain there.

The next problem tackled is the jagged movement from the previous example. I can understand that by considering future turns and generalizing the direction would reduce zigzag movement a lot and make the motion fluid. Games with detailed animation dont give it away but you can notice this in some open world games where i would assume navigation is baked mostly.

As for the question, i would recommend you to go check out Kromster's answer on a list of navmesh generating algorithms.

Also check out The AI Systems of Left 4 Dead of which the examples are a part of. Many more interesting topics covered

Good Luck.

Answer 2

there are many ways, why not just make it local to the player, make a small grid that follows the player and checks under each intersection whether or not its transversable, like is there a floor there and do a ray cast to see if there is a wall/building on any upcoming side..

Answer 3

This is a problem I've seen everywhere. The trick is "separation of concerns". "Say what?", I heard you think. What is displayed on the the screen is NOT what the "data structure" is. Keeping the visuals separate from the data to construct the visual is important. Doing so will always "future proof" your game when new underlying software versions are released.

Build a data structure (aka: model) that will represent your gaming world. Then construct a "view" of the data structure model. If you want to change the world from a checker-board grid to a hexagonal grid, the data structure (model) remains the same, but the display will "paint" (render) a different view.

Answer 4

Make an double array. And then if an object/objects are inpassable, have a methode to tell the array that position is notpassable. When an AI try to move they will look at the double array and see if it is passable.