Структуры пространственных данных для движущихся объектов?

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

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

Конечно, вам нужно будет отслеживать ЦЕНТР вашего объекта; и в идеале вы хотите, чтобы каждый объект был жестким, чтобы избежать необходимости пересчета размеров ограничивающей сферы (хотя пересчет не особенно сложен, особенно если вы используете дерево жестких объектов, каждый со своей ограничивающей сферой для объектов, которые нежесткие, но все усложняется).

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

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

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

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

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

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

Есть несколько приемов, которые вы должны использовать со структурой октодерева:

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

2) Также в каждом узле - и, вероятно, на каждом уровне иерархии - вы сохраняете ссылки на соседей узла. Это потребует большого количества дополнительного кода, но позволит вам перемещать элементы между узлами за время, близкое к O (1), а не за время O (2logn).

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

Некоторые другие идеи, которые вы, возможно, захотите попробовать вместо октодерева, - это использовать kd-tree (я считаю, что это правильное имя) или использовать AABB для построения структуры снизу вверх.

Деревья KD (из памяти) разделяют пространство с помощью выровненных по оси плоскостей, поэтому они хорошо подходят для использования с AABB.

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

(Прошло много времени с тех пор, как я занимался программированием разработки пространственных игр.)

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

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

3. Всегда упрощайте любую форму, которую вы тестируете, с помощью чего-то вроде ограничительной рамки, выровненной по оси. Первоначальный тест на столкновение

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

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

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

7. Я знаю больше, но не могу придумать ни одного из них. Давно не делал этого.

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

развернуть и отсечь широкую фазу + узкую фазу gjk

RDC может быть полезен, особенно если ваши объекты редкие (мало пересечений).