I have recently solved this in a situation where everything is 2d:
The best solution I've found is to combine 2d array of cells and a quadtree that perfectly matches the 2d grid so that each leaf node is also a cell of the 2d array. I will post code once I get back home after work.
The datastructure consists of:
- 2d array that contains cells containing the objects.
- A quadtree where each cell forms a leaf node.
(- A multimap which stores all the objects in iterable form by cell.)
- Fast neighbor finding.
- Fast proximity finding.
- No wasted ascending or descending the tree (ideally only when inserting, removing objects or intersection tests).
- No going through empty cells.
- The game area width in cells must be a power of two.
- Only leaf nodes can contain objects.
- Each object is contained by only one cell even if it intersects multiple cells.
- All objects must be smaller than one cell.
The data structure has:
-addition O(Log n) if added from root node (vs O(n^2) of 2d grid), addition to a cell is O(1);
-remove O(Log n) if removed from a cell, O(n^2) otherwise;
-No ascending the tree when moving objects. In worst case if neighbors aren't found initialization time you have to ascend to root node and then descend back;
-No need to clear the tree and reinsert objects after each update;
-Fast proximity finding O(1) vs ascending and descending of quadtree or complicated initialization algorithms.
-Holding all your game objects in a MultiMap where each cell index(j * size + i) works as a key to the objects eliminates the need to go through a 2d array to update empty cells.
-Using HashSets inside the cells instead of ArrayLists removes the need to copy or move memory when removing objects from leaf nodes (not sure if this happens).
/ \ \ \
/ | | \
Cell Cell Cell cell
Quadtrees alone aren't very good for moving objects. A 2d grid isn't very good for inserting and removing objects at random places. Quadtree is good for deciding whether objects intersect, 2d grid isn't. I am using this for boid movement as well and so far it has been working great.