World parition nav mesh with dynamic build and data layers

Development Programming & Scripting
, ,
1

This question was created in reference to: [World Partition Nav mesh and dynamic data [Content removed]

Hello,

Currently I have been experimenting a little with world partitioned nav mesh. I followed the information in https://dev.epicgames.com/documentation/en-us/unreal-engine/world-partitioned-navigation-mesh and that seems to be working fine. However when I try to combine world partition nav mesh with dynamic nav mesh build (specifically Dynamic Modifiers Only) and with runtime Data layers, the questions keep popping up.

Using the Dynamic Modifiers Only mode seems to be a good fit for our project. We aim to create a larger world where most of the geometry (at least the geometry that influences navigation mesh) will be static.

Only at selected places there will be changes during gameplay that require different nav mesh. Examples of these changes:

* The story of the game requires that a house gets destroyed or rebuilt. We aim to do the change by switching the state of runtime data layers - unloading one state of the house and activating the other state

* The game will spawn a random encounter for the player that contains some additional geometry. The geometry will most likely be prepared in advance and placed in a data layer. Activating the data layer will be then part of spawning the encounter

I want to confirm that you are aware of behavior described in repro or if there are some changes planned? For example ignoring the objects from data layers loaded in the editor when preparing the static (base) nav mesh when using Build Paths?

Naturally for large level we are planning to build nav mesh on a builder using commandlet from https://dev.epicgames.com/documentation/en-us/unreal-engine/world-partition-builder-commandlet-reference?application_version=5.6 and then distribute the results among users. In this workflow, all the data layers must NOT be initially loaded in the editor to achieve the expected nav mesh? From my experiments it would appear so. With the layer initially loaded in the editor I get the same results when using the commandlet as with using the Build Paths menu item.

I have noticed that even after a small change in level (e.g. moving 1 static mesh actor within boundaries of a single nav mesh tile), there are significant changes among the Nav Data Chunk Actors. It would appear that all of the Chunk Actors are removed and new ones are created. We were hoping that after running the nav mesh build on a builder machine, the result will be submitted into VCS and the distribution to the users would be done simply by Sync in UGS. Nevertheless, if every nav mesh build completely removes and creates the Nav Data Chunk Actors, this approach may accumulate a lot of data in VCS history (over the full project development). Do you have any suggestions on how to approach Nav mesh build and distribution during development?

Also, do you have any suggestions regarding the number and size of nav modifiers? I would expect that instead of attaching a Nav modifier component to each actor within a data layer, it is more efficient to create 1 Nav modifier per data layer (or at least for larger chunks within the data layer).

The last question (maybe it should have been the first), what is the difference between Dynamic and Dynamic Modifiers Only modes with world partition nav mesh? In referenced issues there is:

WP dynamic navmesh is a bit different than the non-WP dynamic navmesh. WP dynamic navmesh contains a base navmesh for the level that is loaded similar to static navmesh to prevent needing to build large swathes of the navmesh as areas are loaded/streamed

This leaves me wondering what are the benefits of Dynamic Modifiers Only mode and if they outweigh the cost of dealing with Nav modifiers?

Thanks,

Matej Marko

2

Steps to Reproduce
After following the steps in https://dev.epicgames.com/documentation/en-us/unreal-engine/world-partitioned-navigation-mesh do the following:

* Change Project setting for Navigation mesh Runtime generation - from Static to Dynamic Modifiers Only

* Create a data layer asset (configured as Runtime data layer) and create a data layer with that asset within the level. The layer is initially loaded and visible in editor but Unloaded in runtime.

* Add a static mesh actor (Cube) to the level

* Add a Navigation modifier component to the static mesh actor

* Add data layer to the static mesh actor’s Data layer assets

* Setup a simple trigger box that, upon entering, activates/deactivates the layer - thus adding/removing the Static mesh actor.

At this point everything seems to be working fine. When I enter the trigger box in PIE the static mesh actor from the data layer is added/removed and nav mesh changes accordingly. Notice however that the nav mesh hasn’t been rebuilt using the menu item Build -> Build Paths since adding the data layer and static mesh actor.

If I run the Build Paths (with the data layer loaded in editor) the “cutout” for the static mesh actor will be always present. Regardless of the data layer state and the static mesh actor presence in PIE. I am able to see that the nav mesh actually changes - the topology of nav mesh polygons is different - but the cutout is still there.

However, If I change the setting of the data layer and change it so it is NOT Initially loaded nor Initially visible in editor and reload the level, the Build will once again result in what I would expect. No cutout in base nav mesh and cutout around the static mesh actor after activating the layer.

3

The last question (maybe it should have been the first), what is the difference between Dynamic and Dynamic Modifiers Only modes with world partition nav mesh?

The main difference is that fully dynamic generation will respond to geometry changes to rebuild tiles in the navmesh. Dynamic Modifiers Only will only apply or remove the modifier markup applied to the navmesh. So if you remove or destroy a static mesh in the level, dynamic will rebuild the navmesh where it existed, but dynamic modifiers only will not rebuild and the navmesh hole will remain.

WP navmesh support for data layers is quite minimal. There have been a few PRs over the years about building different navmesh or modifiers that are associated with each data layer, but none of them have been added to the engine. To add to this, Dynamic Modifiers Only generation with WP Navmesh has not been really tested. Most of our efforts initially were around static navmesh and then dynamic was added some time later. Loading initially visible data layers sounds like a bug especially as they are not initially loaded runtime layers. I believe the system is building with the objects in the octree which explains the cutout when it has been rebuilt with Build Paths. It also makes sense that the box does not affect navmesh until after calling Build Paths as the navmesh that is being loaded is data that was present prior to the addition of the cube and data layer. The automatic navigation updates should be turned off from the guide which should keep the former navmesh data in the data chunks.

As for the data chunk actor spam, the system currently destroys existing nav data chunk actors when starting a rebuild and creates new data chunk actors. This is in our backlog of things to potentially investigate once we are working on WP navmesh again. To fix this you would need to diverge from the current code or write your own builder. You could attempt to re-use as many data chunk actors as you could during the rebuild and keep a list of chunk actors that were not re-used in a navmesh build to properly delete them from your source control.

Also, do you have any suggestions regarding the number and size of nav modifiers? I would expect that instead of attaching a Nav modifier component to each actor within a data layer, it is more efficient to create 1 Nav modifier per data layer (or at least for larger chunks within the data layer).

Fewer is often better in terms of performance, but it all depends on what you need the modifiers to do in the data layer. We do not have a firm rule on number that can be used, but each modifier is an additional entry in the nav octree which can possibly add up in a large open world.

The AI team is currently at a team summit so I am working from my laptop and unable to build this repro currently. I can dive into it more after this week, but I believe it is likely a use case that was not handled when the original WP navigation builder was written.

-James

4

Hello James,

Thank you for your answers. I am sorry about the late response, I have been away from office for a while in recent weeks.

From Your explanation, I think we will experiment with Dynamic WP nav mesh in the end. Unless we won’t find a performance issue.

I will look into Nav Mesh Data Chunk actor creation in the build process and try to reuse the existing actors. As a temporary solution, we can use the system as is.

As for the issue with layers loaded in editor, we can work around it, by setting the layers not to be loaded in editor by default.

Thanks again,

Matej

5

I have made a note about the data layer issue to look into when we begin investigating WP navmesh again. We recently added another navigation programmer to our team to be able to tackle more things in our navigation background.

-James

6

Hello James,

Thanks for the update on this issue.

Just to let you know, I have successfully implemented a simple reusing of the nav data chunk actors based on the grid size and cell location. It seems to be working ok, as after a rebuild (without any change in the level) I do not see any new files in P4, just modified files.

However, the amount of modifications is much greater than I would hope for. Now I am trying to find the source of the modifications. So far, I have changed the names of the chunk objects within the nav data chunk actor - after reusing the actor, new chunk objects were getting automatic names with increased internal index.

There is also an alternative to this approach of distributing the built nav mesh via P4 and that would be to use actual cooked nav mesh in the editor. We cook the game regularly anyway so there would be no builder time overhead. Do you have any experience with using cooked nav mesh in the editor?

Cheers,

Matej

7

Hello James,

Small update, I have found a source of discrepancy in between different builds of the WP nav mesh. From the serialization code in FPImplRecastNavMesh::SerializeRecastMeshTile I see that for each polygon the first link index is serialized. However after loading the data, the link index is reassigned when adding the tile to the navmesh. Therefore serializing the first link index into a file is not necessary and it causes the difference :frowning:

In our previous project we have found out the same issue and our recast integration does not serialize the first link index for each polygon at all.

I have experimentally replaced the serialization with a dummy DT_NULL_LINK value serialization

// mesh and off-mesh connection polys
for (int32 PolyIdx=0; PolyIdx < SizeInfo.PolyCount; ++PolyIdx)
{
	dtPoly& P = NavPolys[PolyIdx];
 
	unsigned int FirstLink = DT_NULL_LINK;
	Ar << FirstLink;
 
	for (uint32 VertIdx=0; VertIdx < DT_VERTS_PER_POLYGON; ++VertIdx)
	{
		Ar << P.verts[VertIdx];
	}
	for (uint32 NeiIdx=0; NeiIdx < DT_VERTS_PER_POLYGON; ++NeiIdx)
	{
		Ar << P.neis[NeiIdx];
	}
	Ar << P.flags << P.vertCount << P.areaAndtype;
}

At a first glance, it seems to be working ok. What do you think?

Just to note, my colleagues have found some troubles with landscape regeneration each time the level is loaded in editor. That in turn triggers PCG jobs and they suspect that it also might affect the nav mesh.. I have some local work around that prevents landscape regeneration and I have not seen any changes in nav mesh geometry, only the first link index.

I will remove the “landscape workaround” and see if there are any changes in nav mesh vertex positions.

Cheers,

Matej

8

Hi Matej,

At first glance, it seems okay to me. Was this changed in the Recast library as well? I know we have not updated our Recast version in quite some time so there are certainly changes we may not have in the UE version. With removing the serialized link, does pathfinding still occur correctly? Just so I am following correctly, does removing the first link being serialized address the modifications still being seen from your other post?

As for the landscape regeneration issue, can you create another thread on Epic Pro Support for that issue? It will likely need to be addressed by our team handling landscapes. It allows me to track this ticket closely while getting faster support for the landscape issue than would happen by our ping-pong between the teams.

-James

9

Hello James,

Thanks for your reply.

I don’t think this change (not serializing polygon’s first link index) has been done in Recast. I am not that familiar with the current state of the Recast library but at a first glance the only serialization of the nav data is in the samples that accompany the library. And the serialization is very simple - save the tile data as one blob using fwrite.

My understanding is that serialization of the nav mesh data is part of the Recast integration into the project or engine. We have created our own serialization when integrating recast into previous projects and it is quite similar to what I can see in Unreal Engine - the main difference being that UE uses FArchive for the serialization. So omitting the first link index in the serialization has been a fix we have done in our integration of the Recast library.

In the end there are 2 modifications I have done to remove the unnecessary changes in the nav mesh uasset files:

* Remove the first polygon’s link - that seems to be the only source for changes in the nav mesh data itself

* Assign deterministic names to nav mesh data chunks within the chunk actor - when reusing the actor, the new chunks were assigned automatically generated names with increased sufix numbers.

With these two changes, I don’t get any diffs unless the level is modified and path finding seems to be working :slight_smile:

Regarding the landscape, even after removing the workaround I have mentioned before the navmesh does not change - therefore I deduce that polygon’s first link index is the only source of changes in nav mesh data.

The issue of landscape regeneration triggering the PCG jobs still remains. However, we are in the process of switching from release branches to UE’s main. My colleagues working on the landscape have decided to wait and assess the situation after the switch. If the issue is still present, they will report it and I will send you a link.

I hope this answers your questions. If not, please feel free to ask and I will try to explain.

Cheers,

Matej

10

Hello James,

I have another update regarding the diffs in the generated WP navmesh. After removing the first link from polygon, there are no longer diffs in the generated WP navmesh. At least from I am able to tell right now.

However, when I sync to a newer version using UGS and generate the navmesh, there is a difference in the “header” portion of the resulting uassets. I have tracked down the changed data and it turns out to be engine versions that are in the Build.version file that are written into the uasset file - namely the changelist numbers. That is a bit unfortunate :slight_smile:

After some digging I have found out the following piece of code in the file SavePackage2.cpp

	if (SaveContext.IsProceduralSave())
	{
		// Procedural saves should be deterministic, so we have to clear the EngineVersion fields
		// to avoid indeterminism when it changes
		Linker->Summary.SavedByEngineVersion = FEngineVersion();
		Linker->Summary.CompatibleWithEngineVersion = FEngineVersion();
	}

Resetting the engine versions written to the uasset would solve the issue of creating diffs.

Nevertheless, the only way to enable the IsProceduralSave that I have found, is to add SAVE_BulkDataByReference flag in UWorldPartitionNavigationDataBuilder::SavePackages.

It seems to work, but using the flag and thus changing the return value of IsProceduralSave may have some unexpected consequences (as they are used and tested) in other parts of the code.

Alternative solution is to create a custom flag or some other way to activate the reset of the engine versions. Please, do you have any insight into this topic?

Cheers,

Matej

11

This sounds good. Would you be willing and able to submit these changes as a PR? It helps get this in front of relevant devs and into the engine much faster. We have a process for this which helps create all the relevant diffs and shelves for the dev who would handle this. I can put it in as a task, but WP navmesh is not currently the priority so that would be lower on our list than checking out PRs.

-James

12

Hello James,

I am sorry for a late reply.

I’d be happy to create a pull request. I have been looking into how to do it, the only walkthrough I’ve found is here https://dev.epicgames.com/documentation/en\-us/unreal\-engine/contributing\-to\-the\-unreal\-engine Naturally it is intended for git usage.

We are using the engine code via P4, mirroring code from your P4 to our P4 depot and then merging into a “merging stream” where we can resolve conflicts. From there it is merged to our development stream (our main). We are not using git at all, therefore creating a pull request via git brings a non trivial overhead.

Please, is there some other way for devs not using git? Not even for getting the unreal engine code? If not, I will go with the git route.

Thanks,

Matej

13

The only non-GitHub form for engine changes is if there is a special Epic partner branch where we can share CLs. I do not know that you have one as they are quite rare. I do realize that GitHub is an extra hurdle in trying to make things better, but that is our official way to contribute. We appreciate all the effort that goes into submissions.

14

Hello James,

Thanks for the information, I will create the pull request but I cannot give any guarantees about time :slight_smile:

In the meantime, do you have any comments regarding the engine version serialized into the uasset? Previously I have found out that this is also the source of diffs in the resulting nav mesh files. I have been able to remove the versions by using the SAVE_BulkDataByReference flag in UWorldPartitionNavigationDataBuilder::SavePackages. However, I am unsure of other consequences that may come with using this flag.

Thanks,

Matej

15

I am not 100% sure about the save keeping the engine version in the builder commandlet. I believe this is done to prevent possible crashes/issues of attempting to load a .uasset in an earlier engine version as things may not be the same or even exist. Saving the engine version is a normal step for all packages in the engine.

-James