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.)

Ideal requirements:

- 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.

Limitations:

- 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.

Further optimization:

-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).

1 2 3 4
| Node / \ \ \ / | | \ 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.

Comments? Improvements?