Столкновение на основе четырех деревьев / сетки - приведение логики в действие

Прежде всего, я только на короткое время писал свою собственную игровую логику, поэтому я прошу прощения, если это может показаться прямым.

Я много читал о квад-деревьях и обнаружении столкновений на основе сетки. Я понимаю логику - в основном не проверяйте на столкновение, если объекты в основном не находятся рядом. Но никогда не упоминается, как на самом деле выполнить это.

У меня есть несколько возможных методов в моей голове, но я не уверен, что лучше

Общий тест на столкновение - без оптимизации

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

хранить соседей (метод 1) Но что, если мы хотим оптимизировать коллизии, чтобы проверять только те объекты, которые находятся рядом. Мы все еще пробегаем все объекты или создаем массив с близкими объектами для проверки?

var objects:Array = new Array();
    var neighbours:Array = new Array();

    for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){

               neighbours.push(objectA, objectB);
              }
        }

    }

    //somewhere else
    for(i:int = 0; i < neighbours.length; i++){
        //only check neighbours

        for(j:int = i + 1; j < neighbours.length; j++){

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }
    }

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

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){
               //they are near - check collision!
               if(objectA.collidesWith(objectB){

               //handle collision logic
              }
            }
        }

    }

Сохранение объектов в данных мозаики (метод 3) Использование системы на основе мозаики позволяет использовать другую опцию; Сохраните объекты, которые находятся на определенной плитке, в самих данных плитки. Проверьте, на какой плитке находится объект, окружающие плитки содержат любые объекты, с которыми он может столкнуться:

var ObjectA;

for(var i:int = 0; i < 4; i ++){
//check 4 surrounding tiles from object A

   if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){
   //check collision!
    if(objectA.collidesWith(surroundingTile.object){

    //handle collision logic
     }

}
}

Я всегда стараюсь смотреть на реальный мир в качестве примера. Если бы я хотел сравнить элементы одного цвета, было бы нелогично проверять каждый элемент целиком, даже если они не соответствуют цвету (метод 2, проверьте каждый элемент). Я бы, вероятно, собрал предметы одного цвета (объекты, которые находятся рядом друг с другом) и проверил бы их (метод 1), вместо того, чтобы проверять все.

Это не подходящее сравнение, поскольку элементы в проверке столкновений постоянно перемещаются, поэтому порядок перепутан. Это меня смущает.

Будет ли эффективнее проверять каждый элемент, тем самым устраняя нагрузку, связанную с продолжением генерации массива соседей.

Или более эффективно найти соседей, таким образом, не обходя так много объектов, чтобы проверить столкновение?

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

Я думал об игре защиты башни, где башня должна обнаруживать объекты, если объекты находятся в пределах досягаемости, прежде чем она стреляет в нее. И, кажется, глупо проверять все предметы, в то время как в некоторых случаях рядом не будет никаких предметов.

Я прошу прощения за длинный пост, всегда возникают проблемы с объяснением себя!

Вам необходимо уменьшить количество фактических проверок столкновений. Да, очевидно, я знаю. Итак, давайте уточним это:

Ваш первый алгоритм проверки столкновений без какой-либо оптимизации: сколько проверок он выполнит за один прогон? Если n - количество объектов, это будет около n * (n-1) проверок. Для многих объектов (> 100) это будет ужасно медленно.

Ваш метод проверки соседей не будет намного быстрее. Если ваши объекты не статичны и много перемещаются, вам нужно будет создавать список соседей для каждого объекта каждый раз в игровом цикле. Это на самом деле хуже, чем в первом алгоритме, поскольку вы делаете n * (n-1) для построения списка соседей, а затем проверяете для каждого объекта, сталкивается ли он с одним из его соседей.

Вам нужно разделить игровое пространство. Допустим, игровое пространство имеет ширину 400х400 пикселей. Вы можете разделить это на 4 подпространства каждое размером 200x200 и проверить для каждого объекта, к какому из подпространств он принадлежит (один объект может находиться внутри более чем одного подпространства). Тогда вам нужно будет только проверить, сталкиваются ли объекты в каждом подпространстве с другим объектом в том же подпространстве.

Таким образом, стоимость времени выполнения будет: n для построения списка из 4 подпространств + (n / 4) * ((n-1) / 4), что намного лучше, чем предыдущие затраты времени выполнения. Это можно сократить, уменьшив подпространства (например, 50x50).

Итак, наш алгоритм теперь выглядит примерно так:

for each (object in objects)
  check into which subspace the object belongs

for each (subspace in subspaces)
  for each (object in subspace)
    check object for collision with other objects in same subspace

Это несколько похоже на вашу идею данных тайла. Но подпространства не должны быть того же размера, что и плитки.

Мы можем сделать последний шаг для дальнейшей оптимизации, используя квадри. Пусть k будет количеством подпространств. Чтобы построить списки объектов space, мы делаем k * n проверок, что приводит к множеству проверок, становится ли ваш игровой мир большим.

Чтобы сократить эту стоимость, мы используем quadtree. Quadtree - это еще один способ разделить наше игровое пространство. Вместо того, чтобы делить наше пространство 400x400 на 64 подпространства 50x50 и проверять для каждого объекта, в каком из 64 подпространств оно находится в настоящее время, игровое пространство делится на 4 подпространства, равные половине размера игрового пространства (200x200), которые, в свою очередь, делятся на меньшие подпространства (100x100), которые в свою очередь снова делятся на 50x50 подпространств. Это наше квадри.

Теперь, если мы хотим узнать, к какому подпространству 50x50 принадлежит объект, мы проверяем, к какому из подпространств 200x200 он принадлежит. Затем мы идем на один уровень глубже в нашем квадродереве и сравниваем с 4 подпространствами 100x100, которые находятся внутри только что найденного подпространства 200x200. Это повторяется до тех пор, пока мы не узнаем, к какому подпространству 50x50 принадлежит объект. Итак, сколько проверок было необходимо сейчас? 4 для каждого уровня квадродерева (помните, что объект может находиться на границе двух подпространств). Таким образом, нам нужно 4 * 3 проверки, чтобы назначить объект правильному подпространству 50x50. Намного лучше, чем 64 проверки.

Таким образом, нашему алгоритму quadtree требуется 4 * 3 * n проверок для построения списков подпространств и затем что-то вроде k * (n / k) проверок для проверки столкновений каждого объекта.