Search Unity

Tree Avoidance on Very Large Terrains

Discussion in 'Navigation' started by Mister-Royzo, Apr 16, 2015.

  1. Mister-Royzo

    Mister-Royzo

    Joined:
    Apr 2, 2013
    Posts:
    6
    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.
     
  2. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,487
    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.
     
  3. Mister-Royzo

    Mister-Royzo

    Joined:
    Apr 2, 2013
    Posts:
    6
    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.
     
  4. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,487
    Last edited: Apr 21, 2015
    Mister-Royzo likes this.
  5. Mister-Royzo

    Mister-Royzo

    Joined:
    Apr 2, 2013
    Posts:
    6
    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.
     
  6. Jakob_Unity

    Jakob_Unity

    Unity Technologies

    Joined:
    Dec 25, 2011
    Posts:
    269
    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).
     
  7. Jakob_Unity

    Jakob_Unity

    Unity Technologies

    Joined:
    Dec 25, 2011
    Posts:
    269
    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.
     
  8. Mister-Royzo

    Mister-Royzo

    Joined:
    Apr 2, 2013
    Posts:
    6
    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.
     
  9. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,487
    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.
     
  10. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,487
    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.