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

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:
    25
    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:

    hertz-rat likes this.
  2. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    3,356
    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:
    25
    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:
    3,356
    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:
    3,356
    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:
    25
    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)
     
    hertz-rat likes this.
  7. wildframemedia

    wildframemedia

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

    wildframemedia

    Joined:
    Feb 13, 2013
    Posts:
    25
    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
     
  9. wildframemedia

    wildframemedia

    Joined:
    Feb 13, 2013
    Posts:
    25
    DwinTeimlon likes this.
  10. hertz-rat

    hertz-rat

    Joined:
    Nov 3, 2019
    Posts:
    71
    I'm not sure I have the exact same issue, since that bug reports includes a console error; but my navmesh agents fail to find any path if the path is too long. I did not realize it was due to finding a partial path

    Did you ever fix this for yourself?

    Unity 2019.3.9
     
    Last edited: Apr 20, 2020
  11. Whipexx_DigitalSun

    Whipexx_DigitalSun

    Joined:
    Aug 8, 2017
    Posts:
    17
    I stopped using the vanilla navigation and I'm now using the experimental one with a custom Agent, I've encountered no game breaker problems with this approach so far.

    Are you using the vanilla navigation + agent? Or are you using the NavMesQuery from the AI experimental package?
    Both have an issue with long paths, although the NavMeshQuery can handle paths much longer and more complex than the default navigation. The other key factor is that the vanilla navigation fails because of a design compromise, citing a response from unity support "... there is a limit of 4096 nodes that can be traversed during a path search and this value cannot be changed." While the NavMeshQuery fails in some instances but its considered an issue and is what's being (hopefully) actively worked on.

    If you are using the vanilla navigation and don't feel confident switching to the experimental package there are some workarounds that might do the trick (like chaining multiple partial path requests), but none can guarantee that the path will work.
     
  12. hertz-rat

    hertz-rat

    Joined:
    Nov 3, 2019
    Posts:
    71
    My hesitation with the experimental nav system is that I assume it will change significantly before being fully released. I don't want to have to rewrite a bunch of systems that depend on it in 3 months.

    That said, how different is it? What is different about it?
     
  13. Whipexx_DigitalSun

    Whipexx_DigitalSun

    Joined:
    Aug 8, 2017
    Posts:
    17
    It is very different, it does give you the tools to calculate a path, but you'll probably need to either use some code from the nordeus demo or resolve the path yourself from the polygon list. The biggest difference is the agent, you don't have an agent that works you'll need to build it yourself (or addapt one from somewhere else).
    I made the swap because I was already thinking on building my own agent, but if you are not in a hurry and don't need an agent with special features I would wait.
     
    hertz-rat likes this.
  14. Dinamytes

    Dinamytes

    Joined:
    Nov 3, 2016
    Posts:
    51
    The smaller the Tile size the more occasionally the funneling used in nordeus demo will not work because the path is not optimal,, were you able to get around it?

    Photo of not straigth path
     
    Last edited: Apr 25, 2020
  15. Whipexx_DigitalSun

    Whipexx_DigitalSun

    Joined:
    Aug 8, 2017
    Posts:
    17
    I have not. I haven't actively tried to solve it either, as even though the path is sub-optimal it still is a valid path.
    However, I'm planning on replacing the example funnelling for a custom solution that is better suited for my game, since I have large numbers of units following a path at the same time.