   Good data structure for large number of units?
  So, I've been thinking about a data structure to hold all the units in my game.  The overriding prerogative is O(1) checking to see if an enemy unit is right next to a particular unit.The first idea I had was a sparse-array, which works great except for diagonals/anything other than straight ahead/behind/left/right.  The second was an oct-tree like those used in FPS's except that isn't really O(1), more like O(nlog(n)).  The third idea I had was cutting up the battlefield into logical NxN blocks.  A unit marks it's particular block as occupied, and keeps track of which block it is currently in.  Checking if a neighboring (or any other block) is occupied is O(1)... but for large maps this can be rather memory intensive (hence sparse array idea)The fourth idea is number 3.  Except instead of using a 2d array for the map, use a dictionary keyed to logical coordinates, there being no value for empty blocks, thus saving a ton of memory.  Any suggestions?  I'll be going with number 4 unless someone has a better idea.   
Quote:Original post by luke2So, I've been thinking about a data structure to hold all the units in my game.  The overriding prerogative is O(1) checking to see if an enemy unit is right next to a particular unit.The first idea I had was a sparse-array, which works great except for diagonals/anything other than straight ahead/behind/left/right.  The second was an oct-tree like those used in FPS's except that isn't really O(1), more like O(nlog(n)).  The third idea I had was cutting up the battlefield into logical NxN blocks.  A unit marks it's particular block as occupied, and keeps track of which block it is currently in.  Checking if a neighboring (or any other block) is occupied is O(1)... but for large maps this can be rather memory intensive (hence sparse array idea)The fourth idea is number 3.  Except instead of using a 2d array for the map, use a dictionary keyed to logical coordinates, there being no value for empty blocks, thus saving a ton of memory.  Any suggestions?  I'll be going with number 4 unless someone has a better idea.I would suggest to use either an oct-tree (access is more like O(log n)) or sweep-and-prune. If your units are moving around a lot I would go for sweep'n'prune. You can access units in a certain area (box or sphere) in O(log n).;Quote:Original post by Ashaman73I would suggest to use either an oct-tree (access is more like O(log n)) or sweep-and-prune. If your units are moving around a lot I would go for sweep'n'prune. You can access units in a certain area (box or sphere) in O(log n).++sweep-and-prune. It's effective and simple to implement. It's usually presented in 2D, but you can easily extend it to 3D by performing the test on two axes and intersecting the resulting sets.   ;  wow, sure which I heard of s&p before now...With a little culling, I think that will actually be suitable for my needs!  Thanks   ;  Also, it sounds like you may be trying to optimize prematurely. That's generally a bad idea; best to profile your code and see where the slowdowns actually are.   ;  Get it working first...then optimise.Works every time.com   ;  Look into spatial hashing, where a position in 3D space maps to some bucket in a hash table, effectively creating an infinite grid in finite space requirements.A possible hash function could be:Hash = (large prime 1)*(x/gridsize) + (large prime 2)*(y/gridsize) + (large prime 3)*(z/gridsize)You then take this value modulo the hash table size to get the hash table bucket to search. You then perform a simple O(n) search for any unit within some threshold distance (which must be less than half the grid size for accurate results) in the bucket. This scheme is relatively easy to implement (versus an octree, sweep and prune), and has potentially O(1) average-case performance, whereas the others are all O(log(n)).The idea is that objects that are in the same grid cell will always map to the same hash table bucket (though there will be collisions). Thus, with the right grid size, any objects that are near to another can be determined with a simple linear search through the bucket.This doesn't take into account differing object sizes (this scheme models all objects as points), though it works fine for the scenario you described. If you were to use this for something like collision detection, a more complex scheme with multi-level hash table grid sizes is necessary to account for varying object sizes. In that case you add another dimension to the hash function (w for grid level, where the grid level is the closest grid size to the object in question).   