Search Unity

  1. Unity 2019.2 is now released.
    Dismiss Notice

Nav Mesh Obstacle carving resulting in very inefficient paths

Discussion in 'Navigation' started by Bennett-Lynch, Aug 9, 2015.

  1. Bennett-Lynch

    Bennett-Lynch

    Joined:
    Oct 11, 2014
    Posts:
    35
    I'm working on a tower defense game where towers can be used to block certain areas of the terrain. I'm using Unity's built-in nav mesh agent/obstacle system, and for the most part everything is working great. However, placing nav mesh obstacles in certain areas is causing the agents to calculate very inefficient paths. The best way I can illustrate this is with a quick video:



    At around 0:19 you can see the huge deviation taken by the agents instantiated after the obstacle was placed. In the navigation view you can also see the vertices that appear to be chosen as primary pathing points.

    Is there anyway I can forcefully optimize these paths to be more natural, or any other recommended way for dealing with this issue? I already have the obstacle avoidance quality set to high on the agents:

     
    Harinezumi and neno1204 like this.
  2. neno1204

    neno1204

    Joined:
    Jun 23, 2015
    Posts:
    14
    This is weird, which version of Unity are you using?
     
  3. Bennett-Lynch

    Bennett-Lynch

    Joined:
    Oct 11, 2014
    Posts:
    35
    5.1.1p1
     
  4. neno1204

    neno1204

    Joined:
    Jun 23, 2015
    Posts:
    14
    Any news?
     
  5. Bennett-Lynch

    Bennett-Lynch

    Joined:
    Oct 11, 2014
    Posts:
    35
    Not really, unfortunately. I tried updating to 5.1.2p3 but it made no noticeable difference.

    I did notice one thing, though. The vertex/point that the pathfinding system is choosing is part of some grid system applied to the entire terrain:





    I thought that maybe I could work around this behavior by making the base terrain "not walkable" and use Unity's primitive 3D objects to create a walkable floor only in certain areas:



    Unfortunately, even after re-baking without the terrain, the same point continues to be used as a primary rerouting location.



    So at this point I'm kind of lost on what to do. I could experiment with trying to shift my entire scene so that my desired walking area falls in the middle of one of the grid tiles, but that seems like a really clunky work-around (if it'd even work).

    Here's a longer video of me just playing around with the nav mesh and agent pathfinding system. Maybe it'll offer some clues to someone more experienced in working with it:



    Points of interest:
    • At 0:20 I place a nav mesh obstacle. Agents who were instantiated and established their path prior to that walk around it perfectly fine. Agents instantiated afterwards use the same inefficient point mentioned before (observable at 0:30).
    • A different issue entirely, but at around 1:40 you can see just creating new nav mesh obstacles is causing agents to freeze up until they find a valid path, even when those obstacles aren't currently in their way. The same issue can be seen around 4:00.

    All-in-all, I'm thrilled that Unity has such an easy-to-use pathfinding system (I really didn't want to have to implement my own A* algorithm), but with some of the issues I've seen creeping up, I'm not sure it'll be a viable solution in the end. If anyone has any advice for how to go about troubleshooting any of these problems I'd be very grateful to hear it.
     
    Last edited: Aug 14, 2015
  6. Shbli

    Shbli

    Joined:
    Jan 28, 2014
    Posts:
    126
  7. Lahzar

    Lahzar

    Joined:
    May 6, 2013
    Posts:
    87
    Right so this is a bug, indeed. It looks like the agent is still trying to use the points on the non-carved navmesh. So it does it all right, but it requests the correct point from the wrong navmesh. Understand?

    Anyways, this might take a while for the unity team to fix. You should both try another pathfinding solution. The asset store is filled with them.

    I can see from your video you are making a grid-based game. So why use a navmesh when you could use a grid-based pathfinding system? Try A*! Go give the A* Project by Aron Granberg, the free version atleast, a try. It WILL solve your problems, and make your project exponentially faster. Every obstacle you place on the navmesh will slow it all down, but blocking a point on an A* grid will just make the grid faster!
     
  8. Shbli

    Shbli

    Joined:
    Jan 28, 2014
    Posts:
    126
    Hey man thanks for suggestion, Oraia Rift is not a grid based game ;) There's just a few puzzle here and there that's about it!
     
  9. Bennett-Lynch

    Bennett-Lynch

    Joined:
    Oct 11, 2014
    Posts:
    35
    Can you elaborate on this? I don't see how you can tell they're trying to use points on the non-carved mesh. From what I can see, they are correctly detecting the carved mesh, but they are simply rerouting through some pre-defined vertices in the overall nav mesh. E.g., I can tell which points they are likely to pick before even placing the nav mesh obstacle:





    If I could "remove" those preferred vertices somehow I suspect it would fix my problem.
     
  10. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    25,842
    Casting rays using http://docs.unity3d.com/ScriptReference/NavMesh.Raycast.html is pretty fast actually, and will at least allow them to see if a direct route is available to override, which could solve the majority of your problems.

    However! this isn't perfect for your needs so you will still want to fire off a bug (with repro project demonstrating it or they might not look at the bug in a timely manner).
     
  11. Lahzar

    Lahzar

    Joined:
    May 6, 2013
    Posts:
    87
    Not an expert, just what I thought. I think there happens a bug around 19 seconds where the newly spawned units think that they are using the original navmesh. I don't know how the unity navmesh works, but I know that most navmeshes begin with some other grid-based pathfinding. The whole navmesh updates when you carve it, but the bug makes your units kind of ignore that or something. So they are asking for the wrong points when asking for a path. Its hard to explain, especially without knowing exactly how the unity navmesh works..

    Again, I would seriously recommend using a grid-based pathfinding system rather than a navmesh for a grid-based game! But if you want to stick with the builtin in navmesh, the best way to solve this is to send a bug report.

    Edit: Even if this is not a grid-based game, I have found that grid-based system works very well. Also there are other NavMesh systems available for free on the asset store!
     
    Last edited: Aug 21, 2015
  12. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    25,842
    I agree, grid A* is the best fit for tower defense (it needs to be super consistent) but ensuring navmesh gets fixed unity's end can't hurt.
     
    Lahzar likes this.
  13. Bennett-Lynch

    Bennett-Lynch

    Joined:
    Oct 11, 2014
    Posts:
    35
    Appreciate the replies, guys. Will go ahead and submit a bug report, just wanted to make sure it wasn't some well-known issue first. (I'll also consider checking out an A* approach later on if I'm not happy with this.)
     
    Last edited: Aug 21, 2015
  14. Shbli

    Shbli

    Joined:
    Jan 28, 2014
    Posts:
    126
  15. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    25,842
    No, they're not.
     
  16. Shbli

    Shbli

    Joined:
    Jan 28, 2014
    Posts:
    126
    This bug have driven me crazy, I do not mean to insult anyone. But being honest, the support isn't good for "Pro" users.

    Maybe they are still looking into my case, but getting no reply for a week look like it is sinking and ignored. Usually at least they send me an email "We are able to reproduce your bug ...", which means it was received by them.
     
  17. hippocoder

    hippocoder

    Digital Ape Moderator

    Joined:
    Apr 11, 2010
    Posts:
    25,842
    Which bugs are they, can you list them?

    In addition a lot of staff went on holiday at different times in the last month but should be back now ish as far as I know. Are you including repro scenes?
     
  18. Shbli

    Shbli

    Joined:
    Jan 28, 2014
    Posts:
    126
    It's one bug, the same one I have found a workaround for, and it will help the OP, check the link.

    I don't like to send lots of bugs, I only sent 3 in my 20 months subscription and I make sure I attach a very clear reproduceable project (In this case, a video is also attached).

    Anyways I found the workaround. I hope I also helped the original poster. That's why I posted for him here ...
     
  19. Bennett-Lynch

    Bennett-Lynch

    Joined:
    Oct 11, 2014
    Posts:
    35
    Ah wow, thank you! I wasn't even sure what those white lines were tied to or supposed to represent, but lowering the voxel size definitely had an effect:



    That appears to be as small as I can get them. It's still causing some minor rerouting inefficiency, but it's not nearly as drastic as before. I'll play around with it some more and see if I can fine-tune it.

    I suspect I'll probably still need to implement some kind of A* algorithm eventually if I really want to optimize routing/performance, but this will at least suffice for now while I focus on other gameplay elements.

    Thanks for the tip!
     
  20. Shbli

    Shbli

    Joined:
    Jan 28, 2014
    Posts:
    126
    Galde I'm able to help, this made me go crazy also, hahaha ;)

    I'm happy for you now
     
  21. sysmaya

    sysmaya

    Joined:
    Nov 30, 2013
    Posts:
    14
    The magic in NavMeshAgent is adjust Voxel Size !!