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

在我的android程序中，我有一种碰撞检测方法来检测两个球何时碰撞，并计算它们的新速度。每个球都存储在一个数组中。为了处理碰撞，我迭代每个球，取它的中心坐标并计算一个周围区域。如果其他球的中心在这个区域内，那么我检查两个球是否发生碰撞。
我的方法基本如下

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

我的代码性能很差，运行了一个traceview。令我惊讶的是，在这个方法中，只有大约5%的执行时间用于计算冲突解决率（相当多的浮点除法和乘法）。事实上，在这种方法中，大约60-70%的时间只是从球阵列（linesBall[] ballArray和Ball ball = ballArray[i]）访问球。
我试过使用Ball ball2 = ballArray[j]但那更糟。我能做些什么来加速这段代码吗？或许是另一种数据结构？对我来说好像很长时间了。我是否应该尝试减少ArrayList中的成员变量数？

最佳答案

有一些点可以优化：
你可以用半径来计算球的碰撞。球之间的距离=sqrt（（x1-x2）^2+（y1-y2）^2），现在如果球之间的距离要有效地计算，您应该保持距离平方（无平方比），并与（半径1+半径2）^2进行比较。这样做可能比你现在做的要快。
如果你有n个球，你现在必须做n^2比较，这对很多球来说是非常多的。所以这是一个寻找优化的好方法：
有非常先进的“空间数据结构”（google），可以让你将球与比所有球都少的球进行比较（只是球离得足够近，所以很可能会发生碰撞）。有问题的是，你必须保持这种结构（当你的球移动时更新它），这通常是相当多的计算，可能会比你的方法慢。
示例：http://www.gamerendering.com/2008/11/17/uniform-grid/
你需要一个网格，其中cellsize=一个球的最大直径。每当你移动一个球，你就更新它在网格中的位置（这是一个很简单的除以网格宽度的方法）。然后你只需要把球和这个或直接相邻的细胞内的球进行比较。
我试过使用arraylist，但那更糟。我能做些什么来加速这段代码吗？或许是另一种数据结构？对我来说好像很长时间了。我应该试着减少ball中成员变量的数量吗？
使用不同的类/成员几乎无能为力。您的带有公共成员的ball[]数组是最有效的方法。球的杆数对速度没有影响。