Search Unity

  1. Unity 2019.2 is now released.
    Dismiss Notice

Streaming Navmesh Data to Custom Pathfinding System

Discussion in 'Navigation' started by VengeanceDesign, Aug 9, 2016.

  1. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    Hi everyone,

    For pathfinding in Unity, I need to write a AI solution that is more sophisticated than what Unity supports. My plan is to load the navmesh data into a parallel thread and perform all my calculations there. The issue is with dynamic obstacles. I'm wondering if anyone knows whether the triangulation returned by NavMesh.CalculateTriangulation() will have the triangles updated to reflect the cuts made in the mesh by the obstacles, letting me "stream" updated navmesh data to the thread, or if I'll have to roll out my own dynamic obstacle system?

    - Thanks
     
  2. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
    I read "streaming" and "navmesh" and "custom" and I wonder: why don't you just roll your own?

    Unity navmesh is very limited, you'll hit the limit very quickly. Everyone i know who makes money deving games use Astar which they rewrote parts of to suit their need.
     
  3. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    I am planning to use the navmesh system to give me a data structure representing the walkable areas, and I will use my own algorithm for getting the path since my AI needs to consider things like cover. However there is the issue that the navmesh may be updated by navmesh obstacles moving about, so I hoped someone knew if NavMesh.CalculateTriangulation() will account for the moved obstacles and give me the updated walkable areas.
     
  4. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
  5. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    Thanks for that link. I looked at the panda behaviour script that was meant to have a cover system demo. Unfortunately the demo was super buggy, with something causing the rendering to spike to 99% of the CPU, for a simple 2D scene. I'll just have to mess around with the NavMesh calculate triangulation thing and see if it updates based on the obstacles.
     
  6. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
  7. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    The triangulation gives me the topology that the navmesh agents would use for navigating. I'm running the pathfinding on a parallel thread so I can't do any raycast calls (unity only lets you call it's API from the main thread in most cases), and also navmesh raycasts are actually not a good way to sense the environment I think. I've tried to approximate clever AI using raycasts .I think that pandabt shooter demo uses the same trick. I suspect that what their AI does is keep doing raycasts towards the player and keep track of the last position where there they did a navmesh raycast to where the player is and the raycast hit a obstacle, and treat that position as cover. I had similar tricks, and I found that apart from the stupid things the AI can do using raycast based AI, the solution isn't scalable. The CPU costs start to add up. I really want to move my pathfinding off the main thread so I can have much more agents doing much smarter things.

    I'll bug Eric about the glitch when I get time to open up Unity again and record the profiler.
     
    laurentlavigne likes this.
  8. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
    I ran a test and yes CalculateTriangulation updates the mesh on carving but it takes a little while. When you move the carving the mesh goes back to baking state and then after navmesObstacle.timeToStationary, the carving shows up. There is no API to tell you the navmesh is being updated so it's up to you to lock the triangulation if you want that.
    Code (CSharp):
    1. using UnityEngine;
    2. using System.Collections;
    3.  
    4. public class TestNavmeshTriangulation : MonoBehaviour {
    5.  
    6.     void Start()
    7.     {
    8.         NavMesh.pathfindingIterationsPerFrame = 100000000;
    9.     }
    10.  
    11.     Vector3[] normals;
    12.     void OnDrawGizmos()
    13.     {
    14.         var t = NavMesh.CalculateTriangulation ();
    15.         Mesh mesh = new Mesh ();
    16.         mesh.vertices = t.vertices;
    17.         mesh.triangles = t.indices;
    18.         if (normals == null || normals.Length != t.vertices.Length) {
    19.             normals = new Vector3 [t.vertices.Length];
    20.             for (int i = 0; i < t.vertices.Length; i++)
    21.                 normals [i] = Vector3.up;
    22.         }
    23.         mesh.normals = normals;
    24.         Gizmos.DrawMesh (mesh);
    25.     }
    26. }
    27.  
    Thanks for bringing this to my attention, it makes sense to move path finding to a separate thread. Have you already implemented your pathfinding? I'm curious to see the performances compared to unity navmesh, a simple test show 1000 agents @ 3ms with 1 setdestination/frame.
     

    Attached Files:

    Last edited: Aug 26, 2016
  9. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    Thanks for taking the time do do that test. I think that what I'd have to do is take all objects with NavmeshObstacles and rigidbodies and add a script to track whether they are moving. I'd rather just tell the level designer to avoid placing dynamic objects for now. My algorithm for baking the custom data structure takes like 20+ minutes anyway so even if I know when the triangulation is rebaked I can't afford to rebuild my own version of the Navmesh.

    My first step before I worry about parallelization is to make sure my pathfinding works on the main thread. The ultimate goal is to do NavMesh pathfinding properly but right now I'm more interested in a cheap approximation that I can implement quickly. Once the algorithm is parallelized and done properly (expect to wait a while for that) I can show you a performance measure.
     
    laurentlavigne likes this.
  10. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
    How many agents will you have and what type of AI runs them?
     
  11. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    The number of agents isn't known for certain because the amount of intelligence that the agents can exhibit and the how the intelligence works within the gameplay will affect the number of agents, but my estimate is 64 intelligent agents max (too many intelligent agents, assuming it doesn't overburden the CPU, can lead to the AI tripping over each other's feet). The AI will support stuff like cover usage and flanking.The movement is what distinguishes the AI. It's key interaction with the players is just killing them.
     
  12. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
    64? - that's it? Man, you're over burdening your brain with remaking the wheel. I have 300 agents with cover before getting a hiccup and that's on an old mac, I even benchmarked some horribly unoptimized GOAP and got 400 agents.
     
  13. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    As I noted, it isn't just a performance concern. It's also about not filling the map with AI who then get in each other's way and have conflicting objectives.
     
  14. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
    I skipped that line "The movement is what distinguishes the AI". Conflicting objectives get resolved with locks assigned to targets so I guess it's more involved, making your agents path their movements by anticipating the other's path like humans would. This is a cool one, would love to see your tests when you can show anything.
     
  15. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    Another way to avoid AI getting in each other's way is a heatmap. That would be useful for area occupation algorithms, where you want for several AI groups to carry out an objective but without bunching up. Though I'd rather limit complexity and just avoid anti-flocking code, since this is for a group project and as much as I enjoy going all out I do realize that my first priority is to try and deliver something that will shoot at the players and make some kind of effort to not die. I'll gladly show tests when the AI is getting going. One early way I may test the AI is with a "killhouse" test where the AI must move through a cluttered environment, killing any targets they encounter. It is meant to be completely unscripted. The AI are told to move from A to B and everything between A and B is nothing but the AI assessing the situation and taking action.
     
  16. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
    I've never seen heatmap used with a navmesh, do you "color" each polygon?
     
  17. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    Well that is the simplest way. You could do more fine grained stuff. A friend of mine suggested that I treat the navmesh as a mesh, texture it and use the mapped texture grid for the heat map.
     
  18. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
    Grid sounds easier and maybe faster.
     
  19. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    A grid would be faster, yes. Easier? I'm not so sure. You face two problems: First, how to break up the triangle and work out which squares it covers. Secondly, how will you support differing costs for triangles that are overlapping vertically?
     
  20. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    2,062
  21. VengeanceDesign

    VengeanceDesign

    Joined:
    Sep 7, 2014
    Posts:
    84
    It's a pro part of A* so it must be a pain to do. Since I'm doing my own pathfinding I can't patch in their solution, so I'd rather avoid the layered grid approach.
     
  22. MaxFunity

    MaxFunity

    Joined:
    May 7, 2018
    Posts:
    1