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

Question

Как лучше всего проверить столкновение огромного количества кругов?
Очень легко обнаружить столкновение между двумя кругами, но если мы проверим каждую комбинацию, то это O (n ² ) , что определенно не является оптимальным решением.

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

• Координаты
• Радиус
• Скорость
• Направление

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

Я предложил два решения, но, может быть, есть и лучшие.

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

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

Ответы на вопросы Марка Байерса

1. Это для игры?
   Это для симуляции, но это также можно рассматривать как игру
2. Хотите ли вы пересчитывать новую позицию каждые n миллисекунд, а также проверять наличие столкновений в это время?
   Да, время между обновлениями постоянно.
3. Хотите узнать время, когда происходит первое / каждое столкновение?
   Нет, я хочу найти каждое столкновение и сделать «что-то», когда это произойдет.
4. Насколько важна точность?
   Это зависит от того, что вы подразумеваете под точностью. Мне нужно обнаружить все столкновения.
5. Это большая проблема, если очень маленькие быстро движущиеся круги могут иногда проходить сквозь друг друга?
   Можно предположить, что скорость настолько мала, что этого не произойдет.

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

Раствор 2
Обычно это делается так:

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

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

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

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

Answer 8

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

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

как вы указали

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

-координата

-радиус

-Velocity

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

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

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