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.