При попытке определить, происходит ли столкновение (коллизия) между двумя объектами, вершинные данных самих объектов, обычно, не используются, поскольку объекты часто имеют сложную форму, что, в свою очередь, затрудняет процесс обнаружения столкновений. Вместо этого программисты прибегают к помощи более простых фигур (имеющих, как правило, подходящее математическое описание), накладывая их поверх исходных объектов. После чего уже на основе данных фигур производится проверка наличия столкновений; описанный подход упрощает код программы и экономит вычислительные ресурсы компьютера. К подобным фигурам столкновения относятся: окружности, сферы, прямоугольники и параллелепипеды; с ними намного проще работать в сравнении с мешами (сетками) произвольной формы, состоящих из сотен треугольников.
Хотя такие фигуры действительно дают нам более простые и эффективные алгоритмы обнаружения столкновений, но при этом они имеют и один общий недостаток: не всегда контур накладываемой фигуры совпадает с формой объекта. В результате может быть обнаружено столкновение, которого на самом деле не было; важно помнить, что эти фигуры являются всего лишь приближениями форм объектов, на которые они накладываются.
Столкновение вида «AABB-AABB»
Выровненная по осям ограничивающая рамка (сокр. «AABB» от англ. «Axis-Aligned Bounding Box») представляет собой прямоугольную фигуру столкновения, выровненную вдоль осей базиса сцены (для двумерного случая выравнивание происходит по осям x и y). «Выравнивание по осям» означает, что прямоугольная рамка не вращается, а её стороны параллельны осям базиса сцены (например, левая и правая стороны параллельны оси y). Благодаря тому, что эти рамки всегда выровнены вдоль осей сцены, вычисления становятся гораздо проще. Ниже представлена AABB, описанная вокруг нашего мяча:
Почти все объекты в игре «Breakout» имеют прямоугольную форму, поэтому для обнаружения столкновений с их участием имеет смысл использовать AABB.
AABB могут определяться несколькими способами. Один из них заключается в задании AABB по координатам верхнего левого и нижнего правого углов. Класс GameObject, который мы ранее ввели в игру, уже содержит координаты верхнего левого угла (вектор Position), и мы можем легко вычислить координаты нижнего правого, добавив размер AABB к этому вектору (Position + Size). Фактически, каждый объект класса GameObject помимо прочего также будет содержать и AABB, которую можно использовать для определения столкновений.
Итак, как мы проверим наличие столкновений? Столкновение происходит, когда две фигуры столкновения входят в области друг друга. Например, фигура, определяющая первый объект, каким-либо образом пересекается с фигурой второго объекта. В случае AABB это довольно легко определить в виду того, что они выровнены вдоль осей сцены: мы проверяем для каждой оси, перекрываются ли стороны двух объектов относительно заданной оси. Поэтому нам нужно посмотреть, перекрываются ли соответствующие горизонтальные и вертикальные стороны обоих объектов. Если обе горизонтальных и вертикальных стороны перекрываются, то мы имеем столкновение (коллизию).
Переложить описанную идею в код не составит труда. Требуется выполнить проверку наличия перекрытия по обеим осям: если это так, то возвращается логическое значение true:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
bool CheckCollision(GameObject &one, GameObject &two) // столкновение вида "AABB-AABB" { // Перекрытие по оси x? bool collisionX = one.Position.x + one.Size.x >= two.Position.x && two.Position.x + two.Size.x >= one.Position.x; // Перекрытие по оси y? bool collisionY = one.Position.y + one.Size.y >= two.Position.y && two.Position.y + two.Size.y >= one.Position.y; // Если перекрытия происходят относительно обеих осей, то мы имеем столкновение return collisionX && collisionY; } |
Мы проверяем, если координата правой стороны первого объекта больше, чем координата левой стороны второго объекта, и, если координата правой стороны второго объекта больше, чем координата левой стороны первого объекта; аналогично и для вертикальной оси. Если у вас есть проблемы с пониманием данного процесса, то попробуйте нарисовать стороны/прямоугольники на бумаге, тогда всё сразу станет ясно.
Чтобы сохранить структуру кода столкновения немного более организованной, мы добавим в класс Game дополнительную функцию DoCollisions():
|
1 2 3 4 5 6 |
class Game { public: [...] void DoCollisions(); }; |
В рамках DoCollisions() мы проверяем наличие столкновений между мячом и каждым кирпичом уровня. Если будет обнаружено столкновение, то меняем значение свойства кирпича Destroyed на true, тем самым, исключая визуализацию данного кирпича из рендеринга уровня:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void Game::DoCollisions() { for (GameObject &box : this->Levels[this->Level].Bricks) { if (!box.Destroyed) { if (CheckCollision(*Ball, box)) { if (!box.IsSolid) box.Destroyed = true; } } } } |
Также нужно обновить функцию Game::Update():
|
1 2 3 4 5 6 7 8 |
void Game::Update(float dt) { // Обновление объектов Ball->Move(dt, this->Width); // Проверка столкновений this->DoCollisions(); } |
Если мы сейчас запустим код, то увидим, как у кирпичей появляется реакция на столкновение с мячом, и если кирпич не твердый, он разрушится:
Хотя обнаружение столкновений уже работает, оно не очень точно, так как прямоугольная фигура столкновения мяча реагирует с большинством кирпичей, непосредственно их не касаясь. Давайте посмотрим, сможем ли мы придумать более точный метод обнаружения столкновений.
Столкновения вида «AABB-Окружность»
Поскольку мяч представляет собой объект округлой формы, то использование в качестве формы определения столкновений AABB, вероятно, является не лучшим выбором. Код определения столкновения считает, что мяч представляет собой прямоугольник, поэтому может сталкиваться с кирпичом, даже если сам спрайт мяча кирпича не касается.
Гораздо логичнее в качестве фигуры столкновения использовать окружность. Именно для этого в класс мяча была добавлена переменная Radius. Чтобы использовать окружность в качестве фигуры столкновения, потребуются вектор положения и радиус мяча.
Необходимо обновить алгоритм обнаружения столкновений, так как в настоящее время он работает только между двумя AABB. Обнаружение столкновений между окружностью и прямоугольником немного сложнее, но есть один фокус, смысл которого заключается в следующем: мы находим на AABB точку, которая ближе всего к окружности, и если расстояние от окружности до этой точки меньше радиуса окружности, то имеет место факт столкновения.
Самое трудное — это найти на AABB ближайшую к окружности точку P. На следующем рисунке показано, как мы можем вычислить эту точку для произвольных AABB и окружности:
Сначала нам нужно получить вектор D разности между центром окружности C и точкой B центра AABB. Далее, область значений координат вектора D при помощи функции clamp() сужается до ½ от w (ширины AABB) и до ½ от h (высоты AABB), после чего получившийся вектор добавляется к вектору B. В результате мы имеем вектор положения точки, лежащей на стороне AABB (если только центр окружности не попал внутрь AABB).
Примечание: Функция clamp() сужает область допустимых значений переданной ей переменной до заданного диапазона:
|
1 2 3 |
float clamp(float value, float min, float max) { return std::max(min, std::min(max, value)); } |
Например, значение 42.0f при использовании сужения на диапазон значений от 3.0f до 6.0f превратится в 6.0f, а значение 4.20f при сужении на тот же диапазон так и останется равным 4.20f.
Сужение 2D-вектора означает, что мы сужаем на заданный диапазон значений как значение его x-компоненты, так и значение его y-компоненты.
В итоге, полученный вектор P является ближайшей точкой от AABB до окружности. Затем нам нужно вычислить новый вектор разности D’, то есть разность между центром окружности C и вектором P.
Теперь, когда у нас есть вектор D’, мы можем сравнить его длину с радиусом окружности. Если длина вектора D’ будет меньше радиуса окружности, то можно смело утверждать, что имеет место факт столкновения.
В коде это будет выглядеть следующим образом:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
bool CheckCollision(BallObject &one, GameObject &two) // столкновение вида "AABB-Окружность" { // Сначала вычисляем точку центра окружности glm::vec2 center(one.Position + one.Radius); // Вычисляем информацию по AABB (координаты центра, и половинки длин сторон) glm::vec2 aabb_half_extents(two.Size.x / 2.0f, two.Size.y / 2.0f); glm::vec2 aabb_center( two.Position.x + aabb_half_extents.x, two.Position.y + aabb_half_extents.y ); // Получаем вектор разности между центром окружности и центром AABB glm::vec2 difference = center - aabb_center; glm::vec2 clamped = glm::clamp(difference, -aabb_half_extents, aabb_half_extents); // Добавляя переменную clamped к AABB_center, мы получим ближайшую к окружности точку, лежащую на стороне AABB glm::vec2 closest = aabb_center + clamped; // Получаем вектор между центром окружности и ближайшей к ней точкой AABB, и проверяем, чтобы длина этого вектора была меньше радиуса окружности difference = closest - center; return glm::length(difference) < one.Radius; } |
Мы создаем перегруженную функцию CheckCollision() специально для случая взаимодействия объекта класса BallObject и объекта класса GameObject. Поскольку мы не храним информацию о фигуре столкновения в самих объектах, то должны её вычислить: сначала вычисляется центр мяча, затем половинки сторон AABB и центр.
Используя атрибуты фигуры столкновения, мы вычисляем вектор D в виде переменной difference, значение которой сужаем до заданного интервала, получившуюся переменную clamped добавляем к центру AABB, чтобы получить ближайшую к окружности точку P (переменная closest). Затем мы вычисляем вектор разности D’ между переменными center и closest и возвращаем результат — столкнулись ли две фигуры или нет.
Поскольку мы ранее вызывали функцию CheckCollision() с объектом мяча в качестве её первого аргумента, то нам не нужно менять какой-либо код, поскольку теперь автоматически применяется перегруженная версия CheckCollision(). В результате получается гораздо более точный алгоритм обнаружения столкновений:
GitHub / Часть №6: Обнаружение столкновений в игре «Breakout» на C++/OpenGL — Исходный код
Кажется, что наш метод работает как надо, но все же что-то не так. Мы правильно проводим все обнаружения столкновений, но мяч никак на них не реагирует. Нам нужно обновлять положение и/или скорость мяча всякий раз, когда происходит столкновение. А это уже тема следующего урока.
Оценить статью:
(7 оценок, среднее: 5,00 из 5)
Загрузка...