We'd need a way to calculate path in async mode WITHOUT using NavMeshAgent

I want to use the navmesh system for a game with physics-based character controllers, which means I cannot use the built-in "NavMeshAgent" and I will make my own agent behaviour instead. Actually, even if my characters weren't physics-based, I can see tons of reasons why you'd want to make your own "agents" instead of using the built-in one. The built-in NavMeshAgent gives you no fine control and should only be meant to be an example.

The problem is that, from what I understand, there is no way to asynchronously calculate a path other than NavMeshAgent.SetDestination().

Can we get a NavMesh.CalculatePathAsync() to solve this problem? It could simply return an AsyncOperation that tells you when the NavMeshPath you gave it has been properly updated. Now that the API is still sort-of experimental, it'd be a good time to solve this huge problem. Or is there something I overlooked/misunderstood?

I'd also ask if we could decouple NavMeshAgent from the NavMesh system entirely (for more coherence, versatility, cleanliness, etc...). NavMeshAgent really should just be something external, like an asset store package or something that's part of the high-level navmesh components. It's too much of a specific implementation of an agent to be rooted into the entire system like it is right now.

Basically, I think the entire NavMesh API should be designed with the assumption that people will want to make their own "agents", but NavMeshAgent can remain as an external package to get started quickly

 

I agree wholeheartedly with this. It's quite a strange design choice

 

http://forum.unity3d.com/posts/2457252/

Have a look at this link might be helpful. navmesh.Calculatepath(); doesnt need an agent.

 

But it's not async

 

What do you mean with async?

 

From the NavMesh.CalculatePath page:
https://docs.unity3d.com/ScriptReference/AI.NavMesh.CalculatePath.html


From the NavMeshAgent.SetDestination page:
https://docs.unity3d.com/ScriptReference/AI.NavMeshAgent.SetDestination.html


NavMeshAgent.SetDestination is an async operation that could be calculated over several frames. NavMesh.CalculatePath is a direct calculation that could be too heavy in certain cases

 

I empathize I wish it had also an update method so I can step it manually, I don't want my character to be the agent and but have it "follow" the agent lol like a chariot, it's too automatic as of now, I mean they don't even have a "stop". Though this one problem of mine is manageable.

I mean we could use the updatePosition and nextPosition to implement what we want, in your case you would hijack the pathStatus and then get the computed path once finish to do everything by script, using SetDestination as a way to calculate path async by firing it at opportune moment.

 

Only if you are calculating paths of hundreds at once. And in that case you can make your own method that calculates only example 20% per frame. Unless your aiming for 10+ year old mobile devices or something..

 

Have you ever considered that people might have scenes that are a bit more elaborate?
Calculating a single path can take many milliseconds.
You can't do that in a single frame when you only have 15ms and the rest of your game already takes up 12.


The only way I see right now is creating fake agents and calling SetDestination on them.
When their path is complete, you'd take the path from them.

 

