Search Unity

  1. Check out the Unite LA keynote for updates on the Visual Effect Editor, the FPS Sample, ECS, Unity for Film and more! Watch it now!
    Dismiss Notice
  2. The Unity Pro & Visual Studio Professional Bundle gives you the tools you need to develop faster & collaborate more efficiently. Learn more.
    Dismiss Notice
  3. Improved Prefab workflow (includes Nested Prefabs!), 2D isometric Tilemap and more! Get the 2018.3 Beta now.
    Dismiss Notice
  4. Improve your Unity skills with a certified instructor in a private, interactive classroom. Watch the overview now.
    Dismiss Notice
  5. Want to see the most recent patch releases? Take a peek at the patch release page.
    Dismiss Notice

Connecting "chunks" of navmesh

Discussion in 'Navigation' started by joshcamas, Apr 16, 2018.

  1. joshcamas

    joshcamas

    Joined:
    Jun 16, 2017
    Posts:
    321
    Hello friends.

    I have a big world, so the world is split into scenes. I am using the new NavMeshComponent stuff to auto build a navmesh asset per scene. However, these of course do not connect automatically when the world is loaded...

    Here is an example:


    A simple navmesh link or an offmesh link won't work of course... and this systems needs to be automatic, since I have a lot of scenes.

    Any thoughts? Should I just buy an addon instead of trying to use Unity's unfinished navmesh systems?

    Josh
     
  2. joshcamas

    joshcamas

    Joined:
    Jun 16, 2017
    Posts:
    321
    I guess one possibility would be to load the navmesh as a mesh, and then stitch the vertices to an already existing navmesh... a sort of "master navmesh".

    However there seems to be a strange problem with gaps between built navmeshes:

    The solution of course is to make the volumes just slightly bigger, but that results in overlapping navmeshes, which means combining them as meshes would be harder to manage.

    Turns out this gap problem is specifically for terrain colliders, and not normal colliders...
    So this part is a Unity bug. Probability of Unity fixing? 5%

    If this ever gets fixed, then technically all that would need to be done is merging the navmesh (converted into a mesh), and also merging overlapping vertices, and then converting that into an actual navmesh. Every time a navmesh is added or removed...
     
    Last edited: Apr 16, 2018
  3. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    1,780
    Use a different approach. Build the intelligence into your agents. Or just generate meshes from the terrains and build your navmesh using that.

    I have a complex system of navmesh surfaces and moving platforms and other surfaces that don't meet up exactly either. I use the former approach but generating meshes is probably simpler.
     
    joshcamas likes this.
  4. joshcamas

    joshcamas

    Joined:
    Jun 16, 2017
    Posts:
    321
    I now realize that there really is no simple solution to this problem. If a mesh overlaps onto another chunk (happens all the time) connecting it to the other chunk wouldn't be easy. It looks like I'm going to have to look into generating navmeshes as the game plays, which sounds extremely not fun, since my world loads as you play. But it looks like it may be the only way to go...

    It looks like this means every time a chunk is loaded / unloaded the entire map will need to be regenerated... One way to slightly speed this up would be to cache the sources collected per chunk, and also if the game is loading multiple chunks at once wait until they're all loaded to start generating the navmesh. I just hope refreshing the navmesh doesn't end up causing stutter when an npc is pathing.

    It would be suuper nice if more data could be cached, since most of the generation would be run on areas that wouldn't be changing anyways...
     
  5. joshcamas

    joshcamas

    Joined:
    Jun 16, 2017
    Posts:
    321
    Of course, if someone with good knowledge of meshes tried this, I'm sure they would find a way to correctly merge the mesh data of each chunk. It would basically be a cutout of sorts:
     

    Attached Files:

  6. Radu392

    Radu392

    Joined:
    Jan 6, 2016
    Posts:
    17
    @joshcamas I have the same problem as you, kind of. I tried all available solutions that I could find online using unity navmesh and after spending several days on it, I couldn't make a perfect system to work.

    I tried having each agent build its own navmesh as it walks around and that seemed to be the perfect solution until I required the agent set its destination over a long distance (longer than its own 32 by 32 navmesh). I then tried to make the agent walk in the direction of its target at least, but that doesn't work either if there's an obstacle bigger than its own navmesh in front of it since it can't detect its edges to walk around it. My terrain is procedurally generated and huge and to add even more complexity, you can build stuff at runtime, some of this stuff can be walked on or acts as obstacles. The problem with each agent having its own mini navmesh is that it can't travel farther than the navmesh and on a huge terrain, that's no bueno. Making the personal navmesh bigger is also out of the question as it will just consume cpu if there are many agents around.

    So right now I've been trying to divide my terrain into chunks like you and build the chunks at runtime like in this picture
    https://puu.sh/AIV10/2b329d8925.png

    However, every chunk is its own 'surface' and as you said, it's not connected automatically even if they overlap a bit. Right now, I'm experimenting with linking my 4000 or so chunks using navmesh links but I highly doubt that will work correctly since my idea is to create about 10 very small links on each side of the square navmesh using raycasting.
    I'm using the localnavmeshbuilder and sourcetags mainly
    Have you made any progress on your problem?
     
    joshcamas and JBR-games like this.
  7. joshcamas

    joshcamas

    Joined:
    Jun 16, 2017
    Posts:
    321
    Sadly it seems that Unity's built in navmesh system is a dead end. I tried building a mesh stitcher, that would essentially save navmeshes as actual meshes, then during runtime stitch the bad boys together... however, this isn't exactly fast (although its many many many times faster than actually generating the navmesh during runtime), and it seems that Unity doesn't even support the conversion of mesh to navmesh. So that was a waste of time.

    Currently I'm quite busy with other systems, however it looks like the best option is to use The Astar Pathfinding Project, as it has a system of tiles that can be saved and loaded into place during runtime. Not the best solution, I know - it's a pretty expensive addon, and it also means the reprogramming of a lot of navagent stuff. I haven't done it yet, it doesn't sound like fun. But it may be the only option.

    Sadly Unity's navmesh system is very much a black box. With no way of even *saving* navmesh data, they make it VERY hard to use it in ways that were not specifically designed by them. Which is quite strange, since nearly every other system in Unity is the opposite - very easy to use, and to understand, and to modify. Too bad.

    I wish you luck, keep me posted on your discoveries!
     
  8. Radu392

    Radu392

    Joined:
    Jan 6, 2016
    Posts:
    17
    Thanks for the recommendation, I'll try that pathing system and hope for the best. As for my 'discoveries', well I discovered the stitching with navmeshlinks doesn't work at all hahaha. There's just too much computing power going into it to the point where the fps drops below 60 and the agents also act all weird, going around random paths instead of the most obvious one.

    One thing about the A* pathfinding project. I heard it's not using the gold standard like Unity's navmesh is. Is that true? I'll still try it since now I'm out of options, but just for general knowledge.
     
    joshcamas likes this.
  9. joshcamas

    joshcamas

    Joined:
    Jun 16, 2017
    Posts:
    321
    I'm not sure what you mean by "gold standard"
     
  10. Radu392

    Radu392

    Joined:
    Jan 6, 2016
    Posts:
    17
    I read on some forum once how unity's navmesh is using the best algorithm out there for pathfinding and that A* doesn't. I doubt it was true though.

    Anyway, I finally managed to solve my problem using A* pathfinding from the store. The free version wasn't enough as I needed layered graphs, but it works amazingly well in all possible cases and just has so much more functionality than the unity navmesh. Took me a day or so to convert my project from navmesh to A* and it's still not fully done, but it's worth it. Only thing left to figure out now is how to make more precise layered graphs inside certain moving models at runtime but it looks like this tool has that capability so all I need to do is to learn how to do it.

    So if you need a solution to your pathfinding, then A* is the right (and only) choice for your case as it was for me.
     
    joshcamas likes this.
  11. grant_from_mercuna

    grant_from_mercuna

    Joined:
    Jun 26, 2018
    Posts:
    6
    it's true that many simple solutions can turn out to be dead-ends, and actually end up costing you more time.
     
    joshcamas likes this.
  12. Noisecrime

    Noisecrime

    Joined:
    Apr 7, 2010
    Posts:
    1,487
    I was thinking about your issue and really don't see why your initial proposal wouldn't work.

    If I was approaching this I would try;

    1. Create chunk scene.
    2. Bake its NavMesh.
    3. Use NavMesh.CalculateTriangulation() to get the mesh ( including areas )
    4. Build per chunk, proxy meshes for runtime navMesh generation from the triangulation data.
    Each area becoming its own mesh, so you can tag them later with the correct area ID.
    Maybe add a gameobject with a script to contain references to these meshes so they stay with the scene/level. Alternatively could store them as resources or seperate assetbundle.​
    5. When a chunk/scene is loaded,
    1. Manage your NavMeshBuildSources.
      • Remove old chunk sources if neccessary.
      • Create new ones for each new NavMeshProxy.
    2. Use UpdateNavMeshDataAsync to build the entire navmesh from your list of NavMeshBuildSources
    From what I can tell defining your own sources allows you to simply use mesh data directly ( no need for additional gameObjects, meshRenderers or colliders), define a custom transform/position, set its area id/cost etc, so it should be quite simple to do. Just need a manager so you can add/remove sources as you load/unload chunks.

    In theory this should deal with overlaps between chunks as you are regenerating the navmesh ( i.e. voxelisation ), and thereby avoids requiring navmeshlinks to stitch together chunks as you have a single large unified navMesh.

    It should be reasonably performant too as from the docs,

    So this sounds plausible to me, but obviously not tried it myself so you'll have to investigate a bit.


    fyi - if you could maintain chunk approach for navMesh ( i.e. no overlaps between chunks )
    1. Create NavMeshBuildSource for each new chunk NavMeshProxy mesh you
    2. Use BuildNavMeshData to create NavMeshData for this new chunk.
    3. Use NavMesh.AddNavMeshData() to add it to the navMesh
    4. Use NavMesh.RemoveNavMeshData() to remove old chunk data ( either keep its NavMeshData around to reuse it if the chunk is loaded again or destroy it).
    5. Add NavMeshLinks to stitch together, perhaps even use some auto-navmeshlink generation.
    This is likely more efficient and you have more control over memory, data, load/unload etc.
     
  13. joshcamas

    joshcamas

    Joined:
    Jun 16, 2017
    Posts:
    321
    Sadly this doesn't work. First off, when you build a navmesh, and then try to build a navmesh off that navmesh, it essentially becomes less and less usable due to resolution issues. (Biggest and most obvious issue is when you have a corridor, the first navmesh makes an edge, and then the runtime navmesh makes the edge even bigger, making the corridor disappear):



    Also, using navmeshlinks doesn't work either. It would require having thousands of links (and other people have been saying this causes bad glitches). And sadly auto navmesh links is not supported in the new navmesh components.
     
    Noisecrime likes this.
  14. Noisecrime

    Noisecrime

    Joined:
    Apr 7, 2010
    Posts:
    1,487
    Good point, bit of a downer.

    Though I still think we could use that data to reconstruct a simplified mesh from the source meshes and avoid the shrinking issue. I'll have a think about it.

    As for automesh links someone made a script for doing that here, seams to work at a basic level and with the new width abillility of MeshLinks you might not need quite as many as before. Though I agree its going to be less optimal.
     
    Last edited: Jul 9, 2018
    joshcamas likes this.
  15. malkere

    malkere

    Joined:
    Dec 6, 2013
    Posts:
    924
    A* doesn't work for me because it's not asynchronous. It chews up CPU power constantly and in a dynamic multi-level infinite generation setup that's just not ok. I use NavMesh because you can generate it asynch in runtime despite it's many challenges. I make them too big so they overlap because they create that gap otherwise then use a "push" method to push them over the line when they reach an edge, putting them on the next navmesh and turning them off/on. It works, it's certainly not the most beautiful solution as sometimes they run a meter or two parallel, but it works, it's fast, and it works with 10+ story buildings.

    I'd love to setup links somehow, but because they are 2D that's almost impossible... I could try spawning thousands of them procedurally... but ya... been hoping for a long time Unity would give all of this some more attention.
     
    joshcamas likes this.
  16. joshcamas

    joshcamas

    Joined:
    Jun 16, 2017
    Posts:
    321
    I didn't realize A* wasn't asynchronous... that sounds terrible :(

    How do you generate the navmesh in runtime? When I've tried doing it, it takes FOREVER (Over a minute for a small area)
     
  17. malkere

    malkere

    Joined:
    Dec 6, 2013
    Posts:
    924
    Here is the basic system:
    https://forum.unity.com/threads/navmesh-baking-at-runtime-example.507446/#post-3401247

    Here are some tips on tuning it.
    https://forum.unity.com/threads/bad-fps-spikes-with-navmesh-building-at-runtime.487905/#post-3410870

    It does seem that some of the settings can have an enormous effect on bake time for less than logical reasons. I generate around 100x100 chunks about 600x600 around the player. Each chunk bakes in 1-2 seconds using

    Code (CSharp):
    1.         navMeshBuildSettings.overrideTileSize = true;
    2.         navMeshBuildSettings.tileSize = 100;
    3.         navMeshBuildSettings.overrideVoxelSize = true;
    4.         navMeshBuildSettings.voxelSize = 0.15f;
     
    joshcamas likes this.
  18. christougher

    christougher

    Joined:
    Mar 6, 2015
    Posts:
    328
    They're are multiple ways A*PP is definitely asynchronous... such as the local avoidance and pathing. You can set the number of cores to use or auto high/ low... is there another way that you find it to be not asynchronous and problematic?
     
    Last edited: Jul 25, 2018
    joshcamas likes this.
  19. malkere

    malkere

    Joined:
    Dec 6, 2013
    Posts:
    924
    Certain A* functions are asynchronous, but the actual navigation surface generation is not. For people that have the option to bake their surface data that's not a problem and A* works great. I do not have that option and have to do everything in runtime as the player moves around infinite game space. The Unity NavMeshBuilder can run almost completely off the main thread for surface generation. It has it's own problems too of course.

    I saw someone saying they were able to generate raycast data off the main thread using the new job system in beta or something along those lines... If that evolves well I'll bet A* can make use of it to go fully asynchronous, but it's not since I last used it.