NavMeshQuery is great for accessing information about the Unity NavMesh from jobs. That being said it is deprecated with the Unity 6 Beta.
Does anyone have any suggestions for alternative methods for using the NavMesh (or replacing it) with ECS?
I know that NavMesh.CalculatePath can be used from the main thread, but I’d prefer to be able to query for paths from jobs if possible.
Thanks.
As far as I know it will be deprecated but not removed. You still can use this API but they will not ever update it or add new features
Oof. I was actually hoping to see improvements with that API. It is much faster than the regular APIs e.g. MapLocation gave me a good performance improvement over NavMesh.SamplePosition, and on top of that it is thread-safe so I can use it in parallel.
The only issue I have with the NavMeshQuery API is that there’s no way to get the actual path from it. There was some code shared somewhere which I think originated from a Unity demo, but I found the resulting path to be unstable and it would often be incorrect when passing corners, by directing to a corner that is completely wrong, causing jittery and incorrect movement.
So I’ve had to go back to using NavMeshAgent, which has pretty poor pathing performance through the CalculatePath method. Even if I wanted to buy A*PPP, it is not compatible with projects that disable domain reloading so I can’t use it anyway, and it looks like they use their own separate NavMesh so that would cause other incompatibilities for my project.
I’m not entirely sure what to do about this at the moment, because even if I slice the pathing quite aggressively, it may still be too slow.
It would be good to have a thread-safe method that can path through a NavMesh. If Unity were open-source, I could perhaps just take the code behind NavMeshAgent.CalculatePath() and customise it to fit my needs.
You can actually get pretty good performance from NavMeshAgents if you limit the number of main thread accesses. The velocity of the agent can be inferred using an IJobParallelForTransform that computes the velocity from change in position. The destination and other settings can be updated on the NavMeshAgent when changes are detected in a parallel job writing to a native stream. Here are some basic (incomplete) code snippets that demonstrate the concept.
[BurstCompile]
public struct SyncNavMeshAgentTransformsJob : IJobParallelForTransform
{
[NativeDisableParallelForRestriction] public ComponentLookup<HybridNavMeshAgentState> StateLookup;
[ReadOnly] public ComponentLookup<LocalTransform> LocalTransformLookup;
[ReadOnly] public ComponentLookup<HybridNavMeshAgentSettings> SettingsLookup;
[ReadOnly] public NativeList<Entity> Entities;
public float DeltaTime;
public void Execute(int index, TransformAccess transform)
{
var entity = Entities[index];
ref var state = ref StateLookup.GetRefRW(entity).ValueRW;
var settings = SettingsLookup[entity];
float3 position = transform.position;
// read agent transform to determine position and desired velocity
if (state.Initialized && DeltaTime > 0f)
{
state.Velocity = (position - state.LastPosition) / DeltaTime;
}
// write local transform to agent transform
var localTransform = LocalTransformLookup[entity];
var entityPosition = localTransform.Position;
entityPosition.y = position.y;
if (math.distancesq(entityPosition, position) >= settings.Settings.Value.RadiusSq)
{
position = entityPosition;
transform.position = position;
}
state.LastPosition = position;
state.Initialized = true;
}
}
[BurstCompile]
[WithNone(typeof(HybridNavMeshAgentPrefab))]
public partial struct FilterNavMeshAgentUpdateJob : IJobEntity, IJobEntityChunkBeginEnd
{
[NativeDisableParallelForRestriction] public NativeStream.Writer Writer;
public void Execute(Entity entity, ref HybridNavMeshAgentInternalState agentInternalState,
in HybridNavMeshAgentState agentState, in HybridNavMeshAgentSettings agentSettings)
{
var enabledMatches = agentInternalState.Enabled == agentState.Enabled;
if (!agentState.Initialized || (enabledMatches && !agentState.Enabled))
{
return;
}
if (enabledMatches &&
agentState.IsStopped == agentInternalState.IsStopped &&
agentInternalState.ObstacleAvoidanceType == agentState.ObstacleAvoidanceType &&
math.distancesq(agentInternalState.Destination, agentState.Destination) <
agentSettings.Settings.Value.DestinationDifferenceToUpdateSq)
{
return;
}
Writer.Write(new HybridNavMeshAgentUpdate
{
Entity = entity,
Destination = navMeshDestination,
IsStopped = agentState.IsStopped,
Enabled = agentState.Enabled,
ObstacleAvoidanceType = agentState.ObstacleAvoidanceType,
Velocity = agentState.Velocity
});
agentInternalState.Destination = navMeshDestination;
agentInternalState.IsStopped = agentState.IsStopped;
agentInternalState.ObstacleAvoidanceType = agentState.ObstacleAvoidanceType;
agentInternalState.Enabled = agentState.Enabled;
}
public bool OnChunkBegin(in ArchetypeChunk chunk, int unfilteredChunkIndex, bool useEnabledMask,
in v128 chunkEnabledMask)
{
Writer.BeginForEachIndex(unfilteredChunkIndex);
return true;
}
public void OnChunkEnd(in ArchetypeChunk chunk, int unfilteredChunkIndex, bool useEnabledMask,
in v128 chunkEnabledMask, bool chunkWasExecuted)
{
Writer.EndForEachIndex();
}
}
private void WriteAgentChanges(ref NativeStream stream)
{
var reader = stream.AsReader();
// iterate over changes
var index = 0;
var maxIndex = reader.ForEachCount;
if (maxIndex <= 0)
{
return;
}
reader.BeginForEachIndex(index++);
while (reader.RemainingItemCount == 0 && index < maxIndex)
{
reader.BeginForEachIndex(index++);
}
while (reader.RemainingItemCount > 0)
{
// Read the data
var update = reader.Read<HybridNavMeshAgentUpdate>();
while (reader.RemainingItemCount == 0 && index < maxIndex)
{
reader.BeginForEachIndex(index++);
}
if (!_entityToNavMeshAgents.TryGetValue(update.Entity, out var navMeshAgent) || navMeshAgent == null)
{
continue;
}
if (update.Enabled != navMeshAgent.enabled)
{
navMeshAgent.enabled = update.Enabled;
}
if (!update.Enabled)
{
continue;
}
navMeshAgent.obstacleAvoidanceType = update.ObstacleAvoidanceType;
// Ensure the agent is both active and on a NavMesh before setting destination
if (navMeshAgent.isActiveAndEnabled && navMeshAgent.isOnNavMesh)
{
navMeshAgent.destination = update.IsStopped ? navMeshAgent.nextPosition : update.Destination;
}
else
{
// Get the nearest position on the NavMesh
if (NavMesh.SamplePosition(navMeshAgent.transform.position, out var hit, 5f, navMeshAgent.areaMask))
{
navMeshAgent.Warp(hit.position);
}
if (EntityManager.HasComponent<HybridNavMeshAgentInternalState>(update.Entity))
{
var internalState =
EntityManager.GetComponentData<HybridNavMeshAgentInternalState>(update.Entity);
internalState.Destination = navMeshAgent.transform.position;
EntityManager.SetComponentData(update.Entity, internalState);
}
}
}
}
My problem with NavMeshAgent is that on my 7950X3D it is simply too slow. This is a top of the line CPU and here are my measurements for mean time over 300 frames, for 201 enemies. In each line the first result is in-Editor (frequency cores), the second in-build (frequency cores), the third in-build (cache cores):
Path calculation: 0.52ms, 0.46ms, 0.43ms.
Copy paths: 0.13ms, 0.08ms, 0.07ms.
Set agent current positions: 0.16ms, 0.14ms, 0.06ms.
My game has at least 300 real-time enemies and I need to support more reasonable CPUs. NavMeshAgent would be ok if it was at least thread-safe. The biggest issue here is that the pathing is limited to the main thread, and this is very wasteful.
The path copying is just 800 Vector3s, which is shockingly slow somehow. There’s the NavMeshPath class in the way, but since this cost is similar to the cost of setting the position of the Agent (via .nextPosition, which I found needs to match the agent position before calculating a path to the destination), I guess most of the cost here is from interop. I copy the path corners for use in my avoidance system.
I use NavMeshAgent only to get the path - I made my own avoidance system. The path is all I need from NavMeshAgent. NavMeshAgent does not move itself. I move the NavMeshAgent to the enemy’s current position (via setting .nextPosition) before calculating paths.
At this moment I’m thinking about whether to slice this or try to integrate Detour pathing. As a general rule I don’t allow any CPU spikes to occur so I would need to slice a limited number of enemies per frame. I could slice down to 10 enemies per frame but I don’t know if that would update frequently enough.
I couldn’t immediately find any docs on how to pathfind using Detour (part of RecastNavigation).
EDIT: Oh and because of the reliance on managed objects, I can’t Burst any of these methods. The previous approach I used with NavMeshQuery was Burstable but didn’t produce correct results. Wouldn’t matter here since the source navigation code wouldn’t be Bursted anyway.
For the above measurements, these methods loop over 201 enemies. Some of the unsafe code is redundant - I split this from my old system using NavMeshQuery and more pointers yesterday.
public unsafe static void CalculatePaths(Span<EnemyBrainState> brainStates, Span<bool> shouldTicks, Span<ManagedState> managedStates)
{
Profiler.BeginSample("[EnemyNavMeshPathSystem] CalculatePaths.");
for (int i = 0; i < brainStates.Length; i++)
{
if (!shouldTicks[i])
continue;
ref EnemyBrainState brainState = ref brainStates[i];
ref ManagedState managedState = ref managedStates[i];
bool pathFound = managedState.Agent.CalculatePath(brainState.targetNavMeshLocation.position, managedState.Path);
}
Profiler.EndSample();
}
private unsafe static void CopyPaths(Span<bool> shouldTicks, Span<EnemyBrainState> brainStates, Span<ManagedState> managedStates, Vector3[] tempCornersArray)
{
Profiler.BeginSample("[EnemyNavMeshPathSystem] CopyPaths.");
for (int i = 0; i < brainStates.Length; i++)
{
if (!shouldTicks[i])
continue;
ref EnemyBrainState brainState = ref brainStates[i];
ref ManagedState managedState = ref managedStates[i];
fixed (EnemyBrainState* toBrainState = &brainState)
{
int cornerCount = managedState.Path.GetCornersNonAlloc(tempCornersArray);
// LiamFoot.OptimizationSegregated.Logging.Log($"Found {cornerCount} corners for enemy id {brainState.EnemyId}.");
IntPtrLength intPtrLength = brainState.PathCorners.Span;
Span<float3> corners = new Span<float3>(intPtrLength.ToPointer(), intPtrLength.Length);
int upperBound = math.min(corners.Length, cornerCount);
for (int cornerIndex = 0; cornerIndex < upperBound; cornerIndex++)
{
corners[cornerIndex] = tempCornersArray[cornerIndex];
}
brainState.PathCornersCount = upperBound;
}
}
Profiler.EndSample();
}
private static void SetAgentCurrentPositions(Span<bool> shouldTicks, Span<EnemyBrainState> brainStates, Span<ManagedState> managedStates)
{
Profiler.BeginSample("[EnemyNavMeshPathSystem] SetAgentCurrentPositions.");
for (int i = 0; i < brainStates.Length; i++)
{
if (!shouldTicks[i])
continue;
ref EnemyBrainState brainState = ref brainStates[i];
ref ManagedState managedState = ref managedStates[i];
if (!brainState.currentNavMeshLocationIsValid)
{
shouldTicks[i] = false;
continue;
}
// No need to set the Agent's transform, but we do need to set the nextPosition to the current (starting) position of the agent, where we want to begin the path calculation.
managedState.Agent.nextPosition = brainState.currentNavMeshLocation.position;
}
Profiler.EndSample();
}
Have you looked into the A* Pathfinding Project? The author has recently added ECS support and the pathfinding is multithreaded.
Yeah, I made reference to that with “A*PPP” in my first post (maybe not a well known acronym - A* Pathfinding Project Pro).
I would not re-enable domain and scene reloading for any package (Enter Play Mode settings). It’s also an expensive package and would require me to change other things.
At the moment I’ve altered my pathing system to take a slice of 10 enemies per frame, and now the three profiler markers take 0.06ms in-Editor (down from 0.81ms for 201 enemies). I need to experiment more to see what the results are like.
NavMeshQuery is great, I just don’t know how to pathfind with it. I do have a PathUtils class which is commented as being made by Mikko Mononen, and then modified by Unity, but the code produces problematic paths when the agent is close to a corner. Internally this uses NavMeshQuery.
It would be cool if someone from Unity could drop by and discuss this. Do they know about this issue? Do they have improved code? Am I misusing it somehow? It’s all based on an experimental API which is now deprecated, so maybe it’s just something to be left, which would be unfortunate.
I didn’t look too in depth at your code but roughly speaking you shouldn’t be struggling with that number of agents. The built-in system is fairly decent at what it does considering how old it is. I’ve pushed ten times as many on a Ryzen 5 without anything more technical than using single master monobehaviour that scheduled paths for them.
That really depends on what you consider to be expensive. I’m making an open world, multiplayer, high-fidelity VR game. I have to optimize pretty hard so that the game can even exist. Everything is expensive at this scale. Spending over 1ms on pathing for 300 enemies is unfeasibly slow for a top-of-the-line CPU. The limit could even end up higher than 300 active enemies. Maybe the slicing will work well enough.
My entire avoidance system runs in about 0.25ms - it handles local avoidance for those 300 agents, and wider-scale avoidance. On top of that, I’m going to slice it.
Relatively speaking, I think the pathing of the NavMesh should be less expensive; and if I could parallelize it, it would be.
I went back and re-read and detail and I see why you are having issues. As you have found out, the agent’s CalculatePaths isn’t the best and worse yet, it’s synchronous. Using the built-in agent movement and avoidance system is quite performant if configured well but since you are trying to do your own thing with that it’s probably not going to be feasible with Unity’s navmesh system.
As far as the API you mentioned: It’s dead. There was a thread about it on the forums a couple years ago. A lot of people (including myself) were posting about how unhappy we were but it made no difference. They are not planning to continue work on it and will leave it as it is.
It’s been a while since I looked into A*PFP but last time I did I was pretty sure they allowed disabling domain reload. I’ll take a look tonight and see if something has changed or if I misremembered. It really is a very flexible system and especially good when you want to share, access, or modify paths on the fly. The agent’s path following wasn’t as fast as Unity’s last time i compared them but that was also like, two years ago? With jobs, burst, and ECS, that might have all changed now.
I don’t have a reference point, but I feel the performance of CalculatePath is ok. If it were thread-safe, it would be great. Source code could solve my issue.
If you happen to be part of an enterprise entity with some fat pockets then you can request read-only access to the source code. But that’s not something that’s going to happen for your run-of-the-mill solo dev. Luckily, none of that is necessary anyway since I can tell you that it doesn’t work from another thread. One of the internal methods that CalculatePaths() calls will, just like the majority of the Unity engine API, throw an exception if called on anything other than the main thread.
As it stands your options realistically look like:
a) Accept the performance hit and design around it.
a) Use the built-in NavMesh and NavAgents as they are and get reasonable performance.
b) Try to work around the issues in the depreciated API and use that.
c) Roll your own solution
d) Use someone else’s solution.
Yeah it throws an exception in its current form, but I’d modify the code to work around it. I’d take the code and make a new assembly.
I have to modify libraries all the time - usually for performance reasons. It sucks when the source code is hidden.
Anyway, I’ll be using the slicing around their API for now.
I’m using A* Pathfinding Project from DOTS. There’s free version on the store, maybe you can try that.
Sorry, I forgot to reply earlier about the state of AStar. It just popped into my head since I was working with path finding in my project again.
Anyway, just wanted to say that A*PFP has no issues whatsoever with disabling domain reload and a scouring of the docs didn’t mention anything about it either. The most I could find was one odd post from a couple of years ago suggesting that the scene reloading might need to remain enabled but even that seems dubious.
Performance-wise the pathing itself seems much faster than Unity but agent movement can be on-par or slower depending on what features you enable. Most of those features are much more refined than Unity’s however so it might be worth it in some cases. No matter what, it’s worth it if you want more control and more access to the data for the nav graphs, paths, and agents.
Hi, thanks for following up.
I see that it is indeed Scene Reload which is not supported, and that the package supported disabling Domain Reload via an alpha in 2020: Make A* work with Fast Enter Play Mode - #3 by Adrian_Mesa - Feature Requests - Support Forum
My project is multiplayer and so in the vast majority of cases, I load first into an Offline scene, then an Online scene, so disabling Scene Reload may not benefit me anyway.
Hi, just posting another request for some way to calculate paths without the main thread.
I’ve switched to using NavMesh.CalculatePath() and calculating paths for 10 enemies costs around 0.22ms per frame, all on the main thread, on my cache cores (7950X3D).
I do my best to optimize so this is bugging me a lot. I also really want to move to Unity 6 in the near future and re-evaluate HDRP’s performance primarily for improved lighting, camera-relative rendering, cached shadow maps, and DLSS. HDRP is going to take more CPU time so that’s an additional challenge. Everything that I want to implement eats into my CPU time.
I’m considering A* PPP, but this will mean changing to their own NavMesh, and I’m already integrated with Unity’s NavMesh. A*PPP is also a relatively expensive package.
It would be really helpful if Unity could provide me a thread-safe way to calculate NavMesh paths. I just need the first 8 corners of each path.
Thank you for your input. Single-threaded pathfinding is an inconvenience that we are aware of. We have it logged internally.
Unfortunately the pathfinding code has to run single-threaded currently in order to correctly handle dynamic changes in the NavMesh that occur when re-baking or when obstacles activate carving.
If you believe running the pathfinding queries asynchronously (albeit still single-threaded) can distribute the workload better then please have a look at my suggestion here: NavMesh.CalculatePath & NavMeshAgent.CalculatePath return not full path - #11 by adriant .
Hi, thanks for responding!
I’ve since gone back to NavMeshQuery using the PathUtils class that I found somewhere, and I’m getting good results now. One of the issues I had was caused by the NavMeshQuery.pathNodePoolSize being too small for the length of the path, which I now check for so that I can increase the pre-allocated size. So far I’m now getting good paths with it, and it all runs on job threads in parallel with my other systems. This is saving me about 0.2ms per frame, which is great.
I was aware of the slicing behaviour from SetDestination(), but I’ve not tested if the update rate would be good enough. I am currently using NavMeshQuery to calculate 11 full paths per frame and it seems to work well.
NavMeshQuery is also really useful for thread-safe NavMesh querying, which I’ve noted A*PPP does not support (and perhaps Unity does not support given the deprecation of NavMeshQuery), but this is a very useful feature that I hope Unity will continue in some form.
Fortunately I’m not using NavMesh carving or runtime baking so hopefully I won’t see any issues with this approach.
I go few thoughts on the subject, I spent fairly of time, choosing suitable option for one of the project.
Recently I was investigating various solutions for navigation, specifically using NavMesh not grid, for 1000 agents, on the map size of 1000 x 1000. Units moving “randomly”, not in the formation, like in RTS.
Results may be different for others different scenario.
I have tried old, and new Unity NavMesh systems, as well as A* Project Pro, with conjunction of another asset Agents Navigation.
I was considering sticking to older NavMesh with queries, but future is unclear, as is depreciated and chances are, it may be excluded in future Unity versions (possibly 7+). I consider long term project.
I really wanted to give it try to A*PP, but all results I had, no matter what I did, was just killing performance. What was gained on ECS and jobs side, was killed by displacement and job setters systems, which are passing data between managed data types. So no bursted.
I hoped that NavMesh data is native data type. But since it is not, there is little to gain, comparing to other solutions.
During my research for the case scenario, all CPU cores budget been spent only on pathing / avoidance. Been messing with settings and map chunking etc. But no avail to get good performance out of it, in comparison to Unity Agents based NavMesh.
I found similar analysis by others, when digging in to the subject. So I am not alone with such conclusions. My so far conclusion is, unless someone got other tricks that I am not aware of that if wanting NavMesh navigation and avoidance on large maps, with many agents, A*PP is not way to go. It seems it is good enough for small maps. But so is Unity solution.
However, you can disable avoidance and use other features, to get good results out of it. For example getting only paths alone, without avoidance. For example giving units formation move direction, instead pathing for individual units.
I find A*PP also great for grid based maps. There is Navigation Crowd asset which is compatible with it and uses flowfield. 10s of thousands of units simulated, in small tower defense game.
But in the end, I have decided that I will stick to new Unity Navigation. It is incomparable better in my use case, specially for controlling over 1000 agents in the map size 1000x1000. In my scenario, I don’t need give move command at the same time. Pathing and behaviour is decent for my use case atm.