Best way to find Closest Target Entity?

Hey everyone,

I'm playing around with ECS trying to make a simple game with units fighting.
So in order to do that I need the Entities to be able to find a target.

This is what I've come up with:
I have Units and Targets and a UnitTargeting System to look for Targets

Code (CSharp):

1.  
2. // Target Tag
3. public struct Target : IComponentData { public int dummy; }
4.  
5. // Unit Tag
6. public struct Unit : IComponentData { public int dummy; }
7.  
8. // Added to Entity if has Target
9. public struct UnitHasTarget : IComponentData {
10.     public Entity target;
11. }
12.  
13. // System look for Targets
14. public class UnitTargeting : ComponentSystem {
15.  
16.     protected override void OnUpdate() {
17.         Entities.WithNone<UnitHasTarget>().ForEach((Entity entity, ref Unit unit, ref Translation translation) => {
18.             // Look for target with Entities that dont have a target yet
19.             Entity foundEntityTarget = Entity.Null;
20.             float3 unitPosition = translation.Value;
21.             float3 targetPosition = float3.zero;
22.  
23.             Entities.ForEach((Entity entityTarget, ref Target target, ref Translation targetTranslation) => {
24.                 if (foundEntityTarget == Entity.Null) {
25.                     // Has no target, set this one
26.                     foundEntityTarget = entityTarget;
27.                     targetPosition = targetTranslation.Value;
28.                 } else {
29.                     // Already has target, closest?
30.                     if (math.distance(unitPosition, targetTranslation.Value) < math.distance(unitPosition, targetPosition)) {
31.                         // New Target closer
32.                         foundEntityTarget = entityTarget;
33.                         targetPosition = targetTranslation.Value;
34.                     }
35.                 }
36.             });
37.  
38.  
39.             if (foundEntityTarget != Entity.Null) {
40.                 // Found target
41.                 PostUpdateCommands.AddComponent(entity, new UnitHasTarget { target = foundEntityTarget });
42.             }
43.         });
44.     }
45.  
46. }
47.  

So there's two types of Entities: Units and Targets.

The UnitTargeting System does a ForEach on every Unit that does not have a Target and inside it does a ForEach cycling through all the Targets to find the closest.

Is this the best way to do it? Would this cause problems if it was jobified?
The code works fine I'm just wondering if this is the best way.

Also I added the "dummy" fields since theres an error if the ComponentData is completely empty.
ArgumentException: ArchetypeChunk.GetNativeArray<Unit> cannot be called on zero-sized IComponentData
Is that intended?

Thanks!

 

You could use unity physics.

 

I achieved this scenario using Unity.Physics which provides a 'Closest Target' query.
It's still in very early preview though (preview 2) and there are some quirks to figure out. It also doesn't support 2D colliders yet in case you were looking for those.

It can take up a lot of CPU if you have thousands of entities though.

 

If you had lots of targets to cycle through, you could use some spatial partitioning for them

 

How do you get the Closest with Physics? Doing a Raycast and Colliders? That sounds like it would be much slower.
Is there another way? I haven't fully researched the new ECS Physics so not sure what "Closest Target" query you mean. Is there a function that gets the closest object without a collision?

Yeah I was thinking of implementing some sort of Quadrant System so I don't have to cycle through further away Entities.

 

Yes, one of the CollisionWorld.CalculateDistance overloads returns the closest hit within a maximum range. But you are right, it's not fast (or maybe it is depending on what you're comparing with), as physics is super early, it's stateless, and does not support 2D yet (which is my case). I'm going this route for the time being so I can work on other things while unity physics develops and 'hopefully' gets faster.

This is my 'NearestEnemy' system job which uses UnityPhysics. I use a min update interval of 0.2s to keep the cost manageable.

I have about 3k entities all looking for the closest enemy @ 60fps at the moment. The job takes something like 5ms. I'm considering ways to improve this. But for me, I'm happy with letting the unity physics team worry about things like bounding volumes on my behalf for the time being haha.

Code (CSharp):

