My collision detection generates low fps in java applet

Question

This is my first time experimenting on collision algorithm. I tried checking the rect size of an object with the boundary. Now, in this application, I made running bullets and check if the collision in a no time-delay while loop. The problem is, as I spawn around 30-40 bullets, the fps gets so low. I would be glad if someone could teach me a robust way to write collision detection.

By the way, I used a java Vector collection (Maybe the iteration is not fast enough? or my code is being too messy)

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

This Vector store an object of Bullet with (x,y) as bottom-left corner, and (width,height).

Answer 1

First your algorithm is incorrect because when you remove using vec.remove(i);, the i+1 element become the i element, so you skip one element.

The performance issue come from the fact that on worst case each remove cost O(n), as each subsequent element need to be shifted left. try this:

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

}

Edit:

As Frozen Spider pointed out, removeAll is expensive. It has a complexity of O(outofbounds.size()*vec.size()), which is O(n^2). When slightly changing the logic you can derive an algorithm which is guaranteed to work in 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); 

}

Answer 2

remove() is a very costly operation, much faster will be to create new list, copy desired elements into it and replace original list with new one.

I also recommend you to use ArrayList instead of Vector. If you need synchronization, wrap ArrayList in Collections.synchronizedList().

Try this, works almost instantly - <16 ms (0.016 sec) over 100k elements:

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