Connecting "chunks" of navmesh

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

 

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...

 

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.

 

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...

 

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:

 

@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?

 

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!

 

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.

 

I'm not sure what you mean by "gold standard"

 

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.

 

it's true that many simple solutions can turn out to be dead-ends, and actually end up costing you more time.

 

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.

 

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.

 

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.

 

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.

 

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)

 

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;

 

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?

 

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.

 

From my own research you need to add a navmeshsurface to a game object, add navmeshmodifiers to every meshrenderer and tag them appropriatly, then when you start the game, place all your objects and after that run

Code (CSharp):

1. public NavMeshSurface surface;
2.  
3. // Use this for initialization
4.     void Awake () {
5.             surface.BuildNavMesh();
6.     }

That seems to stitch my chunks together, all though they are normal rooms not terrain objects.

You said you were using multiple scenes, as in additive scenes?
Cause I doubt you could connect a navmesh accros scenes.
Maybe change your system to instantiating prefabs instead of using multiple scenes.

 

It does seem to be a terrain problem, I have much more luck with non-terrain meshes and primitives, which I posted about here:
https://forum.unity.com/threads/navmeshes-treat-terrain-collider-edges-poorly.521634/

BuildNavMesh though is not Asynchronous and will stall or stutter gameplay being the real problem in my opinion. If it's small and super easy geometry, as it is in the only video about it that Unity has posted on the subject in a long time =[ despite the new "terrain team" =[ then it's "fast" but it's still on the main thread, and a lot of us don't use small areas with super easy geometry.

 

Building the navmesh at runtime isn't really a solution for me, sadly. Or rather it adds a very large calculation that is absolutely unneeded, since my game is quite static

 

In your case josh (maybe in mine too) it might work to purposefully overlap them and give agents the ability to switch NavMeshes. If they are a static 256x256 for example a RountToInt and a direction check would show which NavMesh the agent is heading further into.

 

For me, I've decided I simply cannot use unity's navmesh. Hopefully you get your way working though!!

 

I struggled a lot with this last year using Unity's Navmesh, and didn't really get anywhere. For procedural worlds, A* Pathfinding Project generated navmeshes too slow for being used in my use case. For the moment I ended up lowering the resolution of the overworld navmesh greatly, and just live with it for our 4K x 4K worlds.

One thing I did play a bit with on my Navmesh Grid was to apply NavmeshLinks dynamically upon need from a pool. If you try to move a Navmesh Agent to a destination beyond the edge of a navmesh, you will get the position at the edge of the navmesh in return. You could then use this destination to place a navmesh link dynamically. Using find closest edge you'd be able to get the normal of the edge to know which direction to point the end of the navmesh link. Like others have mentioned here though, when you get a large amount of Navmesh Links, odd behavior tends to ensue, not to mention how hard it is to make agents moving over a link to look seamless, as they don't apply the same speed/movement rules as you get from NavmeshAgent when moving over the navmesh. For terrain, we ended up calculating our own terrain mesh and inject as a build source to the navmesh builder. This allowed us to control the resolution of the data, and also prevent navmesh from being generated under the ocean.

Overlapping Navmeshes is not supported by Unity and can cause undefined behavior. So it's not really an option either. What might work is that if those overlapping navmeshes are baked on different area layers, and you set the Navmesh Agent's area mask to the "current" Navmesh area, when you get an edge destination, you could switch the area layer of the Navmesh Agent upon edge arrival and now proceed to find a new destination on the neighbour navmesh. I'm not 100% sure it would work in practice, but it would be a super hacky solution at best.

I've had issues trying to update the navmesh too when things in the world change. Just adding a single new build source and then proceed to update the navmesh async generates huge spikes and just completely freezes our servers for the duration of the rebake. Funnily enough spawning Navmesh Obstacles with simple carving volumes does not cause the same spikes, but the shapes it allows are so limiting that it's not very practical in use.

Unity's navmesh baking does not allow you to set an affinity or priority on the allocation of resources, so it forces use of 100% CPU. We've had to tell server providers to set affinity on the project's process on startup to prevent it from just hogging the resources of the entire server when we generate the navmesh, otherwise it could timeout other services on the server.

In the end, for large worlds with procedural and/or dynamic content, the best solution might just be to go to the origin of Unity's implementation, and work out a custom solution. Recast & Detour is an actively used open source project for navmesh generation, but sadly it lacks a C API at the moment for easy plugin access in C#.

One solution I never tried but that was mentioned in the siste thread of this conversation, is to use a super low-res full world navmesh in addition to higher-resolution chunked navmeshes. If this is used in conjunction with the edge detection idea I mentioned earlier, it should be possible to get a coarse path on the full navmesh for long paths, and use the waypoints from that to get higher definition paths per chunk. Then when an edge is reached on a chunk navmesh, make the Navmesh Agent walk on the area layer of the big navmesh to walk over the gap to the neighbour navmesh chunk, and proceed there. I like this idea more than using Navmesh Links tbh, but I'm sure there is a plethora of corner cases with this solution as well.

 

