Spacial Partitioning with Unity Tiny 16 (DotNet & AsmJS)

So, I've made a Spacial Partitioning script.. Hopefully this will make someone happy :^)

Add the CheckCollision component to any entity you want to take into account for partitioning. The script will result in a List of Quads ,which is a Rect and a List of entities, these entitie lists are all entities that are in the same rect.

Sorry for the massive slab of code..

Code (CSharp):

1. using System.Collections.Generic;
2. using System.Diagnostics;
3. using Unity.Collections;
4. using Unity.Entities;
5. using Unity.Mathematics;
6. using Unity.Tiny.Core2D;
7. using Debug = UnityEngine.Debug;
8.  
9. public class QuadtreeBroadPhase : ComponentSystem
10. {
11.     public struct Quad
12.     {
13.         public int Id;
14.         public Rect rect;
15.         public List<Entity> entities;
16.     }
17.  
18.     public struct QuadGroup
19.     {
20.         public Quad q1;
21.         public Quad q2;
22.         public Quad q3;
23.         public Quad q4;
24.     }
25.  
26.     private int _screenWidth = 6;
27.     private int _screenHeight = 10;
28.  
29.     public int _uniqueId = 0;
30.  
31.     private List<Quad> _quads;
32.     private List<QuadGroup> _quadGroups;
33.  
34.     protected override void OnCreate()
35.     {
36.         // Create initial 4 quads
37.         _quads = new List<Quad>();
38.         _quadGroups = new List<QuadGroup>();
39.  
40.         Quad q1;
41.         q1.Id = UniqueId();
42.         q1.rect = new Rect(-3, -5, _screenWidth / 2, _screenHeight / 2);
43.         q1.entities = new List<Entity>();
44.         _quads.Add(q1);
45.  
46.         Quad q2;
47.         q2.Id = UniqueId();
48.         q2.rect = new Rect(-3, 0, _screenWidth / 2, _screenHeight / 2);
49.         q2.entities = new List<Entity>();
50.         _quads.Add(q2);
51.  
52.         Quad q3;
53.         q3.Id = UniqueId();
54.         q3.rect = new Rect(0, -5, _screenWidth / 2, _screenHeight / 2);
55.         q3.entities = new List<Entity>();
56.         _quads.Add(q3);
57.  
58.         Quad q4;
59.         q4.Id = UniqueId();
60.         q4.rect = new Rect(0, 0, _screenWidth / 2, _screenHeight / 2);
61.         q4.entities = new List<Entity>();
62.         _quads.Add(q4);
63.     }
64.  
65.     protected override void OnUpdate()
66.     {
67.         Debug.Log("---- UPDATE FRAME ----");
68.         Debug.Log("Amount of quads in scene = " + _quads.Count);
69.         Debug.Log("Amount of quadgroups in scene = " + _quadGroups.Count);
70.         var query = GetEntityQuery(typeof(CheckCollision)).ToEntityArray(Allocator.Persistent);
71.  
72.         for (int i = 0; i < query.Length; i++)
73.         {
74.             var position = EntityManager.GetComponentData<Translation>(query[i]);
75.  
76.             for (int j = 0; j < _quads.Count; j++)
77.             {
78.                 if (_quads[j].rect.Contains(position.Value.xy))
79.                 {
80.                     _quads[j].entities.Add(query[i]);
81.                 }
82.             }
83.         }
84.  
85.         // Debug amount of entities per quad (needs new loop to make sure of consitency)
86.         for (int i = 0; i < _quads.Count; i++)
87.         {
88.             Debug.Log("Quad Id : " + _quads[i].Id);
89.             Debug.Log("Contains : " + _quads[i].entities.Count);
90.         }
91.  
92.         for (int i = 0; i < _quads.Count; i++)
93.         {
94.             //Split the quad
95.             if (_quads[i].entities.Count > 10)
96.             {
97.                 var oldRect = _quads[i].rect;
98.                 var oldEntities = _quads[i].entities;
99.  
100.                 _quads.RemoveAt(i);
101.  
102.                 Quad q1;
103.                 q1.Id = UniqueId();
104.                 q1.rect = new Rect(oldRect.x, oldRect.y, oldRect.width / 2, oldRect.height / 2);
105.                 q1.entities = new List<Entity>();
106.  
107.                 Quad q2;
108.                 q2.Id = UniqueId();
109.                 q2.rect = new Rect(oldRect.x + (oldRect.width / 2), oldRect.y, oldRect.width / 2, oldRect.height / 2);
110.                 q2.entities = new List<Entity>();
111.                
112.                 Quad q3;
113.                 q3.Id = UniqueId();
114.                 q3.rect = new Rect(oldRect.x, oldRect.y + (oldRect.height / 2), oldRect.width / 2, oldRect.height / 2);
115.                 q3.entities = new List<Entity>();
116.                
117.                 Quad q4;
118.                 q4.Id = UniqueId();
119.                 q4.rect = new Rect(oldRect.x + (oldRect.width / 2), oldRect.y + (oldRect.height / 2), oldRect.width / 2, oldRect.height / 2);
120.                 q4.entities = new List<Entity>();
121.  
122.                 for (int j = 0; j < oldEntities.Count; j++)
123.                 {
124.                     var position = EntityManager.GetComponentData<Translation>(oldEntities[j]);
125.  
126.                     if (q1.rect.Contains(position.Value.xy))
127.                     {
128.                         q1.entities.Add(oldEntities[j]);
129.                     }
130.  
131.                     if (q2.rect.Contains(position.Value.xy))
132.                     {
133.                         q2.entities.Add(oldEntities[j]);
134.                     }
135.  
136.                     if (q3.rect.Contains(position.Value.xy))
137.                     {
138.                         q3.entities.Add(oldEntities[j]);
139.                     }
140.  
141.                     if (q4.rect.Contains(position.Value.xy))
142.                     {
143.                         q4.entities.Add(oldEntities[j]);
144.                     }
145.                 }
146.  
147.                 _quads.Add(q1);
148.                 _quads.Add(q2);
149.                 _quads.Add(q3);
150.                 _quads.Add(q4);
151.  
152.                 var newGroup = new QuadGroup();
153.                 newGroup.q1 = q1;
154.                 newGroup.q2 = q2;
155.                 newGroup.q3 = q3;
156.                 newGroup.q4 = q4;
157.                 _quadGroups.Add(newGroup);
158.  
159.             }
160.             else if (_quads[i].entities.Count < 2)
161.             {
162.                 var quadGroup = QuadToGroup(_quads[i]);
163.  
164.                 for (int j = 0; j < _quads.Count; j++)
165.                 {
166.                     if (quadGroup.q1.Id == _quads[j].Id)
167.                     {
168.                         quadGroup.q1.entities = _quads[j].entities;
169.                     }
170.  
171.                     if (quadGroup.q2.Id == _quads[j].Id)
172.                     {
173.                         quadGroup.q2.entities = _quads[j].entities;
174.                     }
175.  
176.                     if (quadGroup.q3.Id == _quads[j].Id)
177.                     {
178.                         quadGroup.q3.entities = _quads[j].entities;
179.                     }
180.  
181.                     if (quadGroup.q4.Id == _quads[j].Id)
182.                     {
183.                         quadGroup.q4.entities = _quads[j].entities;
184.                     }
185.                 }
186.  
187.                 if (EntitiesInGroup(quadGroup) < 6)
188.                 {
189.                     // Get all the old entities
190.                     List<Entity> oldEntities = MergeEntityList(quadGroup.q1.entities, quadGroup.q2.entities, quadGroup.q3.entities, quadGroup.q4.entities);
191.                    
192.                     // Destroy the old quads
193.                     DestroyQuadById(quadGroup.q1.Id);
194.                     DestroyQuadById(quadGroup.q2.Id);
195.                     DestroyQuadById(quadGroup.q3.Id);
196.                     DestroyQuadById(quadGroup.q4.Id);
197.  
198.                     // create new rect
199.                     Quad quad;
200.                     quad.Id = UniqueId();
201.                     quad.rect = GroupToRect(quadGroup);
202.                     quad.entities = oldEntities;
203.                     _quads.Add(quad);
204.                 }
205.                 else
206.                 {
207.                     Debug.Log("Quad might be too empty, but his friends are still full");
208.                 }
209.             }
210.         }
211.         for (int i = 0; i < _quads.Count; i++)
212.         {
213.             _quads[i].entities.Clear();
214.         }
215.  
216.         query.Dispose();
217.     }
218.  
219.     public QuadGroup QuadToGroup(Quad quad)
220.     {
221.         var quadGroup = new QuadGroup();
222.  
223.         for (int i = 0; i < _quadGroups.Count; i++)
224.         {
225.             if (_quadGroups[i].q1.Id == quad.Id || _quadGroups[i].q2.Id == quad.Id || _quadGroups[i].q3.Id == quad.Id || _quadGroups[i].q4.Id == quad.Id)
226.             {
227.                 return _quadGroups[i];
228.             }
229.         }
230.  
231.         return quadGroup;
232.     }
233.  
234.     public Rect GroupToRect(QuadGroup quadGroup)
235.     {
236.         // Find bottom left quad
237.         Rect bottomLeft = quadGroup.q4.rect;
238.  
239.         if (quadGroup.q2.rect.x < bottomLeft.x || quadGroup.q2.rect.y < bottomLeft.y)
240.         {
241.             bottomLeft = quadGroup.q2.rect;
242.         }
243.  
244.         if (quadGroup.q3.rect.x < bottomLeft.x || quadGroup.q3.rect.y < bottomLeft.y)
245.         {
246.             bottomLeft = quadGroup.q3.rect;
247.         }
248.  
249.         if (quadGroup.q1.rect.x < bottomLeft.x || quadGroup.q1.rect.y < bottomLeft.y)
250.         {
251.             bottomLeft = quadGroup.q1.rect;
252.         }
253.  
254.         bottomLeft.width = quadGroup.q1.rect.width * 2;
255.         bottomLeft.height = quadGroup.q1.rect.height * 2;
256.  
257.         return bottomLeft;
258.     }
259.  
260.     public int EntitiesInGroup(QuadGroup group)
261.     {
262.         return group.q1.entities.Count + group.q2.entities.Count + group.q3.entities.Count + group.q4.entities.Count;
263.     }
264.  
265.     public void DestroyQuadById(int quadId)
266.     {
267.         for (int i = 0; i < _quads.Count; i++)
268.         {
269.             if (_quads[i].Id == quadId)
270.             {
271.                 _quads.RemoveAt(i);
272.             }
273.         }
274.     }
275.  
276.     public List<Entity> MergeEntityList(List<Entity> list1, List<Entity> list2, List<Entity> list3, List<Entity> list4)
277.     {
278.         for (int i = 0; i < list2.Count; i++)
279.         {
280.             list1.Add(list2[i]);
281.         }
282.  
283.         for (int i = 0; i < list3.Count; i++)
284.         {
285.             list1.Add(list3[i]);
286.         }
287.  
288.         for (int i = 0; i < list4.Count; i++)
289.         {
290.             list1.Add(list4[i]);
291.         }
292.  
293.         return list1;
294.     }
295.    
296.     public int UniqueId()
297.     {
298.         return ++_uniqueId;
299.     }
300. }
301.  

 

And yes I know this isn't the cleanest code