Search Unity

  1. Unity 2019.2 is now released.
    Dismiss Notice

NavMesh is unable to calculate a path from A to B (and no one seems bothered by it)

Discussion in 'Navigation' started by wildframemedia, Oct 31, 2019.

  1. wildframemedia

    wildframemedia

    Joined:
    Feb 13, 2013
    Posts:
    19
    I've been using NavMesh + NavComponents for a while and due to some requirements (and poor integration of the base NavMesh with the components) of the game I'm building I ended up needing to modify a few things and use a couple other in ways that where probably never meant to be. A couple weeks ago, after investigating an issue I found that if you have a path long enough CalculatePath returns a partial path. Not ideal, but you can easily find a workaround by doing recursive pathfinding requests and having a custom navAgent (you need to, as there seems to be no good way to assign an agent a custom path), or so I though.
    It turns out that while it is true that you can append several partial paths to build a complete path, since the search graph for any CalculatePath is only expanded so far it has no guarantee that it'll be able to get closer to the destination; that means that if you fall into a big enough dead end you'll get stuck there for ever; this also happens with SetDestination.
    So yeah, NavMesh isn't able to calculate a path from A to B if you have a map big/complex enough.


    For anyone wondering A* Project properly calculates a path, but in terms of raw power it's much slower that the built in NavMesh, and it might not be enough (I have a big changing map with lots of agents and overlapping navigation, so worst case scenario).


    I have an open issue on FogBugz, but I don't really expect them to actually fix this:
    https://fogbugz.unity3d.com/default.asp?1192502_c8besl5lnte16ii5
     

    Attached Files:

  2. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,429
    The experimental api's might let you get past this. Partial paths from the higher level api's are I think often arbitrary cut for performance reasons. Limited buffers and iterations. The lower level experimental stuff lets you set the buffer size and you have to handle path iterations yourself and you have to straighten them also, it's a crapton more work. But you could test just the pathfinding to see if it actually does let you circumvent this before doing all of that. It should do what recast does, keep returning in progress until it has the full path if one actually exists.
     
  3. wildframemedia

    wildframemedia

    Joined:
    Feb 13, 2013
    Posts:
    19
    Thanks a ton for the recommendation, I was unaware of NavMeshQuery and the other stuff. I've been testing it on the scene where I isolated the issue and while it performs significantly better than NavMesh regarding the issue I can't manage to make it work for really long paths.
    I get a weird situation where the NavMeshQuery itself is successfull, but FindStraightPath fails, any insight on what might be causing this?
     
  4. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,429
    I'm assuming you are using the FindStraightPath from the nordeus demo? Or some github repo that did so.

    In any case I can't think of how that would fail. If PathQueryStatus is success, not success |partial or success | out of nodes, then I would think it would work. You might glance at the code that was ported from which is in https://github.com/recastnavigation/recastnavigation. I can't remember the exact source files but it should be a fairly straightforward port of the path straightening that is there.
     
  5. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    2,429
    Or actually before that you might try calling GetPortalPoints on the query using the last two polygonids just to verify it actually found the full path.
     
  6. wildframemedia

    wildframemedia

    Joined:
    Feb 13, 2013
    Posts:
    19
    That is correct, I'm using this script from the austin presentation repository: https://github.com/Unity-Technologi...ressTesting/Assets/Scripts/Utils/PathUtils.cs

    I've tried debugging the process and find it quite strange. It kind of seems to be related to length. I have a setup where I get a path that has ~1300 portal points and it works properly, but then moving either the start of the destination of the path a bit makes a portal point along the way fail (in this instance the 475). I'll keep investigating this and I'll update if I find anything that might indicate what's wrong in my example.


    On another topic, I've got confirmation that the limit for a single CalculatePath is determined not by frame time but by a limitation of exploring 4096 nodes; so at least that makes it more reliable in the sense that it will be consistent between executions and systems. (doesn't solve the issue, but it might be nice to know for anyone wondering)
     
  7. wildframemedia

    wildframemedia

    Joined:
    Feb 13, 2013
    Posts:
    19
  8. wildframemedia

    wildframemedia

    Joined:
    Feb 13, 2013
    Posts:
    19
    I've discovered that the issue is probably not related to the path straightening or the GetPortalPoints method it looks like the path is not being properly calculated at the end of the process. I've since opened an issue, for anyone interested here is the report: https://fogbugz.unity3d.com/default.asp?1197062_vu8555f45apq1qh1