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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    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. Метод молекулярной динамики очень легко распараллеливать. Вы можете делать это с помощью streamов или даже на GPU. Вы можете рассчитать каждое расстояние в разных streamах. На GPU вы можете легко создавать тысячи streamов практически без затрат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    -Координаты

    -Радиус

    -Скорость

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

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

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

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

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

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

    Давайте будем гением компьютера.