RTS Collision System

Hi everyone.

I've made a simple physics collision system suited to RTS-style games but can be used for other things. It uses a fixed grid for spatial partitioning as I have found it to be the most performant.

If you could give it a look and let me know what you think/improvements would be really great! Especially if you can post stress test with your system specs. Feel free to use it however you like.

Unity 2020.2.3f1

https://github.com/Tree37/Unity-DOTS-RTS-Collision-System

 

https://github.com/Tree37/Unity-DOT.../Scripts/UnitCollisionSystemFixedGrid.cs#L219

count == CELL_CAPACITY

? Seems like a bug.

If you can summarize the criteria for collision and the formula for resolution you are using independent of your broadphase, I can benchmark it against my multibox SAP. Your solution should outperform mine for this particular use case, so you can use that as a sanity check.

 

I did this in 2D AABB about 2 years ago, also fixed grid. Not sure if I posted this back in the days in the forums I benchmarked various approaches back then and recall I was happy with performance (but a lot has changed since, NMHM performance, math lib, burst enhancements, etc)

I skimmed through your implementation, looks you are in 2D as well. If you are interested i can see if I can dig this out (very old api though)

 

You linked line 219 : grid[ gridIndex + count ] = ( ushort ) ( indexOfFirstEntityInQuery + i );

GridIndex is the index of the cell, and count is the entity in the cell. It is not a bug.

I am not 100% certain what you mean by criteria for collision. I am doing circle collision checks. When doing collision resolution, we loop over all copy data, and compare to all other units in current cell + left right and corner. Currentcell is obtained by converting the copy position into a 1-d index. Cells store entity index.

The formula for resolution is to find the overlap of two circles, then adjust the current entity based on the overlap / 2. I will be adding force based on velocity and mass, but I haven't decided exactly how I want to do that yet. Is this what you mean?

For bench marking, its just a simple scene you can use out of the box, nothing in it just a GameManager object, entities are spawned through script.

 

So my only feedback is you have a lot of Complete() calls in your code.
If you wanted to make improvements and learn something, I'd try to find ways to remove them. As I see nothing managed from my quick glance, there should be no reason you can't remove them all.

 

If the cell is full, then count will be equal to the CELL_CAPACITY. Consequently, this index operation is writing to one index past the cell.

The reason I am asking is because it isn't immediately obvious to me which variables are part of the collision resolution, and which are part of the broadphase. I am offering to compare your broadphase against another broadphase, and to make the comparison fair, I want the other implementation to mimic your collision resolution logic (the narrow phase check and adjusting of the entity in response). Benchmarking an algorithm without any sort of comparison isn't all that useful.

 

Ok you are right I fixed the +1 error bug, thank you for catching that

UpdateCellsJob and UpdateGridJob are technically the broad-phase, but I include CopyPositionsJob in the broad-phase handle. In the broad-phase, entities store a component called "collision cell" which is just it's 2d position stored as a 1d-index.

In collision resolution, EntityComponentData (translation, velocity, mass) are used. These are copied to an array and that array is looped over checking the grid for neighboring entity indices, which are used to find the corresponding physics data in the copy array.

Collision resolution just takes the current entity, finds each nearby entity using the grid, and does a distance check. If the distance is less than the two radii combined, they overlap, and both entities are adjusted according to overlap / 2 (static collision resolution). Currently, the velocity and mass are passed into CollisionResolution, but are not operated on (dynamic resolution) yet. I'm sorry it isn't clear, if its still not clear let me know and I'll just comment the heck out of the code.

Code (CSharp):

1.                     float distance = math.sqrt( ( px - px2 ) * ( px - px2 ) + ( pz - pz2 ) * ( pz - pz2 ) );
2.                     int overlaps = math.select( 0 , 1 , distance < RADIUS );
3.                  
4.                     float overlap = 0.5f * ( distance - RADIUS );
5.  
6.                     float adjustmentX = overlaps * ( overlap * ( px - px2 ) ) / ( distance + 0.01f );
7.                     float adjustmentZ = overlaps * ( overlap * ( pz - pz2 ) ) / ( distance + 0.01f );

This is essentially the formula for static collision resolution; I am not using dynamic yet. AX and AZ are just applied to the two colliders.

 

Thanks tertle, the reason I am calling Complete() is because I do not see how it makes a difference? The entire system must run; I cannot have any other jobs run in between the systems jobs, so i just call complete?

 

By calling complete your making the main thread wait on the jobs instead of letting the jobs finish during another system or rendering etc



vs

 

Ohhh, ok I see, I completely forgot Complete() makes the main thread wait, I'm definitely going with your suggestion, thank you!

 

If its very old API then I'm not sure, but if yours is different than mine then sure I'd like to see it.

 

The original code is in 0.0.12preview24 (Feb 2019) and benchmarked around 8 different versions (containers / parallelism). I have apparently updated one of those benchmarked systems to 0.1.1, which I copied below. Unfortunately it is quite messy with lots of commented out code (I think leftovers from the benchmarks). Depending on your use case, you can also "layer the grid" with different resolutions...

The code is organized as follows:
Systems that schedule the jobs
Jobs are isolated in Jobs.cs (because I reused them for the benchmarks)
Hash & Collision code is in Util.cs (also shared between systems / jobs)

Jobs - I think there was a bug with Unity Jobsystem and Buffers readonly if I recall correctly, requiring a dummy tag. I copy both Systems (they are pretty much the same)

Spoiler: Collision System 1

Code (CSharp):

