Efficient pathfinding implementation

General
1

Hello,

I just purchased Pathfinding Project Pro and I’m really loving it.

Right now, I have a simple setup for basic testing, but I’ve found that it will not do for my performance requirements. I’m using a RecastGraph with AIPath, which causes framerate to drop considerably with only 30 active AI following a target. As mentioned in AIPath comments, it is not an efficient solution.

Here are my requirements:
128 active AI, up to 64 separate moving targets.
Up to 10 AI following the same target.
AI needs to be able to closely follow target since AI needs to get within melee range and not easily be avoided.
AI is being run server-side, and server cannot drop below 60fps.
Server process affinity is set to a single core (Xeon processor equivalent to i7-3770k)
If possible with these performance requirements, local avoidance

There is practically no computational overhead for the server logic, so the majority of cycles can be put to use for pathfinding.

Before I try to find out the most efficient solution that will fit these needs, I would first like to find out:
A) Can my requirements be reasonably accomplished with A* Pathfinding Project?
B) If so, can anyone provide tips on which out-of-the-box functionality I should utilize to meet these requirements?

Thank you! :slight_smile:

2

See http://www.youtube.com/watch?v=htoen7x3LuQ for a stress test. That’s 600 agents all pathfinding on a grid graph.

Ok, what to consider to get a low overhead:

  1. DONT USE CHARACTER CONTROLLER. They are really slow. Use rigidbodies if you need physics, a simple raycast if you don’t need that much physics or just transform.Translate if you don’t need physics at all.
  2. Run pathfinding in a separate thread. See A* Inspector -> Settings -> Multithreading. When you say “Server process affinity is set to a single core”, do you mean the server can only run on one core? If so, that is really bad for performance. Pathfinding can run in it’s own thread(s) on a separate core(s) to speed up performance.
  3. Use navmesh based graphs (that you already do)
  4. Don’t test it in the editor, the editor slows things down.
  5. Don’t use debugging. Turn off A* Inspector -> Settings -> Path Log Mode.
  6. Use path pooling for reduced GC pressure (see http://arongranberg.com/astar/docs/pooling.php)
  7. Lower repath rates if possible
  8. AIPath is not the most efficient script if one wants a lot of them. It is best suited for when you have only a few agents since it does some relatively heavy computations, but those computations are mostly wasted on agents the player can’t see anyway if you have a lot of them.
  9. Local avoidance is very cheap, I can simulate several thousand agents at reasonable fps (again, multithreading) while they are as packed as they are going to be.
3

Excellent! Thanks for the reply.

I didn’t give thought about the impact the Character Controller has on performance. I’ll replace that first, and then come up with a barebones replacement to AIPath.

I could allow the server process to utilize more than one core, but since I will be running four server processes on a four core machine, I figure it would be best to bind them to a dedicated core so any performance-killing problems on one server process wont affect the others. Not only that, but I imagine if I cannot get it to run smoothly on one core, there will be resource issues in a situation where all four servers are utilizing the maximum number of AI.

4

I see.
Then you might want to enable the Single Core Optimization. See http://arongranberg.com/astar/docs/optimization.php

5

As you mentioned, Aron, the AIPath Script isn’t made for good performance.
I’d really appreciate a script that is good for performance, to demonstrate how a movement script should look like.

6

Wow, I wasn’t aware that the character controller would present such issues. I definitely second that an example of a different controller would definitely be useful.

7

I’ve found RVOController to offer much better performance. Gravity is handled via downward raycast, and as a bonus, I use the same raycast to see if an AI has been pushed out of the world and needs to be teleported to the nearest node.

Here is the modification I made:

if (Physics.Raycast(realPos + Vector3.up * height * 0.5f, Vector3.down, out hit, 100, mask))
{
adjustedY = hit.point.y;
}
else
{
NNInfo info = AstarPath.active.GetNearest(transform.position);
Teleport(info.clampedPosition);
}
realPos.y = adjustedY;

Simply switching over to the RVO system with RVOController instead of CharacterController, I’m now within my performance requirements.

I’ll still looking for a more efficient implementation for AIPath down the line when I need to squeeze more performance, though.