improving speed of 2d ball collision

Question

I am making a game which has many balls bouncing around the screen (around 200-300 balls in a small area). One thing I am trying to do is improve the performance of the collision detection and resolution.

What I've tried to do so far is to maintain a large number of ArrayLists. I split the screen up into a grid and for each cell I keep an ArrayList containing each ball that is currently inside that particular grid square. Whenever I update the positions of the balls, I also update which list they belong to.

When checking for collisions, I have a separate ArrayList which contains all the balls. I iterate through this list, and for each ball:

• find out what grid square it is in
• check for collisions with all the balls in adjacent grid squares

I've tested this approach and it doesn't seem any different to just iterating over a list of all the bubbles twice.

Does anyone have some suggestions on how I can improve things? For instance, with my current algorithm I am handling collisions twice but I'm unsure how I can work around it.

Answer 1

It sounds like you're halfway to a Quadtree, which I think could help speed things up.

The basic idea is this: Instead of having a fixed number of cells in which these balls can reside, you have a node which subdivides itself into exactly four nodes if there are more than two balls residing in it. Repeat this process until each node has two or fewer balls in it, and then you only have to check the pairs in each node for collisions, rather than checking each ball against a larger potential set of colliders.