我的碰撞检测在Java小程序中导致帧率低下。

Question

这是我第一次尝试撞击算法。我尝试检查一个对象的矩形大小和边界是否相交。现在，在这个应用程序中，我制作了可以运行的子弹，并使用无延迟循环检查碰撞。问题是，当我产生约30-40颗子弹时，帧率会变得非常低。如果有人能教我编写健壮的碰撞检测方法，我会感激不尽。

顺便说一下，我使用了Java中的Vector集合（可能迭代速度不够快？还是我的代码太混乱了？）。

public void checkBoundary(int width, int height) //width and height of the applet
{
    for(int i = 0; i < vec.size(); i++)
    {
        if(vec.get(i).x + vec.get(i).width <= 0 ||
            vec.get(i).y + vec.get(i).height <= 0 ||
            vec.get(i).x >= width ||
            vec.get(i).y >= height)
            vec.remove(i);
    }
}

这个向量存储了一个子弹对象，其左下角坐标为（x，y），宽度和高度分别为width和height。

- user385261

---

为了更快地获得更好的帮助，请发布一个SSCCE。 - Andrew Thompson

Answer 1

首先，你的算法是不正确的，因为当你使用 vec.remove(i); 来移除元素时，i+1 元素会变成 i 元素，所以你会跳过一个元素。

性能问题来自于最坏情况下每个删除操作的成本都是 O(n)，因为每个后续元素都需要向左移动。尝试这样做：

public void checkBoundary(int width, int height) //width and height of the applet
{
  LinkedList<T> outofbounds = new LinkedList<T>();
  for(int i = 0; i < vec.size(); i++)
  {
    if(vec.get(i).x + vec.get(i).width <= 0 ||
        vec.get(i).y + vec.get(i).height <= 0 ||
        vec.get(i).x >= width ||
        vec.get(i).y >= height)
        outofbounds.add(vec.at(i)); 
  }
  vec.removeAll(outofbounds);

}

编辑：

正如Frozen Spider所指出的那样，removeAll是昂贵的。它的复杂度为O(outofbounds.size()*vec.size())，即O(n^2)。当稍微改变逻辑时，您可以得到一个算法，保证在O(vec.size())内运行。

public void checkBoundary(int width, int height) //width and height of the applet
{
  LinkedList<T> newvec = new LinkedList<T>(); 
  for(int i = 0; i < vec.size(); i++)
  {
    if(vec.get(i).x + vec.get(i).width <= 0 ||
        vec.get(i).y + vec.get(i).height <= 0 ||
        vec.get(i).x >= width ||
        vec.get(i).y >= height)
        continue;

        newvec.add(vec.at(i)); 
  }
  vec.clear();
  // or vec = newvec if there are no others reference sharing the same object as vec
  vec.addAll(newvec); 

}

- UmNyobe

---

"removeAll()" 是一项昂贵的操作：该函数需要25秒来处理10万个元素。 - Alex Abdugafarov

Answer 2

remove()是一项非常昂贵的操作，更快的方法是创建一个新列表，将所需元素复制到其中，并用新列表替换原始列表。

我还建议您使用ArrayList而不是Vector。如果需要同步，请在Collections.synchronizedList()中包装ArrayList。

尝试这个，几乎瞬间就能完成 - 在100k个元素上<16毫秒（0.016秒）：

public static void checkBoundary(int width, int height) // width and height of the applet
{
    int size = vec.size();
    List <YourObjectType> newVec = new ArrayList <YourObjectType>(size);
    for (int i = 0; i < size; i++) {
        YourObjectType element = vec.get(i);
        if (element.x + element.width > 0 && 
            element.y + element.height > 0 &&
            element.x < width && 
            element.y < height) {
                newVec.add(element);
        }
    }
    vec = newVec;
}

- Alex Abdugafarov

---

在Java集合中，ArrayList和Vector有何不同是我主要的困惑之一？顺便说一下，我个人还没有理解“同步”的概念，所以你能帮我澄清一下Java中的同步吗？我认为它仅适用于线程方法... - user385261

“synchronized”方法是一种只能同时由一个线程执行的方法。同步类也是如此，除了它的所有方法都作为一个同步块进行同步。这对于防止一些未定义的行为（称为竞态条件）非常有用。然而，同步意味着成本：与常规方法调用相比，每次调用同步方法都需要更长的时间。因此，如果您不打算在多个线程之间使用同一实例，请尽量避免使用同步。 - Alex Abdugafarov