Generating a NavMesh from a Terrain (Partial Code Available)

I have started looking into 3d Pathfinding and am intrigued with the navmesh concept of doing this. I'd love to learn about this style of 3d pathfinding....

To start I have been reading about how to generate a navmesh. Seems this can be done by hand in a 3d program, and it can also be done via script...as it seems Alien's Pathfinding project is capable of. I am trying to start off at the extreme basics... and came across this forum thread during my search:

http://forum.unity3d.com/viewtopic.php?t=22340&highlight=navmesh

In it... dreamora states this...

I am able to see how one would go about extracting the height map and creating a new collection of verticies.... but they mention how to create the triangles from it.... this part I do not understand. Are there some resources I could consult for generating a navmesh from a collection of verticies defined by the terrain's heightmap?

Is it possible just to define the verticies... and then call the Optimize() function? Or must triangles already exist prior to this?

http://unity3d.com/support/documentation/ScriptReference/Mesh.Optimize.html



Thanks in advance,
Cheers

 

The triangles are just generated in a structured way.

That means you do the same thing as you would do with pixels that you use to fill up the "image", doing it pixel by pixel.
Just in your mesh such a pixel are 2 triangles.

If you generate the vertices "line by line" you can easily calculate the vertex indices as they are i, i+1, i+verticesPerLine, i+1+verticesPerLine. with these 4 vertices you can generate the current quad.

you do that for the first numberOfLines-1 lines, that will generate the whole grid


This gives you the basic grid on top of the terrain.

I know above numbering might not make sense straight in the head, thats why I would recommend to draw it on a paper with a something like 6x6 quads, writting in the vertex indices


The mesh optimize function then potentially could be used afterwards. But I don't know how well it works as I've never tested it really.

 

Thanks for your help... figuring out what vertex I should be referencing to make the triangles would have been a nightmare (it almost was anyways lol).

I now have a mesh generating... (yay!)

My problem now is... I often get this error...

and this error always follows it (no doubt because the mesh wasn't properly setup..

What is the best way to make a navmesh of a terrain? Can an entire terrain be done? I have tried shrinking the dimensions of my terrain....and even counted the verticies.... I am not sure I'm passing the pre set out limit..... has anyone seen this before?

Thanks again in advance.

 

Hmm ok I've been tinkering.....

I managed to make the terrain size 100 x 100 and was able to generate a flat plane mesh over it....

For some reason when I use the line...

Code (csharp):

1. float[,] heightMap = Terrain.activeTerrain.terrainData.GetHeights(0, 0, Terrain.activeTerrain.terrainData.heightmapWidth,
2.                                                                             Terrain.activeTerrain.terrainData.heightmapHeight);

It throws the errors I posted above. Now I'm realizing that my heightmap must be done improperly.... as the heighs are all 0.0 or 0.1 (aka not what is on my terrain's mesh).

This is what I use to snag that... what am I doing wrong?

Code (csharp):

1. static void GenerateNavMesh()
2.     {
3.         //float[,] heightMap = Terrain.activeTerrain.terrainData.GetHeights(0, 0, Terrain.activeTerrain.terrainData.heightmapWidth,
4.         //                                                                    Terrain.activeTerrain.terrainData.heightmapHeight);
5.  
6.         float[,] heightMap = Terrain.activeTerrain.terrainData.GetHeights(0, 0, 100, 100);
7.  
8.         Mesh navMesh = new Mesh();
9.         navMesh.name = "NavagationMesh";
10.         Vector3[] verts = new Vector3[heightMap.Length];
11.         int index = 0;
12.         for (int x = 0; x < heightMap.GetLength(0); x++)
13.         {
14.             for (int z = 0; z < heightMap.GetLength(1); z++)
15.             {
16.                 Debug.Log(new Vector3(x, heightMap[x, z], z));
17.                 verts[index] = new Vector3(x, heightMap[x, z], z);
18.                 index++;
19.             }
20.         }
21.  
22.         navMesh.vertices = verts;
23.  
24.         //fill Triangles
25.         List<int> tris = new List<int>();
26.         int vert;
27.         for (int line = 0; line < heightMap.GetLength(0)-1; line++)
28.         {
29.             for (int i = 0; i < heightMap.GetLength(1)-1; i++)
30.             {
31.                 vert = ((heightMap.GetLength(1)) * line) + i; //current vertex in a linear list
32.                 //generate quad
33.                 //tri 1
34.                 tris.Add(vert);
35.                 tris.Add(vert + 1);
36.                 tris.Add(vert + heightMap.GetLength(1));
37.                 //tri 2
38.                 tris.Add(vert + 1);
39.                 tris.Add(vert + heightMap.GetLength(1));
40.                 tris.Add(vert + heightMap.GetLength(1) + 1);
41.             }
42.         }
43.  
44.         navMesh.triangles = tris.ToArray();
45.         navMesh.Optimize();
46.  
47.         GameObject NavObject = new GameObject();
48.         NavObject.AddComponent("MeshFilter");
49.         MeshFilter Filter = (MeshFilter)NavObject.GetComponent("MeshFilter");
50.         Filter.mesh = navMesh;
51.         NavObject.name = "NavMesh";
52.         NavObject.AddComponent("MeshRenderer");
53.     }