1.  
2. using System.Collections;
3. using System.Collections.Generic;
4. using UnityEngine;
5. using Unity.Entities;
6. using Unity.Jobs;
7. using Unity.Burst;
8. using Unity.Mathematics;
9. using Unity.Collections;
10. //using Unity.Rendering;
11. using Unity.Transforms;
12. using UnityEngine.Profiling;
13. using System.Runtime.CompilerServices;
14. using Unity.Profiling;
15. using UnityEngine.Experimental.PlayerLoop;
16.  
17. namespace Creation.ECS
18. {
19.  
20.  
21.    /*
22.    AS E, but merges in AABB collision job, hence no need for collisionPairKeys_Group & associated buffer
23.    ---> not as fast as E in build !!!???
24.  
25.    uses new API - allocates grid entities as permanent array
26.    */
27.  
28.  
29.  
30.  
31.    // [DisableAutoCreation]
32.  
33.    [UpdateAfter (typeof(MovementJobSystem))]
34.    public class CollisionJobSystemE1NewApiV2 : JobComponentSystem
35.    {      
36.       // Component Groups
37.       public EntityQuery collisionCandidateKeys_Group;
38.       public EntityQuery sprite_Group;
39.        
40.       // Native Containers
41.       NativeHashMap<int, CollisionPairBuffer> distinctCollisionPairHashMap;
42.       public NativeHashMap<Entity, int> distinctCollisionEntityHashMap;
43.       NativeArray<Entity> collisionBufferEntityArray;
44.  
45.       // local variables
46.       ColGrid myGrid;
47.  
48.       #region Magic Methods    
49.       protected override void OnCreate()
50.       {
51.          // not used because this runs before Camera.main is set
52.       }
53.      
54.       protected override void OnStartRunning()
55.       {
56.          InitGrid();
57.        
58.          CreateNativeContainers();
59.        
60.          // Setup Entities (Keys) with Bufferes (Values)
61.          for (int i = 0; i < myGrid.CellCount; i++)
62.          {
63.             collisionBufferEntityArray[i] = EntityManager.CreateEntity(ComponentType.ReadWrite<CollisionInfoBuffer>(), ComponentType.ReadWrite<CollisionInfoBufferDummy>());
64.          }
65.        
66.          collisionCandidateKeys_Group = GetEntityQuery(ComponentType.ReadWrite<CollisionInfoBuffer>(), ComponentType.ReadWrite<CollisionInfoBufferDummy>());  
67.          sprite_Group = GetEntityQuery(ComponentType.ReadWrite<SpriteTag>(), ComponentType.ReadWrite<Box>());
68.       }
69.      
70.       protected override void OnDestroy()
71.       {
72.          DisposeNativeContainers();
73.       }
74.      
75.       protected override JobHandle OnUpdate(JobHandle jobHandle)
76.       {
77.          jobHandle = MyUpdateJobified(jobHandle);    
78.          return jobHandle;
79.       }
80.      
81.       #endregion
82.      
83.       #region Main
84.       JobHandle MyUpdateJobified(JobHandle jobHandle)
85.       {
86.          ClearNativeContainers();
87.        
88.          var collisionBufferCandiateFromEntity = GetBufferFromEntity<CollisionInfoBuffer>();
89.  
90.          // Clear spatial grid - ParallelFor
91.          jobHandle = new ClearCandidateBufferFromEntityDictionaryParallelForJob
92.          {
93.             collisionBufferEntityArray          = collisionBufferEntityArray,
94.             collisionBufferCandiateFromEntity     = collisionBufferCandiateFromEntity
95.          }.Schedule(collisionBufferEntityArray.Length, 1, jobHandle);
96.        
97.          // Assign sprites to spacial grid - SINGLE IJobProcessComponentDataWithEntity
98.          jobHandle = new SpriteToGridBufferNewApiPersistentJob
99.          {
100.             grid                           = myGrid,
101.             keyArray                        = collisionBufferCandiateFromEntity,
102.             keyIndexArray                    = collisionBufferEntityArray
103.          }.ScheduleSingle(sprite_Group, jobHandle);
104.        
105.          // Check collisions per grid - ParallelFor
106.          jobHandle = new AABBCollisionBufferToHashMapNewApiJob
107.          {
108.             collisionCandidates                = collisionBufferCandiateFromEntity,
109.             DistinctCollisionPairHashMap         = distinctCollisionPairHashMap.ToConcurrent(),
110.             DistinctCollisionEntityHashMap        = distinctCollisionEntityHashMap.ToConcurrent()
111.          }.Schedule(collisionCandidateKeys_Group, jobHandle);
112.        
113.          // Color Colliding Entities - IJobProcessComponentDataWithEntity
114.          jobHandle = new ColorCollidingEntitiesJob
115.          {
116.             DistinctCollisionEntityHashMap       = distinctCollisionEntityHashMap,
117.             hitColor                        = Settings.hitColor,
118.             normColor                       = Settings.normColor
119.          }.Schedule(this, jobHandle);
120.          // start processing all scheduled jobs
121.          // JobHandle.ScheduleBatchedJobs();
122.          //jobHandle.Complete();
123.          return jobHandle;
124.       }
125.      
126.       #endregion
127.      
128.       #region Main Helper Functions
129.      
130.       void InitGrid()
131.       {
132.          var orthoSize                          = Camera.main.orthographicSize;
133.          var aspect                            = (float) Screen.width /  (float) Screen.height;
134.          var halfScreen                         = new float2(orthoSize * aspect, orthoSize);
135.        
136.          // TO-DO: Test with bigger grids, this version can handle bigger grids well ---
137.          var dim = Settings.dim;
138.          myGrid = new ColGrid (-halfScreen, halfScreen, dim);
139.        
140.        
141.        
142.       }
143.      
144.       void CreateNativeContainers()
145.       {      
146.          collisionBufferEntityArray             = new NativeArray<Entity>(myGrid.CellCount, Allocator.Persistent);
147.          distinctCollisionPairHashMap            = new NativeHashMap<int, CollisionPairBuffer>(Settings.spriteCount, Allocator.Persistent);
148.          distinctCollisionEntityHashMap          = new NativeHashMap<Entity, int>(Settings.spriteCount, Allocator.Persistent);
149.       }
150.        
151.       void ClearNativeContainers()
152.       {
153.          distinctCollisionPairHashMap.Clear();
154.          distinctCollisionEntityHashMap.Clear();
155.       }
156.      
157.       void DisposeNativeContainers()
158.       {
159.          collisionBufferEntityArray.Dispose();
160.          distinctCollisionPairHashMap.Dispose();
161.          distinctCollisionEntityHashMap.Dispose();
162.       }
163.        
164.       #endregion
165.  
166.    }
167. }
168.  

Spoiler: Collision System 2

Code (CSharp):

1.  
2. using System.Collections;
3. using System.Collections.Generic;
4. using UnityEngine;
5. using Unity.Entities;
6. using Unity.Jobs;
7. using Unity.Burst;
8. using Unity.Mathematics;
9. using Unity.Collections;
10. //using Unity.Rendering;
11. using Unity.Transforms;
12. using UnityEngine.Profiling;
13. using System.Runtime.CompilerServices;
14. using Unity.Profiling;
15. using UnityEngine.Experimental.PlayerLoop;
16.  
17. namespace Creation.ECS
18. {
19.  
20.  
21.    /*
22.    AS E, but merges in AABB collision job, hence no need for collisionPairKeys_Group & associated buffer
23.    ---> not as fast as E in build !!!???
24.  
25.    uses new API - allocates grid entities as permanent array
26.    */
27.  
28.  
29.  
30.  
31.    [DisableAutoCreation]
32.  
33.    [UpdateAfter (typeof(MovementJobSystem))]
34.    public class CollisionJobSystemE33 : JobComponentSystem
35.    {      
36.       // Component Groups
37.       public EntityQuery collisionCandidateKeys_Group;
38.       public EntityQuery sprite_Group;
39.        
40.       // Native Containers
41.       NativeHashMap<int, CollisionPairBuffer> distinctCollisionPairHashMap;
42.       public NativeHashMap<Entity, int> distinctCollisionEntityHashMap;
43.       NativeArray<Entity> collisionBufferEntityArray;
44.  
45.       // local variables
46.       ColGrid myGrid;
47.  
48.       #region Magic Methods    
49.       protected override void OnCreate()
50.       {
51.          // not used because this runs before Camera.main is set
52.       }
53.      
54.       protected override void OnStartRunning()
55.       {
56.          InitGrid();
57.        
58.          CreateNativeContainers();
59.        
60.          // Setup Entities (Keys) with Bufferes (Values)
61.          for (int i = 0; i < myGrid.CellCount; i++)
62.          {
63.             collisionBufferEntityArray[i] = EntityManager.CreateEntity(ComponentType.ReadWrite<CollisionInfoBuffer>(), ComponentType.ReadWrite<CollisionInfoBufferDummy>());
64.          }
65.        
66.          collisionCandidateKeys_Group = GetEntityQuery(ComponentType.ReadWrite<CollisionInfoBuffer>(), ComponentType.ReadWrite<CollisionInfoBufferDummy>());  
67.          sprite_Group = GetEntityQuery(ComponentType.ReadWrite<SpriteTag>(), ComponentType.ReadWrite<Box>());
68.       }
69.      
70.       protected override void OnDestroy()
71.       {
72.          DisposeNativeContainers();
73.       }
74.      
75.       protected override JobHandle OnUpdate(JobHandle jobHandle)
76.       {
77.          jobHandle = MyUpdateJobified(jobHandle);    
78.          return jobHandle;
79.       }
80.      
81.       #endregion
82.      
83.       #region Main
84.       JobHandle MyUpdateJobified(JobHandle jobHandle)
85.       {
86.          ClearNativeContainers();
87.        
88.          var collisionBufferCandiateFromEntity = GetBufferFromEntity<CollisionInfoBuffer>();
89.  
90.          // Clear spatial grid - ParallelFor
91.          jobHandle = new ClearCandidateBufferFromEntityDictionaryParallelForJob
92.          {
93.             collisionBufferEntityArray          = collisionBufferEntityArray,
94.             collisionBufferCandiateFromEntity     = collisionBufferCandiateFromEntity
95.          }.Schedule(collisionBufferEntityArray.Length, 1, jobHandle);
96.        
97.          // Assign sprites to spacial grid - SINGLE IJobProcessComponentDataWithEntity
98.          jobHandle = new SpriteToGridBufferNewApiPersistentJob
99.          {
100.             grid                           = myGrid,
101.             keyArray                        = collisionBufferCandiateFromEntity,
102.             keyIndexArray                    = collisionBufferEntityArray
103.          }.ScheduleSingle(sprite_Group, jobHandle);
104.        
105.          // Check collisions per grid - ParallelFor
106.          jobHandle = new AABBperBufferIJobForEach
107.          {
108.             // collisionCandidates                = collisionBufferCandiateFromEntity,
109.             DistinctCollisionPairHashMap         = distinctCollisionPairHashMap.ToConcurrent(),
110.             DistinctCollisionEntityHashMap        = distinctCollisionEntityHashMap.ToConcurrent()
111.          }.Schedule(collisionCandidateKeys_Group, jobHandle);
112.        
113.          // Color Colliding Entities - IJobProcessComponentDataWithEntity
114.          jobHandle = new ColorCollidingEntitiesJob
115.          {
116.             DistinctCollisionEntityHashMap       = distinctCollisionEntityHashMap,
117.             hitColor                        = Settings.hitColor,
118.             normColor                       = Settings.normColor
119.          }.Schedule(this, jobHandle);
120.          // start processing all scheduled jobs
121.          JobHandle.ScheduleBatchedJobs();
122.          //jobHandle.Complete();
123.          return jobHandle;
124.       }
125.      
126.       #endregion
127.      
128.       #region Main Helper Functions
129.      
130.       void InitGrid()
131.       {
132.          var orthoSize                          = Camera.main.orthographicSize;
133.          var aspect                            = (float) Screen.width /  (float) Screen.height;
134.          var halfScreen                         = new float2(orthoSize * aspect, orthoSize);
135.        
136.          // TO-DO: Test with bigger grids, this version can handle bigger grids well ---
137.          var dim = Settings.dim;
138.          myGrid = new ColGrid (-halfScreen, halfScreen, dim);
139.       }
140.      
141.       void CreateNativeContainers()
142.       {      
143.          collisionBufferEntityArray             = new NativeArray<Entity>(myGrid.CellCount, Allocator.Persistent);
144.          distinctCollisionPairHashMap            = new NativeHashMap<int, CollisionPairBuffer>(Settings.spriteCount, Allocator.Persistent);
145.          distinctCollisionEntityHashMap          = new NativeHashMap<Entity, int>(Settings.spriteCount, Allocator.Persistent);
146.       }
147.        
148.       void ClearNativeContainers()
149.       {
150.          distinctCollisionPairHashMap.Clear();
151.          distinctCollisionEntityHashMap.Clear();
152.       }
153.      
154.       void DisposeNativeContainers()
155.       {
156.          collisionBufferEntityArray.Dispose();
157.          distinctCollisionPairHashMap.Dispose();
158.          distinctCollisionEntityHashMap.Dispose();
159.       }
160.        
161.       #endregion
162.  
163.    }
164. }
165.  

