Evaluating Navigation Crowds Performance

Questions
, ,
1

Hello :slight_smile:

Currently working with recast-detour and Navigation Plugin crowds, I’m seeking for infos about the possibility to evaluate Navigation Plugin’s performance.

The plugin works very well, but also it’s quite of a black box. For example after a call to :

crowd.agentGoto(id, position);

Then the agent moves by itself, but how to evaluate this compute cost ?

Maybe @Cedric you can help on this since as far as I can see the git blame, you worked a lot on the implementation :slight_smile:

Here are some questions :

  • When calling crowd.agentGoto(id, position); my guess is :
    • Most of the cost is at the call time since it will compute path finding within the NavMesh
    • Then the path is in memory, no more use of the NavMesh
      → Am I right ?
  • Another way of asking the previous question would be : when increasing the complexity of the NavMesh, will it only increase the cost of the single crowd.agentGoto(id, position); call, or will it as well add some extra compute cost while the agent is moving from point A to point B ?

For example in this Playground you can drag the target with the mouse, and the agentGoto is called again on each frame if mouse moved. But the result won’t be very different if for example I call this goto update only once every 100 ms : Playground (updateDelay line 99)

But is it wortht the effort reducing the calls to crowd.agentGoto ?

Other question :

image
image1441×342 33.5 KB

Let’s say this is the the Map of a game :

  • At start (let’s say “level 1”) doors A,B,C,D are closed
  • The agents will be only in room 1, with player
  • Then at level 2, the door A opens, and agent will be free in both room 1 and 2

I’m looking for optimisation here :

  • “Simplest” is to have one NavMesh, for the full map and that’s it
  • For optimisation I would have a NavMesh room 1 only and at level 2 switch to another NavMesh room 1 + room 2 for example
  • About computing, level 1, when going from point A to point B within room 1 (crowd.agentGoto), does it actually change the compute cost that the NavMesh includes rooms 2,3,4,5 ? I mean, I don’t know exactly the algo, but could be that it’s using some kind of octree bounding volume hierarchy, with as a consequence the fact that if both A and B are included in a sub part 1 of the mesh, the existence of rooms 2,3,4,5 will be at “no cost” …

It’s quite hard to evalutate the general compute cost of the whole Nav Plugin, in term of frame milisecond :thinking:

2

To make it short, agentGoTo is almost free as it find the nearest poly and sets the agent to a gotostate.

Finding the nearest poly is more demanding as it computes distance for each of the navmesh polys. In practice, there are a few hundred poly per navmesh and finding the poly the agent belongs to doesn’t happen each frame.

Now, all path logic is in the update method.

So, you won’t see a cpu usage peak when calling goto but you will next crowd update. A possible improvement here is to dispatch agent godo call to multiple frame so next time update is called, it will compute paths for some agents but not all.

Navmesh data is needed for path computation and steering. I don’t know if it’s possible to separate crowd and nav mesh.
It’s possible up to some point. Once you have a computedpath, you can have your own agent navigation that will try to follow your path but as soon as avoidance happens, you’ll have to recompute a path. Basically, as soon as the agent leaves the poly it’s “attached” to.

1 Like
3

Thanks for your answer :slight_smile:

Do you mean that, by default, that’s already what happens ? (Agents computing multiple times their own new path, in order to avoid collision, without the goto state being modified)

Also, is there a way to get the compute (per frame) time of the Navigation ?

4

Agent will recompute path if it becomes invalid :

I don’t know how frequent it is. At least after setting goto as state is DT_CROWDAGENT_TARGET_REQUESTING. I think it’s quite rare compared to number of frames rendered. It’s part of tick update.

You can profile this block of code to get an idea of tick update duration : Babylon.js/packages/dev/core/src/Navigation/Plugins/recastJSPlugin.ts at master · BabylonJS/Babylon.js · GitHub and Babylon.js/packages/dev/core/src/Navigation/Plugins/recastJSPlugin.ts at master · BabylonJS/Babylon.js · GitHub

I’m curious to know the profiled duration you’ll get :slight_smile:

1 Like
5

On the previous pg staring 250 agents, a raw performance.now() timer (before VS after) gives an average 2 ms of compute :

Screenshot from 2025-04-01 17-32-25
Screenshot from 2025-04-01 17-32-25374×628 18.2 KB

And this timing seems to remain the same, regardless of if I drag the mouse (updating 250 goto targets on each frame) or not.

Edit : in fact it seems that the collision avoidance has a much higher cost than the path finding. By reducing the agents param collisionQueryRange I go down to ~0.5 ms while increasing it have the total going up to ~3.5 ms

1 Like
6

That’s interesting numbers. ~2ms for 250agents sounds like quite performant. I guess rendering will be a bottleneck sooner than navigation.