Hybrid ECS project evaluation

[Unkel_Rambo]

• A* PRO version: 5.2.4
• Unity version: 6000.23.f1 and 2022.3.20f1 (then 2022.3.51f1)
• Burst 1.8.18
• Agents Navigation 4.0.8 (also imported for A/B testing)

I’m a fairly experienced former AAA dev (15+ years, Valve, Microsoft, ArenaNet, etc.) and I’ve had A* PRO for a while, but don’t use it much except for some light prototyping so I’m not super familiar. I’m working on a hybrid ECS top-down, co-op, open-world RPG project and I’m looking for a more performant pathing solution than what I’m using. I’m trying to evaluate if I need to write my own ECS based pathing to meet all my crazy requirements. The A* 5.0 upgrade looks like it may be exactly what I’m looking for! However…

I have some crazy requirements, and basically two questions regarding walls I’ve hit during my initial A* 5.0 evaluation.

Requirements are:

• I’m using Netcode for GameObjects for networking, mostly because Netcode for Entities was missing some important features when I started this project almost 3 years ago. I may end up converting to Netcode for Entities, maybe irrelevant…
• The target world size is pretty large, ~200,000 x 100,000 unity units, but that may change. Depends on quite a few factors that I won’t get into, more design than technical.
• The world uses Unity’s built-in Terrain system (for now) with a proprietary voxel based building system.
• The server runs all authoritative simulation logic using ECS and, when parts of the world come in to a client’s relevancy window, very simple GameObject “actors” are spawned and replicated to that client. I did this for a bunch of reasons, but the TLDR is that most Unity Assets I’m using for visuals don’t have an Entities counterpart or integration. Yet.
• The server dynamically currently generates navmesh for 3 actor size categories for each client’s moving relevancy window. This is pretty slow, can’t remember numbers off the top of my head…
• For now, when structure information changes (a player builds a new voxel structure, part of a structure is destroyed, etc), nav-mesh links are created/destroyed in a custom Job.
• Clients run a paired down ECS simulation for certain systems, mainly for prediction. For instance, there’s a very simplified system for updating ECS character controller state like “isGrounded”, stuff like that. But clients are mostly focused on updating the ~100 GameObject Actors around them in their relevancy window for things like animations, VFX, audio, and other signifiers.
• Clients need a single NavMesh around their camera for some very light weight pathing for things like teleporting local players back onto the screen when they walk off screen, pathing for some visual effects like waypoint markers, etc.
• My goal is to support at least 10 players simulating roughly 100 moving agents around unique relevancy windows, so ~1000 agents total.
• All of the AI pathing is server authoritative (for now), so I need 1000 agents pathing more or less as quickly as humanly possible because there’s SO MUCH other stuff going on. If I can keep the whole pathing update to < 0.5ms on my target hardware (Ryzen 3 2200G) I should be good.
• AI pathing is currently throttled to something like 50 agents/tick on the server with some simple nearest-to-player prioritization.
• I’m currently on Unity 2022.3.20f1 but I’m evaluating updating to Unity 6.
• All tests so far have been done on my Ryzen 5950x workstation.
• I have about 4 hours to evaluate A* 5.0 as a possible solution, burned 2 already this morning

That should hopefully be enough context. Now, questions:

SITUATION: I’ve been trying to set up a sample project to evaluate performance of the new ECS/Jobs/Burst Compatible pathing in 5.0 and Unity 6 and I’m not seeing a clear sample I can use as a base. I want to profile 5000 agents pathing and compare that to my current solution.

ATTEMPT #1:
I modified the LayeredGridGraph example as-is to have 5000 copies of the bot moving toward the cursor. No changes to the bot GO. Enabled Burst ON, Burst Safety Checks OFF. Backend: Mono.

RESULT #1.1:
The result in Unity 6 was ~900ms pathing update in a built Dev exe, which was slower than running in the editor.

RESULT #1.2:
I got an error from A* PRO in Unity 2022.3.20f1 so I installed 2022.3.51f1.
The result in a built Dev exe 2022.3.51f1 was ~1400ms.

Clearly I’m doing something dumb… the update was running on one thread.

ATTEMPT #2:
I modified the 5000 bot test’s A* object’s Thread Count to “Automatic High Load” (aka 32 threads)

RESULT #2:
Still > 900ms in Unity 6 exe, barely any thread utilization in any of the 32 “Pathfinding” threads.

Still doing something dumb…

ATTEMPT #3:
Changed Backend to IL2CPP.

RESULT #3:
AIPath still >900ms, hardly any thread utilization.

Clearly I’m missing something… Past my “ignorant guy going in blind” evaluation period so it’s time to ask the forums

Question #1:
Is there an existing stress test floating around somewhere that I’m not seeing that could fit my requirements?

Question #2:
Is there a sample you would recommend that I start with to quickly evaluate my 5000 agent update scenario?

Question #3:
Barring #1 and #2 being viable, what’s the absolute shortest path (lel) I could take to setup a sample scene to quickly profile ~5000 agents pathing around?

Thanks in advance!

edit:
I forgot to mention that the Agents Navigation Mass sample, slightly tweaked, is ~2.2ms on my workstation with 5000 agents moving around with local avoidance disabled. ~4.2ms w/local avoidance.

I’m investigating the Agents Navigation x A* PRO integration, but I don’t see a sample yet…

[tealtxgr]

Hi there, thanks for the detailed write up!

@Unkel_Rambo