Spoiler: Jobs - most commented out

Code (CSharp):

1.  
2. using UnityEngine;
3. using Unity.Entities;
4. using Unity.Jobs;
5. using Unity.Jobs.LowLevel.Unsafe;
6. using Unity.Burst;
7. using Unity.Mathematics;
8. using Unity.Collections;
9. using Unity.Collections.LowLevel.Unsafe;
10. //using Unity.Rendering;
11. using Unity.Transforms;
12. using Unity.Profiling;
13. using System.Threading;
14. using System.Runtime.CompilerServices;
15.  
16. namespace Creation.ECS
17. {
18.  
19.    #region UTILITY JOBS
20.  
21.    /*
22.    [BurstCompile]
23.    public struct ClearCandidateBufferDictionaryJob : IJobParallelFor
24.    {
25.       [NativeDisableParallelForRestriction][WriteOnly] public BufferArray<CollisionInfoBuffer> collisionCandidateKeyArray;
26.        
27.       public void Execute(int i)
28.       {
29.          collisionCandidateKeyArray[i].Clear();
30.       }
31.    }
32.  
33.    [BurstCompile]
34.    public struct ClearCollisionPairBufferDictionaryJob : IJobParallelFor
35.    {
36.       [NativeDisableParallelForRestriction][WriteOnly] public BufferArray<CollisionPairBuffer> collisionPairKeyArray;
37.        
38.       public void Execute(int i)
39.       {
40.          collisionPairKeyArray[i].Clear();
41.       }
42.    }
43.  
44.    [BurstCompile]
45.    public struct ClearBufferDictionaryJob : IJobParallelFor
46.    {
47.       [NativeDisableParallelForRestriction][WriteOnly] public BufferArray<CollisionInfoBuffer> collisionCandidateKeyArray;
48.       [NativeDisableParallelForRestriction][WriteOnly] public BufferArray<CollisionPairBuffer> collisionPairKeyArray;
49.        
50.       public void Execute(int i)
51.       {
52.          collisionCandidateKeyArray[i].Clear();
53.          collisionPairKeyArray[i].Clear();
54.       }
55.    }
56.  
57.    // new API
58.    [BurstCompile]
59.    public struct ClearCandidateBufferFromEntityDictionaryJob : IJobProcessComponentDataWithEntity<CollisionInfoBufferDummy>
60.    {
61.       [NativeDisableParallelForRestriction][WriteOnly] public BufferFromEntity<CollisionInfoBuffer> collisionBufferCandiateFromEntity;
62.        
63.       public void Execute(Entity e, int i, [ReadOnly] ref CollisionInfoBufferDummy dummy)
64.       {
65.          collisionBufferCandiateFromEntity[e].Clear();
66.       }
67.    }
68.  
69.    */
70.  
71.    // new API ***
72.    [BurstCompile]
73.    public struct ClearCandidateBufferFromEntityDictionaryParallelForJob : IJobParallelFor
74.    {
75.       [ReadOnly] public NativeArray<Entity> collisionBufferEntityArray;
76.       [NativeDisableParallelForRestriction][WriteOnly] public BufferFromEntity<CollisionInfoBuffer> collisionBufferCandiateFromEntity;
77.        
78.       public void Execute(int i)
79.       {
80.          collisionBufferCandiateFromEntity[collisionBufferEntityArray[i]].Clear();
81.       }
82.    }
83.  
84.  
85.    /*
86.  
87.  
88.    // new API
89.    [BurstCompile]
90.    public struct ClearCollisionPairBufferFromEntityDictionaryJob : IJobProcessComponentDataWithEntity<CollisionPairBufferDummy>
91.    {
92.       [NativeDisableParallelForRestriction][WriteOnly] public BufferFromEntity<CollisionPairBuffer> collisionBufferPairFromEntity;
93.        
94.       public void Execute(Entity e, int i, ref CollisionPairBufferDummy dummy)
95.       {
96.          collisionBufferPairFromEntity[e].Clear();
97.       }
98.    }
99.  
100.  
101.  
102.    [BurstCompile]
103.    public struct DequeueIntoListJob<T> : IJob where T : struct
104.    {
105.       public NativeQueue<T> InputQueue;
106.       [WriteOnly] public NativeList<T> OutputList;
107.  
108.       public void Execute()
109.       {
110.          var length = InputQueue.Count;
111.          for (int i = 0 ; i < length; i++)
112.          {
113.             OutputList.Add(InputQueue.Dequeue());
114.          }
115.            
116.          //while(InputQueue.TryDequeue(out T value))
117.          //{
118.          // OutputList.Add(value);
119.          //}
120.       }
121.    }
122.  
123.    [BurstCompile]
124.    struct MultiHashMapKeyToListJob : IJob
125.    {
126.       [ReadOnly] public NativeMultiHashMap<int, CollisionInfo> entitiesPerGridMultiHashMap;
127.       [ReadOnly] public int key;
128.       [WriteOnly] public NativeList<CollisionInfo> entitiesPerGridList;
129.    
130.       public void Execute()
131.       {
132.          NativeMultiHashMapIterator<int> it;
133.          CollisionInfo item;
134.          if (entitiesPerGridMultiHashMap.TryGetFirstValue(key, out item, out it))
135.          {
136.             entitiesPerGridList.Add(item);
137.             while (entitiesPerGridMultiHashMap.TryGetNextValue(out item, ref it))
138.             {
139.                entitiesPerGridList.Add(item);
140.             }
141.          }
142.       }
143.    }
144.    */
145.    #endregion
146.  
147.  
148.    #region Sprites to Grids Jobs
149.  
150.    /*
151.    /// <summary>
152.    /// Allocate Sprites to Grids
153.    /// </summary>
154.  
155.  
156.    // brute force checking all sprites against all grids
157.    [BurstCompile]
158.    [RequireComponentTag (typeof(SpriteTag))]                                                  // required, not scheduled with a component group
159.    public struct SpriteToGridQueueJob : IJobProcessComponentDataWithEntity<Box>
160.    {
161.       [ReadOnly] public Box gridBox;
162.       [WriteOnly] public NativeQueue<CollisionInfo>.Concurrent collisionCandidates;
163.        
164.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
165.       {
166.          if (Util.IsColliding4(gridBox, box))
167.          {
168.             var colInfo = new CollisionInfo {entity = e, box = box};
169.             collisionCandidates.Enqueue(colInfo);
170.          }
171.       }
172.    }
173.  
174.    [BurstCompile]
175.    [RequireComponentTag (typeof(SpriteTag))]                                                  // required, not scheduled with a component group
176.    public struct SpriteToGridMultiHashMapJob : IJobProcessComponentDataWithEntity<Box>
177.    {
178.       [ReadOnly] public ColGrid grid;
179.       [WriteOnly]    public NativeMultiHashMap<int, CollisionInfo>.Concurrent entitiesPerGridMultiHashMap;
180.        
181.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
182.       {
183.          var boxMinGrid = (int2) ((box.Center - box.Extends - grid.Min) * grid.OneOverCellSize);
184.          var boxMaxGrid = (int2) ((box.Center + box.Extends - grid.Min) * grid.OneOverCellSize);
185.            
186.          for (int x = boxMinGrid.x; x <= boxMaxGrid.x; x++)
187.          {
188.             if (x >= 0 && x < grid.Dim.x)
189.             {
190.                for (int y = boxMinGrid.y; y <= boxMaxGrid.y; y++)
191.                {
192.                   if (y >= 0 && y < grid.Dim.y)
193.                   {
194.                      var key = x + y * grid.Dim.x;
195.                      entitiesPerGridMultiHashMap.Add(key, new CollisionInfo {entity = e, box = box});
196.                   }
197.                }
198.             }
199.          }
200.       }
201.    }
202.  
203.  
204.    [BurstCompile]
205.    public struct SpriteToGridBufferJob : IJobProcessComponentDataWithEntity<Box>
206.    {
207.       [ReadOnly] public ColGrid grid;
208.       [WriteOnly] public BufferArray<CollisionInfoBuffer> keyArray;
209.        
210.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
211.       {
212.          var boxMinGrid = (int2) ((box.Center - box.Extends - grid.Min) * grid.OneOverCellSize);
213.          var boxMaxGrid = (int2) ((box.Center + box.Extends - grid.Min) * grid.OneOverCellSize);
214.            
215.          for (int x = boxMinGrid.x; x <= boxMaxGrid.x; x++)
216.          {
217.             if (x >= 0 && x < grid.Dim.x)
218.             {
219.                for (int y = boxMinGrid.y; y <= boxMaxGrid.y; y++)
220.                {
221.                   if (y >= 0 && y < grid.Dim.y)
222.                   {
223.                      var key = x + y * grid.Dim.x;
224.                      keyArray[key].Add(new CollisionInfoBuffer{entity = e, box = box});
225.                   }
226.                }
227.             }
228.          }
229.       }
230.    }
231.  
232.    // new API
233.    [BurstCompile]
234.    public struct SpriteToGridBufferNewApiJob : IJobProcessComponentDataWithEntity<Box>
235.    {
236.       [ReadOnly] public ColGrid grid;
237.       [WriteOnly] public BufferFromEntity<CollisionInfoBuffer> keyArray;
238.       [ReadOnly, DeallocateOnJobCompletion] public NativeArray<Entity> keyIndexArray;
239.       [NativeDisableParallelForRestriction][WriteOnly] public BufferFromEntity<CollisionInfoBuffer> collisionBufferCandiateFromEntity;
240.        
241.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
242.       {
243.          var boxMinGrid = (int2) ((box.Center - box.Extends - grid.Min) * grid.OneOverCellSize);
244.          var boxMaxGrid = (int2) ((box.Center + box.Extends - grid.Min) * grid.OneOverCellSize);
245.            
246.          for (int x = boxMinGrid.x; x <= boxMaxGrid.x; x++)
247.          {
248.             if (x >= 0 && x < grid.Dim.x)
249.             {
250.                for (int y = boxMinGrid.y; y <= boxMaxGrid.y; y++)
251.                {
252.                   if (y >= 0 && y < grid.Dim.y)
253.                   {
254.                      var pos = x + y * grid.Dim.x;
255.                      var key = keyIndexArray[pos];
256.                      keyArray[key].Add(new CollisionInfoBuffer{entity = e, box = box});
257.                   }
258.                }
259.             }
260.          }
261.       }
262.    }
263.  
264.    */
265.  
266.    // ***
267.    [BurstCompile]
268.    public struct SpriteToGridBufferNewApiPersistentJob : IJobForEachWithEntity<Box>
269.    {
270.       [ReadOnly] public ColGrid grid;
271.       [WriteOnly] public BufferFromEntity<CollisionInfoBuffer> keyArray;
272.       [ReadOnly] public NativeArray<Entity> keyIndexArray;
273.        
274.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
275.       {
276.          var boxMinGrid = (int2) ((box.Center - box.Extends - grid.Min) * grid.OneOverCellSize);
277.          var boxMaxGrid = (int2) ((box.Center + box.Extends - grid.Min) * grid.OneOverCellSize);
278.            
279.          for (int x = boxMinGrid.x; x <= boxMaxGrid.x; x++)
280.          {
281.             if (x >= 0 && x < grid.Dim.x)
282.             {
283.                for (int y = boxMinGrid.y; y <= boxMaxGrid.y; y++)
284.                {
285.                   if (y >= 0 && y < grid.Dim.y)
286.                   {
287.                      var pos = x + y * grid.Dim.x;
288.                      var key = keyIndexArray[pos];
289.                      keyArray[key].Add(new CollisionInfoBuffer{entity = e, box = box});
290.                   }
291.                }
292.             }
293.          }
294.       }
295.    }
296.  
297.    /*
298.  
299.    [BurstCompile]
300.    public struct SpriteToGridBufferNewApiParallelInterlockedJob : IJobProcessComponentDataWithEntity<Box>
301.    {
302.       [ReadOnly] public ColGrid grid;
303.       [NativeDisableParallelForRestriction, WriteOnly] public BufferFromEntity<CollisionInfoBuffer> keyArray;
304.       [ReadOnly] public NativeArray<Entity> keyIndexArray;
305.       [NativeDisableParallelForRestriction, DeallocateOnJobCompletion] public NativeArray<int> bufferLocksArray;
306.        
307.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
308.       {
309.          var boxMinGrid = (int2) ((box.Center - box.Extends - grid.Min) * grid.OneOverCellSize);
310.          var boxMaxGrid = (int2) ((box.Center + box.Extends - grid.Min) * grid.OneOverCellSize);
311.  
312.          for (int x = boxMinGrid.x; x <= boxMaxGrid.x; x++)
313.          {
314.             if (x >= 0 && x < grid.Dim.x)
315.             {
316.                for (int y = boxMinGrid.y; y <= boxMaxGrid.y; y++)
317.                {
318.                   if (y >= 0 && y < grid.Dim.y)
319.                   {
320.                      var pos = x + y * grid.Dim.x;
321.                      var key = keyIndexArray[pos];
322.                      unsafe
323.                      {
324.                         while(Interlocked.CompareExchange(ref ((int*)bufferLocksArray.GetUnsafePtr())[pos], -1, 0) != 0) {}  
325.                      }
326.                    
327.                      keyArray[key].Add(new CollisionInfoBuffer{entity = e, box = box});
328.                      bufferLocksArray[pos] = 0;
329.                   }
330.                }
331.             }
332.          }
333.       }
334.    }
335.  
336.    [BurstCompile]
337.    public struct SpriteToGridBufferParallelJob : IJobProcessComponentDataWithEntity<Box>
338.    {
339.       [ReadOnly] public ColGrid grid;
340.       [NativeDisableParallelForRestriction][WriteOnly] public BufferArray<CollisionInfoBuffer> keyArray;
341.          #pragma warning disable CS0649
342.       [NativeSetThreadIndex] int m_ThreadIndex;
343.          #pragma warning restore CS0649
344.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
345.       {
346.          var boxMinGrid = (int2) ((box.Center - box.Extends - grid.Min) * grid.OneOverCellSize);
347.          var boxMaxGrid = (int2) ((box.Center + box.Extends - grid.Min) * grid.OneOverCellSize);
348.          var threadOffset = grid.CellCount * (m_ThreadIndex - 1);
349.              
350.          // TO-DO: THREAD INDEX CAN BE GREATER THAN NUMBER OF CORES !!!! //
351.          threadOffset = math.min(grid.CellCount * (4-1), threadOffset);
352.        
353.          for (int x = boxMinGrid.x; x <= boxMaxGrid.x; x++)
354.          {
355.             if (x >= 0 && x < grid.Dim.x)
356.             {
357.                for (int y = boxMinGrid.y; y <= boxMaxGrid.y; y++)
358.                {
359.                   if (y >= 0 && y < grid.Dim.y)
360.                   {
361.                      var key = x + y * grid.Dim.x;
362.                      keyArray[key + threadOffset].Add(new CollisionInfoBuffer{entity = e, box = box});
363.                   }
364.                }
365.             }
366.          }
367.       }
368.    }
369.  
370.    [BurstCompile]
371.    public struct SpriteToGridBufferParallelInterlockedJob : IJobProcessComponentDataWithEntity<Box>
372.    {
373.       [ReadOnly] public ColGrid grid;
374.       [NativeDisableParallelForRestriction, WriteOnly] public BufferArray<CollisionInfoBuffer> keyArray;
375.       [NativeDisableParallelForRestriction, DeallocateOnJobCompletion] public NativeArray<int> bufferLocksArray;
376.        
377.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
378.       {
379.          var boxMinGrid = (int2) ((box.Center - box.Extends - grid.Min) * grid.OneOverCellSize);
380.          var boxMaxGrid = (int2) ((box.Center + box.Extends - grid.Min) * grid.OneOverCellSize);
381.  
382.          for (int x = boxMinGrid.x; x <= boxMaxGrid.x; x++)
383.          {
384.             if (x >= 0 && x < grid.Dim.x)
385.             {
386.                for (int y = boxMinGrid.y; y <= boxMaxGrid.y; y++)
387.                {
388.                   if (y >= 0 && y < grid.Dim.y)
389.                   {
390.                      var key = x + y * grid.Dim.x;
391.                      unsafe
392.                      {
393.                         while(Interlocked.CompareExchange(ref ((int*)bufferLocksArray.GetUnsafePtr())[key], -1, 0) != 0) {}  
394.                      }
395.                        
396.                      keyArray[key].Add(new CollisionInfoBuffer{entity = e, box = box});
397.                      bufferLocksArray[key] = 0;
398.                   }
399.                }
400.             }
401.          }
402.       }
403.    }
404.  
405.    */
406.  
407.    /*                   Pre determined grid Size                                */
408.    /* -------------------------------------------------------------------------------------------*/
409.  
410.    /*
411.  
412.    [BurstCompile]
413.    public struct SpriteToSingleGridBufferJob : IJobProcessComponentDataWithEntity<Box>
414.    {
415.       [ReadOnly] public ColGrid grid;
416.       [WriteOnly] public BufferArray<CollisionInfoBuffer> keyArray;
417.        
418.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
419.       {
420.          var boxGridPos = (int2) ((box.Center - grid.Min) * grid.OneOverCellSize);
421.          var key = boxGridPos.x + boxGridPos.y * grid.Dim.x;
422.          keyArray[key].Add(new CollisionInfoBuffer{entity = e, box = box});
423.       }
424.    }
425.  
426.    [BurstCompile]
427.    public struct SpriteToSingleGridMultiHashMapJob : IJobProcessComponentDataWithEntity<Box>
428.    {
429.       [ReadOnly] public ColGrid grid;
430.       [WriteOnly]    public NativeMultiHashMap<int, CollisionInfo>.Concurrent entitiesPerGridMultiHashMap;
431.        
432.       public void Execute(Entity e, int i, [ReadOnly] ref Box box)
433.       {
434.          var boxGridPos = (int2) ((box.Center - grid.Min) * grid.OneOverCellSize);
435.          var key = boxGridPos.x + boxGridPos.y * grid.Dim.x;
436.          entitiesPerGridMultiHashMap.Add(key, new CollisionInfo {entity = e, box = box});
437.       }
438.    }
439.  
440. */
441.  
442.    /* -------------------------------------------------------------------------------------------*/
443.  
444.    #endregion
445.  
446.    #region AABB Collisions
447.  
448.    /*
449.    /// <summary>
450.    /// AABB Collision Job Variants
451.    /// </summary>
452.  
453.    [BurstCompile]
454.    public struct AABBCollisionListToQueueJob : IJobParallelFor
455.    {
456.       [ReadOnly] public NativeList<CollisionInfo> collisionCandidates;
457.       public NativeQueue<CollisionPair>.Concurrent collidingEntities;
458.        
459.       public void Execute(int i)
460.       {
461.          for (int j = i + 1; j < collisionCandidates.Length; j++)
462.          {
463.             if (Util.IsColliding4(collisionCandidates[i].box, collisionCandidates[j].box))
464.             {
465.                var cp = new CollisionPair {EntityA = collisionCandidates[i].entity, EntityB = collisionCandidates[j].entity};
466.                collidingEntities.Enqueue(cp);
467.             }
468.          }
469.       }
470.    }
471.  
472.    [BurstCompile]
473.    public struct AABBCollisionListToListJob : IJob
474.    {
475.       [ReadOnly] public NativeList<CollisionInfo> collisionCandidates;
476.       [WriteOnly] public NativeList<CollisionPair> collidingEntities;
477.        
478.       public void Execute()
479.       {
480.          for (int i = 0; i < collisionCandidates.Length - 1; i++)
481.          {
482.             for (int j = i + 1; j < collisionCandidates.Length; j++)
483.             {
484.                if (Util.IsColliding4(collisionCandidates[i].box, collisionCandidates[j].box))
485.                {
486.                   var cp = new CollisionPair {EntityA = collisionCandidates[i].entity, EntityB = collisionCandidates[j].entity};
487.                   collidingEntities.Add(cp);
488.                }
489.             }
490.          }
491.       }
492.    }
493.  
494.    [BurstCompile]
495.    public struct AABBCollisionArrayToListJob : IJob
496.    {
497.       [ReadOnly] public NativeArray<CollisionInfoBuffer> collisionCandidates;
498.       [WriteOnly] public NativeList<CollisionPair> collidingEntities;
499.        
500.       public void Execute()
501.       {
502.          for (int i = 0; i < collisionCandidates.Length - 1; i++)
503.          {
504.             for (int j = i + 1; j < collisionCandidates.Length; j++)
505.             {
506.                if (Util.IsColliding4(collisionCandidates[i].box, collisionCandidates[j].box))
507.                {
508.                   var cp = new CollisionPair {EntityA = collisionCandidates[i].entity, EntityB = collisionCandidates[j].entity};
509.                   collidingEntities.Add(cp);
510.                }
511.             }
512.          }
513.       }
514.    }
515.  
516.    [BurstCompile]
517.    public struct AABBCollisionBufferToBufferJob : IJobParallelFor
518.    {
519.       [ReadOnly] public BufferArray<CollisionInfoBuffer> collisionCandidates;
520.       [NativeDisableParallelForRestriction][WriteOnly] public BufferArray<CollisionPairBuffer> collidingEntities;          // it is ensured not to write in parallel to the buffer (buffer = index)
521.        
522.       public void Execute(int index)
523.       {
524.          var collisionCandidatesPerGrid = collisionCandidates[index].AsNativeArray();
525.          var collidingEntitiesPerGrid = collidingEntities[index];
526.  
527.          for (int i = 0; i < collisionCandidatesPerGrid.Length - 1; i++)
528.          {
529.             for (int j = i + 1; j < collisionCandidatesPerGrid.Length; j++)
530.             {
531.                if (Util.IsColliding4(collisionCandidatesPerGrid[i].box, collisionCandidatesPerGrid[j].box))
532.                {
533.                   var cp = new CollisionPairBuffer {EntityA = collisionCandidatesPerGrid[i].entity, EntityB = collisionCandidatesPerGrid[j].entity};
534.                   collidingEntitiesPerGrid.Add(cp);
535.                }
536.             }
537.          }
538.       }
539.    }
540.  
541.    [BurstCompile]
542.    public struct AABBCollisionBufferToHashMapJob : IJobParallelFor
543.    {
544.       [ReadOnly] public BufferArray<CollisionInfoBuffer> collisionCandidates;
545.       [WriteOnly] public NativeHashMap<int,CollisionPairBuffer>.Concurrent DistinctCollisionPairHashMap;
546.       [WriteOnly] public NativeHashMap<Entity,int>.Concurrent DistinctCollisionEntityHashMap;
547.        
548.       public void Execute(int index)
549.       {
550.          var collisionCandidatesPerGrid = collisionCandidates[index].AsNativeArray();
551.  
552.          for (int i = 0; i < collisionCandidatesPerGrid.Length - 1; i++)
553.          {
554.             for (int j = i + 1; j < collisionCandidatesPerGrid.Length; j++)
555.             {
556.                var candidateA = collisionCandidatesPerGrid[i];
557.                var candidateB = collisionCandidatesPerGrid[j];
558.                if (Util.IsColliding4(candidateA.box, candidateB.box))
559.                {
560.                   var hash = Util.GetCollisionHash(candidateA.entity.Index, candidateB.entity.Index);
561.                   var cp = new CollisionPairBuffer {EntityA = candidateA.entity, EntityB = candidateB.entity};
562.                   if (DistinctCollisionPairHashMap.TryAdd(hash,cp))
563.                   {
564.                      DistinctCollisionEntityHashMap.TryAdd(candidateA.entity, 1);
565.                      DistinctCollisionEntityHashMap.TryAdd(candidateB.entity, 1);
566.                   }
567.                }
568.             }
569.          }
570.       }
571.    }
572.  
573.    */
574.  
575.    // new API ***
576.    [BurstCompile]
577.    public struct AABBCollisionBufferToHashMapNewApiJob : IJobForEachWithEntity<CollisionInfoBufferDummy>
578.    {
579.       [ReadOnly] public BufferFromEntity<CollisionInfoBuffer> collisionCandidates;
580.       [WriteOnly] public NativeHashMap<int,CollisionPairBuffer>.Concurrent DistinctCollisionPairHashMap;
581.       [WriteOnly] public NativeHashMap<Entity,int>.Concurrent DistinctCollisionEntityHashMap;
582.        
583.       public void Execute(Entity e, int index, [ReadOnly] ref CollisionInfoBufferDummy dummy)
584.       {
585.          var collisionCandidatesPerGrid = collisionCandidates[e].AsNativeArray();
586.  
587.          for (int i = 0; i < collisionCandidatesPerGrid.Length - 1; i++)
588.          {
589.             for (int j = i + 1; j < collisionCandidatesPerGrid.Length; j++)
590.             {
591.                var candidateA = collisionCandidatesPerGrid[i];
592.                var candidateB = collisionCandidatesPerGrid[j];
593.                if (Util.IsColliding4(candidateA.box, candidateB.box))
594.                {
595.                   var hash = Util.GetCollisionHash(candidateA.entity.Index, candidateB.entity.Index);
596.                   var cp = new CollisionPairBuffer {EntityA = candidateA.entity, EntityB = candidateB.entity};
597.                   if (DistinctCollisionPairHashMap.TryAdd(hash,cp))
598.                   {
599.                      DistinctCollisionEntityHashMap.TryAdd(candidateA.entity, 1);
600.                      DistinctCollisionEntityHashMap.TryAdd(candidateB.entity, 1);
601.                   }
602.                }
603.             }
604.          }
605.       }
606.    }
607.  
608.    [BurstCompile]
609.    public struct AABBperBufferIJobForEach : IJobForEach_B<CollisionInfoBuffer>
610.    {
611.       //[ReadOnly] public BufferFromEntity<CollisionInfoBuffer> collisionCandidates;
612.       [WriteOnly] public NativeHashMap<int,CollisionPairBuffer>.Concurrent DistinctCollisionPairHashMap;
613.       [WriteOnly] public NativeHashMap<Entity,int>.Concurrent DistinctCollisionEntityHashMap;
614.        
615.       public void Execute([ReadOnly] DynamicBuffer<CollisionInfoBuffer> collisionBuffer)
616.       {
617.          var collisionCandidatesPerGrid = collisionBuffer.AsNativeArray();
618.      
619.          for (int i = 0; i < collisionCandidatesPerGrid.Length - 1; i++)
620.          {
621.             for (int j = i + 1; j < collisionCandidatesPerGrid.Length; j++)
622.             {
623.                var candidateA = collisionCandidatesPerGrid[i];
624.                var candidateB = collisionCandidatesPerGrid[j];
625.                if (Util.IsColliding4(candidateA.box, candidateB.box))
626.                {
627.                   var hash = Util.GetCollisionHash(candidateA.entity.Index, candidateB.entity.Index);
628.                   var cp = new CollisionPairBuffer {EntityA = candidateA.entity, EntityB = candidateB.entity};
629.                   if (DistinctCollisionPairHashMap.TryAdd(hash,cp))
630.                   {
631.                      DistinctCollisionEntityHashMap.TryAdd(candidateA.entity, 1);
632.                      DistinctCollisionEntityHashMap.TryAdd(candidateB.entity, 1);
633.                   }
634.                }
635.             }
636.          }
637.       }
638.    }
639.  
640.    /*
641.  
642.    [BurstCompile]
643.    public struct AABBCollisionBufferToBufferParallelJob : IJobParallelFor
644.    {
645.       [ReadOnly] public BufferArray<CollisionInfoBuffer> collisionCandidates;
646.       [ReadOnly] public int maxThreads;
647.       [ReadOnly] public ColGrid grid;
648.       [NativeDisableParallelForRestriction][WriteOnly] public BufferArray<CollisionPairBuffer> collidingEntities;
649.        
650.       public void Execute(int index)
651.       {
652.          var collidingEntitiesPerGrid = collidingEntities[index];
653.            
654.          for (int t = 0; t < maxThreads; t++)
655.          {    
656.             var collisionCandidatesPerGrid = collisionCandidates[index + grid.CellCount * t].AsNativeArray();    
657.  
658.             for (int i = 0; i < collisionCandidatesPerGrid.Length; i++)
659.             {
660.                var candidate1 = collisionCandidatesPerGrid[i];
661.                int u = t;  
662.                int j = i + 1;
663.                  
664.                if (i == collisionCandidatesPerGrid.Length -1)
665.                {
666.                   u = u + 1;
667.                   j = 0;
668.                }
669.                    
670.                while (u < maxThreads)
671.                {
672.                   var collisionCandidatesPerGrid2 = collisionCandidates[index + grid.CellCount * u].AsNativeArray();
673.                   while (j < collisionCandidatesPerGrid2.Length)
674.                   {
675.                      var candidate2 = collisionCandidatesPerGrid2[j];
676.                    
677.                      if (Util.IsColliding4(candidate1.box, candidate2.box))
678.                      {
679.                         var cp = new CollisionPairBuffer {EntityA = candidate1.entity, EntityB = candidate2.entity};
680.                         collidingEntitiesPerGrid.Add(cp);
681.                      }
682.                      j = j + 1;
683.                   }
684.                   u = u + 1;
685.                   j = 0;
686.                }
687.             }
688.          }
689.       }
690.    }
691.  
692.  
693.    public struct AABBCollisionHashMapToHashMap : IJobNativeMultiHashMapVisitKeyValue<int, CollisionInfo>
694.    {
695.       [ReadOnly] public NativeMultiHashMap<int, CollisionInfo> entitiesPerGridMultiHashMap;
696.       [ReadOnly] public ColGrid myGrid;
697.       [WriteOnly] public NativeHashMap<int,int>.Concurrent PairAlreadyCheckedHashMap;
698.       [WriteOnly] public NativeHashMap<int,CollisionPairBuffer>.Concurrent DistinctCollisionPairHashMap;
699.       [WriteOnly] public NativeHashMap<Entity,int>.Concurrent DistinctCollisionEntityHashMap;
700.      
701.       public void ExecuteNext(int key, CollisionInfo candidateA)
702.       {
703.          NativeMultiHashMapIterator<int> it;
704.          CollisionInfo candidateB;
705.        
706.          int x = key % myGrid.Dim.x;
707.          int y = key / myGrid.Dim.x;
708.        
709.          for (int nY = math.max(0, y - 1); nY < math.min (myGrid.Dim.y, y + 2); nY++)
710.          {
711.             for (int nX = math.max(0, x - 1); nX < math.min (myGrid.Dim.x, x + 2); nX++)
712.             {
713.                var gridKey = nX + nY * myGrid.Dim.x;
714.              
715.                if (entitiesPerGridMultiHashMap.TryGetFirstValue(gridKey, out candidateB, out it))
716.                {
717.                   do
718.                   {
719.                      var entityA = candidateA.entity;
720.                      var entityB = candidateB.entity;
721.                    
722.                      // if not self
723.                      if (entityA.Index != entityB.Index)
724.                      {
725.                         var hash = Util.GetCollisionHash(entityA.Index, entityB.Index);
726.                         // if not already checked
727.                         //if (PairAlreadyCheckedHashMap.TryAdd(hash, 1))                                    // faster in editor to comment out
728.                         {
729.                            if (Util.IsColliding4(candidateA.box, candidateB.box))
730.                            {
731.                               var cp = new CollisionPairBuffer {EntityA = entityA, EntityB = entityB};
732.                               if (DistinctCollisionPairHashMap.TryAdd(hash,cp))
733.                               {
734.                                  DistinctCollisionEntityHashMap.TryAdd(entityA, 1);
735.                                  DistinctCollisionEntityHashMap.TryAdd(entityB, 1);
736.                               }
737.                            }
738.                         }
739.                      }
740.                   } while (entitiesPerGridMultiHashMap.TryGetNextValue(out candidateB, ref it));
741.                }
742.             }
743.          }
744.       }
745.    }
746.  
747.    public struct AABBCollisionNMHMtoNMHMJob : IJobNativeMultiHashMapVisitKeyValue<int, CollisionInfo>
748.    {
749.       [ReadOnly] public NativeMultiHashMap<int, CollisionInfo> entitiesPerGridMultiHashMap;
750.       [WriteOnly] public NativeHashMap<int,CollisionPair>.Concurrent DistinctCollisionPairHashMap;
751.       [WriteOnly] public NativeHashMap<Entity,int>.Concurrent DistinctCollisionEntityHashMap;
752.      
753.       public void ExecuteNext(int key, CollisionInfo candidateA)
754.       {
755.          NativeMultiHashMapIterator<int> it;
756.          CollisionInfo candidateB;
757.        
758.          if (entitiesPerGridMultiHashMap.TryGetFirstValue(key, out candidateB, out it))
759.          {
760.             // advance to own position
761.             while ( (entitiesPerGridMultiHashMap.TryGetNextValue(out candidateB, ref it)) && (candidateA.entity.Index != candidateB.entity.Index) );
762.             // check all following for collision
763.             while (entitiesPerGridMultiHashMap.TryGetNextValue(out candidateB, ref it))
764.             {
765.                var entityA = candidateA.entity;
766.                var entityB = candidateB.entity;
767.                var hash = Util.GetCollisionHash(entityA.Index, entityB.Index);
768.                {
769.                   if (Util.IsColliding4(candidateA.box, candidateB.box))
770.                   {
771.                      var cp = new CollisionPair {EntityA = entityA, EntityB = entityB};
772.                      if (DistinctCollisionPairHashMap.TryAdd(hash,cp))
773.                      {
774.                         DistinctCollisionEntityHashMap.TryAdd(entityA, 1);
775.                         DistinctCollisionEntityHashMap.TryAdd(entityB, 1);
776.                      }
777.                   }
778.                }
779.             }
780.          }
781.       }
782.    }
783.  
784.  
785.    #endregion
786.  
787.    #region Merge Collisions per ColGrid to Distinct List Jobs
788.  
789.    /// <summary>
790.    /// Dequeues input queue into a hashmap for collision pairs and for unique colliding entities --- is called sequentially, to unload various input queues
791.    /// </summary>
792.  
793.    [BurstCompile]
794.    public struct MergeCollisionsPerGridDistinctFromQueueJob : IJob
795.    {
796.       public NativeQueue<CollisionPair> InputQueue;
797.       [WriteOnly] public NativeHashMap<int,CollisionPair> DistinctCollisionPairHashMap;
798.       [WriteOnly] public NativeHashMap<Entity,int> DistinctCollisionEntityHashMap;
799.  
800.       public void Execute()
801.       {
802.          var length = InputQueue.Count;
803.            
804.          for (int i = 0; i < length; i++)
805.          {
806.             var value = InputQueue.Dequeue();
807.             var entityA = value.EntityA;
808.             var entityB = value.EntityB;
809.             var hash = Util.GetCollisionHash(entityA.GetHashCode(), entityB.GetHashCode());
810.             if (DistinctCollisionPairHashMap.TryAdd(hash,value))
811.             {
812.                DistinctCollisionEntityHashMap.TryAdd(entityA, 1);
813.                DistinctCollisionEntityHashMap.TryAdd(entityB, 1);
814.             }
815.          }
816.       }
817.    }
818.  
819.    [BurstCompile]
820.    public struct MergeCollisionsPerGridDistinctFromListJob : IJob
821.    {
822.       [ReadOnly] public NativeList<CollisionPair> InputList;
823.       [WriteOnly] public NativeHashMap<int,CollisionPair> DistinctCollisionPairHashMap;
824.       [WriteOnly] public NativeHashMap<Entity,int> DistinctCollisionEntityHashMap;
825.  
826.       public void Execute()
827.       {
828.          for (int i = 0; i < InputList.Length; i++)
829.          {
830.             var value = InputList[i];
831.             var entityA = value.EntityA;
832.             var entityB = value.EntityB;
833.             var hash = Util.GetCollisionHash(entityA.GetHashCode(), entityB.GetHashCode());
834.             if (DistinctCollisionPairHashMap.TryAdd(hash,value))
835.             {
836.                DistinctCollisionEntityHashMap.TryAdd(entityA, 1);
837.                DistinctCollisionEntityHashMap.TryAdd(entityB, 1);
838.             }
839.          }
840.       }
841.    }
842.  
843.    [BurstCompile]
844.    public struct MergeCollisionsPerGridDistinctFromListParallelJob : IJobParallelFor
845.    {
846.       [ReadOnly] public NativeList<CollisionPair> InputList;
847.       [WriteOnly] public NativeHashMap<int,CollisionPair>.Concurrent DistinctCollisionPairHashMap;
848.       [WriteOnly] public NativeHashMap<Entity,int>.Concurrent DistinctCollisionEntityHashMap;
849.  
850.       public void Execute(int i)
851.       {
852.          var value = InputList[i];
853.          var entityA = value.EntityA;
854.          var entityB = value.EntityB;
855.          var hash = Util.GetCollisionHash(entityA.GetHashCode(), entityB.GetHashCode());
856.          if (DistinctCollisionPairHashMap.TryAdd(hash,value))
857.          {
858.             DistinctCollisionEntityHashMap.TryAdd(entityA, 1);
859.             DistinctCollisionEntityHashMap.TryAdd(entityB, 1);
860.          }
861.       }
862.    }
863.  
864.    [BurstCompile]
865.    public struct MergeCollisionsPerGridDistinctFromBufferJob : IJobParallelFor
866.    {
867.       [ReadOnly] public BufferArray<CollisionPairBuffer> InputBuffer;
868.       [WriteOnly] public NativeHashMap<int,CollisionPairBuffer>.Concurrent DistinctCollisionPairHashMap;
869.       [WriteOnly] public NativeHashMap<Entity,int>.Concurrent DistinctCollisionEntityHashMap;
870.  
871.       public void Execute(int index)
872.       {
873.          var InputArray = InputBuffer[index].AsNativeArray();
874.          for (int i = 0; i < InputArray.Length; i++)
875.          {
876.             var value = InputArray[i];
877.             var entityA = value.EntityA;
878.             var entityB = value.EntityB;
879.             var hash = Util.GetCollisionHash(entityA.GetHashCode(), entityB.GetHashCode());
880.             if (DistinctCollisionPairHashMap.TryAdd(hash,value))
881.             {
882.                DistinctCollisionEntityHashMap.TryAdd(entityA, 1);
883.                DistinctCollisionEntityHashMap.TryAdd(entityB, 1);
884.             }
885.          }
886.       }
887.    }
888.    */
889.    #endregion
890.  
891.    #region Coloring Job
892.  
893.  
894.    /// <summary>
895.    /// Resets color of all sprites and flags the colliding ones
896.    /// </summary>
897.  
898.    [BurstCompile]
899.    [RequireComponentTag (typeof(SpriteTag))]
900.    public struct ColorCollidingEntitiesJob : IJobForEachWithEntity<SimpleRenderColor>
901.    {
902.       [ReadOnly] public NativeHashMap<Entity,int> DistinctCollisionEntityHashMap;
903.       [ReadOnly] public Vector4 hitColor;
904.       [ReadOnly] public Vector4 normColor;
905.        
906.       public void Execute(Entity e, int i, [WriteOnly] ref SimpleRenderColor color)
907.       {
908.      
909.          if (DistinctCollisionEntityHashMap.TryGetValue(e, out int item))
910.          {
911.             color.Value = hitColor;
912.          }
913.          else
914.          {
915.             color.Value = normColor;
916.          }
917.       }
918.    }
919.      
920.    #endregion
921.  
922. }
923.  

