进程中的java循环冲突优化

Question

我创建一个project，在其中我操纵球。我有些问题不知道怎么解决。我正在使用处理

在我的项目中，圆圈相互碰撞。在这一点上，为了检查对象是否相互碰撞，我检查了所有对象，这是非常欠优化的。我想通过创建一个NetForCircu类来改进这一点，在这个类中，我将对象放在一起，只比较那些靠得很近的对象。我的主要问题是，如果圆在网格的不同部分有一个中心，那么将对象插入网格是不起作用的。另外，如果窗口大小改变，我不知道如何更改网格大小

void checkForCollision()
{
  for (int i = 0; i<cir.size() -1; i++)
  {
    for (int j = i + 1; j<cir.size(); j++)
    {
      //calculating distance between object
      PVector lengthFrom_i_to_j= PVector.sub( cir.get(j).point, cir.get(i).point);
      float oldDist = lengthFrom_i_to_j.mag();
      float min_dyst = cir.get(j).radius + cir.get(i).radius;
      //checking for collision
      if (oldDist <= min_dyst)
      {    
        collision(cir.get(i), cir.get(j), oldDist, min_dyst, lengthFrom_i_to_j);
      }
    }
  }
}

void collision(Circum con1, Circum con2, float dist_, float min_, PVector lock)
{
  float u1, u2, distance = dist_, min_dyst = min_;

  //static collision
  float distanceCorrection = (min_dyst-distance)/2.0;
  PVector correctionVector = lock.normalize().mult(distanceCorrection);
  con2.point.add(correctionVector);
  con1.point.sub(correctionVector);

  //dynamic collision

  // Defining the X axis
  PVector dirX = lock.copy();
  dirX.normalize();
  // Defining the Y axis
  PVector dirY = new PVector(dirX.y, -dirX.x);

  // X coordinates of velocities
  float vx1 = dirX.dot(con1.velocity);
  float vx2 = dirX.dot(con2.velocity);
  // Y coordinates of velocities
  float vy1 = dirY.dot(con1.velocity);
  float vy2 = dirY.dot(con2.velocity);

  // Applying the collision to X coordinates
  u1 = (2 * vx2 * con2.mass + vx1 * (con1.mass - con2.mass)) / (con1.mass + con2.mass);
  u2 = (2 * vx1 * con1.mass + vx2 * (con2.mass - con1.mass)) / (con1.mass + con2.mass);

  // Turning velocities back into vectors
  PVector vel1 = PVector.mult(dirX, u1);
  PVector vel2 = PVector.mult(dirX, u2);
  vel1.add(PVector.mult(dirY, vy1));
  vel2.add(PVector.mult(dirY, vy2));

  con1.velocity = vel1;
  con2.velocity = vel2;
}

class NetForCircum {
  int cell = 8;
  PVector size = new PVector(0, 0);
  IntList[][] objectsInCell = new IntList[cell][cell];


  NetForCircum(ArrayList<Circum> cir)
  {
    size.x = width/cell;
    size.y = height/cell;

    for (int i = 0; i<cell; i++)
    {
      for (int j = 0; j<cell; j++)
      {
        objectsInCell[i][j] = new IntList();
      }
    }

    for (int i = 0; i<cir.size() - 1; i++)
    {
      float pozLeft = cir.get(i).point.x - cir.get(i).radius, pozRight = cir.get(i).point.x + cir.get(i).radius, pozUp = cir.get(i).point.y - cir.get(i).radius, pozDown = cir.get(i).point.y + cir.get(i).radius;

      for (int j = 1; j<=cell; j++)
      {
        for (int k = 1; k<=cell; k++)
        {

          float curentSizeX = size.x * j, curentSizeY = size.y * k, previousSizeX = size.x * (j - 1), previousSizeY = size.y * (k - 1);

          if ((pozLeft>previousSizeX && pozRight<curentSizeX && pozUp>previousSizeY && pozDown<curentSizeY) || (cir.get(i).point.x>previousSizeX && cir.get(i).point.x<curentSizeX && cir.get(i).point.y>previousSizeY && cir.get(i).point.y<curentSizeY))  
          {
            cir.get(i).cellNumber.add(new PVector(j, k));
            cir.get(i).cellBorderX.set(previousSizeX, curentSizeX);
            cir.get(i).cellBorderY.set(previousSizeY, curentSizeY);
            objectsInCell[j-1][k-1].append(i);
          } 
         }
        }
       }
      }
     }

Answer 1

除了@rabbi76的优秀答案之外，我可以建议避免两次循环（例如，检查I和j，然后检查j和I）：

void checkForCollision()
{
  final int numCircles = cir.size();
  
  for(int i = 0; i < numCircles - 1; i++)
  {
    
    Circum circumI = cir.get(i);
    
    for(int j = i + 1; j < numCircles; j++)
    {
     
      Circum circumJ = cir.get(j);
      
      float dx = circumJ.point.x - circumI.point.x;
      float dy = circumJ.point.y - circumI.point.y;
      float distanceSquared = ((dx * dx) + (dy * dy));
      float radii = circumJ.radius + circumI.radius;
      float thresholdDistanceSquared = radii * radii;
      
      if(distanceSquared < thresholdDistanceSquared){
        //collision(circumI, circumJ, ...)
      }
      
      
    }
    
  } 
  
}

我很久以前就从actionscript中的Keith Peter's Making Things Move中学到了这一点，在那里，每一点性能都很重要。还要注意对象属性如何只被访问一次并缓存到局部变量中以供重用。这是另一个习惯，因为访问actionscript（或javascript）虚拟机中的嵌套数据（getter）代价高昂。Java虚拟机可能效率更高一些，这可能不是必需的

我还强烈要求将优化放在最后，并使用VisualVM等分析工具来确定要优化的内容。你所指出的是一个很好的候选人，但可能还有其他地方需要研究。从最慢的开始，剩下的你可能需要触摸

例如，基于pastebin代码，圆和线的渲染看起来有点慢。您可以研究使用PShape/createShape(ELLIPSE)和处理>；示例>；演示>；性能

Answer 2

一种廉价的优化方法是比较距离的平方，而不是距离。为了计算Euclidean distance，需要平方根：

distance = sqrt( (x2-x1) ^ 2 + (y2-y1) ^ 2 )

即使对于今天的计算机来说，计算平方根也是非常昂贵的。对于距离的平方，不需要平方根：

distance_square = (x2-x1) ^ 2 + (y2-y1) ^ 2

使用^{}而不是^{}，并将其与min_dyst*min_dyst而不是min_dyst进行比较：

PVector lengthFrom_i_to_j= PVector.sub( cir.get(j).point, cir.get(i).point);

// Calculates the magnitude (length) of the vector, squared.
float oldDistSq = lengthFrom_i_to_j.magSq();

float min_dyst = cir.get(j).radius + cir.get(i).radius;

// Compare squared distances
if (oldDistSq <= min_dyst * min_dyst) { 
    // [...]
}