Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

DOTS Quadtree

Discussion in 'Entity Component System' started by Matt-Cranktrain, Oct 8, 2019.

  1. Matt-Cranktrain

    Matt-Cranktrain

    Joined:
    Sep 10, 2013
    Posts:
    129
    Hey, I'm just wondering if anyone has worked on a Burst compiled DOTS generic Quadtree? (Insert, Remove, GetAllObjectsInRect, Clear... nothing out of the ordinary.)

    I'm often wanting to track where different objects are spatially, so I can look-up nearby objects quickly. Since objects move around, I'm constantly chucking out-of-date Quadtrees away and rebuilding them from the latest set of positions... and this seems to be a perfect use-case for ECS and Burst and Jobs.

    I'm checking if anyone has had a crack at this already because while I've done some work with DOTS, I've a feeling that a properly implemented DOTS Quadtree has to implement it as a Native Collection, ala Jackson Dunstan's work, something that is a bit beyond my understanding of the underlying systems right now!

    If anyone is working on the same problem and wants to get particularly fancy, I would also take a look at this recent paper from the University of Idaho which investigates parallel construction of quadtrees across multiple cores. Some clever ideas there, and it all seems ripe to be Jobified.

    (Antypodish was working on an Octree which is a little more complicated than I'm looking for, concerned as it is with ray intersections. Taking a look at the code itself, I'm also spotting [Inject] labels, so it's using the old API.)

    I appreciate anyone sharing their progress in the same problem space!
     
  2. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    4,223
    Unity.Physics has a custom BVH implementation for collision and spatial queries. You can easily make a QuadTree<T> : IDisposable and a Node<T> and have a NativeArray<Node<T>> or NativeList<Node<T>> as an internal member variable of the QuadTree. Attributes might be a little quirky, but it will at least unblock you.

    I can't help you much with the actual quadtree implementation though. I've always used box pruners for this type of problem, which I find more intuitive to implement in a jobified manner.
     
    Matt-Cranktrain likes this.
  3. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    10,754
    @Matt-Cranktrain hi, thx for mentioning ;)
    If you use at the front of nick name, I would be even notified promptly.
    Just luck I was passing by.

    Yes I used Entities package, when Injection was a thing. I haven't updated it publicly since then. Sorry for that.
    I have learned few thing however, where I could improve in future.

    Also, possibly you have find out, I use entities buffers. That specific requirement toward my project.
    But indeed, it may be a bit overkill for what you need.

    What I can suggest, look into github, and search for quadtrees in Unity/C#. I think I have see some. But haven't looked for them specifically. In worse case scenario, look in other languages.

    Building quadtrees is possible in multi threading approach, but I think main challenge is, how to arrange data allocation, across threads, to avoid race conditions.

    Another matter is, do you really need multithreading, for building quadtree? Is that something you expect 1k+ inserts / removes per frame on multi depth? I don't know your application of course, however, would simple grid be insufficient in your case? I am asking, as if you seen this tech talk vid with minions battle., and it may fit your requirements?

    Unite Austin 2017 - Massive Battle in the Spellsouls Universe
     
    Matt-Cranktrain likes this.
  4. Matt-Cranktrain

    Matt-Cranktrain

    Joined:
    Sep 10, 2013
    Posts:
    129
    Thanks guys, I appreciate your replies!
    Is this exposed in the Physics API at all? I'm not an expert on all the different methods, so perhaps I'm missing something.
    Do you have any favourite documentation/links on multi-box pruners? I know Quadtrees pretty well, but Broadphase physics stuff is not a thing I've ever had to look into.

    @Antypodish, I think your most important question is:
    I do have ~1000 objects that are moving around, so I have to rebuild the Quadtree regularly, and I have to do spatial look-ups every frame.

    My current solution is to build the Quadtree on another thread using, of all things, CeilaSpike's Thread Ninja (a solution I settled on years before ecs/DOTS was a thing!) The advantage is there's no hit to my framerate, and if Quadtrees take a couple of frames to build then who cares because the accuracy is close enough for it not to matter. The disadvantages are: garbage collection overhead when the whole thread is suddenly recycled. Also, I've no idea how cross-platform that old Thread Ninja asset really is! It's a solution that works for me, but it would be a shame not to make use of DOTS here.

    Perhaps, as you say, an improvement would be a simple look-up grid built in DOTS with. It might be slower than a DOTS quadtree, but faster than what I have right now.

    Thanks for the suggestion, something for me to think about there!
    The Quadtree implementation I'm currently using is actually this one from Github, but with a few little changes to reduce Allocations and garbage.

    Thanks for the thoughts guys, I'll have a think about a DOTS-based grid/bucket system, and if I can prototype something then perhaps I can also share the performance improvements in this thread too!
     
  5. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    10,754
    I read briefly in to this quadtree.
    Few thing you can do. First concentrate to allow burst.
    Second, leave it for now in single threaded. Just use job. It should allocate spare thread automatically.

    Then you need replace all vectors to floats.
    And then, figure out, how to take out List, and replace with an array.
    You may want preallocate array size.
    List .Add and AddRange, is what kills its performance here.
    Alternatively you could use buffer array of entities, if you want to go that route.
    Buffer is more elastic, when comes to resizing. But make sure, you resize it as few times as possible. Specially when capacity / size approaches magic thresholds of 2,4,8,16,32 ... 1024 etc.
    If you got array big enough, you just play with index offset, to allocate new elements.

    Also, in linked code, I see m_storedObjects.Clear(). I in fact don't use clear at all in my octree. Just simply resize unallocated length to 0, or set index to 0. Whenever suitable. That is not a problem, as new indexes and data will be overitten, when next indexes of array/buffer will be used.

    In my octree, I have fixed size of allowed element per each node. So I don't need resize arrays, as in above code example. I run each octree creation / modification on single thread. But I can run multiple octrees in different threads.
    However, I can search octree on different threads, when no modification happens.

    Just to give some thoughts.
     
    Last edited: Oct 9, 2019
    Matt-Cranktrain likes this.
  6. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    4,223
    The queries are exposed. The BVH builder is more internalized (though the source code is all visible). It rebuilds the entire BVH for dynamic entities every frame, but it also builds that BVH pretty fast.
    Conceptually, box pruning is just a specific method of the Sweep and Prune (also referred to as Sort and Sweep) where by sorting your data spatially, you can then identify nearby objects by simply iterating adjacent objects in the sorted list. You typically sort all three (or two) axes in separate lists and use some scratch table, compress the spatial axes into a single parameter using a z-order curve, or just sort and iterate one axis and brute force the other two (or one) axes, which is what box pruning usually refers to.
    Implementation-wise, there's lots of optimization tricks presented in this series: http://www.codercorner.com/blog/?page_id=1632
    Many of those tricks also can be applied to Burst, and fortunately the code looks a lot cleaner in C#!
    What most people forget about box pruning is that you can "inflate" the search range by adding and subtracting constants to each min and max.
     
    Matt-Cranktrain likes this.
  7. DwinTeimlon

    DwinTeimlon

    Joined:
    Feb 25, 2016
    Posts:
    300
    If you really have lot's of moving object, I would not use a quadtree as it is not build for adding/removing objects every frame. Go with a spatial grid, easy to DOTsify and also much better for objects which move around.

    I haven't looked into the latest DOTs examples, but the boids example had a very clever spatial position implementation about a year ago.

    That said, for a lot of static objects it might be still an option, but the data structure of quadtrees is by nature not very favourable for multithreading imho.
     
    Ziplock9000 and Matt-Cranktrain like this.
  8. Matt-Cranktrain

    Matt-Cranktrain

    Joined:
    Sep 10, 2013
    Posts:
    129
    For anyone else wanting to have a crack at a Quadtree, a Quadtree represented entirely in a preallocated array is 'Linear Quadtree', that'll help with Googling.

    I've been investigating this with two comparable test, one with my existing Quadtree, and other with a simple DOTS solution. First, here's a Quadtree with 10,000 cubes in it, which move around the available space:



    Red lines show the calculated Quadtree. Clicking anywhere does a Cube lookup within a circular radius of the clicked point and then... sets all the Cube's X position to zero, because that was the easiest thing to do to prove it was finding the right cubes! The Quadtree is being recalculated every single frame.

    Next I tried a straight-forward DOTS setup with every cube's position hashed from a grid. Again: 10,000 cubes, red lines are the debug of the grid:



    Implementation details: I looked into how the Boids demo was doing the position hashing, liked what I saw, and copy/pasted it:
    Code (CSharp):
    1. public static int GetHashedPosition(float2 position, float cellRadius) {
    2.     return (int)math.hash(new int2(math.floor(position / cellRadius)));
    3. }
    4.  
    5. [BurstCompile]
    6. [RequireComponentTag(typeof(NewQuadtreeThing))]
    7. struct HashPositions : IJobForEachWithEntity<LocalToGrid> {
    8.     public NativeMultiHashMap<int, int>.ParallelWriter hashMap;
    9.     public float cellRadius;
    10.  
    11.     public void Execute(Entity entity, int index, [ReadOnly]ref LocalToGrid pos) {
    12.         var hash = GetHashedPosition(pos.Position, cellRadius);
    13.         hashMap.Add(hash, entity.Index);
    14.     }
    15. }
    My game is not pure-ECS, so there is no doubt some overhead as I'm boxing up the position into my LocalToGrid entity, and then at the lookup end I'm performing a Dictionary lookup via EntityID to get the results from the hashMap. This click-test to lookup all Cubes within a radius would be muuuch faster when jobified and Burst compatible, I am sure, but I'm not in a position to rewrite my game with DOTS from the ground up, so this is a hybrid situation.

    Results Time! How did these two similar tests compare?

    Building the Quadtree (non-DOTS) is about 200 to 250 times slower than building the hashmap of hashed positions within the grid (DOTS). Building that hashmap across four processor cores is, for my purposes, essentially free to compute, even with thousands of entities. DOTS is fast, who knew! The added benefit is the nice disposing of collections within the System leads to a bonus performance increase from the lack of nasty garbage collection happening on Quadtree instances.

    But! Lookups are three times faster in the old Quadtree system than in my new Hashmap system. (Again: a DOTS-based lookup would be faster.) So it's a trade-off. Do I want lightning-fast spatial map building, but slightly slower lookups? I mean, yeah, probably. But I can imagine situations where a game would need the Quadtree solution instead.

    You know what would be stunningly fast? A DOTS-based Quadtree. ;) Aaaand we come full-circle back to the beginning of the thread! I still think that University of Idaho paper I linked in my first post is where the cutting-edge of the parallel construction of spatial lookup structures is, and someone who knows the DOTS API much better than I do could absolutely kill my benchmarks with a sensible implementation of that.

    I've spent all the time I can on this problem right now, I'm going to bring my new DOTS-Hashmap-Grid system into my proper game and see what performance increases I experience in the Real World. If I can, I'll report back what I find from my real game.
     
    Last edited: Oct 10, 2019
    NotaNaN, MNNoxMortem, ElliotB and 2 others like this.
  9. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    10,754
    This is nice brake down of the subject.
    I am really curious, if initial implementation in OOP, after conversion to DOTS and burst it, could lead to potential 100x improvement. Even on single thread. In the end, burst is amazing :)

    But that just working on arrays, or relevant, rather hashmap.

    What time duration is taken, for each case? We assume building duration in editor is excluded from timing.
     
  10. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    1,154
    How do you set the grid size? Looks wide, you have to check all neighbor cells for collision, right?

    I did this long ago and recall that my version that hashed in all overlapping cells and used a buffer per cell (instead of NMHM) was the fastest.
     
    DwinTeimlon likes this.
  11. Antypodish

    Antypodish

    Joined:
    Apr 29, 2014
    Posts:
    10,754
    Cell doesn't need to be square. However it may help to be square, for certain applications, or simpler calculations.
     
  12. eizenhorn

    eizenhorn

    Joined:
    Oct 17, 2016
    Posts:
    2,683
    In our game we build hierarchial spatial hash map, it's builds faster than quadtree and lookups faster than one layer spatial hash map (cause it divide more granular and we can discard big empty areas earlier). We decided use 4 layered spatial hash map. with cell sizes 40x40 20x20 5x5 1x1. It feels like something middle between quadtree and spatial hash map, but getting good from all of them. We use it for enemy search and it works pretty well.
     
  13. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    1,154
  14. AlexandrBuryakov

    AlexandrBuryakov

    Joined:
    May 30, 2018
    Posts:
    31
    Tell me where exactly is the source code?
     
  15. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    4,223
    Library->PackageCache->com.unity.physics@0.2.4-preview->Unity.Physics->Collision
    Geometry and World folders contain the BVH stuff.
     
  16. marijnz

    marijnz

    Joined:
    Sep 20, 2012
    Posts:
    67
    Hey, I'm working on a native quadtree. It's here: https://github.com/marijnz/NativeQuadtree
    It currently only supports points and range queries on those points. There's also some preliminary performance results on the repo.
     
    Mikael-H, lclemens, keypax and 6 others like this.
  17. Matt-Cranktrain

    Matt-Cranktrain

    Joined:
    Sep 10, 2013
    Posts:
    129
    Wow, this is looking really impressive - Bulk inserts of 20,000 elements in 0.7ms, a thousand lookups in 1.5ms... looks like you're getting some ridiculously excellent performance already. I'm really looking forward to seeing more!
     
    Walter_Hulsebos likes this.
  18. MintTree117

    MintTree117

    Joined:
    Dec 2, 2018
    Posts:
    340
    Hi! Any updates? I am starting to implement a partition system in DOTS.
     
  19. MintTree117

    MintTree117

    Joined:
    Dec 2, 2018
    Posts:
    340
    Could I ask how you build the hierarchical map? How is the map represented?
     
  20. Matt-Cranktrain

    Matt-Cranktrain

    Joined:
    Sep 10, 2013
    Posts:
    129
    No updates really, the content of that post you quoted is still my experience with the partition system I describe, and it works great in my actual game too. It does what I need!
     
    MintTree117 likes this.
  21. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    3,753
    I have a full working native quad tree container but I can't really share it as it was based off work by aron granberg (a* pathfinding.)

    I'd actually recommend you look at alternate solutions (that have been mentioned here) as I don't really use it, was more a proof of concept. However if you want broad details of implementation I can discuss it a bit.
     
    MNNoxMortem likes this.
  22. MintTree117

    MintTree117

    Joined:
    Dec 2, 2018
    Posts:
    340
    I am trying out the boids example but I am hashing units to multiple cells based on some bounding box.
     
  23. MintTree117

    MintTree117

    Joined:
    Dec 2, 2018
    Posts:
    340
    How does one make a Hasmap Hierarchical?
     
  24. eizenhorn

    eizenhorn

    Joined:
    Oct 17, 2016
    Posts:
    2,683
    Just custom struct wrapped around 4 NMHM with add/remove/create/dispose logic. If I will find time, maybe rewrite that to custom native container. It’s not ideal but works very well for us :)
     
    MintTree117 likes this.
  25. marijnz

    marijnz

    Joined:
    Sep 20, 2012
    Posts:
    67
    MintTree117 likes this.
  26. MintTree117

    MintTree117

    Joined:
    Dec 2, 2018
    Posts:
    340
  27. MintTree117

    MintTree117

    Joined:
    Dec 2, 2018
    Posts:
    340
    Is your container hierarchical because of varying entity size? What if all your entities are nearly uniform size?
     
  28. eizenhorn

    eizenhorn

    Joined:
    Oct 17, 2016
    Posts:
    2,683
    No, logic behind that similar to QuadTree - when we can early out from top, bigger level, if we don't find anything in required area\radius on top level, we just don't need check more adjacent regions on low level. Implementation just based on different detalization levels of spatial partioning. Example, 2 level map - instead of check every low level cell inside radius (green squares) we first check big cell on top level (big red square) and because there is no red dots in this big cell we can guarantee that you don't find any thing in your radius (of course with checks of radius AABB in case you on edge between red cells, thus this check can contain 2,3 or 4 big cells)
    upload_2020-4-22_11-28-6.png
     
    MNNoxMortem, bb8_1 and MintTree117 like this.
  29. marijnz

    marijnz

    Joined:
    Sep 20, 2012
    Posts:
    67
    Nope should just work :) Let me know if it doesn't. Even for non static objects you could use it and just update it once per second or so if that works for your case. Note how fast it is even with many elements and how it can be done on a separate thread.
     
    MintTree117 and Matt-Cranktrain like this.
  30. MintTree117

    MintTree117

    Joined:
    Dec 2, 2018
    Posts:
    340
    Is your hashmap a fixed grid or mapping n-dimensions to one dimension?
     
  31. eizenhorn

    eizenhorn

    Joined:
    Oct 17, 2016
    Posts:
    2,683
    The playable game map has fixed size (XZ), and spatial iterator builds internal hash maps sizes based on this size with flatting XZ coord to 1D index.
     
    Matt-Cranktrain and MintTree117 like this.
  32. lclemens

    lclemens

    Joined:
    Feb 15, 2020
    Posts:
    760
    This is really slick!!

    At first I tried following the codemonkey tutorial, but so much has changed since the video was developed that there was an error that I couldn't get rid of.

    In my application I need to select all the entities in a specified radius instead of via an AABB rect. I tried unsuccessfully to make my own filter for the NativeQuadTree that accepts a custom callback function that would let me write simple filter lambdas... seemed like a great idea, but it huge bust. I blew an entire day fighting against horrid non-descriptive template and Burst errors. I tried everything I could think of Func<>, delegates, function pointers, interfaces... they all resulted in errors. Finally I found https://docs.unity3d.com/Packages/c...al/docs/AdvancedUsages.html#function-pointers which shows that there is a method to use function pointers within a burst function with a bunch of ugly voodoo hacks. At that point I threw in the towel and decided to just make a specialized version of the tree that lets me filter the way I want to.

    Sometimes I feel like Burst and Jobs is going back in time... it's such a small subset of C# - it's like a castrated version of C from the 1980s. Over and over again I find myself wasting time reinventing the wheel because there are so many C# features and libraries that can't be used with Burst and Jobs.

    Anyway... I just want to double-check and make sure I'm refreshing the tree the correct way... I'm new to this. So this is what I have for the system that rebuilds the quad tree:

    Code (CSharp):
    1. // This system constantly rebuilds the quad tree
    2. // To access the quad tree from other systems, use:
    3. //   NativeQuadTree<MyData> tree = World.GetExistingSystem<QuadrantSystem>().tree
    4.  
    5. using Unity.Entities;
    6. using Unity.Mathematics;
    7. using Unity.Collections;
    8. using NativeDataQuadTree;
    9. using Unity.Transforms;
    10.  
    11. public struct MyData
    12. {
    13.         public Entity entity; // holds the entity
    14.         public float3 position; // holds the position
    15.         public uint agentType; // holds the agent type
    16. }
    17.  
    18. public class QuadTreeRefreshSystem : SystemBase
    19. {
    20.     public NativeQuadTree<MyData> tree;
    21.  
    22.     protected override void OnCreate()
    23.     {
    24.         // todo - change this to fetch values from the terrain instead of hardcoding here
    25.         AABB2D bounds;
    26.         bounds.Center.x = 128;
    27.         bounds.Center.y = 128;
    28.         bounds.Extents.x = 128;
    29.         bounds.Extents.y = 128;
    30.         tree = new NativeQuadTree<MyData>(bounds, Allocator.Persistent, 6, 16, 256);
    31.     }
    32.  
    33.     protected override void OnDestroy()
    34.     {
    35.         tree.Dispose();
    36.     }
    37.  
    38.     protected override void OnUpdate()
    39.     {
    40.         EntityQuery query = GetEntityQuery(ComponentType.ReadOnly<Translation>(), ComponentType.ReadOnly<AgentData>());
    41.         NativeArray<Translation> translations = query.ToComponentDataArray<Translation>(Allocator.Temp);
    42.         NativeArray<AgentData> agents = query.ToComponentDataArray<AgentData>(Allocator.Temp);
    43.         NativeArray<Entity> entities = query.ToEntityArray(Allocator.Temp);
    44.         NativeArray<QuadElement<MyData>> elements = new NativeArray<QuadElement<MyData>>(agents.Length, Allocator.Temp);
    45.         MyData data;
    46.         float2 pos2D;
    47.         for (int i = 0; i < elements.Length; i++) {
    48.             data.entity = entities[i];
    49.             data.position = translations[i].Value;
    50.             data.agentType = (uint)agents[i].type;
    51.             data.distanceSq = 0;
    52.             pos2D.x = data.position.x;
    53.             pos2D.y = data.position.z;
    54.             elements[i] = new QuadElement<MyData>() { element = data, pos = pos2D };
    55.         }
    56.         tree.ClearAndBulkInsert(elements);
    57.     }
    58. }
    Another way to do it is via:

    Code (CSharp):
    1.  
    2.     protected override void OnUpdate()
    3.     {
    4.         EntityQuery query = GetEntityQuery(ComponentType.ReadOnly<AgentData>());
    5.         int entityCount = query.CalculateEntityCount();
    6.         NativeArray<QuadElement<MyData>> elements = new NativeArray<QuadElement<MyData>>(entityCount, Allocator.TempJob);
    7.         MyData data;
    8.         float2 pos2D;
    9.         Entities.ForEach((Entity e, int entityInQueryIndex, in Translation pos, in AgentData agent) => {
    10.             data.entity = e;
    11.             data.position = pos.Value;
    12.             data.agentType = (uint)agent.type;
    13.             data.distanceSq = 0f;
    14.             pos2D.x = data.position.x;
    15.             pos2D.y = data.position.z;
    16.             elements[entityInQueryIndex] = new QuadElement<MyData>() { element = quad, pos = pos2D };
    17.         }).Schedule();
    18.         CompleteDependency();
    19.         tree.ClearAndBulkInsert(elements);
    20.     }
    21.  
    Which will run in a separate thread.

    Is it normal to run this every frame? Or do you guys normally run it every couple of frames or something?

    Edit (before I was getting some physics error but it turned out to be totally unrelated).
     
    Last edited: Sep 27, 2021
  33. marijnz

    marijnz

    Joined:
    Sep 20, 2012
    Posts:
    67
    Hey. Nice to see you're playing around with this. This quadtree is especially good when you have many static entities. With movable entities, the tree constantly needs to be rebuild. So indeed what you're doing seems about right!

    I btw made another similar project, a BVH. That does support changes without complete rebuilds and also contains some more example code.

    See: https://github.com/marijnz/NativePhysicsBVH/blob/main/Assets/NativeBVH/Scripts/BVHTreeWorld.cs
    Example usage: https://github.com/marijnz/NativePhysicsBVH/blob/main/Assets/NativeBVH/Scripts/BVHTreeWorld.cs (usage in test: https://github.com/marijnz/NativePh...ts/PlayModeTests/NativeBVHIntegrationTests.cs).

    Ofc. that's all for 3d and not just points, so maybe the QuadTree is a better fit for you. How's it performing for you?

    Sorry for the late response, btw.
     
  34. lclemens

    lclemens

    Joined:
    Feb 15, 2020
    Posts:
    760
    I mainly have movable entities. The quad-tree seems to be working pretty well (at least it's n per frame instead of n * targeter-count like I had before). I haven't tested it with a huge number of entities yet. As for BHV, I couldn't quite figure out how to integrate it with my game... I'm using mostly SystemBase and Entities.ForEach().
     
  35. lclemens

    lclemens

    Joined:
    Feb 15, 2020
    Posts:
    760
    @marijnz I have been using your NativeQuadTree quite a bit (via the second method I stated above with .Schedule() and refreshing it every update). It works very well, but I realized that since my game is using Unity.Physics for the agents, I can use world.OverlapAabb() which is super fast. The circle query for NativeQuadTree is very fast - usually between 0.0ms and 0.4ms for 200 entities and 15 targeters, however, with QuadTreeRefresh running every frame, that adds between 0.09 and 0.12ms. World.OverlapAabb() takes about 0.01ms every frame. Of course, the physics engine itself takes a huge chunk of time (~2ms per frame). Also, world.OverlapAabb() is 3 dimensional, so for terrains that aren't flat, it's a good fit there too.

    So I guess the moral of the story is.... if you're already using Unity.Physics, then world.OverlapAabb() is a great way to go. If you're not using physics, then NativeQuadTree is a fast and easy way to get up and running.
     
  36. marijnz

    marijnz

    Joined:
    Sep 20, 2012
    Posts:
    67
    @lclemens only seeing your reply now! Glad to hear your've been using it! I agree that if you're using Unity.Physics you probably already have the needed queries at hand and don't need my quad tree project.
     
  37. lclemens

    lclemens

    Joined:
    Feb 15, 2020
    Posts:
    760
    If anyone is wondering... here's and example of using a quad tree:

    Code (CSharp):
    1.  
    2. public class ImpactSplashDamageSystem : SystemBase
    3. {
    4.     QuadTreeRefreshSystem m_quadSys;
    5.     protected override void OnCreate()
    6.     {
    7.         m_quadSys = World.GetExistingSystem<QuadTreeRefreshSystem>();
    8.     }
    9.     protected override void OnUpdate()
    10.     {
    11.         NativeQuadTree tree = m_quadSys.m_tree;
    12.         Entities.ForEach((...) => {
    13.              tree.RangeQuery(aabbrectangle, results);
    14.         });
    15.     }
    16. }
    17.  
    To make life easier, I made a copy of NativeQuadTreeRangeQuery.cs and renamed it NativeQuadTreeCircleQuery.cs and changed it so that it defines a query that takes a radius + a point instead of an AABB2D rectangle like this:

    Code (CSharp):
    1. using System;
    2. using Unity.Collections;
    3. using Unity.Collections.LowLevel.Unsafe;
    4. using Unity.Mathematics;
    5.  
    6. namespace NQT
    7. {
    8.     public unsafe partial struct NativeQuadTree
    9.     {
    10.         struct CircleQuery
    11.         {
    12.             NativeQuadTree m_tree;
    13.  
    14.             UnsafeList* m_fastResults;
    15.             int m_count;
    16.  
    17.             float m_radiusSq;
    18.  
    19.             AABB2D m_bounds;
    20.  
    21.             public void Query(NativeQuadTree tree, float radius, float3 point, NativeList<QuadElement> results)
    22.             {
    23.                 m_tree = tree;
    24.                 m_bounds.Extents.x = radius;
    25.                 m_bounds.Extents.y = radius;
    26.                 m_bounds.Center.x = point.x;
    27.                 m_bounds.Center.y = point.z;
    28.                 m_count = 0;
    29.                 m_radiusSq = radius * radius;
    30.  
    31.                 // Get pointer to inner list data for faster writing
    32.                 m_fastResults = (UnsafeList*) NativeListUnsafeUtility.GetInternalListDataPtrUnchecked(ref results);
    33.  
    34.                 RecursiveRangeQuery(tree.m_bounds, false, 1, 1);
    35.  
    36.                 m_fastResults->Length = m_count;
    37.             }
    38.  
    39.             public void RecursiveRangeQuery(AABB2D parentBounds, bool parentContained, int prevOffset, int depth)
    40.             {
    41.                 if (m_count + 4 * m_tree.m_maxLeafElements > m_fastResults->Capacity) {
    42.                     m_fastResults->Resize<QuadElement>(math.max(m_fastResults->Capacity * 2, m_count + 4 * m_tree.m_maxLeafElements));
    43.                 }
    44.  
    45.                 int depthSize = LookupTables.DepthSizeLookup[m_tree.m_maxDepth - depth+1];
    46.                 for (int l = 0; l < 4; l++) {
    47.                     var childBounds = GetChildBounds(parentBounds, l);
    48.  
    49.                     var contained = parentContained;
    50.                     if (!contained) {
    51.                         if(m_bounds.Contains(childBounds)) {
    52.                             contained = true;
    53.                         } else if(!m_bounds.Intersects(childBounds)) {
    54.                             continue; // ignore squares that aren't intersecting or contained
    55.                         }
    56.                     }
    57.  
    58.                     // if code gets here, it means the square is either contained or partially intersecting
    59.  
    60.                     int at = prevOffset + l * depthSize;
    61.  
    62.                     int elementCount = UnsafeUtility.ReadArrayElement<int>(m_tree.m_pLookup->Ptr, at);
    63.  
    64.                     if (elementCount > m_tree.m_maxLeafElements && depth < m_tree.m_maxDepth) {
    65.                         RecursiveRangeQuery(childBounds, contained, at+1, depth+1);
    66.                     } else if(elementCount != 0) {
    67.                         var node = UnsafeUtility.ReadArrayElement<QuadNode>(m_tree.m_pNodes->Ptr, at);
    68.  
    69.                         for (int k = 0; k < node.count; k++) {
    70.                             var element = UnsafeUtility.ReadArrayElement<QuadElement>(m_tree.m_pElements->Ptr, node.firstChildIndex + k);
    71.                             // go through the filters in order from least expensive to most expensive
    72.                                 if (m_bounds.Contains(element.pos)) { // if this entity falls within the boundary
    73.                                     float distSq = math.distancesq(element.pos, m_bounds.Center);
    74.                                     if (distSq < m_radiusSq) { // if this entity is within the specified distance
    75.                                         element.element.distanceSq = distSq;
    76.                                         UnsafeUtility.WriteArrayElement(m_fastResults->Ptr, m_count++, element);
    77.                                     }
    78.                                 }
    79.                         }
    80.                     }
    81.                 }
    82.             }
    83.         }
    84.  
    85.     }
    86. }
    Then I added a function in NativeQuadTree.cs like this:

    Code (CSharp):
    1.        
    2.         // This query will pick up all objects that match the specified filter
    3.         public void PerformCircleQuery(float radius, float3 point, ref NativeList<QuadElement> results)
    4.         {
    5. #if ENABLE_UNITY_COLLECTIONS_CHECKS
    6.             AtomicSafetyHandle.CheckReadAndThrow(safetyHandle);
    7. #endif
    8.             new CircleQuery().Query(this, radius, point, results);
    9.         }
    10.  
    That's not necessary, but it's handy because then in your ForEach loop you can just write: tree.PerformCircleQuery(radius, point, results);

    Another thing that might come in handy for targeting situations.... put 2 trees as member variables into QuadTreeRefreshSystem . One for enemies and one for players (or however you want to divide your factions). Then when you refresh the trees, you can put only enemies in one and only players in the other and when you query them, the queries will run even faster because they can ignore entities that you're not interested in.
     
  38. nijnstein

    nijnstein

    Joined:
    Feb 6, 2021
    Posts:
    78
    i had this problem and managed to reduce it a lot by allowing small updates within a region to not invalidate the tree, also if there is room in another leaf node it can be used without invalidations.

    I would store much less data and use no recursion and mostly stack memory on query:

    Code (CSharp):
    1.  
    2.         // Stores all the elements in the quadtree.
    3.         //  data = lft, top, rght, bottom & element id
    4.         public ConstantIndexIntList elements;
    5.  
    6.         // Stores all the element nodes in the quadtree.
    7.         // - the elements in the leafs
    8.         public ConstantIndexIntList element_nodes;
    9.  
    10.         // Stores all the nodes in the quadtree. The first node in this
    11.         // sequence is always the root.
    12.         // - the regions making up the tree
    13.         // data =  next (if -1 end of list), elementid
    14.  
    15.         // data = nodeid or leafid,  element: count or -1 if leaf
    16.         public ConstantIndexIntList nodes;
    17.  
    Everything is an integer index into these lists with constant indices on removals (freelist principle), regions are only stored for the element and even that could be removed if its stored somewhere else (bounds of entity..)

    it all gets a little more complex inserting:

    Code (CSharp):
    1.  
    2.   unsafe private void node_insert(int index, int depth, int mx, int my, int sx, int sy, int element)
    3.         {
    4.             // Find the leaves and insert the element to all the leaves found.
    5.             int j = 0;
    6.             int* stack = stackalloc int[stack_size];
    7.             ConstantIndexIntList leaves = ConstantIndexIntList.Create(nd_num, temp_allocator, stack, stack_size);
    8.             int lft = data->elements.Get(element, elt_idx_lft);
    9.             int top = data->elements.Get(element, elt_idx_top);
    10.             int rgt = data->elements.Get(element, elt_idx_rgt);
    11.             int btm = data->elements.Get(element, elt_idx_btm);
    12.      
    13.             data->find_leaves(ref leaves, index, depth, mx, my, sx, sy, lft, top, rgt, btm, temp_allocator);
    14.             for (j = 0; j < leaves.Size; j++)
    15.             {
    16.                 int nd_mx =    leaves.Get(j, nd_idx_mx);
    17.                 int nd_my =    leaves.Get(j, nd_idx_my);
    18.                 int nd_sx =    leaves.Get(j, nd_idx_sx);
    19.                 int nd_sy =    leaves.Get(j, nd_idx_sy);
    20.                 int nd_index = leaves.Get(j, nd_idx_index);
    21.                 int nd_depth = leaves.Get(j, nd_idx_depth);
    22.                 leaf_insert(nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy, element);
    23.             }
    24.             leaves.Destroy();
    25.         }
    26.  
    27.         unsafe private void leaf_insert(int node, int depth, int mx, int my, int sx, int sy, int element)
    28.         {
    29.             // Insert the element node to the leaf.
    30.             int nd_fc = data->nodes.Get(node, node_idx_fc);
    31.             data->nodes.Set(node, node_idx_fc, data->element_nodes.Insert());
    32.             data->element_nodes.Set(data->nodes.Get(node, node_idx_fc), enode_idx_next, nd_fc);
    33.             data->element_nodes.Set(data->nodes.Get(node, node_idx_fc), enode_idx_elt, element);
    34.             // If the leaf is full, split it.
    35.             if (data->nodes.Get(node, node_idx_num) == max_elements && depth < max_depth)
    36.             {
    37.                 int fc = 0, j = 0;
    38.                 int* stack = stackalloc int[64];
    39.                 ConstantIndexIntList elts = ConstantIndexIntList.Create(1, temp_allocator, stack, 64);
    40.                 // Transfer elements from the leaf node to a list of elements.
    41.                 while (data->nodes.Get(node, node_idx_fc) != -1)
    42.                 {
    43.                     int index = data->nodes.Get(node, node_idx_fc);
    44.                     int next_index = data->element_nodes.Get(index, enode_idx_next);
    45.                     int elt = data->element_nodes.Get(index, enode_idx_elt);
    46.                     // Pop off the element node from the leaf and remove it from the qt.
    47.                     data->nodes.Set(node, node_idx_fc, next_index);
    48.                     data->element_nodes.Erase(index);
    49.                     // Insert element to the list.
    50.                     elts.Set(elts.PushBack(), 0, elt);
    51.                 }
    52.                 // Start by allocating 4 child nodes.
    53.                 fc = data->nodes.Insert();
    54.                 data->nodes.Insert();
    55.                 data->nodes.Insert();
    56.                 data->nodes.Insert();
    57.                 data->nodes.Set(node, node_idx_fc, fc);
    58.                 // Initialize the new child nodes.
    59.                 for (j = 0; j < 4; ++j)
    60.                 {
    61.                     data->nodes.Set(fc + j, node_idx_fc, -1);
    62.                     data->nodes.Set(fc + j, node_idx_num, 0);
    63.                 }
    64.                 // Transfer the elements in the former leaf node to its new children.
    65.                 data->nodes.Set(node, node_idx_num, -1);
    66.                 for (j = 0; j < elts.Size; j++)
    67.                 {
    68.                     node_insert(node, depth, mx, my, sx, sy, elts.Get(j, 0));
    69.                 }
    70.                 elts.Destroy();
    71.             }
    72.             else
    73.             {
    74.                 // Increment the leaf element count.
    75.                 data->nodes.Set(node, node_idx_num, data->nodes.Get(node, node_idx_num) + 1);
    76.             }
    77.         }
    78.  
    79.  
    and query needs memory for each thread accessing it but is thread safe. (its a small change to use stack or pre-allocated memory for each thread. 256Kb for 2M items if done with a bitarray)

    Code (csharp):
    1.  
    2.         public void Query(ref ConstantIndexIntList output, int qlft, int qtop, int qrgt, int qbtm, int omit_element, Allocator allocator)
    3.         {
    4.             // Find the leaves that intersect the specified query rectangle.
    5.             int j = 0;
    6.             int* stack = stackalloc int[QuadTree.stack_size];
    7.             ConstantIndexIntList leaves = ConstantIndexIntList.Create(QuadTree.nd_num, allocator, stack, QuadTree.stack_size);
    8.             ///  update to use a stack based list..
    9.             ///  TODO
    10.             ///  bit array list .
    11.             byte* temp = (byte*)UnsafeUtility.Malloc(elements.Size, 1, allocator);
    12.             UnsafeUtility.MemClear(temp, elements.Size);
    13.             // For each leaf node, look for elements that intersect.
    14.             find_leaves(ref leaves, 0, 0, root_mx, root_my, root_sx, root_sy, qlft, qtop, qrgt, qbtm, allocator);
    15.             output.Clear();
    16.             for (j = 0; j < leaves.Size; j++)
    17.             {
    18.                 int nd_index = leaves.Get(j, QuadTree.nd_idx_index);
    19.                 // Walk the list and add elements that intersect.
    20.                 int elt_node_index = nodes.Get(nd_index, QuadTree.node_idx_fc);
    21.                 while (elt_node_index != -1)
    22.                 {
    23.                     int element = element_nodes.Get(elt_node_index, QuadTree.enode_idx_elt);
    24.                     int lft = elements.Get(element, QuadTree.elt_idx_lft);
    25.                     int top = elements.Get(element, QuadTree.elt_idx_top);
    26.                     int rgt = elements.Get(element, QuadTree.elt_idx_rgt);
    27.                     int btm = elements.Get(element, QuadTree.elt_idx_btm);
    28.                     if (temp[element] == 0 && element != omit_element && QuadTree.intersect(qlft, qtop, qrgt, qbtm, lft, top, rgt, btm))
    29.                     {
    30.                         output.Set(output.PushBack(), 0, element);
    31.                         temp[element] = 1;
    32.                     }
    33.                     elt_node_index = element_nodes.Get(elt_node_index, QuadTree.enode_idx_next);          
    34.                 }
    35.             }
    36.             leaves.Destroy();
    37.             // IF DONT OWN TEMP BUFFER: Unmark the elements that were inserted.
    38.             //  for (j = 0; j < output.Size; ++j)
    39.             //{
    40.             //    temp[output.Get(j, 0)] = 0;
    41.             //}
    42.             UnsafeUtility.Free(temp, allocator);
    43.         }
    44.  
    45.  
    But this is lighning fast with burst, a system handling many thousands of queries barely registers in cpu. It doesnt use floats, as probably you wouldnt really need to depending on use and it helps with hyperthreading in my case as the floatingpoint unit is free on the core running it. The main thing is that it doesnt fragment memory and would allocate only once per thread during program lifetime if used correctly (dont use the query function as is)

    Internally the 3 constantintlists are kept in a struct as pointers that is past around for jobs.

    i think i used this thread to produce the above code for information: https://stackoverflow.com/questions...ementation-of-a-quadtree-for-2d-collision-det

    here it is in action, only operating on dynamic objects and not checking any collisions for testing its structure (i cant draw or paint so dont mind the graphics)


    As noted earlier, use different trees for different things, in this demo all static and dynamics are seperated and vegetation operates on a different tree with a different granularity.
     
    Last edited: Dec 13, 2021
  39. MintTree117

    MintTree117

    Joined:
    Dec 2, 2018
    Posts:
    340
  40. gato0429

    gato0429

    Joined:
    Mar 5, 2015
    Posts:
    22
    hello, after reading the whole post, I decided to try the nativequeadtree from: https://github.com/marijnz/NativeQuadtree , but I have a problem when trying to add it to my project, I get the following error.

    upload_2022-2-26_16-3-3.png

    I tried putting it into an assembly, but I still can't figure out why the error persists. Could someone tell me how he added it to his project, and avoid that error.

    Thanks in advance.
     
  41. WAYNGames

    WAYNGames

    Joined:
    Mar 16, 2019
    Posts:
    988
    You are probably using a different version of the collection package in your project than the one used to make that quad tree package.

    From what I can see the quad tree package is 2 years old and rely on the physics package to import the dependencies. You probably work with a more recent version of the collection package so it may no longer have the method used by that class in the package.

    Edit: You can probably remove line 78 of the NativeQuadTree.cs since T is already constrained to be unmanaged by the struct definition line 32
     
    Last edited: Feb 27, 2022
  42. nijnstein

    nijnstein

    Joined:
    Feb 6, 2021
    Posts:
    78
    i've put a implementation of the method used in https://stackoverflow.com/questions...ementation-of-a-quadtree-for-2d-collision-det on github: https://github.com/nijnstein/Unity-Performance-Utils/blob/main/quadtree.cs

    Its a managed class with a burstable data structure that can be searched in jobs, i ripped it from another project that kinda got shelved in favor of yet something else so let me know if something is missing. In implementation a pointer to the internal structure is used in jobs and usually the code to search the tree is implemented in the jobs code, ive added some functions in the structure to search it but you should really implement your own for max performance /r
     
  43. gato0429

    gato0429

    Joined:
    Mar 5, 2015
    Posts:
    22
    thanks, for the answer
     
  44. bartofzo

    bartofzo

    Joined:
    Mar 16, 2017
    Posts:
    150
    If anyone is interested, I made my own implementation of a quadtree and octree that's compatible with Burst and DOTS.
    It's generic, supports AABB's, raycast, overlap and K-nearest neighbour queries:

    https://github.com/bartofzo/NativeTrees