что такое коллизия в играх
Box2d: анатомия коллизий
Что такое коллизии?
В Box2D принято считать, что друг с другом сталкиваются тела, однако на самом деле при расчете коллизий используются фикстуры (fixtures, переводы слова существуют, но я не уверен, есть ли среди них устоявшийся). Объекты могут сталкиваться разными способами, поэтому библиотека предоставляет большое количество уточняющей информации, которая может быть использована в игровой логике. Например, вы можете захотеть узнать следующее:
Все настроено таким образом, чтобы нижняя часть треугольника столкнулась с верхним углом квадрата. Тонкости реализации этого процесса выходят за рамки статьи — основное внимание уделим тому, какую информацию можно извлечь на каждом этапе столкновения. Если есть желание самостоятельно запустить предлагаемый пример, исходный код прилагается.
Получении информации о столкновении
Информация о столкновении содержится в объекте типа b2Contact. Из него можно узнать, какие именно фикстуры сталкиваются, и определить их положение и направление результирующих импульсов. Существует два способа получения объектов b2Contact в Box2D. Первый — перебрать текущий список контактов каждого тела объекта, второй — использовать слушатель контактов. Рассмотрим каждый из них, чтобы дальше было понятнее, о чем идет речь.
Проверка списка контактов
В любой момент можно перебрать все контакты мира (имеется в виду b2World)
или получить контакты тела определенного объекта
Если выбран этот подход, очень важно помнить, что наличие контакта в этих списках не означает, что фикстуры соприкасаются — это значит только, что пересекаются их AABB. Если требуется убедиться, что контактируют сами фикстуры, воспользуйтесь методом IsTouching(). К этому вопросу мы еще вернемся.
Слушатели контактов
Проверка списка контактов становится неэффективной в ситуациях, когда столкновения происходят часто и в больших количествах. Устанавливая слушателей контактов, вы отдаете поручение Box2D сообщать, когда происходит что-то интересное, вместо того, чтобы вручную следить за началом и завершением столкновений. Слушатель контактов — это объект класса b2ContactListener, часть функций которого замещается при необходимости.
Должен заметить, что в зависимости от ситуации, некоторые события дают нам не только объект b2Contact. В процессе выполнения функции Step, когда Box2D определяет, что произошел контакт, он выполняет обратный вызов определенных функций слушателя, чтобы уведомить вас. Практическое использование «обратных вызовов при коллизиях» рассматривается в отдельной статье. Здесь мы все внимание сосредоточим на том, что можно узнать, обрабатывая события столкновений.
В общем случае я рекомендую метод слушателей контактов. На первый взгляд он может показаться несколько неуклюжим, однако он более эффективен и полезен в долгосрочной перспективе. До сих пор мне не встречалась ситуация, когда проверка списка контактов давала бы ощутимый выигрыш.
Вне зависимости от способа получения контактов, они содержат одинаковую информацию. Наиболее важные данные о пересекающихся фикстурах можно получить так
Когда происходит обход списка контактов определенного объекта, возможно, одна из фикстур коллизии известна, но если используется слушатель контактов, придется полностью положиться на эти функции, чтобы понять, что с чем сталкивается. Четко заданного порядка фикстур не существует, так что часто приходится устанавливать пользовательские данные (user data), чтобы понять, какому именно объекту принадлежит фикстура или тело. Располагая объектом фикстуры, можно воспользоваться методом GetBody(), чтобы получить ссылку на тело.
Столкновение шаг за шагом.
Теперь давайте подробнее рассмотрим последовательность событий, происходящих при столкновении. Надеюсь, картинок с описанием каждого шага будет достаточно для понимания материала. Возможно, вы захотите загрузить исходники к уроку, чтобы запускать их во время чтения. Тестовая программа позволяет ставить симуляцию на паузу, перезапускать и выполнять ее по шагам.
Начнем с ситуации, когда AABB фикстур не пересекаются, так мы сможет проследить историю полностью. Кликните флажок «AABBs», чтобы увидеть фиолетовые прямоугольные области вокруг каждой фикстуры.
AABB фикстур начинают перекрываться
Несмотря на то, что сами фикстуры еще не пересеклись, на этом этапе уже создается экземпляр b2Contact и добавляется в список контактов мира и списки каждого тела. Если вы просматриваете эти списки, то по наличию объектов b2Contact можно судить о том, что в принципе контакт возможен, хотя фикстуры не обязательно пересеклись.
Результат: контакт существует, но IsTouching() возвращает ложь
Продолжаем симуляцию, пока не пересекутся непосредственно фикстуры…
Фикстуры начинают пересекаться.
Приблизив верхний угол квадрата, можно увидеть переход, как на следующих изображениях
Шаг n
Шаг n+1 (не bullet-объекты)
Все это происходит за один шаг симуляции, значит, реальную точку пересечения (к которой ведет пунктирная линия на рисунке выше), мы проскочили. Это происходит потому, что Box2D сначала смещает все тела и только потом проверяет пересечения, по крайней мере, это его поведение по умолчанию. Если вам нужна реальная точка соприкосновения, то нужно сделать следующее
Шаг n+1 (треугольник — bullet-объект)
Bullet-тела, расходуют больше процессорного времени на расчеты и для большинства приложений не требуются. Просто помните о том, что при обычных настройках, иногда коллизии могут пропускаться — в нашем примере, если бы треугольник двигался достаточно быстро, он мог бы пролететь сквозь угол квадрата, не инициировав столкновения. Если у вас есть очень быстро перемещающиеся тела, контакты которых не должны пропускаться, например, мммм… пули 🙂 тогда их нужно объявлять как bullet-объекты. Дальнейшее изложение будет вестись для не-bullet-тел.
Точки столкновения и нормаль
К этому моменту в нашем контакте присутствует реальное соприкосновение, что дает возможность ответить не некоторые вопросы в начале статьи. Для начала давайте получим нормаль и точку касания. Предполагается, что приведенный далее код вызывается или из метода BeginContact слушателя контактов или из вашего метода после предварительного получения контакта из списка.
Объект контакта содержит информацию о коллизии в локальных координатах тел сталкивающихся объектов, а это не совсем то, что нам нужно. Однако можно запросить у контакта более полезную структуру b2WorldManifold, которая содержит позицию коллизии в мировых координатах.
Полученные точки будут использованы Box2D для расчета реакции на столкновение для вычисления импульса, который направит фикстуры в противоположные стороны. Это будут неточные места соприкосновения фикстур (если только вы не использовали bullet-объекты), хотя на практике их обычно достаточно для расчетов столкновений в игровой логике.
Далее рассмотрим нормаль коллизии, которая направлена от фикстуры A к B:
Похоже на то, что для этого столкновения самый быстрый способ избавиться от перекрывающихся объектов, это оттолкнуть угол треугольника вверх и влево, а квадрата — вниз и вправо. Хотелось бы обратить ваше внимание на то, что нормаль — это просто направление, она не привязана ни к какой точке контакта — я изобразил ее проходящей через points[0] для удобства.
Важно также помнить, что нормаль столкновения не определяет угол между фикстурами (ведь треугольник двигается вообще горизонтально) — она лишь задает направление, следуя которому быстрее всего компенсируется перекрытие объектов. Например, представьте, что треугольник двигается немного быстрее, и перекрытие выглядит так:
Тогда самый быстрый способ разделить фикстуры — оттолкнуть треугольник вверх и вправо. Так что использовать нормаль для расчета угла между объектами нецелесообразно. Если требуется узнать направления, по которым будут разделяться фигуры, можно воспользоваться следующим кодом:
Он позволит получить относительную скорость реакции всех точек столкнувшихся тел. В нашем простом случае можно было бы ограничиться линейной скоростью треугольника, так как известно, что квадрат неподвижен, а треугольник не вращается. Но вышеуказанный код будет учитывать и случаи, когда оба дела движутся или вращаются.
Также нужно заметить, что не при каждом столкновении будет именно две точки коллизии. Я намерено остановился на достаточно сложном примере, когда перекрываются два угла многоугольников, но чаще бывает только одна такая точка. Вот несколько примеров столкновений, для которых достаточно одной точки
Итак, только что мы рассмотрели, как определить точки и нормаль коллизии, на основе которых Box2D будет рассчитывать реакцию, направленную на компенсацию перекрытий. Теперь вернемся к последовательности событий.
Реакция на столкновение
( (b2Contact::Update, b2Island::Report))
Шаг_столкновения
Шаг_столкновения + 1
Шаг_столкновения + 1
Когда фикстуры перекрываются, реакция Box2d по умолчанию — приложить импульс к каждой из них, чтобы направить в разные стороны. Однако это не всегда удается сделать за один шаг моделирования. Как показано на рисунках для нашего примера, две фикстуры будут перекрываться на протяжении трех шагов, пока отскок не состоится, и они окончательно не разделятся.
В это время мы можем вмешаться и настроить поведение модели, как нам захочется. Если используется подход со слушателем контактов, методы PreSolve и PostSolve будут вызываться на каждом шаге, пока фикстуры перекрываются, давая возможность модифицировать контакт перед тем, как он будет обработан стандартными средствами реакции на коллизию (PreSolve), и узнать, какие импульсы были приложены Box2D (PostSolve)
Для большей наглядности приведу вывод printf, которая помещена в в функцию Step и каждый метод слушателя контактов:
Результат: PreSolve and PostSolve вызываются несколько раз
PreSolve and PostSolve
Оба эти метода получают в качестве параметра указатель на b2Contact, так что мы имеем доступ к той же информации о точках и нормалях, что и в BeginContact. PreSolve дает на возможность изменить характеристики контакта перед расчетом реакции на столкновение и даже отменить реакцию полностью. PostSolve позволяет получить информацию о вычисленной реакции.
В PreSolve можно сделать следующие настройки объекта контакта:
Вызов SetEnabled(false) деактивирует контакт, значит, реакция на столкновение просчитываться не будет. Это может понадобиться, когда необходимо временно позволить объектам пролетать друг сквозь друга. Классический пример — односторонняя стена или платформа, когда игрок может пройти сквозь обычно непроходимый объект при определенных условиях, которые можно проверить только во время выполнения — например, позиция игрока или направление его движения.
Важно помнить, что на следующей итерации контакт снова активируется, так что если нужно отключить его на продолжительное время, придется делать это на каждом шаге.
Кроме ссылки на контакт, PreSolve содержит второй параметр, из которого можно получить характеристики коллизии (точки и нормаль) с предыдущего шага моделирования. Если кто-то знает, зачем это может пригодиться — расскажите мне 😀
PostSolve вызывается после того, как реакция на столкновение была рассчитана и применена. У метода есть второй параметр, содержащий информацию о приложенном в результате импульсе. Обычно он используется для проверки, не превысила ли реакция некоторое пороговое значения, в результате чего объект можно разрушить и т.п. В статье » sticky projectiles» содержится пример использования функции PostSolve для определения, должна ли стрела застревать в мишени.
Возвращаемся к сценарию столкновения
Фикстуры больше не перекрываются
(b2Contact::Update)
AABB все еще перекрываются, так что контакт пока остается в соответствующих списках мира и тела.
(увеличенный масштаб)
AABB фикстур не перекрываются
(b2ContactManager::Collide)
Результат: контакт удаляется из списка контактов мира и тела.
Метод EndContact получает указатель на b2Contact, когда фикстуры уже не соприкасаются, так что в нем уже не содержится актуальной информации. Тем не менее EndContact является неотъемлемым элементом слушателя контактов, так как позволяет контролировать, когда игровые объекты покидают зону соприкосновения.
Game Engine своими руками #8: Коллизии
Очередной привет всем поклонникам гейм-девелоперского дела! Ненавязчиво закончив свое повествование о графической начинке игрового движка, я перехожу к остальным его не менее важным составляющим, и на этот раз речь пойдет об обработке коллизий.
Коллизии играют одну из первых ролей в устройстве игрового мира. Моделирование физического взаимодействия игровых объектов целиком и полностью основано на обработке коллизий. Очень часто мы сталкиваемся с проблемами определения пересечения двух объектов: если это шутер нам требуется определить, попала ли пуля во врага, если это гонка, то нас интересует взаимодействие колес автомобиля с дорогой, в бильярде мы рассматриваем столкновение шаров. Существует огромное количество различных типов коллизий, равно как и способов их обнаружения. Я начну с рассмотрения самых простых случаев, а ты проникайся, потому что такого скопления ценной инфы ты больше ни где не найдешь 😉
Пересечение двух сфер выявляется очень просто: мы находим расстояние между центрами сфер и если это расстояние больше суммы радиусов сфер, то сферы не пересекаются.
Расстояние между двумя точками находится по школьной формуле:
Здесь нам нужно найти расстояние от центра сферы до плоскости и сравнить его с радиусом сферы. Расстояние от точки до плоскости ищется по следующей формуле:
Не барское это дело рассказывать про уравнение плоскости, но все же напомню, что любая плоскость определяется уравнением первой степени:
Подставив в первое уравнение, получаем:
Для упрощения вычислений бывает удобно заранее нормировать уравнение плоскости, т.е. поделить все коэффициенты (A, B, C, D) на длину нормали, т.е. на sqrt(A^2 + B^2 + C^2), тогда расстояние от точки до плоскости превратится в скалярное произведение:
Аналогично двум предыдущим случаям, для определения пересечения прямой и сферы нам нужно найти расстояние от центра сферы до прямой и сравнить его с радиусом сферы.
Зная координаты (x0, y0, z0) точки лежащей на прямой и радиус-вектор (l, m, n) задающий направление прямой, можно записать параметрические уравнения прямой:
x = x0 + lt; y = y0 + mt; z = z0 + nt;
Очевидно, что расстояние от точки M(x*, y*, z*) до прямой есть расстояние от точки М до точки N пересечения прямой и перпендикулярной ей плоскости проведенной через
M.
Плоскость перпендикулярная прямой и проходящая через точку M задается уравнением:
Подставив параметрические уравнения прямой в уравнение плоскости, найдем значение параметра t определяющего координаты точки N пересечения прямой и плоскости:
Если заранее нормировать вектор (l, m, n), то уравнение примет вид:
Подставив теперь это значение параметра t в параметрические уравнения прямой, найдем координаты точки N. После чего будет нетрудно найти расстояние между точками M и N.
Очевидно, что для определения пересечения сферы и отрезка недостаточно найти расстояние от центра сферы до прямой, которой принадлежит отрезок (см. рис.) нужно еще убедиться, что точка N принадлежит самому отрезку.
x = x1 + lt; y = y1 + mt; z = z1 + nt;
Это один из самых простых для обнаружения видов коллизий. Допустим у нас есть отрезок MN заданный двумя точками: M(x1, y1, z1) и N(x2, y2, z2) и плоскость заданная точкой (x0, y0, z0) и единичной нормалью (l, m, n), нужно охарактеризовать их взаимное расположение.
Уравнение плоскости запишется в виде:
lx + my + nz = lx0 + my0 + nz0
Найдем расстояние от каждого из концов отрезка до плоскости, по вышеописанной формуле, опустив знак модуля, получим для расстояние от M до плоскости:
Расстояние от N до плоскости:
Мы не стали учитывать знак модуля по следующим соображениям. Если принять, что направление нормали плоскости определяет внешнюю сторону плоскости, то знак этих выражений позволяет сказать по какую сторону от плоскости лежит точка. Например, если dist1 больше 0, то точка M лежит перед плоскостью, а если меньше 0, то позади. Таким образом, учитывая все вышесказанное, можно сделать следующий вывод: если знаки выражений dist1 и dist2 равны, то оба конца отрезка лежат по одну сторону от плоскости и следовательно отрезок плоскость не пересекает. Если же знаки различны, т.е. dist1*dist2 ASize[i]/2 + BSize[i]/2)
return 0;
>
Чтобы определить пересекаются ли OBB’ы или нет, мы должны спроецировать их на некоторую ось и проверить пересекаются ли проекции. Теорема о «разделяющих осях» (Separating Axis Theorem)гласит, что существует только 15 потенциальных разделяющих осей, спроецировав OBB’ы на которые можно однозначно выявить наличие коллизии. Этими осями являются шесть локальных осей (по три для каждого OBB’а) и девять их векторных произведений. Чтобы нам было легче проецировать OOB’ы на оси, преобразуем один из OBB’ов в координатную систему другого с помощью матрицы преобразований (см. листинг)
typedef struct <
vec3_t pos; // координаты центра
vec3_t size; // размеры
vec3_t axis[3]; // локальные оси
> obb_t;
bool OBBsOverlap (obb_t a, obb_t b)
<
vec3_t a, b; // размеры уменьшенные вдвое (радиусы)
vec3_t v, T;
float rmatrix[3][3];
float ra, rb, t;
int i, j;
// делим размеры пополам
a[0] = a.size[0]/2;
a[1] = a.size[1]/2;
a[2] = a.size[2]/2;
b[0] = b.size[0]/2;
b[1] = b.size[1]/2;
b[2] = b.size[2]/2;
//
// преобразуем B в систему координат первого OBB’а
//
VectorSubtract (b.pos, a.pos, v);
T[0] = DotProduct (v, a.axis[0]);
T[1] = DotProduct (v, a.axis[1]);
T[2] = DotProduct (v, a.axis[2]);
// строим матрицу преобразования
for( i=0 ; i ra + rb ) return 0;
>
// на оси B
for( i=0 ; i ra + rb) return 0;
>
// 9 векторных произведений
// если до сих пор не вышли, то боксы пересекаются
return 1;
>
Разработка игр под NES на C. Главы 7-10. Работа с джойстиком. Коллизии спрайтов
Плавно движемся к написанию игры. В этой части описана работа с джойстиками и коллизиями спрайтов.
Пользовательский ввод
Еще удобно определить битовые маски для кнопок. Это позволит получать события быстрыми и наглядными битовыми операциями.
Воспользуемся метаспрайтом из прошлого урока и подвигаем его по экрану. Этот кусок намного удобней было написать на Ассемблере, вникать в него нет необходимости.
Чтобы вызвать ассемблерную функцию из кода на С, нужен ее прототип. Линкер соберет их вместе на своем этапе компиляции.
Объявлять функцию как void необязательно, это больше для единообразия кода. Настоятельно рекомендую использовать __fastcall__, потому что в этом случае последний (или единственный) аргумент будет передан через регистры A и X — это быстрее, чем через стек. 8-битный аргумент передается через регистр А, 16-битный — в паре А/Х, 32-битный — А/Х/sreg, где sreg — 16-битная переменная в нулевой странице памяти. Подробности описаны в документации к компилятору.
Но вернемся к Get_Input(). Если мы вызовем эту функцию один раз после каждого кадра, то она соберет и приведет в удобный формат все нажатия кнопок.
Теперь можно двигать человечка по экрану с помощью джойстика. Весь ассемблерный код вынесен в файл asm4c.s. Скрипты сборки тоже подправлены. А обработчик событий джойстика вынесен в отдельную функцию:
Коллизии спрайтов
Проще всего обнаружить столкновение двух спрайтов. Здесь будем рассматривать метаспрайты размером 16х16 точек. Это в принципе можно считать стандартом для большинства NES-игр.
Определение столкновений реализовано через сравнение координат краев объектов. Там получается куча достаточно очевидных сравнений. Позиции спрайтов удобно определять через координату левого верхнего угла, а потом рассчитывать границы. Это выглядит примерно так:
Отступ слева нужен для корректной обработки пустого края
Но целочисленное переполнение сделает нам неприятный сюрприз. Если спрайт уедет на правый край экрана, в район A_X = 250, то A_X+12 = 6, а это очевидно неправильно. Нам нужно проверить края и при переполнении присвоить значение 255. Это не идеально, но работает неплохо. Завести 16-битную переменную под координату можно, но неэффективно — код проверки на коллизии выполняется для многих спрайтов каждый кадр, а процессор 6502 не силен в таких больших числах. Или можно принудительно ограничить приближение спрайтов к краям.
В следующем примере объект В будет двигаться сам по себе кодом из предыдущей главы, а А будет управляться джойстиком. При каждом их касании счетчик будет увеличиваться на 1. Проверка будет проходить один раз за кадр. Счетчик будем хранить как целочисленную переменную на каждую цифру счетчика и делать переносы вручную.
При каждом обновлении счетчика выставляется флаг, по которому счетчик перерисовывается на следующем кадре. Мы можем менять спрайты только в период V-blank. Это событие ловится через обработчик NMI.
Отрисовка фона целиком
Теперь мы умеем показывать спрайты — в период V-blank или принудительно отключив экран. V-blank хватает только на 2 ряда тайлов, а во втором случае на полную перерисовку надо пропустить пару кадров — экран при этом зальет фоном по умолчанию.
Второй вариант проще и требует меньше кода. Фоны очень удобно рисовать в NES Screen Tool, и он поддерживает сохранение таблиц имен с RLE-сжатием. Распаковываются они простым декодером на Ассемблере. В подробности вникать не будем, а возьмем готовый код.
Будем менять фон при нажатии Start на джойстике. Также проследим, чтобы при длительном нажатии кнопки отрисовка прошла только один раз — иначе могут наложиться несколько запусков рендера, а это ой.
Логика примерно такая:
Коллизии с фоном
Чуть сложнее отследить коллизии спрайтов с фоном. Примем по умолчанию, что мы используем квадратные метатайлы 16х16, и такого же размера спрайты. Большинство игр используют такую схему. Спрайт будет двигаться в одну из четырех сторон на 1 пиксель за кадр, и каждый кадр будем проверять коллизии.
Обычно сначала спрайт двигается, проверяется, нет ли контакта, и это касание обрабатывается. Мы же разнесем это по двум координатам — сначала сдвинем и проверим по горизонтали, а потом по вертикали.
Чтение из PPU — это боль. Надо посчитать адрес актуальной таблицы имен, и запросить ее из PPU во время V-blank, чтобы при этом хватило времени на работу логики игры и обновление спрайтов. Не будем так делать.
Нам надо хранить карту фоновых метатайлов в одной странице RAM. Эта же карта может использоваться для быстрого расчета коллизий, если тайлов всего два вида — сделаем нулевой проходимым для персонажа, а первый нет. Если же надо больше видов тайлов, то таблицу проходимости надо хранить отдельно. В принципе, карты можно хранить и в ROM картриджа.
Теперь можно импортировать ее в код на С и сослаться по указателю на массив.
Точный адрес удобен и для отладки в FCEUX — можно зайти дебаггером в работающей игре и посмотреть что и как.
А вот так карта коллизий грузится из ROM в RAM:
Но через какое-то время я переписал это с memcpy — копирование по байтам занимает 42688 тактов процессора, это в 9 раз больше, чем memcpy.
Но и это не все. Третий подход к снаряду был с Ассемблером — получилось на 4% быстрее. Думаю, что пока оно того не стоит. Хотя возможно в большой игре именно этих тактов процессора не хватит, и придется выжимать из приставки абсолютно все возможное.
Логика проверки коллизий с фоном примерно такая:
+3 нужно, чтобы скомпенсировать 3-пиксельные прозрачные края спрайта.
Проверка коллизий по вертикали делается аналогично. Судя по всему, код не будет работать, если спрайт движется быстрее, чем 1 точка/кадр.
Надо помнить, что спрайт всегда рисуется на 1 точку ниже, чем ожидается. Поправку можно внести перед обновлением вертикальной координаты в OAM. В платформерах этого обычно достаточно. Игры с видом сверху могут выглядеть странно — персонаж немного провалится в текстуру.