Столкновение объектов (collision detection)

(С) Андрей Радченко, 2000.

Добрый день!

Вот решился предложить вам статью по collision detection.
Если понравиться, можете выложить у себя на сайте.
Успехов.
Андрей.

Столкновение объектов (colission detection).
Алгоритм уменьшения размерности пространства.

Алгоритм рождался в процессе обсуждения в различных эхах ФИДО и представляет собой что-то вроде FAQ. В связи с этим данное описание почти полностью состоит из фрагментов различных писем, поэтому стилистика и грамматика здесь не блещет.

А нужно это было для online RTS.

Задача
Решение
Вариант 1: BSP
Вариант 2
Вариант 3
Ссылки

Задача

Есть огромное количество 2D (в будущем 3D) объектов порядка 10^4. Многие из них могут двигаться. Большинство двигается группами (т.е. относительные координаты объектов в группе не изменяются и группа движется как одно целое), но есть и независимо двигающиеся. Объекты разного размера, ограничений размера нет (бесконечных объектов вообще-то тоже нет, но их размеры могут сильно варьироваться). Группы тоже могут быть разных размеров, но как правило они большие.

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

Для упрощения задачи все объекты можно считать прямоугольными (bounding boxes причем аxis aligned т.е. объекты окружены прямоугольными оболочками со сторонами параллельными осям координат).

Решение

Попарно сравнивать все объекты (~10^8/2 сравнений) - тормоза великие, даже если на асме, то остается мало времени на все остальное (AI, отрисовку и т.д.).

Что первое приходит в голову так это как-то их предварительно отсортировать.

Вариант 1: BSP

Но я не очень представляю как при этом разбивать пространство так как объекты (группы) могут очень отличаться по своим размерам и многие из них изначально пересекаются. С плоскостями при пересечении нет проблем их можно разбить на 2 и таким образом избавиться от пересечений, а втот объекты пилить нехочется их и так много. Кроме того как при довольно большом количестве движущихся объектов динамически генерировать BSP, да еще и быстро... :-/

Вариант 2

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

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

Вариант 3

Гибрид первых 2-х, но с квадрантным деревом (чтоб не хешировать, хотя имхо квадрантное дерево при большой глубине тормознее будет).

Maxim Kamensky (МК)

МК> Для взаимных пересечений лучше использовать разбиение
МК> пространства регулярной сеткой. В каждой ячейке сетки строить
МК> BBox,для всех попадающих в ячейку своими _центрами_ BBox'ов,
МК> и определять пересечения м-ду BBox'ами. Если пересечения есть,
МК> то определять пересечения м-ду объектами входящими в BBox'ы.

...

Прошло 2 недели в течении которых я возился с BSP, квадрантными деревьями, bounding box'ами и т.д., а также разрабатывал новый (как я наивно думал:) алгоритм. Суть его в следующем.

Спроецируем все ВВох'ы на координатные оси. Разместим все ВВох'ы в 2-х отсортированых списках. В 1-м списке находятся х-координаты всех проекций ВВох'ов на ось Х (т.е. минимальное и максимальное значение х-координат ВВох'ов), во 2-м тоже самое, но по у-координате.

(ВВох представлен в списке в 2-х элементах -- для min и для max координаты.)

Х' - минимальная координата какого-либо объекта, а Х" -- максимальная.

Рассмотрим движение ВВох'а. Пусть он движется вправо по оси Х. Нам нужно отслеживать 2 случая: 1-й — пересечение ВВох'ов и 2-й — рассоединение пересеченных (на предыдущем шаге) ВВох'ов.

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

2. При движении проверяем его минимальную координату (левую) - Хmin с ближайшей (справа) координатой - Х" какого-либо другого ВВох'а в х-списке. Если Хmin<Х", то х-проекции ВВох'ов перестали пересекаются. Так же как и в 1-м случае меням местами в списке Хmin и Х", и удаляем из списка пересеченных ВВох'ов эту пару (если она там была, так как пересечение проекций на одной из осей еще не означает пересечение ВВох'ов). Если поиск и удаление из списка занимает много времени (зависит от типа списка), то предварительно можно проверить у-координату (на предыдущем шаге) чтобы знать наверняка есть ли всписке эта пара.

Для движения в обратную сторону все точно также, но наоборот ;)

Тоже самое делаем и для движения по у-координате.

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

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

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

Но вот в fido7.ru.algorithms мне дали ссылочку на документ по colission detection (но совершенно не в тему). Но на этом сайте www.cs.unc.edu/~geom/ я нашел почти такой же алгоритм :( обидно, однако). Но, имхо, всетаки мой вариант лучше, так как там предлагается для сортировки списков использовать пузырьковую сортировку (самый тормозной алгоритм) или сортировку вставками, у меня же списки все время поддерживаются в отсортированном виде.

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

Сейчас думаю как оптимизировать удаление из списка пересеченных ВВох'ов. Есть идея использовать хеш, но к этому же списку мне нужен последовательный доступ ко всем элементам, а хешированный масиив очень дырчатый и не очень подходит. Может есть идеи?

(Далее следуют фрагменты из моей (AR) переписки с Maxim Kamensky (МК).)
.

Страницы: 1 2 3 Следующая »

19 октября 2005 (Обновление: 19 ноя 2005)

Комментарии [1]