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

Concurrent NativeList and SpatialHashing

Discussion in 'Entity Component System' started by dadude123, Jun 4, 2019.

  1. dadude123

    dadude123

    Joined:
    Feb 26, 2014
    Posts:
    789
    Hi,
    I want to use spatial hashing to quickly find nearby entities.
    I've spent quite some time looking into the boids example but the way it works is pretty complicated. Too complicated in fact.

    What I want to do is something like hashing the position of each entity, and then putting it in the right bucket.
    In the "narrow phase" I can then iterate over all entities, get their bucket, and all 8 neighboring buckets (for the 2D case).

    Some people create a real "grid", using an multidimensional array (or two nested arrays), but for what I'm doing I want to maintain more control over the exact number of buckets.

    So here is what I tried first:

    Code (CSharp):
    1.  
    2.     struct HashPositionsIntoBuckets : IJobForEachWithEntity<Translation>
    3.     {
    4.         NativeArray<NativeList<int>> buckets;
    5.         public float cellRadius;
    6.  
    7.         public void Execute(Entity entity, int entIndex, [ReadOnly] ref Translation translation)
    8.         {
    9.             float3 p = translation.Value;
    10.             int3 rounded = int3(floor(p / cellRadius));
    11.             int hash = (int)math.hash(rounded);
    12.  
    13.             var bucketIndex = hash % buckets.Length;
    14.             var bucket = buckets[bucketIndex];
    15.  
    16.             bucket.Add(entIndex);
    17.         }
    18.     }
    19.  
    However there's no `.Concurrent` version of NativeList. Why?
    Not really sure how to progress here.

    I'd rather not spend more time with the super convoluted boids example.
    It doesn't look like it even solves the specific problem I want to solve.
    The way it works, it doesn't seem like it can access neighboring cells, but I definitely need that.

    https://github.com/Unity-Technologi...s/Assets/Advanced/Boids/Scripts/BoidSystem.cs
     
  2. recursive

    recursive

    Joined:
    Jul 12, 2012
    Posts:
    669
    You can use a NativeQueue<T>.Concurrent accessor and linearize its contents into a NativeList<T> using an IJob dependent on the concurrent writing jobs.
     
  3. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    3,753
    I'm not sure how many queries you're doing a frame but have you considered just using Unity.Physics?

    Originally I was a bit hesitant to use it for nearby neighbor queries (in 2D) but after testing it I have no issues doing 300 queries every frame.

    Now it's not going to scale to the 1-10k+ queries/frame which is where you need some super optimized solution like boids, but if you're basically just implementing a broad phase then narrow phase like a physics engine does, they're probably going to have optimized it better than you will.
     
  4. snacktime

    snacktime

    Joined:
    Apr 15, 2013
    Posts:
    3,356
    I would just use a NativeHashMap with an int2 key if you want something simple. Or a NativeArray with 2d to 1d mapping.
     
  5. dadude123

    dadude123

    Joined:
    Feb 26, 2014
    Posts:
    789
    Hmm, I just realized that nested collections are not possible in the first place.
    NativeArray<NativeQueue<int>.Concurrent>
    will result in
    InvalidOperationException: Unity.Collections.NativeQueue`1[System.Int32] used in NativeArray<Unity.Collections.NativeQueue`1[System.Int32]> must be unmanaged (contain no managed types)


    And even if that were possible, how would I convert each NativeQueue into a NativeList then? Each queue-to-list operation should be in its own job, right?

    So probably like
    Code (CSharp):
    1.  
    2. [BurstCompile]
    3.     struct QueueToList : IJob
    4.     {
    5.         public NativeQueue<int> queueBucket;
    6.         public NativeList<int> listBucket;
    7.  
    8.         public void Execute()
    9.         {
    10.             while (queueBucket.TryDequeue(out int i))
    11.                 listBucket.Add(i);
    12.         }
    13.     }
    and

    Code (CSharp):
    1.  
    2.  
    3. var handles = new NativeArray<JobHandle>(_buckets.Length, Allocator.Temp);
    4.         for (int i = 0; i < _buckets.Length; i++)
    5.         {
    6.             var job = new QueueToList
    7.             {
    8.                 queueBucket = _buckets[i],
    9.                 listBucket = _listBuckets[i],
    10.             };
    11.             handles[i] = job.Schedule(hashHandle);
    12.         }
    13. var queueToListStageHandle = JobHandle.CombineDependencies(handles);
    14.  
    but then how/where would "handles" even be disposed? I can't dispose it right there and then because queueToListStageHandle is still in use, and CombineDependencies probably doesn't make a copy of the array, or does it?
    Unfortunately no documentation shows up for it either :(
    (and the website doesn't mention anything about copy or not)


    Anyway, the whole concept of having to "convert" one collection into another one feels like a hack :S
     
  6. dadude123

    dadude123

    Joined:
    Feb 26, 2014
    Posts:
    789
    I'm not quite sure what you mean, could you elaborate? The mapping isn't the hard thing I think.
    But how would I get multiple jobs to iterate over that single NativeHashMap?

    Maybe I'm missing something obvious here, but are you saying that there is indeed a simple way where I could run may "narrow phase" collision code on each bucket in the hash map in parallel? (and of course each bucket should also include the entities of the 8 other buckets around it!)


    That is actually a pretty good idea man!
    I do have a lot of entities, but maybe that could work, I'll give it a try :)



    edit:

    I just want to add: Even if unity physics fully solves my problem, I would still really like to learn the correct (dots-)way of implementing my initial approach. (the "hashing positions into buckets" thing)

    It's such a simple algorithm... surely there's a relatively simple dots-solution, right?
     
    Last edited: Jun 5, 2019
  7. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    4,219
    The "correct" approach is always going to be a broadphase algorithm of some sort.

    The Boids sample uses a fixed-grid broadphase using a NativeMultiHashMap. Such a data structure has concurrent write capabilities.

    I know some people opt for a dynamic buffer of entities with dynamic buffers attached to each instead of the NativeMultiHashMap. That resolves dependencies automatically at the cost of making parallelism more challenging.

    The second type of broadphase is "bucketing" which is a small fixed grid with large sorted arrays of data inside of it. It is more conventionally known as multi-box pruning. I use the technique for my CCDE and I implemented it using T4 to generate a struct containing a bunch of NativeLists with 2D indexers into all those NativeLists. You have to manually parse work between threads if you want to build the data structure in parallel, but it is possible.

    Fun fact, PhysX uses multi-box pruning.

    The third type of broadphase is a BVH. Unity.Physics uses this, and with their recent release, their implementation is fast! I'm seeing 10,000 entities built into a BVH in under a millisecond. And distance queries are fast too. If the rest of the Unity.Physics implementation and API don't get in your way, it is the ideal solution to your problem.
     
    andywatts likes this.
  8. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    1,154
    For 2D, i have tested pretty much all variants I could think of for a fixed grid, although a long while back (old API)

    I found the best data structure to be dynamic buffers instead of NMHM. You create one entity per grid and add a dynamic buffer to it.
    Edit: I also put each collider in all overlapping grids, instead of testing the surrounding ones (and using a min grid size)

    In a real project, the best solution depends on many other things (ie static, dynamic, size deltas, density, etc)
     
    dadude123 likes this.
  9. dadude123

    dadude123

    Joined:
    Feb 26, 2014
    Posts:
    789
    That sounds like a really good idea. Straightforward, I like it!
    I will try that today.

    Also, adding each entity to each cell it touches: is there some trick to that to make it more efficient?
    The best I can think of is to calculate the hash of the top-left and bottom-right corner and then only doing the check for the remaining 2 corners if the first two already give different hashes. (only works when we can assume that no entity will be equal or larger than the cell size, but we can definitely go with that assumption for my scenario)


    How do you prevent race conditions though?
    If I iterate over all my entities, hashing their position in a job, and then adding them to the buffer of the correct grid-cell, then two entities might end up adding themselves to the same cell at the same time, no?

    I'd have to add
    [NativeDisableParallelForRestriction]
    , but that doesn't fix the problem, it just suppresses the protection...
     
    Last edited: Jun 7, 2019
  10. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    4,219
    Scale and offset your Entities' AABBs and grid such that the grid spacing is 1 with the left corner set to [0, 0]. Then floor to int your scaled AABB's min and max values and clamp them to the scaled grid dimensions. Now you have min and max indices for your grid that you can loop through and add your entity to. It optimizes really well with Burst if you use the math library and vectorized types.
     
    jdtec likes this.
  11. dadude123

    dadude123

    Joined:
    Feb 26, 2014
    Posts:
    789
    Hmm I'm hesitant about introducing a loop there. However from experience I can definitely agree that burst optimizations are often really good. (actually I've never seen a less than incredible performance increase)

    It would also mean that there will be one less thing to keep in mind regarding maximum entity sizes. I'll give it a try once I've figured out a way to fix my other problem (concurrently appending to DynamicBuffer / IBufferElementData)
     
  12. DreamingImLatios

    DreamingImLatios

    Joined:
    Jun 3, 2017
    Posts:
    4,219
    What's wrong with the loop? Don't you have to put them in the same buckets anyways? The method I provided instantly solves for all buckets an entity belongs inside, which is way faster than calculating the hashes for each corner.

    As for concurrency, the only safe way to do this without some really complicated atomic counters is to have a dynamic buffer per bucket per thread. And then afterwards you would combine all the threads' dynamic buffers associated with the same bucket into a single dynamic buffer. You can calculate the correct dynamic buffer for a given thread using the thread index.
     
  13. sngdan

    sngdan

    Joined:
    Feb 7, 2014
    Posts:
    1,154
    You assign to grid in one thread (not parallel) - don’t fall in the trap to try to make everything parallel - remove sync points and likely the remaining threads will be filled up with something else.

    That being said, you can also lock and write in parallel (requires unsafe) and is in general a bad idea for performance.

    Edit: saw your other post on thread safety...also tried this, but there is no good way to get max threads so you have to take a hard coded value of 128 or so and use thread index. This is in my view all wasted effort, if you stress test an isolated system - maybe. In a game context, avoid sync points and have other system fill up the threads.

    In my experience the alternative with the 8 adjacent cells is worse (but as mentioned before, likely depends on your specific situation, ie density / distribution)

    I can post code if you get stuck but try first...
     
    Last edited: Jun 7, 2019