For a system to sort units into cells on a 2d grid based on their positions, so that each unit can check and avoid all other units nearby.
My first thought was NativeMultiHashMap where key = grid position, and values are the entities. But on testing, it seems kinda slow. I was thinking I can represent grid cells with entities and dynamic buffers. I can sort the entities into the buffers each frame. However, I don’t know if Dynamic Buffers are the same as arrays/lists under the hood.
Or, what about once for each key (cell) in the map, iterating all values and adding them to a temp list, than doing the nearby units check with that list?
I’d be interested in the fastest possible spatial partitioning approach. Check out the boids examples from Mike Acton. I’m not sure if it’s possible to go faster than the NativeMultiHashMap. If it is possible let me know, I would want to try it out.
Hi. I checked Boids but it does not work for my use-case; unit-avoidance. In the Boids demo, each key in the map is iterated only once as the boids work on an average of all values of other boids in each cell. This way, the example simply need to iterate each key once to sum it’s value into an array. However, my understanding of the demo is not complete.
I need to check every unit in each cell for every unit in each cell. This means I would need to iterate each key (n) times. That is alot of hash function running, especially for thousands of units.
I did try the HashMap. For 20 thousand units, it is about 3x faster than iterating over an array of all units for all units, but its not fast enough.
I am looking up quad trees and I think this is much better for performance. I’ll post an implementation when I can. I think HashMap can work in many cases, but it depends on how many checks you are doing. HashMap lookup is theoretically O(1), but each lookup runs a mathematical function to get said value.
The most performant would be a 2d-grid (arrays), but memory usage will spiral out of control if you have a map lets say 10 thousand x 10 thousand. If you map is much smaller, 2d arrays are perfect.
The eighth post links to a NativeQuadTree. Its fast, but it has limitations as the nature of a quadtree is kinda against multithreading. Also quad-trees seem more suited to static objects rather than thousands of moving ones. It seems HashMap is still the best option.
I have done this when ECS came out and the fastest at this time was the Entity (key) - > Dynamic Buffer approach. A lot has changed since then but I would still think it is the case. NMHM was (is?) slow to clear when you have lots of entities.
I found something called FixedList. Its an umanaged array allocated on the stack, so it perfect for the cahce we spoke about. So far, its very fast to use a hashmap and this stack list.
The key here is I have 8 hashmaps. For 8 frames the system writes to and reads each consecutive map. On the eight frame, the system does nothing but clear all the maps. This is not noticeable in my game. Also, I squeezed in find closest enemy on this frame, because the clearing of the maps is faster than the writing and reading, so I had a little space.
I insert each unit into only one bucket. While doing this, I calculate the hash on the neighbour cell the unit is nearest to, and store this key with the entity (a component). Then when I read the map, I check all units in the cell and the neighbour cell from said key.
My game can have over 70 thousand units on the battlefield, and this method gives me epic performance and is accurate enough. All with collision detection and find nearest enemy, and follow path.
I get 90 fps for 42 thousand units, and 55-60 fps at 72 thousand. On Dell Inspiron with old 4 core AMDCPU. Write to and read from map takes about 4 ms with 42 thousand units, in parallel of course.
The hashmap gets slow when it gets very large, so thats why I only have one insertion per unit, and the unit just stores the key of the nearest neighbour cell. The Dynamic Buffer approach in my case was slower. Clearing the buffers took 4 times longer than the hashmap, and used alot of memory.
The only way to go faster I think is to use a similar approach to high end physics engines, but I don’t have the time for need for that.
NativeMuiltiHashMap and NativeHashMap uses underlying UnsafeHashMapData.
which stores data by write order. And if ParallelWriter is involved the case would be even more complex.
No matter what, the internal key/value array is store in somehow “Random Order”.
So when you iterator a large HashMap by key. It could involve heavy Paging in memory.
If you just want to put some data in Grid. it would be better to Make a
public struct Grid2D : ISharedComponentData, IEquatable<Grid2D>
{
public int2 Location;
public bool Equals(Grid2D other) => throw new NotImplementedException();
}
Add and change this SCD on Entity
And Query Grid by adding SharedComponentFilter to your query.
then use IJobChunk to work on entities
Advantage:
Chuck elements are sequential by design
Chuck query time is O(0), and SCD filter Time is (O(n))
Disadvantage:
Grid could span over multiple Chunks
In that case use EntityQuery.GetArchetypeChunkIterator. to get ChunkIterator
and Use LambdaJob or IJob to iterate over chunks
Thanks for your post! My concern is this. If I make a grid, the cells will either be completely empty, or very dense. This is because my units move in tight formations. So, unless I make by grid cells very small (2x2m), each unit could be checking against over a thousand others. If I make my grid cells small, the memory would be very big because my maps are huge.
This is why I picked hashmap, as it only stores populated cells.
I did find a solution in my prev post, unless you are replying to that?
EntityManager.GetAllUniqueSharedComponentData will give you all Grid with data.
Those “Grid” that not used by any Chunk will be removed. And Empty Chunks will be Removed too.
So you will always iterate over Grids With Units in it by using SCD.
In this case, SCD is clearly better than NativeHashMap.
Ok, so are you saying that each unit will have a SCD? Doesn’t changing the SCD of an entity move it to a new chunk? Would this add alot of overhead if tens of thousands of entities were changing chunks every frame?