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

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.

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?

• When do you expect to generate the mesh? Compile-time, Load-time or Real-time? We struggled with this same problem and ended up deciding it was overkill for our scenario (load-time generation in a top-down shooter without overlapping paths), we decided to go with a quad-tree based approach. This worked well enough for us. So I guess what I'm asking is, do you really need this, or what is the easiest solution that meets your initial requirements because this can be a time-sink. If you do manage a good solution I'd love to hear how you fixed it. Mar 15, 2016 at 9:24
• @Niels I plan on pre-building, then loading it into the game. Mar 16, 2016 at 3:11
• Then the time consumption shouldn't be too much of an initial drawback, since the player wont be waiting on it. You can always optimize after you've got something working. Mar 16, 2016 at 7:54
• How big is your level? We've used recast on large games and had no problem - you simply need to tune the tiie values, etc. Apr 5, 2016 at 4:21
• I think you're missing the "gridded" bit. Which isn't quite the same as the tiles that recast uses. I'm trying to figure out how to repurpose recast to do such a thing. But it's been mostly a nightmare. Apr 5, 2016 at 7:08

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.

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

• A good idea, but not a viable one for the end goals. I need to support a large world, and allow AI to navigate from one side of a continent to another side of the continent. That much is doable but I'd need to have a fixed nav grid in place to generate the higher nodes. May 15, 2016 at 5:59

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.

• While separating concerns is indeed a good practice in general, this answer is currently light on details specific to answering the question (ie. how to generate a suitable grid-based pathfinding model from a given set of world geometry). You're quite right that whatever this model is, it should likely be separate from the data used to draw the level, but to answer the question we still need a method to generate this pathfinding model. Jul 9, 2017 at 18:12

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.

• The method to populate this array is the hard part. ;) Mar 27, 2017 at 14:07