ComputeAsync Pathfinding Calculation Taking Absurd Amounts of Time

I’ve created an NPC hivemind system that uses pathfinding to keep NPCs from clumping together when fighting a player.

How the system works:

-Closest NPC aggressively attacks player
-Other NPCs “hover” around the player, through the use of pathfinding. The system was designed for them to avoid a certain radius around the player if possible.

EXPECTED BEHAVIOR:


As you can see in this video, the NPCs are successfully pathfinding to random points around the player.

PROBLEM:

The NPCs will suddenly all stop pathfinding and stand completely still. This seems to happen at complete random.

I have narrowed this behavior down to ComputeAsync calls slowing down drastically, and at random, sometimes taking up to 45 seconds, when most of the time it takes < .2 seconds. The result is that all pathfinding-related processes are paused due to ComputeAsync’s long yield time and the NPCs stand still. This seemingly happens to all of the NPCs in the game at once.

local StartTime = tick()
local success, errorMessage = pcall(function()
	path:ComputeAsync(CharacterModel.PrimaryPart.Position - offset, destination)
end)
			
local TotalTime = tick() - StartTime
print("Path Compute Time: "..tostring(TotalTime))

image

Above is a less extreme example, but it’s still extremely odd that ComputeAsync yields for up to 3 seconds in this case.

THESE ARE NOT THE CAUSES:

-Memory leakage. I have confirmed that there is no memory leakage relating to Navigation
-Networkownership. I have confirmed that networkownership is always set to nil for NPCs
-Logic errors in my code. I have confirmed that the NPCs are attempting to pathfind when they should, it’s just taking a very long time thanks to ComputeAsync

POTENTIAL CAUSES:

Are there limits to the number of consecutive ComputeAsync calls you can make? Does it start to throttle if there are too many? I make calls very frequently so this explanation seems plausible, and I’m taking measures to lessen the amount of ComputeAsync calls.

Any other ideas? Beyond that, I’m completely stumped. Thank you for your help.

1 Like

Curious

  1. How many NPCs do you have and are they all somehow running path computing even when at an idle state?
  2. Have you tried testing at specific locations? I’m not well versed in pathfinding, is it possible that the offset is somehow “clipping” the location out of bounds, causing a very long compute time due to impossibilities?
1 Like
  1. There are 141 NPCs total on the map. Paths are not computing in an idle state, only when a player is aggro’d.
  2. I do not think the offset causes impossibilities. Here is how it’s defined:
local offset = Vector3.new(0, CharacterModel.PrimaryPart.Size.Y/0.75, 0)

It offsets the start position by a small amount. I did this because of what I read in this post:

1 Like

In addition, I just ran 2 tests with absurd amounts of NPCs.

100 NPCs


300 NPCs

You can see in the output that there is little slowdown, even with all of these NPCs pathfinding constantly at once. Even with 300 NPCs aggro’d simultaneously, ComputeAsync yields for a relatively short amount of time, ~1 second at most. This is not what I expected at all.

1 Like

Those tests looks relatively fine to me. What about your destination variable, is that guaranteed to be at a valid non-clipped location?

I honestly don’t know the exact solution, I’m just throwing possible theories out there.

To simplify, in hover mode when NPCs aren’t pathfinding directly to the player, I use raycasting to verify a location exists in the first place and call ComputeAsync if I get a position from the raycast.

The ComputeAsync function is the only way to tell if the NPC can traverse obstacles to get to destination in the first place, so there will be times when ComputeAsync indicates that there is no calculated traversable path.

When the path computation time is long, is it for every npc and for a short duration (restores to expected behaviour)? If so then the server is probably busy doing something that might be not even related to pathfinding. Also not sure how path computations work if a destination happen to be slightly inside a part. But yeah you could check script performance or something to check if the server is dying

Yes, it does restore to expected behavior. Based on this output in one of my game’s servers, there seems to be a gradual increase in computation time, a peak, and then a gradual decrease back to normal.

It seemingly becomes more frequent the older a server is, and the extremity of the computation time also increases.

The length and duration of the spikes seem to be completely random.

Well the only assumption I can make is that you have a memory leak somewhere, or something in your game is overloading your servers. Which basically translates into I can’t help

Wrong. I’ve confirmed there are no memory leaks.

If it were a memory leak, the computation time would also increase on average across the board. The computation time only spikes and returns to normal.

Update:

I have drastically reduced the rate at which ComputeAsync is called, and the long yield spiking still occurs.

It seems like an internal (bugged?) behavior if the behavior is random and possibly based on server uptime. I’m not too sure how ComputeAsync works internally, but it is very possible that some other internal task is holding up the computation.

The reason why I said the following is that I’ve noticed that the computation time spikes whenever the Master_Data gets printed out for a player in both images (which I’m speculating does a DataStore (web) call). Does this issue happen on an live empty server (since your studio tests seems fine)?