Spoiler: Utility - Hash & AABB collision

Code (CSharp):

1.  
2. using System.Collections;
3. using System.Collections.Generic;
4. using UnityEngine;
5. using System.Runtime.CompilerServices;
6. using Unity.Mathematics;
7.  
8. namespace Creation.ECS
9. {
10.    public static class Util
11.    {
12.      
13.       [MethodImpl(MethodImplOptions.AggressiveInlining)]
14.       public static int GetCollisionHash (int a, int b)
15.       {
16.          int hash = (a+b) * (a+b+1) / 2 + math.min(a,b);
17.          //int hash = (a+b) * (a+b-1) / 2 + math.max(a,b);
18.        
19.          //int hash = (math.min(a,b) + math.max(a,b) * Settings.spriteCount);
20.          return hash;
21.       }
22.      
23.       /* Alternatives - still to be tested which one is the fastes
24.      
25.       [MethodImpl(MethodImplOptions.AggressiveInlining)]
26.       public static bool IsColliding1 (Box b1, Box b2)
27.       {
28.          float2 d = math.abs(b1.Center - b2.Center);
29.          float2 e = b1.Extends + b2.Extends;
30.        
31.          return (math.all(d <= e));
32.       }
33.      
34.       [MethodImpl(MethodImplOptions.AggressiveInlining)]
35.       public static bool IsColliding2 (Box b1, Box b2)
36.       {
37.          float2 d = math.abs(b1.Center - b2.Center);
38.          float2 e = b1.Extends + b2.Extends;
39.        
40.          return ((d.x <= e.x) && (d.y <= e.y));
41.       }
42.      
43.       [MethodImpl(MethodImplOptions.AggressiveInlining)]
44.       public static bool IsColliding3 (Box b1, Box b2)
45.       {
46.          bool x = math.abs(b1.Center.x - b2.Center.x) <= (b1.Extends.x + b2.Extends.x);
47.          bool y = math.abs(b1.Center.y - b2.Center.y) <= (b1.Extends.y + b2.Extends.y);
48.        
49.          return x && y;
50.       }
51.       */
52.      
53.       [MethodImpl(MethodImplOptions.AggressiveInlining)]
54.       public static bool IsColliding4 (Box b1, Box b2)
55.       {
56.          if (math.abs(b1.Center.x - b2.Center.x) > (b1.Extends.x + b2.Extends.x)) return false;
57.          if (math.abs(b1.Center.y - b2.Center.y) > (b1.Extends.y + b2.Extends.y)) return false;
58.        
59.          return true;
60.       }
61.    }
62. }
63.  

 

