Я всегда задавался этим вопросом. В такой игре, как GTA, где есть 10 000 000 объектов, как игра узнает, как только вы попадете в пакет здоровья?
Не может быть прослушиватель событий для каждого объекта? Итерация тоже не хороша? Мне просто интересно, как это делается на самом деле.
Там нет ни одного ответа, но большие миры часто разделяются по пространству, используя что-то вдоль строк quadtree или kd-tree, который дает время поиска для нахождения ближайших соседей ниже линейного времени (дробная мощность или в худшем случае O (N ^ (2/3)) для 3D-игра). Эти методы часто называют BSP для разбиения двоичного пространства.
Что касается обнаружения столкновений, каждый объект также имеет связанную с ним сетку ограниченного объема (множество многоугольников, образующих выпуклую оболочку). Эти сильно упрощенные сетки (иногда только куб) не нарисованы, а используются для обнаружения столкновений. Самый примитивный метод - создать плоскость, перпендикулярную линии, соединяющей середины каждого объекта с плоскостью, пересекающей линию в средней точке линии. Если объектный ограничивающий объем имеет точки на обеих сторонах этой плоскости, это столкновение (вам нужно только проверить один из двух ограничивающих томов на плоскости). Другим методом является расширенный алгоритм GJK. Если вы хотите, чтобы учебное пособие проходило, просмотрите Урок OpenGL NeHe Productions № 30.
Случайно, ограничивающие объемы могут также использоваться для других оптимизаций, таких как так называемые окклюзионные запросы. Это процесс определения того, какие объекты находятся за другими объектами (окклюдеры), и поэтому их не нужно обрабатывать/визуализировать. Ограничивающие объемы также могут использоваться для отбраковки усеченного конуса, который является процессом определения того, какие объекты находятся за пределами перспективного объема обзора (слишком близко, слишком далеко или за пределами поля обзора), и поэтому его не нужно визуализировать.
Как отметил Килотан, использование ограничивающего объема может генерировать ложные срабатывания при обнаружении окклюзии и просто не работает вообще для некоторых типов объектов, таких как тороиды (например, просматривая отверстие в пончике). Наличие объектов, подобных этим, правильно закрывается, это целая другая нить при выборе портала.
Quadtrees и Octrees, еще один квадрант, являются популярными способами, используя разметку пространства, для достижения этого. В более позднем примере показано сокращение на 97% обработки по взаимному перекрестному поиску коллизий.
Общей техникой в двигателях физики игр является метод подметания и обрезки. Это объясняется в заметки Дэвида Барафа SIGGRAPH (см. Главу "Движение с ограничениями" ). Havok определенно использует это, я думаю, что это вариант в Bullet, но я не уверен в PhysX.
Идея состоит в том, что вы можете посмотреть на перекрытия AABB (ограничивающие по оси рамки) на каждой оси; если проекция AABB двух объектов перекрывается на всех трех осях, тогда AABB должны перекрываться. Вы можете проверить каждую ось относительно быстро, сортируя начальную и конечную точки AABB; существует много временной согласованности между кадрами, поскольку обычно большинство объектов не двигаются очень быстро, поэтому сортировка не сильно меняется.
Как только sweep-and-prune обнаружит совпадение между AABB, вы можете выполнить более детальную проверку объектов, например. сфере против коробки. Если детальная проверка обнаруживает столкновение, вы можете разрешить столкновение, применяя силы, и/или запускать игровое событие или воспроизводить звуковой эффект.
Правильно. Обычно для каждого объекта нет слушателя событий. Часто в памяти есть небиная древовидная структура, которая имитирует вашу карту игр. Представьте себе метро/подземную карту. Эта память strucutre - это набор вещей в игре. Вы игрок, монстры и предметы, которые вы можете получить, или предметы, которые могут разразиться и нанести вам вред. Так как игрок перемещается по игре, указатель объекта игрока перемещается в структуре памяти игры/карты.
см. Как я должен знать, что мои игровые сущности осведомлены о вещах вокруг них?
Можно использовать много оптимизаций.
Во-первых - любой объект (например, с индексом i, например) ограничен кубом с центральными координатами CXi, CYi и размером Si
Во-вторых - обнаружение столкновения работает с оценками:
a) Найти все пары кубов i, j с условием: Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)
b) Теперь мы работаем только с парами, полученными в a). Мы вычисляем расстояния между ними более точно, что-то вроде Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj)), объекты, представленные в настоящее время как множества из нескольких чисел простых фигур - кубов, сфер, конусов, - и мы используем формулы геометрии для проверки этих пересечений фигур.
c) Объекты из b) с обнаруженными пересечениями обрабатываются как столкновения с вычислением физики и т.д.
Я хотел бы рекомендовать солидную книгу Кристера Эриксона о обнаружении столкновения в режиме реального времени. В нем представлены основы обнаружения столкновений, а также ссылки на современные исследования.