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?

  • \$\begingroup\$ Another angle you may want to consider is whether individual units is the right level of granularity here. You might want to do a coarse evaluation where each logical unit is a whole army. Then once you know which armies are close enough together for their units to interact, do a finer-grained pass on a local grid that spans just the bounds occupied by those armies. \$\endgroup\$ – DMGregory Apr 7 '20 at 14:36
  • \$\begingroup\$ This is an excellent idea, thanks! To be clear, are you suggesting partitioning the armies, and then partitioning the units in a local grid. Or, partitioning the armies, then simply doing an array search on all units in nearby armies? \$\endgroup\$ – Tree3708 Apr 7 '20 at 14:40
  • \$\begingroup\$ You're the expert on which implementations work for your scenario. \$\endgroup\$ – DMGregory Apr 7 '20 at 14:41
  • \$\begingroup\$ Fair enough lol \$\endgroup\$ – Tree3708 Apr 7 '20 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.