Pseudocode of the method is roughly...

1) Obtain the height of each vertex in the mesh.
2) Populate the Vertex list and assign it to a new mesh
3) Generate triangles based on dreamora's above notes


Any help is appreciated!

Cheers,
DavidB

 

All terrain heights are in fact between 0.0 and 1.0...that's how the data is stored.

--Eric

 

Oh really? Interesting... how would I go about converting these height points into actual verticies for a mesh?

Is there a height factor or something I can multiply with to actually define verticies?

 

TerrainData.size (plus transform.position possibly).

--Eric

 

as for the error you originally ran into: vertices and triangles are short indexed, the max amount of vertices / tris is 65536

As such you are restricted on the precision you can use.

 

Indeed, 129x129 is the max you can use and still get an exact copy as a mesh. For 257x257, do every 2nd point, and so on.

--Eric

 

Interesting stuff!

After hanging in the IRC channel I was also informed of an alternate way to do this... I basically passed a raycaster across a grid pattern to obtain a low res version of the terrain.

Works quite nicely. Now of course this is just the beginning and a very preliminary step towards USING the navmesh... but it's the start I was looking for.

Thanks to everyone who helped... everyone in this thread and of course NCarter from IRC. I appreciate the help this community is willing to give...it definitely sets Unity apart.

Anyways here's the code I have so far. It's rough, largely uncommented and likely could be far more optimized. But in case anyone is in this predicament in the future... they can get a leg up just as I did.

Cheers.

Code (csharp):

1. using UnityEditor;
2. using UnityEngine;
3. using System.Collections.Generic;
4. class NavmeshGenerator : MonoBehaviour
5. {
6.     [MenuItem("Terrain/Create Navmesh from Terrain")]
7.     static void RayGenerateNavMesh()
8.     {
9.         int SamplesPerLine = 10;
10.         int LineSamples = 10;
11.         int RayCasterHeight = 1000;
12.  
13.         float X_PerSample = (Terrain.activeTerrain.terrainData.size.x) / (SamplesPerLine - 1);
14.         float Z_PerSample = (Terrain.activeTerrain.terrainData.size.z) / (LineSamples - 1);
15.         float terrainX = Terrain.activeTerrain.transform.position.x;
16.         float terrainZ = Terrain.activeTerrain.transform.position.z;
17.         Vector3 currPos = new Vector3(terrainX, RayCasterHeight, terrainZ);
18.         RaycastHit hitInfo;
19.  
20.         //Iteration Vars
21.         List<Vector3> vertexes = new List<Vector3>();
22.  
23.         for (int x = 0; x < LineSamples; x++)
24.         {
25.             for (int z = 0; z < SamplesPerLine; z++)
26.             {
27.                 Physics.Raycast(currPos, Vector3.down, out hitInfo, Mathf.Infinity);
28.                 //If Normal vs raycast angle is too great (which is what?) then do not add point
29.                 vertexes.Add(hitInfo.point);
30.                 currPos.z += Z_PerSample;
31.             }
32.             currPos.x += X_PerSample;
33.             currPos.z = 0;
34.         }
35.  
36.         //Generate the mesh and set it's verticies to raycasted points
37.         Mesh navMesh = new Mesh();
38.         navMesh.name = "NavagationMesh";
39.         navMesh.vertices = vertexes.ToArray();
40.  
41.         //Link Triangles from vertexes
42.         List<int> tris = new List<int>();
43.         int vert;
44.         for (int line = 0; line < LineSamples - 1; line++)
45.         {
46.             for (int i = 0; i < SamplesPerLine - 1; i++)
47.             {
48.                 vert = (SamplesPerLine * line) + i; //current vertex in a linear list
49.                 //generate quad
50.                 //tri 1
51.                 tris.Add(vert);
52.                 tris.Add(vert + 1);
53.                 tris.Add(vert + SamplesPerLine);
54.                 //tri 2
55.                 tris.Add(vert + 1);
56.                 tris.Add(vert + SamplesPerLine);
57.                 tris.Add(vert + SamplesPerLine + 1);
58.             }
59.         }
60.  
61.         navMesh.triangles = tris.ToArray();
62.  
63.         GameObject NavObject = new GameObject();
64.         NavObject.name = "NavMesh";
65.         NavObject.AddComponent("MeshRenderer");
66.         NavObject.AddComponent("MeshFilter");
67.         MeshFilter Filter = (MeshFilter)NavObject.GetComponent("MeshFilter");
68.         Filter.mesh = navMesh;
69.  
70.     }
71.  
72.     // Validate the menu item.
73.     // The item will be disabled if there is no active terrain
74.     [MenuItem("Terrain/Create Navmesh from Terrain", true)]
75.     static bool ValidateRayCastMeshConstruction()
76.     {
77.         //return (Selection.activeObject is Terrain);
78.         return Terrain.activeTerrain != null;
79.     }
80. }

