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

Ответ 1

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

Решение 1
Разделите свое пространство на прямоугольные ячейки, которые не перекрываются. Поэтому, когда вы проверяете один круг для столкновения, вы просматриваете все круги внутри ячейки, в которой находится ваш первый круг, и смотрите X-ячейки в каждом направлении. Я пробовал много значений X и обнаружил, что X = 1 является самым быстрым решением. Таким образом, вы должны разделить пространство на размер ячеек в каждом направлении, равном:

Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;

Дивизор должен быть больше 3, иначе он вызовет ошибки (если он слишком мал, вы должны увеличить окно симуляции).
Тогда ваш алгоритм будет выглядеть следующим образом:

• Поместите все круги внутри коробки
• Создайте структуру ячеек и сохраните индексы или указатели на круги внутри ячейки (в массиве или в списке)
• Сделайте шаг во времени (переместите все) и обновите позиции кругов внутри ячеек
• Посмотрите вокруг каждого круга на столкновение. Вы должны проверять одну ячейку во всех направлениях.
• Если есть столкновение - сделайте что-нибудь
• Перейдите к 3.

Если вы напишете его правильно, вы получите что-то о сложности O (N), потому что максимальное количество кругов внутри 9 ячеек (в 2D) или 27 ячеек (в 3D) является постоянным для любое общее количество кругов.

Решение 2
Ususaly это делается следующим образом:

• Для каждого круга создайте список кругов на расстоянии R < R_max, вычислите время, после которого мы должны обновить списки (что-то о T_update = R_max / V_max, где V_max - максимальная текущая скорость)
• Сделайте шаг за шагом
• Проверить расстояние каждого круга с кругами в его списке
• Если есть столкновение - сделайте что-нибудь
• Если текущее время больше, чем T_update, перейдите к 1.
• Осталось перейти на 2.

Это решение со списками очень часто улучшается путем добавления другого списка с R_max_2 > R_max и с его собственным временем истечения T_2. В этом решении этот второй список используется для обновления первого списка. Конечно, после T_2 вам нужно обновить все списки, которые O (N ^ 2). Также будьте осторожны с этими T и T_2 раз, потому что, если столкновение может изменить скорость, тогда эти времена изменились бы. Кроме того, если вы вводите некоторые фокусы в свою систему, это также приведет к изменению скорости.

Решение 1 + 2 Вы можете использовать списки для обнаружения конфликтов и ячейки для обновления списков. В одной книге было написано, что это лучшее решение, но я думаю, что если вы создадите маленькие ячейки (как в моем примере), то лучше решение 1. Но это мое мнение.

Другие вещи
Вы также можете делать другие вещи, чтобы улучшить скорость моделирования:

• Когда вы вычисляете расстояние r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...), вам не нужно выполнять операцию с квадратным корнем. Вы можете сравнить r^2 с некоторым значением - это нормально. Также вам не нужно выполнять все операции (x1-x2)*(x1-x2) (я имею в виду, для всех значений), потому что если x*x больше, чем некоторые r_collision^2, тогда все остальные y*y и т.д., Суммированные, будут больше.
• Метод молекулярной динамики очень легко распараллеливать. Вы можете делать это с помощью потоков или даже на GPU. Вы можете рассчитать каждое расстояние в разных потоках. На GPU вы можете легко создавать тысячи потоков практически без затрат.

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

Ответ 2

Есть " пространственный индекс" структуры данных для хранения ваших кругов для быстрого сравнения позже; Примеры: Quadtree, r-tree и kd-tree.

Решение 1 представляется пространственным индексом, и решение 2 получало бы пользу от пространственного индекса каждый раз, когда вы пересчитываете свои пары.

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

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

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

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

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

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

Ответ 7

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

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

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

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

-координаты

-радиус

-Velocity

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

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

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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

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

Единственный правильный способ - добавить измерение (время) и дать каждому объекту отрезок, описанный как "начальные координаты и конечные координаты", плюс "траектория после конечных координат". Когда какой-либо объект меняет свою траекторию (либо потому, что произошло непредвиденное, либо потому, что он достиг своих "конечных координат"), вы найдете "самое быстрое" коллизия, пройдя "расстояние между двумя линиями" (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);" для каждого объекта параллельно

• выполняйте всю работу "состояние имитации до времени следующего кадра" параллельно с "render()" (особенно, если большая часть рендеринга выполняется с помощью графического процессора, оставляя процессоры свободными).

Для исполнения:

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

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

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

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

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