Мое обнаружение столкновений генерирует низкие fps в java-апплете

Question

Это мой первый эксперимент по алгоритму столкновений. Я попытался проверить размер прямоугольника объекта с границей. Теперь, в этом приложении, я запустил пули и проверил, не произошло ли столкновение во время цикла без задержки. Проблема в том, что, когда я создаю около 30-40 пуль, fps становится настолько низким. Я был бы рад, если бы кто-нибудь научил меня надежному способу записи обнаружения столкновений.

Кстати, я использовал ява Коллекция векторных (Может быть итерация не достаточно быстро? Или мой код слишком грязный)

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

Этот вектор магазин объект Пули с (х, у) в нижнем левом углу и (ширина, высота).

Answer 1

remove() - очень дорогостоящая операция, гораздо быстрее будет создавать новый список, копировать в него нужные элементы и заменять исходный список на новый.

Я также рекомендую использовать ArrayList вместо Vector. Если вам нужна синхронизация, оберните ArrayList в Collections.synchronizedList().

Попробуйте это, работает почти мгновенно - < 16 мс (0,016 сек) над 100k элементов:

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

Answer 2

Первый ваш алгоритм неверен, так как при удалении с помощью 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); 

} 

Edit:

Как Замороженный паук отметил, 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); 

}