Looks nice! I'm wondering why you don't have the BurstCompile attribute on your write and copy job structs? I could be wrong but I don't think it will actually burst your jobs from just having it on the execute methods

 

Thats what the unity docs say to do. They run much slower without the tags.

 

You're right, in the docs they only have it on the execute methods. In the samples they have it on the structs themselves. Maybe there's no difference.

For non job structs (like ISystemBase) you definitely need it on the struct itself at a bare minimum, not sure why it's different in this case.

 

How many collision were you doing per frame?

 

Sorry for bump, but does anyone have any negative criticism of my system? I have a hard time believing its without its flaws . Any design flaws? Algorithmic flaws? Etc.

I wanna learn more, go ahead roast the system to pieces.

 

I cannot remember but a forum search shows two old post of mine one stating 10,000 in 2ms (collision only) and 50,000 with 60fps (with a few additional systems running). If I find a moment on the weekend, I could rewrite to practice the new DOTS API's. I have not been active for a long time...

https://forum.unity.com/threads/see...using-performance-issues.628078/#post-4213066

 

So I think line 290 has the same bug.

Something in your project was causing asmdefs to get corrupted. And I had to reconstruct your project. But once I got that working, and I fixed your jobs to actually use Burst (most of them were either missing the attribute or had the attribute in the wrong spot), I was able to get some profiling done.

