# improving speed of 2d ball collision

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.

• Did you try 9 squares instead of four? – ashes999 Mar 13 '12 at 3:32
• Some more implementation details would be helpful. How do you add the balls to the grid? Do you go for(x=0 to gridnum,y=0 to gridnum) if (ballIsInGrid(x,y)) addBallToGrid()? With a naive method like that speed would suffer. How many squares do you have? I know someone that did the exact same thing you're doing but with 10,000 particles or so, and it could run in real time, so i dont think your problem is with the theory. – user10968 Mar 13 '12 at 22:07