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

Question

Каковы, на ваш взгляд, лучшие ресурсы (книги или веб-страницы), описывающие алгоритмы или методы, используемые для обнаружения столкновений в 2D-среде?

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

Answer 1

Лично я люблю работу Paul Bourke.

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

Answer 2

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

Answer 3

Компания Metanet Software опубликовала some relevant tutorials. Metanet разрабатывает N (на базе Flash, для Windows, Mac, Linux) и N+ (для X360, DS и PSP).

Answer 4

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

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

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

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

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

Answer 5

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

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

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

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