Как бы вы представили алгоритм для обнаружения столкновений между различными объектами?

Question

Во время работы над действительно интересным проектом я столкнулся с некоторой проблемой.

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

Что я хотел бы сделать, это сделать способ обнаружения столкновения между ними. Вот что я стою прямо сейчас:

• Для меня Ball-Ball - это легко, я просто вычисляю расстояние от их позиций и сравниваю их с суммой их «размеров».
• Столкновение Шара с краем света тоже просто - я просто проверяю расстояние от него, которое в декартовых координатах простое.
• Более общие проблемы: как обнаружить столкновение между Линией (начало и конец в некоторых точках) или другими объектами, которые у меня там могут быть? Расстояние между линией и точкой тоже можно легко вычислить, но мне бы хотелось, чтобы

Какой-то общий способ сказать, сталкивается ли Объект A с Объектом B. Код, как он выглядит сейчас, выглядит примерно так:

class WorldCreature:
    def detectCollision(self, otherObject):
        # do something 
        if collision:
            self.onCollision(otherObject)
            otherObject.onCollision(self)
class Ball(WorldCreature):
    # someing here
class Line(WorldCreature):
    # someing here

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

Должен ли я просто хранить список всех объектов в памяти и перебирать все их в каждый шаг ? Или есть какой-нибудь лучший способ улучшить производительность этой задачи?

Answer 1

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

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

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

Answer 2

Python. Вроде странный зверь для меня 8)

У меня есть опыт создания игр на c ++, поэтому я говорю с этой точки зрения.

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

Затем идет узкая фаза - когда проверяются пары.

Я использовал следующую схему (обратите внимание - она ​​была создана с учетом примитивов, если вам нужны столкновения многогранников - просто используйте GJK и сферы, плюс лучи, сегменты):

Все, что нуждается в коллизиях, имеет CollisionObject, который обрабатывает преобразование и хранит CollisionPrimitive (прямоугольник, сфера и т. Д.)

Каждый CollisionPrimitive имеет type_id - когда вы пишете A_B_CheckIntersection - первый объект всегда имеет более низкий type_id

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

Что касается конкретных процедур столкновения: посетите http://realtimerendering.com/intersections.html Это хорошее место для начала

Answer 3

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

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

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

Answer 4

Я думаю Hough Transform должно как-то помочь.