java - 我的碰撞检测在 Java 小程序中生成低帧率

Question

这是我第一次尝试碰撞算法。我尝试检查具有边界的对象的矩形大小。现在，在这个应用程序中，我制作了运行的子弹并检查是否在无时间延迟的 while 循环中发生碰撞。问题是，当我产生大约 30-40 颗子弹时，fps 变得如此之低。如果有人能教我一种可靠的方法来编写碰撞检测，我会很高兴。

对了，我用了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);
    }
}

此 Vector 存储一个 Bullet 对象，左下角为 (x,y)，(width,height)。

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); 

}