For 100_000 units, your algorithm outperforms my general-purpose multibox SAP. Yours took 3 milliseconds while mine took 8. Most of that comes from your extremely fast incremental update. If we just looked at the resolution stage, my algorithm actually had yours beat, but not by much (0.2 ms).

Those numbers are right in line with what I would expect for this use case. So performance-wise you got the fundamentals right (once Burst is enabled).

You'll get a lot of mileage out of cleaning up your variable names and adding some newlines between structures so that you don't screw up your attributes so easily. After that, you will likely want to add some bounding radius to each entity to perform a vectorized pre-pass in each cell before loading up all the data for the collision solver. That should speed up your resolution stage, which accounts for 93% of the collision detection and resolution.

 

Thanks Latios! I'm sorry the project was corrupted I'm not sure why.

Did you profile in play-mode or did you build the project? Because on my machine the system is taking like 10ms... I'm glad its much faster on your machine though.

Regarding the Burst attributes; Unity Docs show them using it on the execute methods for IJobEntityBatch, and using it on the job structs for all other jobs. When I put the BurstCompile tag at the top of the struct, my IJobEntityBatch jobs don't run.

https://docs.unity3d.com/Packages/com.unity.entities@0.17/manual/ecs_ijobentitybatch.html

Do you mean cleaning up variable names inside the jobs, or the system?

