# Space partitioning when everything is moving

Background

Together with a friend I'm working on a 2D game that is set in space. To make it as immersive and interactive as possible we want there to be thousands of objects freely floating around, some clustered together, others adrift in empty space.

Challenge

To unburden the rendering and physics engine we need to implement some sort of spatial partitioning. There are two challenges we have to overcome. The first challenge is that everything is moving so reconstructing/updating the data structure has to be extremely cheap since it will have to be done every frame. The second challenge is the distribution of objects, as said before there might be clusters of objects together and vast bits of empty space and to make it even worse there is no boundary to space.

Existing technologies

I've looked at existing techniques like BSP-Trees, QuadTrees, kd-Trees and even R-Trees but as far as I can tell these data structures aren't a perfect fit since updating a lot of objects that have moved to other cells is relatively expensive.

What I've tried

I made the decision that I need a data structure that is more geared toward rapid insertion/update than on giving back the least amount of possible hits given a query. For that purpose I made the cells implicit so each object, given it's position, can calculate in which cell(s) it should be. Then I use a HashMap that maps cell-coordinates to an ArrayList (the contents of the cell). This works fairly well since there is no memory lost on 'empty' cells and its easy to calculate which cells to inspect. However creating all those ArrayLists (worst case N) is expensive and so is growing the HashMap a lot of times (although that is slightly mitigated by giving it a large initial capacity).

Problem

OK so this works but still isn't very fast. Now I can try to micro-optimize the JAVA code. However I'm not expecting too much of that since the profiler tells me that most time is spent in creating all those objects that I use to store the cells. I'm hoping that there are some other tricks/algorithms out there that make this a lot faster so here is what my ideal data structure looks like:

• The number one priority is fast updating/reconstructing of the entire data structure
• Its less important to finely divide the objects into equally sized bins, we can draw a few extra objects and do a few extra collision checks if that means that updating is a little bit faster
• Memory is not really important (PC game)
• "[...] it will have to be done every frame." Why? Can't you predict if a object will leave their cell in the near future? – API-Beast Nov 23 '12 at 11:26
• Can't you skip updating objects that are very far away from the player? Or at least update them significantly less often? – Liosan Nov 23 '12 at 11:41
• @Mr.Beast and Liosan, those two ideas combined could work but objects will have to be able to figure out themselves if something significant happened (like rapid speed increase) etc... Do you got any examples of this idea being used? – Roy T. Nov 23 '12 at 11:53
• The profiler tells you that most time is spent creating the ArrayList or initializing the contained objects? Couldn't you preallocated and pool these objects? – Fabien Nov 23 '12 at 16:27
• @Fabien indeed allocating and growing the ArrayList is the biggest problem, pooling could be a solution. I wonder if I can figure out by trial and error how big the pool should be and how big the arraylists in the pool should be. – Roy T. Nov 26 '12 at 9:50

The technique you are using is very similar to a computational physics technique called molecular dynamics, where the trajectories of atoms (usually now in the 100k to 10M particle range) are followed with very small time steps. The main problem is that to figure the force on one particle, you have to compare its position to the position of every other particle, which scales very poorly (n squared).

There are a trick I can suggest, which requires you to pick a maximum distance that things can interact. As a starting point, I'd start with something like 1/10 of the long dimension of your space, and adjust to taste (longer cutoff means more accurate, but more calculations).

The method is to loop through every particle (i). (I) gets an array where all the particles in range of i are added to the array. What you get in the end is a 2d array, where the ith entry is an array of the particle in range of i. To calculate the forces for i, you only have to check the entries in i's array.

The art of this method is picking the cutoff distance, and the extra padding (eg 20%). The speed gain is that you only have to check a few interactions for each particle, and you recalculate neighbors only every several steps. I'd suggest picking a somewhat fast speed, and figure out how many time steps it would take to cross the "padding" region. Making the padding larger (50% or even 100% of the cutoff) gives you more steps between neighbor recalculating, but makes each step a bit slower. The balancing of this is a tradeoff.

One other trick in calculating the distances is to work with d^2 instead of d, removing a bunch of calls to pow() and sqrt().

Edit: Hard to find a ref link that isn't super technical. This is the only one I could find.

• That sounds like a promising idea, I'm gonna look in to that for sure! – Roy T. Dec 11 '12 at 9:03

Your own solution sounds pretty good if you can achieve building the data structure in o(n) then I would say the optimisation must be done on the choice of data structure rather than on the algorithm.

I have a similar implementation with some differences : The main data structure is an fixed-size array (like ArrayList) which is the best for direct access to an element. Each cell of the array contains a linked list, which is the best for insertions and as good as array list to loop into. We'll need later to delete elements from the linked list, so to make this operation very fast an idea is to store in each element of the list an iterator that points to itself (you said memory is not a problem, right?)

For initialisation, each "particle" is inserted at the end of the linked list that corresponds to the cell in the array that matches its position in space, assuming that the space is partitioned in fixed-size tiles. So we're still with o(n) complexity, but we optimize the whole thing by using containers more fitted to the use.

Each "particle" has a reference to its containing linked list to provide fast access to its neighbours.

At each frame we can make the interaction between each particle with its list of neighbours, and I would say also with the 8 surrounding tiles to avoid treshold effects near tile borders.

There's no need to recalculate the whole partitioning at each frame ; we only need to remove and put again an item when it moves more than a given distance or, by security, every X frames. An idea could be to store the position of each item at the moment when it was inserted in a linked list, and at each frame compare the current position with the old one.

• PS: see also en.wikipedia.org/wiki/Cell_lists – Joel Mar 1 '13 at 10:07
• I used something similar to this in calculating data based on simulated atom positions. It sped up a calculation that took hours/days and turned it into minutes. It is a bit complicated to setup. – Brian Broom Oct 11 '13 at 16:28