java - 处理冲突 - 数组查找很昂贵

Question

我的 android 程序中有一个碰撞检测方法来检测两个球何时发生碰撞并计算它们的新速度。每个球都存储在数组 Ball[] ballArray 中。为了处理碰撞，我遍历每个球，获取它的中心坐标并计算周围区域。如果任何其他球的中心位于该区域内，那么我将检查这两个球是否发生碰撞。

我的方法基本如下

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
            } 
}

我的代码性能很差并运行了跟踪 View 。令我惊讶的是，此方法中只有大约 5% 的执行时间用于冲突解决计算(相当多的浮点除法、乘法)。事实上，此方法中大约 60-70% 的时间只是从球数组访问球(行 Ball ball = ballArray[i] 和 Ball ball2 = ballArray[j])。

我试过使用 ArrayList 但效果更差。我可以做些什么来加快这段代码的速度吗？也许是另一种数据结构？对我来说似乎真的很长一段时间。我是否应该尝试减少 Ball 中的成员变量数量？

Answer 1

尝试按位置对球进行排序。这可能会减少您需要执行的计算次数，因为您只需要将每个球与附近的其他球进行比较——一旦球太远(至少在您排序的轴上) ) 那么你不需要考虑任何更远的球。