Мое обнаружение столкновений генерирует низкий fps в Java-апплете - PullRequest
Новая
       1

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

3 голосов
/ 31 января 2012

Я впервые экспериментирую с алгоритмом столкновения. Я попытался проверить размер прямоугольника объекта с границей. Теперь в этом приложении я запустил пули и проверил, нет ли столкновения без задержки во время цикла. Проблема в том, что, когда я появляюсь около 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);
    }
}

В этом векторе хранится объект Bullet с (x, y) в левом нижнем углу и (ширина, высота).

Ответы [ 2 ]

2 голосов
/ 31 января 2012

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

}

Редактировать:

Как указано Ледяной паук , 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); 

}
1 голос
/ 31 января 2012

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

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

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

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