I’m a fairly experienced former AAA dev (15+ years, Valve, Microsoft, ArenaNet, etc.)

Very cool btw!

I off-hand do not have a ton of answers for your questions, however I did want to link this page on optimization as it may contain some useful information you might’ve not seen yet. In any case, I’ll tag @aron_granberg on this one to see what he may think is the best option here. I’d be interested to know how someone could test the performance limits.

There’s also this section about the FollowerEntity on performance that may be of use?

Also I might’ve missed it in your post, but did you mention which of the agent types you were using? Mostly asking because I also know that A* is pretty extensible and you can usually get some pretty good work with some customization, since the built-in movement scripts are a really good catch-all but not the end-all-be-all. (I’m not even sure if Aron intended that but that’s definitely one of my favorite things about this package is just how much you can do with it depending on how deep you personally want to go)

[Unkel_Rambo]

@tealtxgr

issed it in your post, but did you mention which of the agent types you were using? Mostly asking because I also know that A* is pretty extensible and you can usually get some pretty good work with some customization, since the built-in movement scripts are a really good catch-all but not the end-all-be-all. (I’m not even sure if Aron intended that but that’s definitely one of my favorite things about this package is ju

Thanks for the response!

I’m not sure which agent type I was using, I literally just duplicated the bot GameObject that was in the LayeredGridGraph example scene I mentioned that’s part of the package. I haven’t looked at this since, but I need to throw some time at it Soon:tm:

One thing I did just notice: I didn’t change the default graph size so a number of bots were spawning off grid. I disabled ~4000 of those bots, and the 1000 that are still enabled are definitely on the grid. In RELEASE mode in the Editor, I’m seeing a 76ms BathedEvents.Update() and NO other job/thread utilization.

BUT, RESULTS!

Then, I tried the Agents Navigation packages A* integration test scene with 5000 agents and local avoidance turned off (not a big deal for my project.) Here’s what I saw:

~3.5ms for a Dev build in that scene. Not bad!

With Local Avoidance enabled, about 9ms. Can’t upload a screenshot because I just discovered the 4 image per post limit and this is one I deleted

For comparison, the Agent Navigation package using Unity Navmesh is just over 3ms with Local Avoidance turned off:

and just about 6.3ms with Local Avoidance turned on (image deleted due to limit.)

Then I did an IL2CPP A/B test for Dedicated Server on my target hardware with Local Avoidance disabled.

IL2CPP Agent Navigation/Unity Navmesh ~7ms:

IL2CPP Agent Navigation/A* ~11ms:

I think this is good enough for me, for now. I’ll have to see if I can import my test scene to see how A* handles the voxel buildings on terrain with layered grids, but this is a good start. I’ll do some more tweaking and tuning to see if I can optimize this test a bit more.

The feature set that I need is broad and the less time I can spend implementing my own pathfinding system, the more other cool stuff I can build

[aron_granberg]

Looks like you got some good results!

I have a few points to add:

@Unkel_Rambo

The target world size is pretty large, ~200,000 x 100,000 unity units, but that may change. Depends on quite a few factors that I won’t get into, more design than technical.

This is pretty big. I typically recommend people to keep their world within about ±16000 units, due to reduced floating point precision as you go to higher values. I cannnot gurantee that all movement scripts will work reliably up to 200 000 world units. At those values, floats don’t even have centimeter resolution.

In any case, I would recommend a recast graph for a large world. It will be the fastest and use the least memory. A grid graph scales badly to very large worlds.

@Unkel_Rambo

I’m not sure which agent type I was using, I literally just duplicated the bot GameObject that was in the LayeredGridGraph example scene I mentioned that’s part of the package. I haven’t looked at this since, but I need to throw some time at it Soon:tm:

Then you were likely using the AIPath movement script. This one is completely single-threaded and not the fastest.
The newer FollowerEntity movement script uses ECS and burst for extra performance. It also just has better movement overall.

I just tried out 5000 agents in the editor with only gizmos rendering and it spends about 3 ms on the main thread, though my computer has 16 cores, which is not really representative of most players. This is also when the destination is stationary for all agents. If it moves, then performance goes down as agents have to repair their paths more thoroughly. Typically most agents in a game will have a stationary target, though.

I would expect the Agents Navigation Package with the A* integration to be slightly faster than using the FollowerEntity overall. It doesn’t have an as complex movement behaviour. And it is also pure ECS, instead of the FollowerEntity which still has a GameObject to keep track of.

[Unkel_Rambo]

Thanks for the response @aron_granberg ! This was exactly what I was looking for.

Would you consider adding a “stress test” scene like this to the examples for distribution? I think I got what I need given my time constraints. I’ve got a few more questions I’ll post as separate threads as I investigate integration a bit more. Right now I’m using Unity’s AI Navigation package, which is ok but it has some severe limitations that I’ve had to work around in ways that I won’t be able to ship. For instance, since I create a scrolling nav window based on player position, whenever two remote players come near each other I have to combine those nav windows and regenerate the nav mesh. Unity doesn’t seem to have a good solution here (something I’ll ask about separately…)

As for the world size, my project has a fairly zoomed out camera so the 1x2m characters aren’t huge. Centimeter accuracy is an absolute upper bound, and at 200,000 units a minimum float step is like 0.007812, or ~8mm at my scale. Good enough for what I’m doing The final world size will probably end up being smaller, I just started noticing artifacts above that scale.

Thanks again!