Ресурсы использования методов для обнаружения столкновений в 2D?

Ответ 1

Обнаружение столкновений часто является двухфазным процессом. Какой-то "широкомасштабный" алгоритм для определения того, имеют ли два объекта вероятность перекрытия (чтобы попытаться избежать n ^ 2 сравнения), а затем алгоритм обнаружения столкновений "узкой фазы", ​​основанный на требованиях к геометрии вашего приложения.

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

Узкое фазовое столкновение часто может быть таким же простым, как "CircleIntersectCircle". Снова библиотеки Bullet имеют хорошие справочные реализации. В 3d-области, когда для произвольных объектов требуется более точное обнаружение, GJK входит в текущий слиток урожая - ничто в моем понимании не помешает ему будучи адаптированным к 2d (но он может оказаться медленнее, чем просто грубый, заставляющий все ваши края;)

Наконец, после обнаружения столкновения вам часто нужен какой-то ответ на столкновение. Вставка 2d является хорошей отправной точкой для решения физического ответа.

Ответ 2

Лично мне нравится работа Paul Bourke.

Кроме того, Пол Нетлт писал на эту тему. У него есть полная 3D-библиотека обнаружения столкновений, но вас могут больше заинтересовать идеи, стоящие за такими библиотеками (которые очень применимы к 2D). Для этого см. Общее обнаружение столкновений для игр с использованием эллипсоидов.

Ответ 3

Metanet Software опубликовала несколько соответствующих учебных пособий. Metanet разрабатывает N (на основе Flash, для Windows, Mac, Linux) и N + (для X360, DS и PSP).

Ответ 4

Книга "Обнаружение столкновений в реальном времени" Кристера Эриксона (ISBN: 1-55860-732-3) - это недавняя (2005) и широко распространенная книга, которая должна дать вам несколько хороших ответов.

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

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

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

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

Ответ 5

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