Testing A* for project with 4000 - 10,000 agents

Beginner Questions
#1

Hi,
I am working on a project that has 4000-10,000 agents.

Using Unity NavMesh system i have been able to get a minimum of 30fps with 4000 agents, i figure this asset may be able to give way better performance.

Some very beginer questions if i may:

How do i get groups of AIpath.cs to start moving at the same time (within a few frames) Unity navmesh has such as function as:
NavMesh.pathfindingIterationsPerFrame = 400;

Is there a variable such has agent.hasPath or agent.pathPending?

I am testing with AIpath.cs at present, but i assume AILerp is the fastest movement script?

I was very impressed by your example scene with 5000 RVO SIM, i was able to get 74fps using SIM FPS 5. (& 10000 agents 42fps with SIMFPS of 3).

#2

Hi

10000 agents is a lot.

Yes, in fact they use those exact names.
See https://arongranberg.com/astar/docs/iastarai.html#hasPath
and https://arongranberg.com/astar/docs/iastarai.html#pathPending

(note that IAstarAI is an interface which all built-in movement scripts in this package implements).

That parameter doesn’t have anything directly to do with them starting at the same time, it just allocates a larger time slice to pathfinding.

In my package you can do this in one of several ways:

  • You can block until all paths have been calculated using the path.BlockUntilCalculated method (you can get the current path that a Seeker is calculating using seeker.GetPath()).
  • You can make all agents stand still until all paths have been calculated. You can do this by enabling ai.isStopped while any agent’s ai.pathPending property returns true.

You have probably already figured this out, but make sure to use multithreading in A* Inspector -> Settings -> Theads to get good performance for that many agents.

AILerp is the fastest, however it does not support local avoidance. For 10000 agents it is however possible that you will have to either write your own movement script or customize the AIPath script for best performance. The AIPath script has a lot of features that you probably don’t need and are thus only an unnecessary performance cost (e.g. using rigidbodies/character controllers for movement, walking on rotated surfaces, slowing down very precisely to a particular point, and many other things).

Note that using a simulation fps that low can have negative effects on the quality of the local avoidance. If it works for you, then that’s fine, but usually I wouldn’t go below a simulation fps of around 10.

Note also that the example scene with that many RVO agents is very lightweight. It doesn’t even use a GameObject for every agent, because that has a lot of overhead when you have that many agents, instead it just renders a single quad for each agent.

I see that you sent me an email a short while before you started the thread here in the forum with roughly the same questions. I assume just answering here is ok?

#3

Hi Aron,
Thank you very much for taking the time to write such a detailed reply, its much appreciate.

10,000 agents is indeed a lot, i think flowfields may well be the solution i need to go with but i’ll continue to test and let you know if i find any success.

1 Like
#4

Okay.

You should check out the FloodPath btw. It is not really a flow field, but uses a similar principle. It allows you to calculate a bunch of paths to a single point very quickly (at least after the initial path calculation, which may be quite slow though, depending on the graph size).