Understood, i guess the best thing to do is test with profiler and see which option is better, navmesh.Calculatepath in My small city scene (3-6 corners) on a computer only uses around 0.1ms or 0.35ms for 4 paths at once. (i have 350 characters that roam the city and divide them up evenly so each is calculated once per second when not seen by player. but as you say that likely goes up if you have a very complicated scene or on mobile.

 

It did not occur to me until right now that maybe "SetDestination" is only async in the sense that it manages the workload of path calculations across all active agents in the scene (doing only a few of them per frame), but not in the sense that a single path calculation is actually async...

In that case I suppose it is entirely doable to do our own system that does this with CalculatePath

 

I would say that the existance of pathStatus member of the navMeshAgent object is suspicious:

https://docs.unity3d.com/ScriptReference/AI.NavMeshAgent-pathStatus.html

Better test the hypothesis first

 

Oh this is very interesting. I remember when we were moving 100 agents that I had to bake the navmesh in low precision to avoid stalls, that was before the number of path calculate per frame could be set by the user. Yes that's old as we were using 3 and 4 but maybe that is something you can also use.

Now I read that navmesh queries are already jobified so until jobs is in a beta, maybe you can bear it for now? (if you still want to use unity navmesh)

 

Just found this thread.

My FPS drops from 60 --> 10 due to NavMesh.CalculatePath( ) call if I "activate" all my dungeon's monsters and they all try to pathfind (About 100 monsters calling NavMesh.CalculatePath every Update frame).

I think I will use NavMesh.CalculatePath but do something like if monster is really far from target (several screens away) then recalculate infrequently. But if it is on-screen the recalculate quickly... for 2 reasons.
1: The calculation is much less intense if it is close (I think)
2: The monster needs to aim correctly if on-screen and react to player motion (and not keep walking towards where the player was 0.5sec ago).

 

LOD-ing the pathing is a very good idea. I use CullingGroups for AI, if you haven't used them, I think you'll like them.
100 enemies at 10 fps shouldn't happen on a PC, try optimizing navmesh geometry by increasing voxel size and rebaking.

 

NavMesh.CalculatePath is the single line of code that drops 60FPS --> 10FPS. On a large outdoor map with 100 monsters all pathfinding it really takes a tole.

LOD'ing the NavMesh.CalculatePath rate fixed the issue. I maintain 60FPS by recalculating nearby objects a few times per second and far away objects every few seconds. Here's the code I used.
float recalculateTimer = Mathf.Pow(distanceToTarget + 30f, 0.2f) - 1.5f;




In general struggling with pathfinding though. Issues
1: FPS drop due to NavMesh.CalculatePath cost (~fixed above)
2: Multiple agent sizes (i.e. small monsters can fit through a small opening, but large monsters cannot and must walk around). https://docs.unity3d.com/Manual/NavMesh-BuildingComponents.html aren't released yet and I'm afraid to use undeveloped things (I don't want another UNET experience)
3: You can compute multiple navmeshes for different agent sizes but then you run into issues where say a large cyclops is trying to reach you... and you stand near a wall... your actual character will be "out of bounds" of the navmesh due to the large offset on the navmesh from walls/obstacles. What I want to happen is for the cyclops to walk towards the nearest point to the target... even if the target is small in diameter and slightly outside the large agent size cyclops navmesh.
4: Computing navigation for different types of monsters. Walking monsters, flying monsters (can go over pits, but not through walls), ethreal monsters (can go through walls but not over pits), ethreal flying monsters (can go over/through anything), stupid monsters (will not avoid traps).
5: Flanking monsters. I've programmed some to try and sneak up behind you. But it becomes complicated. If the monster is really really far away it will walk directly towards you and navigate to get there. But once it gets closer it will try and get behind you. But doing this while also avoiding walls/traps is tricky... haven't figured out a good way. And if you have your back to the wall then you can't be flanked and the monster must know this and attack you in the face instead.
6: Similar to #5... meandering monsters. For example my zombies wander around a bit... they don't make an optimum direct path towards you. But if I make add in a random wander angle... then they can accidentally walk into traps or off cliffs. But if I add in the wandering offset before I call NavMesh.CalculatePath then the random offset may be outside the navmesh or on the otherside of a wall. It's tricky.
7: Similar to #5/#6: Charging monsters. Some monsters are coded to walk about a screen away and then charge in. They then charge past the target and repeat. Coupling this with the nav system to also avoid traps is proving difficult (I think I may leave it where a monster will charge off a cliff... adds an extra interesting way to defeat them).

Here's an example video of a wall spike trap that most monsters would avoid.

Here's examples of wandering/charging monsters.

 

On a very large outdoor map I did some testing with NavMesh.CalculatePath's cost.
1: If the pathfind target is out of bounds (cannot find path) it doesn't use up much overhead. (no FPS with 200 NavMesh.CalculatePath's per update)
2: If the pathfind source & target destination are close to eachother it doesn't use up much overhead. (no FPS with 200 NavMesh.CalculatePath's per update). This is even true if the path isn't direct and has to navigate around a few corners.
3: If the pathfind source & target destination are at opposite ends of the map the overhead is very large causing a FPS drop if you do about 10 or so NavMesh.CalculatePath's per second. (In my case the final calculated path had 33 nodes).

So what this means.
-Having a fine Voxel size not only increases bake time but likely also increases the computation time when pathfinding. (untested but likely)
-LODing the pathfind update rate seems to be the way to go. If a monster is on-screen I plan on calling pathfind every update (in my game there will only be a <10 monsters at a time). Reducing the NavMesh.CalculatePath recalc rate to even 100ms causes a noticeable jerky motion of the monster as it looks to where the character was up to 100ms ago and then snaps to the new character location. This could possibly be smoothed out but would require work.

 

I wonder if it's actually planned to add something like NavMesh.CalculatePathAsync()?
It's been over a year since OP, maybe something has changed?

