Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  NeuroFuzzy Mar 13 '12 at 22:07
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.