Ресурсы методов использования для обнаружения столкновений в 2D? - PullRequest
12 голосов
/ 28 августа 2008

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

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

Ответы [ 5 ]

13 голосов
/ 18 сентября 2008

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

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

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

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

2 голосов
/ 31 августа 2008

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

2 голосов
/ 28 августа 2008

Лично я люблю работы Пола Бурка .

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

1 голос
/ 02 сентября 2008

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

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

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

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

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

0 голосов
/ 28 августа 2008

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

...