Do you mean going through the grid and finding which entities are colliding, then doing collision resolution in another job on colliding pairs only?

Thanks again.

 

I profiled in the editor with checks and stuff disabled. This isn't always the right way to do it, but for capturing performance of specific job chains, it is pretty accurate.

Now when you say it takes your system 10 ms, for how many units? Because I modified your CreateUnits function to perform 500 CreateArmy calls in a loop to get the 100_000 entities.

I don't think those docs are correct. I moved the [BurstCompile] attribute to the job struct and they showed up Bursted in the profiler. Granted, they were pretty tiny until I bumped up the entity count.

You have some variables that use abbreviations, and other variables in ALL_CAPS. Some variables are coming from data structures. Others are coming from entities. I found it difficult to identify the logic to emulate in my comparison benchmark.

Yes and no. Finding which entities are colliding for a given cell, and then resolving the pairs for that cell. So instead of:
CellStart -> Check -> Resolve -> Check -> Resolve -> Check -> Resolve -> Check -> Resolve -> CellEnd
you would have:
CellStart -> Check -> Check -> Check -> Check -> Resolve -> Resolve -> Resolve -> Resolve -> CellEnd.
Doing it this way then allows you to perform SIMD operations on the checks, which I think are your primary bottleneck based on what I saw in the Profiler.

 

For 50,000 units.

That's weird, maybe I have a Unity bug, because the jobs don't run at all when I do that. I spent a few hours trying to understand why they weren't working.

I see. The all caps were constants passed into jobs; I thought it made it easier to identify which were constants and which were changeable. I forget its not obvious to people who didn't write the code

Yes that's exactly what I was thinking of doing next! Would something like a FixedList be appropriate here? It's stack allocated, so I guess loop through the cells and fill up the list, then do resolution on the list?

 

That's probably a good start. The step beyond that would be lane-left packing the indices into a fixed array.