Лучшая производительность 2D обнаружения столкновений, чем простая проверка каждой пары объектов

Question

Мне нужно, чтобы алгоритм 2D-обнаружения столкновений был масштабируемым, но я боюсь, что это не так. Мой алгоритм делает это:

1. Создан LinkedList объектов спрайта (который включает в себя все их данные)

   private LinkedList<Sprite> collisionSpritesList = new LinkedList<Sprite>();

2. Затем основной игровой цикл добавляет все спрайты в LinkedList:

   public void GameUpdate() { collisionSpritesList.add(avatar); collisionSpritesList.add(enemy1); collisionSpritesList.add(enemy2); }

3. Затем вызывается метод collisionCheck(); он циклически перебирает все пары объектов в списке в поисках коллизии. Затем LinkedList полностью стирается. Это потому, что сущности должны быть обновлены с их новыми местоположениями.

public boolean checkCollision () {

for(int i = 0; i < collisionSpritesList.size(); i++)
{


for(int j = 0; j < collisionSpritesList.size(); j++)
 {
if(i != j)
 {
     if(collisionSpritesList.get(i).getRectangle().intersects(collisionSpritesList.get(j).getRectangle()))
     {
        Point p = gridMap.getRandomWalkableLocation();
        collisionSpritesList.get(j).setLocation(p.x * gridMap.getCellSize(), p.y * gridMap.getCellSize());
        collisionSpritesList.clear();
        return true;
     }
  }

} }

  collisionSpritesList.clear();
    return false;
}

Мой вопрос: насколько эффективен этот способ проверки столкновения? Должно ли это быть сделано по-другому? Если да, то какие методы являются масштабируемыми?

Answer 1

Я хотел бы рассмотреть возможность использования QuadTree для разделения вашего пространства, а затем проверять только столкновения в спрайтах, которые находятся в тех же «корзинах» или пространстве.

Answer 2

Сохраняйте отсортированный список (отсортированный по одной из осей) и прибавляйте его каждый цикл с помощью пузырьковой сортировки, которая будет масштабироваться до O (n * x) с x средней величиной движения в каждом цикле.

, а затем используйте алгоритм развертки, который имеет O (n * k) с k средним перекрытием по оси сортировки

(список отсортирован по minX здесь)

for(int i = 0; i < collisionSpritesList.size(); i++)
{
  for(int j = i+1; j < collisionSpritesList.size(); j++)
   {
     if(collisionSpritesList.get(j).getRectangle().minX()>collisionSpritesList.get(i).getRectangle().maxX())
         break;//breakout inner for when no overlap on x-axis possible

     if(collisionSpritesList.get(i).getRectangle().intersects(collisionSpritesList.get(j).getRectangle()))
      {
        Point p = gridMap.getRandomWalkableLocation();
        collisionSpritesList.get(j).setLocation(p.x * gridMap.getCellSize(), p.y * gridMap.getCellSize());
        return true;
      }
  }
}

Answer 3

Если вы можете разделить свои спрайты в структуре данных, которая учитывает их положение, то вы можете ограничить число тестов на столкновение, которые вам нужно выполнить.

Одна используемая структура данных называется четырехугольным деревом,В следующем разделе описывается, как использовать обнаружение столкновений в сочетании с квадродеревом:

http://lab.polygonal.de/2007/09/09/quadtree-demonstration/