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

13

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

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

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

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

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), вместо того, чтобы проверять все.

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

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

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

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

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

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

omgnoseat
источник
Что это за язык? Javascript?
Кайл C
2
Actionscript 3, но язык довольно нерелевантный. Просто хочу выяснить, как лучше всего справиться и структурировать это :)
omgnoseat

Ответы:

8

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

Ваш первый алгоритм проверки столкновений без какой-либо оптимизации: сколько проверок он выполнит за один прогон? Если 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) проверок для проверки столкновений каждого объекта.

Стивен
источник
Это очень ясный и понятный awnser, большое спасибо! Как обрабатывается, в каком подпространстве находится объект? Подпространство обрабатывается как объект, где объект на нем сохраняется в виде массивов и проверяется друг против друга? Или вы просто проверяете, какое это подпространство, проверяя X и Y внутри основного цикла? Похоже, что создание и изменение массивов все время довольно неэффективно. Поэтому я хочу быть уверен, что я использую соответствующий метод :) Я также вижу проблему, возникающую, когда объекты различаются по размеру. Я думаю, самое маленькое подпространство должно быть примерно таким же большим, как самый большой объект?
omgnoseat
Я рад помочь :) Подпространство будет объектом, который поддерживает 4 подпространства, которые он содержит. Наименьшее подпространство отличается тем, что оно не содержит больше подпространств, но содержит список ваших объектов. Учитывая стоимость обновления: дерево подпространств строится один раз в начале игры. В каждом цикле основного цикла списки объектов в наименьших подпространствах очищаются и заполняются снова. Так что нужен только список добавления / удаления. Нет необходимости менять массивы. Наименьшее подпространство должно быть достаточно большим, чтобы содержать несколько игровых объектов. Размер зависит от вашей игры и может быть изменен позже.
Стивен
Спасибо, забыл, что мы также будем проверять столкновения между реальными объектами в наименьшем подпространстве, имеет смысл, что теперь он может содержать несколько объектов. Я начал тестирование, и оно идет хорошо. Самая большая проблема, с которой я столкнулся, - это определение, к какому подпространству относится объект. Я продолжаю циклически проходить по подпространствам значений X и Y дочерних элементов, это подходящий метод?
omgnoseat
Как вы обрабатываете объекты, которые простираются в более чем одно подпространство (то есть, чье местоположение находится на границе или вблизи границы)?
Mghicks
Просто: нет. Объекты могут быть частью нескольких подпространств, если они находятся на границе каждого подпространства. Таким образом, один объект может быть частью до 4 подпространств. Но это меньшинство.
Стивен