I simply want to implement some sort of grid where I can sort units in an RTS into cells, and then for each unit check to avoid other units and attack other units, in 2d.
My map grid is currently 10 000 x 10 000 cells, with 20+ thousand units. To be specific, my grid is sparse but the units move together in very dense groups of about 300 each (like an ancient army type of formation). So cells will either be extremely dense, or completely empty, no in-between really.
My issue in deciding is that I am using Unity job's system and burst compiler. If you do not know, jobs is a multithreading system, and burst is an LLVM based compiler outputting very fast assembly. The limitations of these systems is you can only use value types. So no classes.
I have looked at using a MultiHashmap, but from what I read this can be very slow because I need to run a hash function for every unit. Then when I want to iterate al units in a cell, this is much slower than iterating an array. Especially, because I will also be checking the 8 neighbour cells for each unit as well. That's a lot of hashing being done. Finally, I have to clear the map every frame. The advantage here is Unity provides a container NativeMultiHashMap which is thread-safe, so I can build and query it in parallel.
I have looked into quad-trees. But quad-tree does not seem suited to multithreading, especially without using references. So if I did this, it would most likely be single threaded.
My question is, are my above statements correct in thought? Is there a faster way to organize my data? If I go with a hashmap, how can I query it most efficiently?