Was using A* Pathfinding Project most of the time, but now forced to use Unity's NavMesh for the current project.
Can't really find a way to properly path without much of an overhead, and can't use NavMeshAgents as well (since they don't support leaving NavMesh bounds properly).

I guess NavMeshAgent with disabled movement feature can be used as well, simply as a pathfinder.

 

Why are you calculating the path every frame?
How much can they have moved or be that far off in a single frame.

I think you should try to find a better way to judge if you really need to update the path or not. And then those that really need it only update x per frame to spread the load like you mentioned.

Off the top of my head for example if your areas are mostly empty then maybe do some simple raycasts first to the target. I think the NavMesh can do this too(assuming it’s faster). If nothing is colliding then just move them directly that way. And never calculate a path.

 

It's not about necessity, but rather scalability.
Indeed most of the time lots of pathing is not need, but once the numbers of units grow, e.g. in strategy, when ordering to a lots of units to move, etc. Or when the scene scale grows. Or it's complexity grows.

It's more convenient to have async method. There should not be such thing as non-threaded pathing in 2018.

 

The CalculatePath doesn't look like async because it's not shapped like an async function but it is async under the hood, you just need to test the path status in a loop.
https://docs.unity3d.com/ScriptReference/AI.NavMesh-pathfindingIterationsPerFrame.html

 

The async function looks like it limits the # of NavMesh.CalculatePath's per update loop.

For me the pathfinding cost varies drastically based on distance and number of obstacles between source and destination. Limiting the # of pathfindings per Update loops might be an OK way of handling the problem but still gives 2 issues.
1: If the path is complex it could still cause FPS drop (unless the limit is set really really low for worst case scenario)
2: Close monsters would have periodic pathfinding causing jerky motion (unless smoothed out with additional code).

Not sure if there is a way to make an async function that varies the # of NavMesh.CalculatePath's based on loading... but that would be more ideal than a fixed number of calculations.

@daxiongmao I'm not sure if I need to calculate the path every Update or not. But that's currently the way I get the monster to "aim" at it's target. If I recalculate every 100ms the monster jitter rotates as it only updates it's aim every 100ms. I considered moving over to a different system if the monster is close... but my game has traps and obstacles an such that the monsters navigate around. So even if you are close to the monster I still want to pathfind around those. I'm not sure of any alternative to pathfinding every Update. Open to ideas.

In any case I LOD'd the NavMesh.CalculatePath rate and it seems to work well.

This NavMesh.CalculatePath cost is another thorn in the side of getting a smooth game. Getting smooth visual motion is already difficult (impossible?) with Unity due to Time.deltaTime variation issues.
https://forum.unity.com/threads/time-deltatime-not-constant-vsync-camerafollow-and-jitter.430339/

 

Yeah it does, which is pretty neat if you tightly control the calls to that function like it seems you are doing.

It looks like you got enough attention on this long standing issue and they're fixing it! Bravo. I always took jerking motion for granted in Unity and never paid attention to it, after the first year. But yes you can always recognize a unity game from its uneven motion
I don't know if it is related but I noticed that ECS tests are very smooth, maybe this is a solution?

Back to Unity navmesh, it is not showing much love from UT, that's for sure, I thought they surveyed large pro customers and found out that nobody uses it, but since they have recently updated navmesh to run with jobs blazing fast, my guess is that they preferred to wait until that was completed before adding granular control.

 

Does this mean it's not synchronous even though manual clearly states that it is?

https://docs.unity3d.com/ScriptReference/AI.NavMesh.CalculatePath.html

Which makes no sense at all.

Or do you mean that it starts # of threads and then blocks main thread waiting for them to complete?

This do make sense. But it's still, a synchronous call, blocking the thread. This can be avoided.

 

Oh you're right, the old calculatepath is still main thread. weird isn't it that the haven't made this one async and the navmeshagent is async.
Anyway, this guy navmeshed tens on thousands of agents with ECS, it's very hard to setup but if you need that much power, you just gotta
https://github.com/zulfajuniadi/unity-ecs-navmesh

 

Yap， need an async mode.

 

Thumbs up for async mode.

 

Same here... Async would be great! Thumbs Up

 

There's experimental NavMeshQuery API:
https://docs.unity3d.com/ScriptReference/Experimental.AI.NavMeshQuery.html

Interested methods:

Code (CSharp):

1. BeginFindPath
2. UpdateFindPath
3. EndFindPath

It's synchronous, but it can be used from jobs, which is a way to make it async.

 

Man unity needs to add this asap. Meanwhile, I hacked together a solution

Code (CSharp):

1.     IEnumerator SetAgentDestinationWhenReady()
2.     {
3.         agent.SetDestination(AgentTargetPosition);
4.         while(agent.pathPending)
5.         {
6.             agent.velocity = (AgentTargetPosition - agent.transform.position).normalized * agent.speed;
7.             yield return new WaitForEndOfFrame();
8.         }
9.     }

I'm just moving the agent in a more primitive way until the path calculation is done.

The agent was briefly stopping after each waypoint. Both velocity and desired velocity dropped to 0 for a few frames and this caused the agent to start accelerating again. So I found this solution. Hope this helps

 

I agree, we really need this!

Wow I had no idea, I thought I was just bad at coding my bots as some of them were doing exactly that every now and then, thanks a lot!

 

I disagree. Async would be a band-aid. Navmesh needs to be moved to another thread, where it can happily take 100ms to calculate a path without affecting the framerate one bit.

 

So it's already 4 years and still no async, or did I miss something?

Thank you for this solution. I just hope async really considered as an official feature in future

 

Not Only Async but also return the OffmeshLinks too, not just a Vector3 List