Обнаружение коллизий огромного количества кругов

Если Ваш код зависит от "галочки" (и тестирует, чтобы определить если перекрытие объектов в галочке), то:

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

• , когда несколько объектов сталкиваются в той же галочке, конечный результат (например, как они возвращаются, сколько ущерба они наносят...) зависит от порядка, который Вы проверяете на коллизии а не порядок, что коллизии/должны, происходят. В редких случаях это может заставить игру запираться (например, 3 объекта сталкиваются в той же галочке; object1 и object2 корректируются для их коллизии, затем object2, и object3 корректируются для их коллизии, вызывающей object2 для столкновения с object1 снова, таким образом, коллизия между object1 и object2 должна быть восстановлена, но это заставляет object2 сталкиваться с object3 снова, так...).

Примечание: В теории эта вторая проблема может быть решена "рекурсивным подразделением галочки" (если больше чем 2 объекта сталкиваются, разделяют длину пополам галочки и повторной попытки, пока только 2 объекта не сталкиваются в той "подгалочке"). Это может также заставить игры запираться и/или отказывать (когда 3 или больше объекта сталкиваются в тот же самый момент, Вы заканчиваете с, "рекурсивно вызывают навсегда" сценарий).

, Кроме того; иногда, когда разработчики игр используют "галочки", они также говорят "1 галочку фиксированной длины = 1 / переменная частота кадров", которая абсурдна, потому что что-то, что, как предполагается, является фиксированной длиной, не может зависеть от чего-то переменного (например, когда GPU не удается достигнуть 60 кадров в секунду, все моделирование входит в замедленное воспроизведение); и если они не делают этого и имеют "галочки переменной длины" вместо этого затем, обе из проблем с "галочками" становятся значительно хуже (особенно в низкой частоте кадров), и моделирование становится недетерминированным (который может быть проблематичным для многопользовательского, и может привести к другому поведению, когда плеер сохраняет, загружает или приостанавливает игру).

единственный корректный путь состоит в том, чтобы добавить размер (время) и дать каждому объекту линейный сегмент, описанный как "запуск координат и окончание координат", плюс "траектория после окончания координат". Когда любой объект изменяет свою траекторию (или потому что что-то непредсказанное произошло или потому что это достигло своих "конечных координат"), Вы найдете "как можно скорее" коллизия путем выполнения "расстояния между 2 строками < (object1.radius + object2.radius)" вычисление для объекта, который изменился и любой объект; затем измените "конечные координаты" и "траекторию после окончания координат" для обоих объектов.

внешний "игровой цикл" был бы чем-то как:

    while(running) {
        frame_time = estimate_when_frame_will_be_visible(); // Note: Likely to be many milliseconds after you start drawing the frame
        while(soonest_object_end_time < frame_time) {
              update_path_of_object_with_soonest_end_time();
        }
        for each object {
            calculate_object_position_at_time(frame_time);
        }
        render();
    }

Примечание, что существует несколько способов оптимизировать это, включая:

• разделяет мир на "зоны" - например, так, чтобы, если Вы знаете, object1 прошел бы через зоны 1, и 2 затем он не может столкнуться ни с каким другим объектом, который также не проходит через зону 1, или зона 2

• удерживают объекты "end_time % bucket_size" блоки для уменьшения времени, потраченного, чтобы найти "затем как можно скорее, что время окончания"

• использование несколько потоков делает "calculate_object_position_at_time (frame_time)"; для каждого объекта в параллели

• делают все "моделирование усовершенствования указывает до следующей работы" времени кадра параллельно с "рендерингом ()" (особенно, если большая часть рендеринга сделана GPU, оставив CPU/s свободным).

Для производительности:

• , Когда коллизии нечасто происходят, это может быть значительно быстрее, чем "галочки" (Вы не можете сделать почти никакой работы в течение относительно длительных промежутков времени); и когда у Вас есть свободное время (по любой причине - например, включая то, потому что плеер приостановил игру), можно воспользовавшись ситуацией вычислить далее в будущее (эффективно, "сглаживая" издержки со временем для предотвращения скачков производительности).

• , Когда коллизии часто происходят, это даст Вам корректные результаты, но может быть медленнее, чем поврежденная шутка, которая дает Вам неправильные результаты при тех же условиях.

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

Наконец; также более удобно для многопользовательских сценариев, где Вы не хотите тратить впустую огромную сумму пропускной способности, отправляющей "новое местоположение" за каждым объектом каждому клиенту в каждой галочке.

, Конечно, оборотная сторона является сложностью - как только Вы хотите иметь дело с вещами как ускорение/замедление (сила тяжести, трение, покачнувшееся перемещение), плавные кривые (эллиптические орбиты, шлицы) или объекты различной формы (например, произвольные сетки/полигоны и не сферы/круги) математика, вовлеченная в вычисление, когда как можно скорее коллизия произойдет, становится значительно более твердым и более дорогим; который является, почему разработчики игр обращаются к нижнему подходу "галочек" для моделирований, которые более сложны, чем случай сфер N или кругов с линейным движением.

