Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Calculating paths to multiple destinations at once (i.e. Dijkstra's algorithm)

Discussion in 'Navigation' started by Waz, Oct 13, 2019.

  1. Waz

    Waz

    Joined:
    May 1, 2010
    Posts:
    287
    Distance to multiple destinations is an essential input to decision making in AIs to choose the best destination, not merely find the way to one pre-selected destination.

    NavMesh doesn't seem to be able to do this except by calculating the whole path, from scratch, for each destination, which has linear complexity with the number of destinations. It has all the data necessary to implement Dijkstra's algorithm expanding out through the polygons until all destinations are reached, which has complexity the same as the worst case for finding the distance via A* to just the most distant single destination.

    Am I missing something, or is this really not possible with NavMesh? It certainly has all the information needed to run the algorithm, and is even a simple implementation compared to the A* algorithm that is supplied, but from what I can tell, the NavMesh stuff isn't on GitHub and there's nothing beyond NavMesh.CalculateTriangulation (which loses all polygon connection information such that it would have to be reconstructed) for processing the data outside the system.
     
  2. Abbrew

    Abbrew

    Joined:
    Jan 1, 2018
    Posts:
    417
    I've been trying to solve the problem myself. There is a way to "reuse" some degree of calculations efficiently using the NavMeshQuery API, namely its MapLocation, BeginFindPath, UpdateFindPath, EndFindPath, and GetPathResult methods. If you have a grid of potential destinations, call MapLocation for each of them and store the resulting unique NavMeshLocation in a NativeHashMap. Call BeginFindPath on each of the unique NavMeshLocations inside of an IJobNativeMultiHashMapVisitKeyValue. The rest is up to you, but it involves calling UpdateFindPath, EndFindPath, and finally GetPathResult later on in other jobs. Finally, once you have a NativeSlice of PolygonIds, retrace the path using Unity's PathUtils class at https://github.com/Unity-Technologi...ressTesting/Assets/Scripts/Utils/PathUtils.cs. You can modify it so that it accepts an extra parameter called originalEnd::float3.The path will continue to the final polygon that several destinations share. From the shared final polygon trace a small path to the unique destination.
     
  3. Waz

    Waz

    Joined:
    May 1, 2010
    Posts:
    287
    I think you're saying "Use more cores to solve the problem", which doesn't help if the cores already have better things to do. Coupled with the bugs associated with NavMesh tile corners, I'm wondering if this code is even worth using, or whether there is a more fully implemented polygon-based A* available?
     
  4. Yandalf

    Yandalf

    Joined:
    Feb 11, 2014
    Posts:
    491
    When default Unity's Navmesh solution isn't enough people seem to flock towards Aron Granberg's A* solution. Can't speak from personal experience, but people seem to love it. Maybe see if that allows you to do what you want?