I have a collision detection method in my android program to detect when two balls have collided and to calculate their new velocities. Every ball is stored in an array Ball[] ballArray. To handle collisions, I iterate through each ball, take it's center coordinates and calculate a surrounding region. If the center of any other ball lies within this region, then I check the two balls for a collision.
My method is basically as follows
public void handleCollisions(){
int size = ballArray.length;
for(int i = 0; i < size; i++){
Ball ball = ballArray[i];
int centerX = ball.centerX;
int centerY = ball.centerY;
int radius = ball.radius;
//calculate box around ball
int lowXLimit = (centerX - radius - largestPossibleRadius);
int highXLimit = (centerX + radius + largestPossibleRadius);
int lowYLimit = (centerY- radius - largestPossibleRadius);
int highYLimit = (centerY+ radius + largestPossibleRadius);
for(int j = j+1; j < size; j++){
Ball ball2 = ballArray[j];
int centerX2 = ball.centerX;
int centerY2 = ball.centerY;
int radius2 = ball.radius;
//if ball2 is inside the possible collision region around ball1
if (centerX2 > lowXLimit && centerX2 < highXLimit && centerY2 > lowYLimit && centerY2 < highYLimit) {
//do calculations to determine new velocities
}
}
I was getting pretty poor performance from my code and ran a traceview. To my surprise, only around 5% of the execution time in this method is spent doing the collision resolution calculations (quite a number of floating point divisions, multiplications). In fact, around 60-70% of time in this method is simply accessing the balls from the ball array (lines Ball ball = ballArray[i] and Ball ball2 = ballArray[j]).
I've tried using an ArrayList but that is even worse. Is there something I can do to speed up this code? perhaps another data structure? It seems like a really long time to me. Should I try reduce the number of member variables in Ball?
There are some points that could be optimized:
You could calculate ball collision with just the radius. Distance between balls = sqrt((x1-x2)^2 + (y1-y2)^2), now if distance between balls < (radius1 + radius2) then they collide.
To calculate that efficiently you should keep distance squared (no sqrt) and compare with (radius1 + radius2)^2. That way might be faster than what you currently do.
If you have n Balls you currently have to do like n^2 comparisons which gets quite a lot for many balls. So that would be a good point to look for optimizations:
There are really advanced "spatial data structures" (google that) that would allow you to compare Balls with less then all Balls (just with balls close enough so it's likely that they collide). The problematic thing with those is that you have to maintain that structure (update it whenever your balls move) which is usually quite a lot of calculations and might end up slower that your approach.
Example: http://www.gamerendering.com/2008/11/17/uniform-grid/ You take a grid with cellsize = the max diameter a ball can have. Whenever you move a ball you update it's position in the grid (that's a quite simple divide by gridwidth). Then you just need to compare a Ball with Balls inside this or directly adjacent cells.
I've tried using an ArrayList but that is even worse. Is there something I can do to speed up this code? perhaps another data structure? It seems like a really long time to me. Should I try reduce the number of member variables in Ball?
There is pretty much nothing you can do by using different classes/members. Your Ball[] array with public members is the most efficient way to do that. The amount of members of Ball should have no effect on the speed.