Какой ответ будет наиболее эффективным, в некоторой степени будет зависеть от плотности кругов. Если плотность низкая, то размещение сетки с низким разрешением на карте и отметка тех элементов сетки, которые содержат круг, вероятно, будет наиболее эффективным.Это займет приблизительно O (N * m * k) на обновление, где N - общее количество кругов, m - среднее количество кругов за точка сетки, а k - среднее количество точек сетки, охватываемых одним кругом. Если один круг перемещает более одной точки сетки за оборот, вам необходимо изменить м , чтобы включить количество перемещаемых точек сетки.

С другой стороны, если плотность чрезвычайно высока, вам лучше попробовать метод обхода графика. Пусть каждый круг содержит всех соседей на расстоянии R ( R > r_i для каждого радиуса круга r_i ). Затем, если вы двигаетесь, вы запрашиваете все круги в «прямом» направлении о соседях, которые у них есть, и берете все, что будет в пределах D; тогда вы забываете все те, которые в обратном направлении находятся дальше, чем D. Теперь полное обновление займет O (N * n ^ 2) , где n - среднее количество круги в радиусе R . Для чего-то вроде близкорасположенной гексагональной решетки это даст вам гораздо лучшие результаты, чем метод сетки, описанный выше.

Одна из возможных техник заключается в использовании триангуляции Делоне в центре ваших кругов.

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

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

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

Существуют структуры данных « пространственный индекс » для хранения ваших кругов для последующего быстрого сравнения; Quadtree, r-tree и kd-tree являются примерами.

Решение 1 похоже на пространственный индекс, а решение 2 выиграет от пространственного индекса каждый раз, когда вы пересчитываете свои пары.

Чтобы усложнить ситуацию, ваши объекты движутся - у них есть скорость.

Использование пространственных индексов для объектов в играх и симуляторах является нормальным, но в основном это касается стационарных объектов и, как правило, объектов, которые не реагируют на столкновение движением.

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

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

Обрисованный вами парный подход звучит многообещающе. Вы можете сохранить пары отсортированными по следующему столкновению и повторно вставить их, когда они столкнулись в соответствующих новых положениях. Вам нужно только отсортировать новый сгенерированный список столкновений (O (n lg n)) для двух объектов, а затем объединить два списка (новые коллизии для каждого объекта и существующий список коллизий; вставка новых коллизий, удаление тех устаревшие коллизии, в которых перечислены два объекта, которые столкнулись), что составляет O (n).

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

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

Как говорит Марк в комментариях, было бы довольно просто распараллелить вычисления.

Вы можете создать 2D-версию «сферического дерева», которое представляет собой особый (и очень простой в реализации) случай «пространственного индекса», который будет предложенный. Идея состоит в том, чтобы «объединить» круги в «содержащий» круг, пока вы не получите единственный круг, который «содержит» «огромное количество кругов».

Просто чтобы показать простоту вычисления «содержащего круга» (верхняя часть моей головы): 1) Добавьте центры двух кругов (как векторы) и масштабируйте на 1 / 2, это центр окружности 2) Вычтите положения центров двух окружностей (как векторы), добавьте радиусы и масштаб на 1/2, то есть радиус окружности

Разделите свое пространство на регионы и ведите список кругов с центром в каждом регионе.

Даже если вы используете очень простую схему, например, поместите все круги в список, отсортированный по centre.x, вы можете значительно ускорить процесс. Чтобы протестировать данный круг, вам нужно всего лишь сравнить его с кругами по обе стороны от него в списке, выходя, пока не дойдете до круга, координата x которого больше радиуса .

Как упомянул Уилл в своем ответе, пространственные деревья разбиения являются обычным решением этой проблемы. Эти алгоритмы иногда требуют некоторой доработки для эффективной обработки движущихся объектов. Вы захотите использовать правило свободной подгонки ведер, чтобы на большинстве шагов перемещения объект не менял ведра.

Я видел, как ваше "решение 1" использовалось для этой проблемы раньше и называлось "хэш столкновений". Оно может хорошо работать, если пространство, с которым вы имеете дело, достаточно мало, чтобы быть управляемым, и вы ожидаете, что ваши объекты будут хотя бы смутно близки к равномерному распределению. Если ваши объекты могут быть сгруппированы, то очевидно, что это создает проблему. Использование гибридного подхода с некоторым типом дерева разделов внутри каждого хэш-бокса может помочь с этим и может преобразовать чисто древовидный подход в нечто, что легче масштабировать параллельно.

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

Предложение - я не разработчик игр

Почему бы не рассчитать заранее, когда столкновение произойдет

, как вы указываете

Мы можем предположить, что объект круга имеет следующие свойства:

-Координаты

] -Радиус

-Скорость

-Направление

Скорость постоянна, но направление может меняться.

Затем, когда направление одного объекта изменится, пересчитайте те пары, которые затронуты. Этот метод эффективен, если направления не меняются слишком часто.