Open World Navigation... is it impossible?

Hello friends!

I'm currently trying to get the "new" navmesh system working on my game. My world is split into chunks (scenes), and building the navmesh all at once doesn't seem to be an option, of course. (It's a large large world!)

First thing I tried was building chunks of navmeshes separately, but this did not work, since of course these meshes weren't attached...

So then I tried doing something I really didn't want to do... build during runtime. This works... but takes literally minutes to do, which is fine in the editor but *not* during runtime...

So... not sure what to do at all. How do open world games do it?

Josh

 

There is an example of navmesh built async as the player is moving. Use that

 

As I said, runtime building of navmesh is not gunna work for my game, sadly. I use this feature, and it results in massive lag (so not really async) and it can take minutes just to build a smaller navmesh than I would actually use.

 

I have used A* Pathfinding Project; https://www.assetstore.unity3d.com/en/?stay#!/content/87744 with procedurally generated levels. It works just fine. I have (earlier) pro version, but i believe runtime pathfinding did work even with free version (at least with grid graph). At the time, free version was available from the web site. Not sure how it is now, check it out.

edit: grammar

 

define "lag"

 

They fake it. Games are 90% smoke and mirrors.

In Breath of the Wild, there are several characters that go on long journeys, but if you play the game enough, you'll realize that they're always taking the exact same path every time. So the AI is not pathfinding, it's simply moving along a preset path. If you put something it it's way or move them yourself, it will use pathfinding only long enough to get itself back on it's preset path.

I've followed characters in Skyrim before too and they will stop moving after a while. They are not walking from one end of the may to another, they simply walk until they're either out of view or at the end of their preset path. Then they'll stay there until you go away and they'll teleport to their destination. Enemies also have a zone that they don't go beyond. You can not lure an enemy infinitely across a map because it can't get past certain invisible barriers.

Halo is not open world, but has some really big maps with enemies on vehicles. Their world is also broken into chunks that enemies will not pass between. There are several places where in even normal gameplay you can cross a loading zone and see the AI simply freeze in place.



I could conceive of some sort of multilayered navmesh though. Would it be possible for you to have a baked navmesh for each little zone, plus a less detailed one encompassing the entire world? You AI could dynamically switch between them based solely on how far away it is from it's target and the player. For an NPC that's a mile away from your player, you want them to say walk around a mountain, but don't really care if they walk through a building or two. Games do weird things just outside of the camera view. There is a great channel on Youtube called Boundary Break where you can see what game objects do when you can't see them.

 

The async navmesh building slows down the game to a crawl.

Yes, I know of this I'm not talking about how characters move when beyond the loaded area, I'm talking about how to have a navmesh where the player is currently.

I would loveee to be able to build during edit time, since I have no need for a fancy dynamic navmesh during game (I just need a static navmesh). But there is no built in way to stitch navmesh chunks together... And building navmeshes, even a 300x300 navmesh, takes minutes ingame using async. (and it doesn't seem to be truly async either)

 

I guess a good explaination of stitching would be skyrim.

Skyrims world is split into chunks, like my game is (scenes). For each chunk, a navmesh is built.

When the chunk is loaded, the chunk's navmesh is stitched onto the "master navmesh"

That would be by far the best option for me, since it would mean very little calculation in game, just some generation during edit time.

However, I have no idea how to stitch meshes (I'm sure to stitch we'd convert the navmesh to a mesh first), especially cause overlap and can and will happen.


EDIT: Here's an insane idea... What of instead I built a MASSIVE navmesh (the entire world!), then split the navmesh into chunks? The only problem with this is that this would mean a slight change in a chunk would mean a complete rebuild of the entire navmesh.... Ehhhh that's not a very good option...

 

Then you are not using async. Show me your code, it'll go faster.

 

This is the function that is lagging the game:

Code (CSharp):

1. NavMeshBuilder.UpdateNavMeshDataAsync(m_NavMesh, defaultBuildSettings, m_Sources, bounds)

Regardless, it takes several minutes to build, which of course is not optimal. : (

 

Skyrim use small chunk too (53m), and they aren't updated at the same time...
and Navmesh link is what you use to stitch navmesh in unity!
https://docs.unity3d.com/Manual/class-NavMeshLink.html

But yeah if you want agent walking across the whole map, you need two layer of simulation, one simplified abstract navigation when outside view, and the current one. Though most game simply use spawn point on destination path.

BOTW don't even have the character do the whole path, they are simply duplicated at both area and use schedule to move in and out of their area by spawning.

 

Very clever, do they tag some sort of portals between areas?

Better you post your full code, including bounds & settings, also a screen shot of the typical scene you bake, with grid ON for scale.

 

Nothing that complicated, it's just duplicated, npc are local to the area, in fact they exist in all area they need to be at the same time, scheduling and flag just turn on and off the character, some don't even turn off, Beedle and Kass exist everywhere at once and never travel between point, beedle just move super slowly, then turn back to return at the same place ... if you move a gameplay pace and don't follow it, the illusion just work. Super patient player have actually push some of these npc across the entire game to meet their clone! The player can't be at all places at the same time, so you just need to move them or move the player outside of view for the illusion to work.

Why overthink stuff?

 

Japanese devs, master of simple tricks. Does that game also have large NPC that you can see from faraway?

 

Solutions here are often based on very specific things in your game. So beyond the basics it's hard to help with the information given.

Async navmesh updates still use a chunk of cpu and they do impact framerate. You can't avoid that you can only minimize it to some extent. If you have a very dynamic and complex world you might need to move to grid pathfinding for some or all of it.

Your previous approach of building chunks is likely the best solution. Figuring out ways to navigate those is ultimately the better/simpler problem to have then trying to make building navmeshes more efficient. You have little control over the latter.

I went the route of build more intelligence into agent navigation. But for instance you could in a fairly straight forward way automate creating offmesh links at certain points where the chunks meet. Like along an edge record all the points that are accessible from the edge of the other navmesh. Then filter to the ones that are accessible from some radius into the mesh or even some known good location.

The main thing is force yourself to think outside the box. Don't get tunnel vision. Back up now and then and rethink your assumptions and approaches.

 

skyrim use the same tricks

Teleport can be interpreted in many way, it's likely to be duplicate spawning

 

Would it be possible to have the navmeshes overlap slightly and when the character reaches the overlap have them switch over to the next navmesh.

 

Fair enough. I meant that the character model would likely simply disappear and it's global position would be updated. I doubt it'd actually spawn another copy until the player got close to it.

 

I believe that is exactly what @neoshaman was saying (not really teleporting in real time)

 

To everyone: yes!! once the NPC is outside of the loaded area, there are lots of tricks you can run, it's very fun to figure that sort of stuff out My personal plan for now is to simply make the NPC "disappear"oonce they walk outside the loaded area, and even when the player tries to find them, they won't. Then after a certain amount of time (depending on distance and NPC speed) the NPCs position in the data will be set to the target location, so whenever the player goes to that area, the NPC will load there. Of course one fix is what if the player is at the location when the NPC is supposed to load there? I suppose a fix is if this is true, spawn the NPC out of sight and make it path towards the location, as if it was traveling all along.

I love video games <3

Sadly no, since if the character is in one navmesh and needs to get to the other one, it cannot calculate a path.

I agree, I think since my world isn't very dynamic trying to shoehorn a fancy async builder just doesn't make sense at all. I'm going to try this navlink approach, it sounds messy but if it works it works!

 

My current plan is to build a dataset containing all of the outer edges of the navmesh for each chunk: these edges will be possible locations for navmesh links

Then when a neighbor chunk is loading, it will compare these edges to find matching pairs or points that are somewhat close to each other, then connect them using a navmesh link. And of course, along a long edge, multiple links will be needed.

We shall see where this goes!!

Edit: one possible issue will be overlapping navmeshes, aka on one navmesh there was a rock so it's slightly higher than the other navmesh. So I guess it'll need to check if the point is underneath the other navmesh. This of course will need to be thought out in the future.

 

You could limit the number of links using topology. Rivers and mountains are good natural barriers and create chokepoints like bridges and passes.

I'm also not sure a waiting time is necessary. It makes it more realistic, but I can't think of any game that does that. For example, in Breath of the Wild, there are lots of quests where you find a character and send them somewhere. I'm sure there is no wait time. Every character you send to Tarrey Town, will instantly appear there. I remember specifically being curious about that and trying to beat characters there. I'm also fairly certain that Kass the singing bird thing is literally just in multiple places at once, he doesn't seem to actually travel at all.

 

Sadly my chunks are pretty small (300x300) so this isn't an option :'(

And that's true! Maybe I am overthinking it!

 

300m? that's not small that's huge!
Skyrim's chunk is exactly 57.6 meters (63 yards) to the side

 

That's something I never understood! Apparently Skyrim also only loads size chunks (so a total of 9 chunks at a time), which seems SO small! Should I shrink my cells?

A major reason why I have cells so big is simply because otherwise I'll have dozens of scenes open at once in the editor, which makes it very annoying :/

 

A scene can have multiple cells? small cell makes bitsize loading/generating less chokeful by separating the load, it also make it easier for job like multithread.

Just had one level of grouping more, that would be a chunk = 6 cells side? assuming 50m side cells. Would be useful to have for LOD evaluation (like updating beat) on chunks, then cells, then objects level, it would be a sorts of spatial partitioning for various optimization almost free too. Using a position hash makes it easy to reference any chunk/cell per object position super easy too, which is cool for update.

 

That's true, my foliage system's LOD utilizes cells, and I plan on building an automated LOD system for buildings and such, which will also use cells as well (applying a lod to the entire cell)

I think trying to further split my cells is going to make things pretty tough, I think 150x150 is a good size for me. (Houses for scale)

 

Ideally the splitting (assuming you haven't build the world yet) should be handled invisibly in edition by tools, it's basically assigning the right data to the right container. You basically edit by operating on group at a certain level (like chunk level) but the system use cells under the hood. Therefore editing still happen in a chunk size group of 3*3 for example?

 

Ahhh that makes a lot of sense.

What exactly would I gain by doing this? My foliage system already uses subcells (4x4) since I had to program culling and LODS specifically for the system, but for actual scene objects culling, occlusion culling, and LODS are already handled by Unity without the need for subcells... I can only imagine it would allow for the disabling objects if they are in a "disabled" subcell, which does sound interesting...

 

It reduce hick ups when saving, streaming or updating, it allow you to spread the load, which is what you must be doing already with the foliage system. Streaming in and out is what I had in mind mostly.

I'm just giving you options anyway, we can make it infinitely complex lol, and playtest will be needed to see what's best for your game. For example not all object have the same importance depending on their size and whether they are static, vegetation, background animation, cosmetic, dynamic or agent, maybe subcells can vary across these category, who knows. It also depend on the sparsity of the world and the speed of travel, or even the type of travel, (no man's sky don't load objects other than landmark and megafauna up until we land).

Funnily I just made a huge post about it with save system on the game kit controller thread lol.

 

Ahh I see! I very much value your thoughts, since it seems these sort of things isn't talked much on this forum. I'll check out that post! However, if objects are in a scene but in separate subcells/containers, wouldn't loading that scene load all of the containers?

 

Well only if you load the scene in a single load, they are subcells for the organization level, so the scene logic would manage loading its part on a per cells or even per objects. It depend on what you want to use on a logic or editing level, maybe cells makes more sense for logic and scene for editing.

Now I research this because I want to do (space travel) open (planetary) world too, I haven't implemented that in unity (yet), so I'm not sure how it would work effectively in unity, especially streaming, especially with resources folder and streaming assets, which seems to have some issue in unity (The dev of inside, which isn't an open world, had to use access to unity's source code to solve this problem). But minecraft chunk size was adjusted to remove hickup in the original game release made in java. I'm passing what I have learned. In general smaller bit size allow you to smoothly cut the load in manageable time, but it also have risk of overhead, so there is a balancing issue.

But right now, I think we have reach a point where it's only testing that will gave us further answer. If you get result please report back

I hope this is good too:
https://forum.unity.com/threads/30-...les-2-4b-released.351456/page-32#post-3492956

 

Skyrim had to work with very tight hardware limitations. Fallout 4 had far fewer restrictions and as a result if you tell your dog to head home and follow him he will eventually make it there. If you want to see it in action there's a video recording below in the spoiler.

Spoiler

 

It could also be an artefact of the dog never crossing the event horizon, thus never been unload to lower simulation LOD. I think it also happen for some (important) character in skyrim too, though I could check on companion too, not all character are treated the same by the logic. I assume NPC would be more tied to area and thus cheat (to avoid all npc wandering teh world at the same time for whatever unforeseen reason) while dynamic character that are supposed to be everywhere worked differently. I'm sure dogmeat reach destination without fighting enemy if you don't follow him to kill obstacle.

In zelda BOTW, kass can be pushed everywhere to another kass, as long you don't get too far from him, and that works for many object too.

 

Quite possibly. There is an actual stage in the main story where you are supposed to follow the dog. It's possible that the game keeps a minimal world navmesh in memory at all times that entities follow and only improves their placement and navigation if the cell they're currently in is loaded by the player being nearby.

 

@neoshaman Thanks for posting that, i got lot of new info / ideas reading it. I think you should post it to https://forum.unity.com/forums/game-design.71/

 

I figured you could probably do that. Lots of games act like that. Does mass actually still have AI though? Most of the time if you push a character too far, their AI will unload.

Are chunks fixed sizes in most games? I would make the assumption that instead they would use a dynamically created BSP system, where dense areas have smaller chunks and empty areas have much larger ones.

 

The reason for the automation is that it makes world editing much easier, since all I gotta do is press a single button to extend the map, and don't have to worry about resizing cells for example (since 99% of the time the first initial location of a city will not be the final location). Not only this, but it makes a whole lot of calculations a hell of a lot easier, since everything fits into everything, and each cell has 4 neighbors.



Elder scrolls has fixed chunks, as does of course minecraft.

I plan onn adding non-chunked cells, but these are not gridded and the loading / unloading of them is not automatic. I plan on allowing level designers to add some logic to the loading of these special cells (for example, there may be a dungeon cell underground... this isn't loaded until the player enters a volume that triggers the loading and another volume triggers the unloading of the overworld since the player will be underground.

I handle this logic by grouping cells into "Cell Layers", which can be gridded (automatically loaded depending on player distance) and non gridded (requiring custom logic).

This of course is extremely custom to my game and my goals

 

Do you know if it works with floating origin (moving the entire world with moving agents while everything continue working)? I'm with the same problem, I cannot use Navmesh due to open world... I bought NAV-AI (from the Asset Store) but it does not work with my large projects, the navigation mesh appears empty (maybe because they are too large).

 

Never tried, but i don't see why not. However, it's been awhile i've used it for anything, but simple pathfinding. I had to check the docs, and not sure if it was this what i used: https://arongranberg.com/astar/docs/class_procedural_grid_mover.php ..anyway there still seems to be free version, check it out (and see procedural example). I haven't use 4.x (free or pro), so there might be something better for these kind of problems.

 

That actually reminds me, wouldn't implementing floating origin into a game after a lot of development be INCREDIBLY difficult? So much information is stored as global positions... : (

 

It's next on my todo list, but floating origin depend on global position anyway (you need them to translate into floating coordinate), assuming your global use correct precision, floating coordinate become more like a view vs model situation, ie your logic run on global, but it is viewed in floating. Does that make any sense?

 

Ima be honest, it doesn't xD But I will research it! Thanks ^_^

 

Alright my friends, I have a new idea that I am 90% sure will work for navigation!!

Lets say that I move a rock in one of my chunks, and want to build the navmesh for it. One solution would be to build the ENTIRE navmesh for the entire world... but that's insane.

Instead, build that chunk's navmesh... but also build the chunks around it! Then slice the mesh, and save that as a navmesh, per chunk! It also saves the neighbor navmeshes, since it may have been modified due to overlap. And of course to build the neighbor navmeshes, MORE neighbors need to be loaded, but can be discarded. (Since the "extra"/"neighbor-neighbor" meshes shouldn't be modified due to the tile positions)

What this results in is each chunk having a navmesh that can be perfectly stitched together! (By detecting overlapping vertices and connecting them on the edges).

I found a wonderful mesh slicer: https://github.com/DavidArayan/EzySlice

Here's basically what the plan is. Also, note that it doesn't need to do this one chunk at a time! It just needs to load all the chunks you wanna build, then do the same thing (load neighbor and extra chunks)

 

Alright my progress so far: I have made it so the navmesh mesh can be generated, and sliced it. Now I just need to figure out how to stitch it back together



I have now made it split the navmesh into chunks, then gave it the ability to merge these chunks, and wield any duplicate vertices. HOWEVER...

There doesn't seem to be any way to convert a mesh into a Navmesh????

If this is true... I'm not sure what to do anymore. Navmesh stuff is SO ignored by the Unity Developers, and SO many features are missing. This is getting to be depressing.

 

Haven't tried but isn't this useful?
https://docs.unity3d.com/ScriptReference/AI.NavMeshTriangulation.html

Also not sure if cutting mesh is the best to make a navmesh when you don't have all the tags and meta data that makes the navmesh, I think you should bake navmesh per cells rather than chopping a big unit. Untested idea, bake a the big navmesh, bake per cell navmesh, use the bignavmesh to sample connection between small navmesh.

I haven't done anything that complex yet with navmesh anyway, I'll have to do it some day anyway.

 

This is how I convert a navmesh into a mesh, but what I need is the reverse...

Also, how would baking the navmesh per cells work? The whole issue is that if you do this they are unconnected.

 

That's why I proposed the two step baking, basically, have an agent that goes from cells to neighbor using the big baked navmesh, sampling at each step the cell navmesh he is on, add links whenever he cross the cell boundaries.

 

Sadly this would mean an agent cannot calculate a position between chunks, since the links wouldn't exist yet

 

Luckily A* Pathfinding Project can turn a mesh into a navmesh! Sadly it looks like my welding isn't working, however: