Hello,
My project is RTS (lockstep) on pure ECS. I wrote my own systems for RVO, movement, etc. There can be about 10k units on a map. I am currently using UnityNavmesh (new components) and it works almost fast and well. I use Navmesh to find paths and to find the nearest point on the surface.
Since there are a lot of units, instead of physics, I use the search for the nearest point on NavMesh. In the case of Unity NavMesh, this takes ~ 8ms in 7 threads (each).
But unfortunately I cannot use Unity NavMesh as it is not a fully deterministic system.
As I understand it, A * PP is deterministic.
I am considering a multilevel grid or navmesh. However, due to the large number of units, I want to clarify: can A * PP do what I need?
I need:
World size: 2k x 2k
Pathfinding (~ 128 / frame)
Search for the nearest point on the graph (possible in a small radius) (~ 10k / frame,)
I don’t need an RVO, etc.
There are also obstacles in the game, a rare rebuild of parts of NavMesh (now this is done using separate surfaces and links).
Can Burst functions be used? Or can I use NativeArray and asynchronously / synchronously (and not from Burst) pass them to A * PP so that it will return the result to me in the same (or another NativeArray) array?
10000 units is a lot of units.
There are several considerations:
128 pathfinding requests per frame… doesn’t really tell me much without knowing how long the paths are.
Is the map static, or does it change?
Are most units moving towards a single target, or do they all have mostly individual targets?
10k nearest node queries per frame… That is a lot. I’m kinda doubtful that this can be done with a reasonable frame rate. If you set a small maximum distance (A* Inspector -> Settings -> Max Nearest Node Distance) it might be doable though. As it primarily gets expensive if you search for the closest point when that point is far away.
However, if you know that you always search for the closest point on the navmesh for an agent that is moving across it, then you can do things in a potentially more optimized way. Keep track of the closest triangle in the navmesh and then search for the closest point on that triangle and its neighbours. This is not always perfectly optimal, but it’s usually faster and good enough I think.
It is only deterministic if you exclude things like paths taking a varying amount of time to calculate. You will need to deterministically call path.BlockUntilCalculated() to ensure the paths are ready when you need them.
Those parts of the system are not burstified yet. Currently, only local avoidance, recast graph scanning and grid graph scanning are burstified (in the beta version). However, those parts are kept strictly internal and are not exposed to users.
Each unit recalculates the path approximately 200 meters every N frames. Thus, I divide 10k units into several frames and in 1 frame I search for a path for only 10k / N units. Now it is 128 requests per frame. NavMesh does this in about 10-20ms on a single thread (I haven’t split this part into multiple threads yet).
The map has a static terrain and dynamic objects. This is now done with Obstacles and a few small surfaces (linked via NavMeshLink) that are quickly recalculated in real time.
Most units move towards one target. However, I have already made an optimization for this: the game uses groups of units (formations) and units do not recalculate their path if they are close to their group. In this case, the path is counted 1 time for the entire group. But since there are situations where units are split up in narrow aisles, I expect that a search may be needed for each unit. But this is optional.
Actually my biggest problem is the placement of the unit on the NavMesh surface or mesh. Since there are a lot of units, I don’t use physics. Every frame I check if there is a NavMesh surface in radius N (for example 5). If not, most likely the bridge (just for example) under the unit was broken and the unit begins to free fall (and here the physics on raycasts is already turned on). If a surface is found, the unit simply moves to the nearest point on the surface. This allows, without using physics, it is guaranteed to prevent the penetration of a unit into an obstacle (building, mountain, etc.).
At the moment I am using the NavMeshQuery.MoveLocations function for this. https://docs.unity3d.com/ScriptReference/Experimental.AI.NavMeshQuery.MoveLocations.html
And also its own extension for NavMeshLink detection.
When tested on 10k units, it takes 8ms per thread (7 threads). This is actually the slowest part, but it still gets through fast enough.
Perhaps there is a way to do the same as with RaycastCommand (regular physics via DOTS)? They don’t support Burst either.
For them, I just need to create a NativeArray with requests and send them synchronously to the physics engine. And after that get the NativeArray with the results.
Here’s some sample code: https://docs.unity3d.com/ScriptReference/RaycastCommand.html
That is, I do all my calculations, then after the synchronization point I send an array with the position of the units in A * PP, and it returns me an array with the nearest points (if any) in radius N for each unit. This would allow A * PP to be used indirectly in DOTS even if A * PP itself does not support it. Is there no such possibility?
Yes, there is an optimization in NavMeshQuery too: if the surface has been changed or the unit is not on the surface, every frame I look for the location for the unit (NavMeshQuery.MapLocation). This additionally takes the same ms as MoveLocations. However, this is not called every frame.