Creating a quad tree with native collections?

I'm attempting to re-create a quad-tree for the 2d physics broadphase.
Now I'm not sure how to do it with native collections. I've got this:

Code (CSharp):

1. public struct QuadTreeNode2D {
2.     public NativeList<QuadTreeNode2D> Children;
3.     public NativeList<QuadTreeData2D> Contents;
4. }

Which isn't allowed because that would make QuadTreeNode2D non-blittable.
Does anyone know good architectural solution for this kind of case?

 

I have made a tree-like structure like this:

Code (CSharp):

1. struct Node {
2.     public int parentIndex;
3.     public int firstChildIndex;
4.     public int nextSiblingIndex;
5.     // blittable contents. you can store a (startIndex, count) to some other parallel NativeArray<> here
6. }
7. NativeArray<Node> tree;

or you could use Entities as nodes, with a

struct Children : IBufferElementData {public Entity Value;}

 

I've hoped to avoid using array to unwrap a tree into due to how often that tree would get updated.
I guess there's no other way around it.

Managing indexes would probably be a pain tho.

 

yeah I used that structure only for appending nodes
if you need to move/delete nodes it could be a pain
if your children count is fixed, you can do

struct Node {int parent, leftChild, rightChild, etc;}

instead. or

unsafe struct Node {int parent, fixed int children[N];}

 

There is Unity.Collections.LowLevel.Unsafe.UnsafeList/UnsafePtrList which are blittable. There is no AtomicSafety on them so you'd need to do those checks in your wrapper node class if you want to use jobs. Alternatively you could learn to write your own, I think the DisposeSentinel is the main thing making NativeList and others not blittable.(there may be others because NativeList/NativeArray shouldn't be safe to use in a component if it were blittable)

 

Well, that's a bit too late. I've already rewritten almost everything to the int pointers in the array.
But it's good to know. Thanks

 

Hmm, reading this got me curious . I also rewrote kdtree with int pointers and NativeArrays to store all points and indices:
https://forum.unity.com/threads/point-nearest-neighbour-search-class.29923/

So I was curious if using unsafe to store data through structs could be petter performing (assuming that we don't add, move or delete individual nodes)?

 

I'd say it depends on the implementation.

 

I guess the best thing is just to try it

P.S. As for quadtree, are you using it mostly for collisions or to find nearest neighbours?

 

For broadphase approximation, e.g. to find nearest colliders within some adequate scope to perform intersection checks in the later phase. So it's a search more than collision resolution.

I haven't done anything in regards of collision resolution, as that seems to be a completely different topic.

And simply making things interact and intersect may not be that easy with ECS setup (personally).
I wonder if the actual jobified version with burst would be faster than adequate broadphase w/o jobs. I guess that depends on the object count.

 

Hmm, interesting, didn't knew about broadphase approximation before but googled and seems to be quite interesting topic.

As for collision, I looked a bit in Unity's provided collisional local avoidance and did some tests described here:
https://forum.unity.com/threads/collisional-local-avoidance-extracted.599023/

Wasn't sure what algorithm that one represents, but looks like locality sensitive hashing... In short it runs about 20k-40k units at playable FPS. The kdtree tests show that it's slower, i.e. only 7-10k units. Now I am quite keen where quadtree falls in this picture since it's another approach and I didn't tested it yet .

 

Would be interesting to see the quadtree's performance. I did some aabb 2d collision testing before and simply used a grid for the broadphase.

 

Well, it seems like I've made a huge architectural mistake, as there seems to be no way to inject the entire quad tree struct by ref into jobs. (Cannot inject it due to native collections / non-blittable, cannot use it as componentdata)

Should've thought about this before implementing everything, doh!

I wonder if without qt will it run fast enough.
Or perhaps I should not have done this in an old way. Maybe something like grouping components in certain bounds and then processing them would work the same way.

 

On my iMac 2015, I have the AABB collision running at about 2ms for 10,000 entities. This includes highlighting colliding entities as a simple “collision resolution”. Including moving and rendering it takes about 3.5ms.

It’s not fully optimized and brute forces the special grid allocation, but many jobs run parallel (4 cores)

 

Nice one! I may also try to do a grid version at some point. Did some reading and it seems if cell sizes are close to the sizes of units, then brute force is minimal. How large are your grids? I am a bit worried memory wise as I am using 6km x 6km size worlds and want to resolve units with sizes of 1 m. This would give 36M grid cells .

 

It’s only a test, the grid in a real case should be optimized for sprite dimensions, density, movement patterns,...ideally the grid would be structured in a way that the colliding entities keep at all times equally distributed across the grid cells.

I have used an 8x8 Grid, if I recall correctly.

 

This does not seem to be the thing that should be implemented with native collections, instead it should be implemented as a native collection.

 

@tertle that's also my take on it. I started on something here: https://github.com/marijnz/NativeQuadtree. Still WIP but the insertion and querying works.

 

Looks good.

I recently created one for something at work but unfortunately I can't post it as it's based off something that needs licensing.