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

19 Likes

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

1 Like

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

2 Likes

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.

5 Likes

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

1 Like

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.

1 Like

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). Home Page. | AI Navigation | 1.1.5 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.

1 Like

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.

1 Like

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.