I feel like the fact that this simple concept of navmeshing across world chunks (unity is now touting world chunks as an actual workflow, with 2018.3) is essentially impossible is sort of crazy.

Not that I expect them to build a fancy chunk loader and saver, I'd honestly be so happy with just the ability to modify the currently existing navmesh during runtime. Imagine how powerful that would be! We could do ANYTHING. We could save chunks of navmeshes then stitch them during runtime, in any way we wish. I'm sure unity has some sort of plan for it but I'm guessing it's pretty far out on their list.

Very frustrating.

 

there are only clunky work-arounds using the limited tools that they give us =[
I hate when they put out an awesome feature set like this and leave it at 70% finished. Could be so much more powerful with a little more love.

I do use runtime procedural navmesh in an infinite game space. But I have to let them overlap and push my agents onto new navmeshes whenever they reach an edge, which can make them run parallel to it for a few meters or spin in spot for a second or two, things like that. But more or less it works.

 

Any ideas on how we can get the unity team to notice this? I feel like all we need is the ability to modify navmesh data during edit/runtime, and we can figure out the rest on our own, no problem.

 

Did you try this? https://docs.unity3d.com/Manual/NavMesh-BuildingComponents.html

 

Navmesh components don't connect, sadly.

 

a neighbor awareness system would be phenomenal.

 

Or even better, having the navmesh data have read / write access. This would let us do whatever our hearts desired.

 

How about using Navmesh Surface on Empty object and then using Collect Objects > Volume thus creating navmesh for everything in the bounding volume, thus theoretically you could overlap these volumes and from what I think if 2 navmesh overlap they should function without problem. https://docs.unity3d.com/Manual/class-NavMeshSurface.html

 

Cna you do a proof of concept?

 

Two navmeshes do not connect, even if they overlap.

 

I don't know if this is exactly what you meant but try to look at this

 

That's a single navmesh, which works great. In larger worlds though we tend to split the navmesh into sections. My game world is 2,000,000km^2 for example. There is no "nice" way to connect sections with the current closed source Unity navmesh system.

 

Check out https://docs.unity3d.com/Manual/MultiSceneEditing.html
You should open all your scenes in multi edit mode and bake the navmesh.

 

This only works if you want a massive navmesh, sprawling across the entire world loaded into memory at once, even if most of the world isn't loaded. Not exactly the best solution in my opinion. However, it is what you are stuck with unless you use an addon like Astar

 

Hello,

You should be able to achieve this using baking navmesh at runtime...
Here is a simple tutorial: https://unity3d.com/fr/learn/tutorials/topics/navigation/baking-navmesh-runtime
I've used this in a minecraft prototype, and it worked great when new chunks were crated, updated or removed...
If you make it right it will rework only the modified parts, and you get no lags at all...

Good luck!

 

Sadly this isn't a solution for me, im now using Astar Pathfinding Project and very happy with the results

But very glad you got it working for you!!

 

or if you really want your navmesh to not be baked at runtime, you can generate navmesh links at runtime to join your meshes (navmesh links can be wide...)

[Edit] Was writing when you replyed
Great you got the results you wanted!

have fun! bye

 

i see on your screens that you have navmesh on roofs and other things... don't forget that you can add sub-object with modifiers before baking, then it should be able to remove them... it's a bit cleaner.

 

Do links disregard the Y position? I can't imagine they do... To be honest I've never tried because I just assume they don't work. When you've got terrain chunks that are not flat there's really just no way to connec them with NavMesh links is there?

@joshcamas I used Astar a long time ago and it was pretty rough. Which type of graph are you using, and is it multi-threaded?

 

It must have gotten better! :O I'm using the recast graph, and it's multi-threaded. Also I really like how it supports rigidbodies, unlike unity's. (Explosions, being pushed, falling, etc). Speed wise, I've never had issues, as far as I know it's good. Also the developer answers questions quite quickly on the forum.

In short, it's a awesome plugin with awesome support. Very happy with it, and while it is definitely pricey I'd say it's worth it if you need the features.

 

I bought pro a long time ago, I'll have to check it out again! I was working with recast, but it wasn't threaded back then. Just hard to find time to work something like that in!

 

Any news?

 

https://docs.unity3d.com/Packages/com.unity.ai.navigation@1.0/manual/index.html

 

and? do you even read this topic? i need to connect 64 separate terrain nav meshes to each other, how the hell this almost-ready-very-informative-documentation (as unity always do) of asset what im using now will help me?

 

You asked for news on navmesh generation by necroing an ancient topic. That's the news. They released the package version of the navmesh-system which has an API, supports even run-time navmesh generation. The rest is up to you.