Thanks again! (I'll likely be back to ask for more guru advice before I'm done with navmeshes... )

~DavidB

EDIT: Edited some code as I had a mesh generating to an improper size and it could not dynamically detect the terrain 0,0 position.

 

It occurs to me--a bit late--that I actually basically did this with the TerrainObjExporter. It does stuff you don't need, like UVs and saving to .obj format, but the "convert terrain to mesh of arbitrary resolution" idea is there. Well, at least you can see how I did it with just the data and no raycasting; not sure it really matters as long as you get usable results.

--Eric

 

Sorry to revive an old thread but I'm looking into unities AI and like the NavMeshAgents but i want the use to be able to layout objects (TD Style ) and have my AI navigate around the world so cannot use the pre-baked nav mesh,

Did you have any joy setting the nav mesh so that the unity AI can use it?

 

I have the same problem Adam, does anybody have a solution for this ? I'm planning to generate a randomly generated level and need navmesh support for it.

 

*Necromancer*
Since nobody answered in 3 years how, the engine have changed a lot since, I post here how I did it (Tested in Unity 5.6b1)

Code (CSharp):

1.     public void Init()
2.     {
3.         NavMeshBuildSettings settings = NavMesh.GetSettingsByIndex(0);
4.         List<NavMeshBuildSource> buildSources = new List<NavMeshBuildSource>();
5.  
6.         for(int i = 0; i < LevelGenerator.rooms.Length; ++i)
7.         {
8.             Room room = LevelGenerator.rooms[i];
9.  
10.             NavMeshBuildSource s = new NavMeshBuildSource();
11.             s.transform = room.ground.transform.localToWorldMatrix;
12.             s.shape = NavMeshBuildSourceShape.Mesh;
13.             s.sourceObject = room.ground.GetComponent<MeshFilter>().mesh;
14.             buildSources.Add(s);
15.         }
16.  
17.         NavMeshData datas = NavMeshBuilder.BuildNavMeshData(settings, buildSources, new Bounds(Vector3.zero, Vector3.one * 100), Vector3.zero, Quaternion.identity);
18.  
19.         NavMesh.AddNavMeshData(datas);
20.     }

 

Hate to break the necromancers bubble but isn't NavMeshBuilder inside the UnityEditor namespace? And therefore not available in built games?

Which means that the previous answer is still the best to go for...

 

I forgot to specify it, but it's in Unity 5.6 beta which open access to this into UnityEngine, not UnityEditor.

https://forum.unity3d.com/threads/welcome-new-navmesh-features-experimental-preview.438991/

 

Thanks for sharing this. How would this work for dynamically generated terrain? Any help would be greatly appreciated.

 

if you follow the link the navigation panel in unity to the repository there is literally examples of exactly how to have dynamic nav meshes on generated (and modifiable) terrain

https://github.com/Unity-Technologies/NavMeshComponents

 

Thanks for pointing this out for me, I appreciate it. I don't know why my searches came up blank.