1.     [BurstCompile]
2.     private struct NearestCastJob : IJobForEachWithEntity<Translation, Rotation, PhysicsCollider, NearestEnemy>
3.     {
4.         public float Time;
5.         [ReadOnly] public CollisionWorld CollisionWorld;
6.  
7.         public void Execute(Entity entity, int index, [ReadOnly] ref Translation tran, [ReadOnly] ref Rotation rot, [ReadOnly] ref PhysicsCollider col, ref NearestEnemy nearestEnemy)
8.         {
9.             if (Time - nearestEnemy.LastRefreshTime < MinUpdateInterval)
10.             {
11.                 return;
12.             }
13.  
14.             unsafe
15.             {
16.                 CollisionFilter filter = new CollisionFilter
17.                 {
18.                     CategoryBits = 1u << (int)PhysicsLayer.RayCast,
19.                     MaskBits = 1u << (int)PhysicsLayer.Ships,
20.                     GroupIndex = col.ColliderPtr->Filter.GroupIndex
21.                 };
22.          
23.                 PointDistanceInput pointInput = new PointDistanceInput
24.                 {
25.                     Position = tran.Value,
26.                     MaxDistance = nearestEnemy.QueryRange,
27.                     Filter = filter
28.                 };
29.  
30.                 DistanceHit hit;
31.                 CollisionWorld.CalculateDistance(pointInput, out hit);
32.  
33.                 Entity hitEntity = CollisionWorld.Bodies[hit.RigidBodyIndex].Entity;
34.                 if (hitEntity == entity)
35.                 {
36.                     nearestEnemy.Entity = Entity.Null;
37.                 }
38.                 else
39.                 {
40.                     nearestEnemy.Entity = CollisionWorld.Bodies[hit.RigidBodyIndex].Entity;
41.                 }
42.  
43.                 nearestEnemy.LastRefreshTime = Time;
44.                 //Logger.Log($"{entity} found {nearestEnemy.Entity}.");
45.             }
46.         }
47.     }

I'm sure things could be better than this implementation though...

 

Correct me if I am wrong but if entities are near cell borders, it will not detect them as neighbors. Does that sound right?

 

In boids entities are represented by a single point in space so that's not a possibility in that case. If your entities are represented by a collision bounds then you need to adjust for that by inserting all entities into all regions they overlap and adjust your collision checks accordingly.

 

Some spatial options are, Octree for 3D, quadtree for 2D can help with finding near entities.
Mentioned Boids another alternative.

 

I think it is a possibility as boids should be affected by nearby boids. In Unity's example, if 2 nearby boids are right next to each other in different cells (near the border) they will not affect each other. What about this is wrong?

 

Providing I understand the problem, is that boid case, takes only nearby points, located in same cell, or overlapping cell.
Bordered neighbor cell boid's points are ignored.
But to be honest, I would need to look back, into boid's cell definition.

 

Providing this is an old thread, I'm wondering if anyone has an updated and concrete solution to this problem.

Since this is the first thread that comes up in google, I'll link to this more recent thread which seems to have a good updated physics solution. I'm not sure if this is the fastest way to accomplish this however.

https://forum.unity.com/threads/ove...istance-check-performance-comparison.1175435/

 

Unity included a bursted KDTree in the updated MegaCity sample that I believe is used to located the closest audio emitters, which would probably prove useful.

https://github.com/Unity-Technologi.../Assets/Scripts/Utils/KDTree/KDTree/KDTree.cs

 

It depends on the application.
If you have static entities, then you can generate KDTree.
However, if entities are dynamic and moving, KDTree probably is not really a best option. Not sure if it can be multithreaded.

In our project, where many thousands of units move, we use brute force hashing system, to generate possible targets.
Then we search nearby cells.
Multithreaded and bursted solution.

 

I have a very fast spatial hash map that I use to calculate the nearest neighbours of entities every frame in my implementation of the ORCA simulation.
https://gitlab.com/tertle/com.bovinelabs.core/-/blob/0.9/BovineLabs.Core/Spatial/SpatialMap.cs

It's fast enough you can rebuild it every frame, taking just 0.56ms for 200,000 entities on a single thread utilizing a lot of custom extensions to hashmaps.

This demo finds the 10 nearest neighbours for each entity every frame to avoid colliding. It's not good for anything else other than nearest neighbors though.

-edit-

I should add it is a touch slower in 1.0 now over 0.51 due to it having to use MemCpySlice instead of MemCpy for the positions in the new transform system...

-edit2-

actually I forgot I significantly improved performance since i made this generic and re-usable compared to the previous screenshot (populatespatialhashmap is now the calculatemap part now)



At this level of density



Lookups are around 7.5ms to find up to 10 neighbours for 200,000 entities which while still really good imo, especially for a spatial container that can build every frame so quickly, I would like to improve somehow

 

@tertle
Just ouf of curiosity how are you finding the "10" closest entities in your example?

I was under the impression that you could only search on a specific radius with SpatialHash structures, are you just creating a massive radius around the entitiy - or are you somehow not using a radius at all?

Wouldn`t the calculation of buckets be really ëxpensive in that scenario?

With that in mind - how are you calculating the buckets to search in then in your example?

 

Sorry should have been clearer.
It just finds the 10 closest neighbours within a radius, if there are less, less are returned.

As for buckets you can see how fast I calculate them


The source codes all there but basically what I do is I write directly to the key/value buffers in the hashmap in parallel then in a single job afterwards I iterate all elements and calculate the bucket. It's extremely fast this way - linear memory access.

 

Oh I see, It makes sense, I was looking at your code, and the bit missing was the calculate in radius (or I couldnt find it). I thought you somehow had magically found a solution to get the nearest 10 without a radius.

Then its just normal spatial hash, you then calculate the buckets aggregate the results and sort by distance.

Thank you! really helpfull