Tree Avoidance on Very Large Terrains

Dear sir or madam,

I'm experimenting with a 3 km² terrain, with 300,000 trees, which I managed to get running very smoothly thanks to Unity's billboarding system.

Upon generating a nav mesh -which took very long- I found myself in the company of a very generous 179 MB of navigation data which I may very conservatively say is 'somewhat unwieldy'.

I removed all trees by way of Mass Placing an astonishing 0 trees without keeping the existing ones, re-baked the nav mesh and then found myself with a delightfully modest 4 MB of navigation data. Splendid.

My next step would have been to have non-player characters avoid trees via local navigation by adding Nav Mesh Obstacle components to the tree prefabs. Surprisingly the nav mesh agent cheerfully ignores all trees after doing so.


Some casual reading of related literature has implied that with the exception of colliders, no components make it to the actual tree instances. Is that true?


What do the bright fellows of the Unity Community think about this predicament and how would they themselves tackle navigation on such a very large complex terrain?


Thank you for your time.

 

There is something horribly wrong with how they handle trees. creating a navmesh for 6 1km terrains with a decent number of trees ate up 8gb during generation. I just stopped at that point.

I created meshes from my terrains, and then placed capsule colliders where my trees are, and it worked fine without the crazy memory usage.

I suspect that they use hole punching for trees, and that's actually the culprit. Or something that's not just normal geometry, because normal geometry doesn't bloat ram or the nav data like I see with trees.

 

The one time I patiently waited for the nav mesh to be generated with the trees still on it, it indeed created a diamond shaped hole for every tree on the mesh. That's clever and it works well for small terrains but it scales poorly.

I have a lot of trees so I'm not sure if it's feasible to place a capsule collider on every single tree. I guess I can try it out just to see how it performs. My current battle plan is to cache all the locations of my trees in a spatially accessible way like a grid so that I can figure out which trees are close to the player and then place colliders on them from a pool of colliders.

I will report back once I've had time to try these things out and share my findings.

 

The capsules I placed were temporary, I remove them as soon as the navmesh generation is complete.

You might take a look at some code I posted in another thread for dynamically placing colliders on trees (and other objects). It uses a spatial grid.

http://forum.unity3d.com/threads/terrain-culling-and-colliders-is-hosed.310594/

 

Thanks, that sounds like exactly what I was going to build. You might have saved me a bunch of work there snacktime.

More people should know about this. Your thread did not show up when I googled the matter. I will spread the gospel.

 

A bit late for the party - yes adding navmeshobstacle to trees in makes sense if the trees are sparse enough to have navigation go through.

Colliders on trees are handled in a special way - there are no other components that get instantiated on terrain in a similar way. Unfortunately this means some extra work is required for placing obstacles.
You'll need to keep a budget of instances and place the obstacles only where they make a visible impact - e.g. close to camera or player character - below is a proof of concept script that decorates the nearest trees with a prefab.

Code (csharp):

1.  
2. // DecorateNearbyTrees.cs
3. using UnityEngine;
4. using System.Collections.Generic;
5.  
6. // Decorate nearby trees on terrain by prefab
7. // Decorates the closest "count" trees on "terrain" with a "decorationPrefab" each
8. public class DecorateNearbyTrees : MonoBehaviour {
9.    public Terrain terrain;
10.    public GameObject decorationPrefab;
11.    public int count = 10;
12.  
13.    // Info for sorting trees spatially
14.    struct TreeData {
15.      public float x,y,z;
16.      public int id;
17.      public Vector3 pos { get {return new Vector3 (x,y,z);}  set {x = value.x; y=value.y; z=value.z;}}
18.    }
19.  
20.    Vector3 terrainSize;
21.    TreeData[] treeData;
22.    List<Transform> decorationPool = new List<Transform>();
23.  
24.    static float localSearchPosX;
25.    static float localSearchPosZ;
26.  
27.    void Start () {
28.      if (terrain == null || decorationPrefab == null) {
29.        Debug.LogError ("Terrain and decorationPrefab required");
30.        return;
31.      }
32.  
33.      var data = terrain.terrainData;
34.      terrainSize = data.size;
35.  
36.      // Sample tree info for spatial ordering
37.      int treeCount = data.treeInstanceCount;
38.      treeData = new TreeData[treeCount];
39.      for (int i = 0; i < treeCount; ++i) {
40.        TreeInstance t = data.GetTreeInstance(i);
41.        treeData[i].pos = t.position;
42.        treeData[i].id = t.prototypeIndex;
43.      }
44.  
45.      // Construct pool of GO's to use for decorating trees
46.      for (int i = 0; i < count; ++i) {
47.        GameObject go = (GameObject)GameObject.Instantiate (decorationPrefab, Vector3.zero, Quaternion.identity);
48.        decorationPool.Add (go.transform);
49.      }
50.    }
51.  
52.    // Sort trees by 2D distance to localSearchPos
53.    static int TreeDistance2DCompare (TreeData a, TreeData b) {
54.      float dxa = a.x - localSearchPosX;
55.      float dza = a.z - localSearchPosZ;
56.      float dxb = b.x - localSearchPosX;
57.      float dzb = b.z - localSearchPosZ;
58.      float daSq = dxa*dxa + dza*dza;
59.      float dbSq = dxb*dxb + dzb*dzb;
60.      if (daSq < dbSq) return -1;
61.      if (daSq > dbSq) return 1;
62.      return 0;
63.    }
64.  
65.    void Update () {
66.      if (treeData == null)
67.        return;
68.  
69.      // Prepare for sort callback
70.      Vector3 worldPos = transform.position;
71.      localSearchPosX = worldPos.x / terrainSize.x;
72.      localSearchPosZ = worldPos.z / terrainSize.z;
73.  
74.      // Sort is slow and allocates GC memory (aux storage for the non-recursive qsort impl.)
75.      // Ultimately one should use a 2D spatial hash lookup for better performance
76.      System.Array.Sort (treeData, TreeDistance2DCompare);
77.  
78.      for (int i = 0; i < count; ++i) {
79.        Vector3 treePos = Vector3.Scale(terrainSize, treeData[i].pos);
80.        decorationPool[i].position = treePos;
81.      }
82.    }
83. }
84.  

In this case the decoration could be a prefab with a NavMeshObstacle component (capsule).

 

Is this using Unity5 ? 8Gb sounds like a problem. NavMesh building is done mostly local - and memory requirements should be reasonable. please report a bug on this.

 

I very much appreciate the reply, especially the fact that you took the time to write some example code.

Sounds like the pool solution makes the most sense. Assured that my approach was not overcomplicating things I feel that I have enough input to implement the solution.

Thanks again Jakob_Unity and snacktime for sharing your experience. I hoop the Google crawler is kind to us and more people find this thread.

 

I tried replicating the issue in a separate project, one that's not 3gb, but of course it works fine there. The only obvious difference being that instead of 100 terrains I used 4. I increased the detail on the 4 terrains to have around the same number of trees and static mesh detail objects, but couldn't trigger it.

I'm going to do some more testing, don't really want to submit a bug report until I get it narrowed down a bit.

 

Ok so narrowed it down a bit. The memory bloat happens when you have height mesh enabled. Memory use stays relatively constant until it hits the storing tiles phase, and there it skyrockets.