Player Entering Small Gaps in Recast Graph Causing Agents to Stop Seeking

[oneflowman]

• A* version: 5.3.2
• Unity version: 2022.3.27

Hello!

I’ve got some decent sized maps (around 800x800 maximum) in size, and at times, (a max of) 300 agents all trying to navigate to the player (always over a shortish distance). I was using a grid graph before, but I am in the process of trying to optimize all of my pathfinding stuff and so I am trying to switch over to a recast graph.

The problem: My player can potentially find gaps in the graph and by entering those gaps, all enemy agents stop seeking them.

The obvious solution is to adjust agent radius/voxel size to close those gaps, but the best I can do for an acceptable functionality is a 0.3 character radius, and a 0.15 voxel size, the result of which can be seen below. Those sizes seem well below the default settings, and I get a little warning about scan time, so not sure how much optimization I am losing at those settings (I am caching the graphs, so not worried about initial load times).

Even still, if a landmass is near enough another landmass, it creates a space where there is no graph, but in which the player could fit. I can certainly solve that with some level redesigning, but first I wanted to be sure there are no other solutions I am missing. Also just slightly concerned I will miss a spot and create a bug, it’s not exactly easy to review a map this big to find every possible gap.

Really, my goal is simply for the agents to keep seeking the player. If there’s some sort of way to fudge it to where they will still seek them, even outside of the graph, I’m open to that. Or if there’s a better way to configure this graph (settings shown below). Just looking for ideas, or maybe information I lack. I am also not sure at what point the benefits of recast over grid graph start to flip, or if there’s an easy way to take a guess, such as the voxel/tile count vs the grid graph. (Obviously I can profile it, which I have done a little bit, and it seemed to be faster, but Unity’s profiler is a slog to use and having to do it repeatedly after every settings tweak is a bad time lol, would rather look at some rough data, and then profile it once I think I’ve got “ideal” settings).

Thanks!

Edit: Also curious if going low in the agent radius/voxel size settings has an impact on actual runtime performance, or if that only slows the initial scan (which will be irrelevant if cached). Maybe I’m trying to solve an imaginary problem that I can just solve with using smaller sizes in those settings.

Edit2: After a bit of profiling with these settings vs my previous grid graph, the grid graph seems to work better actually… I seem to get about half as many sub-30fps spikes with the same agent load… Verified I am using same thread settings on both (automatic high load, which for me is 16 cores).

I’ve also not mentioned that I am using RVO and AIPath for movement, in case it is relevant. I also tried my grid graph without RVO and with AILerp instead, but my gains there also seemed negligible, and the NPCs seemed to jitter a lot when the game was paused for some reason.

I profiled various spikes to see where my problems were when I started out (using my normal grid graph / rvo / aipath setup). Probably TMI lol, but this is what I was looking at when I started my optimization journey. Movement, though it was among the lowest of spike times, was the most common cause of spikes that I saw. Not sure if there’s anything else on this list that jumps out as an “aha!”

[tealtxgr]

@oneflowman

but the best I can do for an acceptable functionality is a 0.3 character radius, and a 0.15 voxel size, the result of which can be seen below

Can you dive more into this? I think having a larger radius and larger voxels may help here, but this seems to be prohibitive in your case.

[oneflowman]

This is the problem I am trying to avoid, agent size 1, voxel size 0.5

At 0.8 / 0.4:

At 0.6 / 0.3:

I could probably make 0.6 / 0.3 work if I review my level a bit and make sure there’s no blank spots that the player’s collider can squeeze into. But, based on my testing with that just now, I average like 26fps on the recast graph with those settings, and 30fps on the grid graph over a 2 minute period for each. It’s such a small difference that I can’t necessarily attribute it to the difference in graph itself imo, and the grid graph gives me better looking movement, so I am leaning towards just sticking with it and finding other ways to improve performance.

I’ve looked into the heuristic optimization, but I have a lot of large open spaces, so my understanding is I wouldn’t see much gain from that.

I think I have a bit of overhead I am losing though using BehaviorDesigner to direct all of my NPCs around. It really isn’t necessary for the simplicity of my enemy behaviors, and when I tried swapping off of it and just using your AIDestinationSetter, I saw a pretty decent performance increase. That might honestly get me into a realm that I am comfortable with. Still need to do more extensive testing on that though.

I also mentioned that I am using RVO, not sure if there’s any optimization tips for that.

I also had a question about the Batch Graph Updates… Does a higher update interval necessarily mean better performance? I don’t really understand fully what this feature is doing, if it is holding onto paths to update them all in batches, wouldn’t allowing the batch to become too big lead to lag spikes? Or are there limits on the batch sizes already? Or am I misunderstanding what this feature does completely?

Sorry, I know I am typing a lot and am a little all over lol. I feel like in most normal cases, optimization like this wouldn’t even be an issue, I am just pushing limits here with 300 agents, and trying to determine how I can rein it in a bit. I’ve been fiddling with settings all week. I thought switching to recast graph was gonna be a game changer lol, but doesn’t seem to make much of a difference at all strangely.

[tealtxgr]

For your performance questions, I’m thinking playing with tile size may also help to some extent. Actually, I wanna go ahead and link this entire page on optimization that may be helpful. Local avoidance is actually pretty dang performant, and AIPath is pretty good too- not as good as FollowerEntity, as its core is based in ECS (important note, you don’t need to know ECS to utilize it!). Lastly, I’m looking at graphUpdateBatchingInterval and it looks like, just by virtue of how it works, setting that a tad higher may help performance, but will decrease latency/accuracy of pathfinding which may or may not be a dealbreaker depending on your game. It defaults to 0.2f which 5 times a second so bumping that up to 0.5f may yield some results? Not sure, but I’d play with that too!

@oneflowman

I don’t really understand fully what this feature is doing, if it is holding onto paths to update them all in batches, wouldn’t allowing the batch to become too big lead to lag spikes? Or are there limits on the batch sizes already? Or am I misunderstanding what this feature does completely?

To answer this more directly, it looks like it will just hold graph updates and calculate them all at once. I can’t imagine this causing a lag spike as, AFAIK, this would be all done in parallel sorta asynchronously. You may notice a dip in frames for a split second based on your graph settings. I’m pretty sure agents will only “continue on the existing path” until their paths are refreshed (like if you have repathing turned on). So TLDR, I’d imagine this may help depending on what your bottleneck is.

@oneflowman

Sorry, I know I am typing a lot and am a little all over lol.

Brother I have ADHD, this is my type of conversation

So, quick post-script question- how many agents are requesting a new path every frame? All of them? I don’t know what the normal amount of calls to those methods are, but I’m sure, for a single unit, it would only be one per. Mind giving some insight into how your pathfinding and movement updates are being handled, such as with AIDestinationSetter, manually in code, etc?

[aron_granberg]

Hi

Paths will normally go to the closest point to the destination that the path can reach. However, there’s a distance limit set by A* Inspector → Settings → Max Nearest Node Distance.

By default it is set pretty high, but maybe you have lowered it? If so, I would suggest increasing it a bit.

@oneflowman

Also curious if going low in the agent radius/voxel size settings has an impact on actual runtime performance, or if that only slows the initial scan (which will be irrelevant if cached). Maybe I’m trying to solve an imaginary problem that I can just solve with using smaller sizes in those settings.

It may increase the detail in the navmesh, which has some impact on pathfinding performance. This effect is pretty minor, though.