这是我第一次尝试碰撞算法。我尝试检查具有边界的对象的矩形大小。现在,在这个应用程序中,我制作了运行的子弹并检查是否在无时间延迟的 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)。
最佳答案
首先,您的算法不正确,因为当您使用 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);
}
关于java - 我的碰撞检测在 Java 小程序中生成低帧率,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9079306/