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

Question

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

Существует 2D мир, населенный круглыми шарами, заостренными треугольниками и тощими линиями (и, возможно, другой дикой природой). Все они являются подклассами 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's tutorial на the separating axis theorem. В своей флагманской игре они фактически используют сетку, чтобы найти все объекты для проверки на столкновение, но не должно быть слишком сложно использовать квадрант вместо этого.

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

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

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

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

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

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

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

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