Advertisement
  1. Game Development
  2. Game Physics

Основы физики 2D платформера, часть 5: Обнаружение столкновения объекта с объектом

by
Difficulty:BeginnerLength:LongLanguages:
This post is part of a series called Basic 2D Platformer Physics .
Basic 2D Platformer Physics, Part 4
Basic 2D Platformer Physics, Part 6: Object vs. Object Collision Response

Russian (Pусский) translation by Alexey Malyutin (you can also view the original English article)

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

Демонстрация

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

Это демо было опубликовано под Unity 5.4.0f3, и исходный код также совместим с этой версией Unity.

Обнаружение столкновения

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

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

Пространственное разбиение!

По существу, это разбиение пространства игры на более меньшие области, которое позволит нам проверять столкновения только между объектами, принадлежащими к одной области. В такой оптимизации чрезвычайно нуждаются игры наподобие Terraria, где мир и количество объектов, могущих столкнуться, гигантские и объекты расположены редко. В одноэкранных играх, где количество объектов сильно ограничено размером экрана, это обычно не требуется, но все еще полезно.

Метод

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

The Rectangular space for our objects

Здесь есть один нюанс: объект может находиться более, чем в одном подпространстве одновременно. Это абсолютно нормально - просто это значит, что мы должны обнаруживать объекты, принадлежащие каждой области, ч которой пересекается наш прежний объект.

An object residing in more than one sub-space

Данные для разделения

Основа проста. Нам нужно решить, насколько велика будет каждая ячейка в двумерном массиве, каждый элемент которого представляет собой список объектов, расположенных в определенной области. нам нужно поместить эти данные в класс Map.

В нашем случае, я решил выразить размер секции в тайлах, и каждая секция получилась размером 16 на 16 тайлов.

Для наших объектов нам понадобится список областей, с которыми объект в данный момент пересекается, а также его индекс в каждой секции. Давайте добавим все это в класс MovingObject.

Вместо двух списков мы можем использовать одиночный словарь, но к сожалению производительность при использовании сложных контейнеров в текущей итерации Unity оставляет желать лучшего, поэтому мы в нашем демо будем колупаться  со списками.

Инициализация секций

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

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

Теперь давайте инициализируем секции.

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

Назначаем секции объекта

Теперь пришло время создать функцию, которая будет обновлять области, с которыми пересекается конкретный объект.

Прежде всего, нам нужно узнать, с какими тайлами карты пересекается объект. Так как мы используем только AABB, все, что нам нужно сделать - это проверить, в каком тайле оказался каждый угол AABB.

Теперь, чтобы получить координату в поделенном пространстве, все, что нам нужно сделать, это разделить позицию тайла на размер секции. Нам не нужно рассчитывать нижний правый угол секции прямо сейчас, потому что его координата x будет равна координате верхнего правого угла, а его координата y будет равна координате нижнего левого угла.

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

Теперь, возможно объект расположен полностью внутри одной секции, возможно - в двух, или он может занимать пространство как раз там, где встречаются четыре секции. Это все делается в предположении, что нет объектов размером больше, чем размер секции, когда объект, будучи достаточно большим, может занимать всю карту и все секции сразу. Я работал, исходя из этого допущения, поэтому именно так мы будем поступать с этим в уроке. Модификации, позволяющие более большие объекты, достаточно тривиальны, но, тем не менее, я также объясню, в чем они состоят.

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

The object occupying a single area

Если же это не этот случай, и координаты одинаковы по оси x, значит объект пересекает две разных секции по вертикали.

An object occupying two of the same partitions along the x-axis

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

Та же логика применима, если одинаковы только вертикальные координаты.

An object occupying two of the same partitions along the y-axis

Наконец, если все координаты разные, нам нужно добавить все четыре области.

An object occupying four quadrants

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

Как видите, процедура очень простая - мы добавляем индекс области в список областей, пересекаемых объектом, мы добавляем соответствующий индекс в список id объектов, и наконец мы добавляем объект в секцию.

Теперь давайте создадим функцию удаления.

Как вы можете видеть, мы используем координаты области, с которой персонаж больше не пересекается, его индекс в списке объектов внутри этой области, и ссылку на объект, который нам нужно удалить.

Чтобы удалить объект, мы будем менять местами его с последним объектом в списке. Это потребует от нас также убедиться, что индекс объекта для этой конкретной области будет обновлен на тот, который был у нашего удаленного объекта. Если бы мы не меняли объекты местами, нам нужно было бы обновлять индексы всех объектов, которые идут после того, который нам нужно удалить. Вместо этого, нам нужно обновить только тот, с которым мы меняемся местами.

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

Теперь нам нужно найти интересующую нас область в списке областей обмениваемого объекта, и изменить индекс в списке id на индекс удаленного объекта.

Наконец, мы можем удалить последний объект из секции, который теперь является ссылкой на объект, который нам нужно удалить.

Полный текст функции должен выглядеть вот так:

Давайте вернемся к функции UpdateAreas.

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

Теперь давайте обойдем в цикле новые области, и если объект не был назначен им ранее, давайте добавим их сейчас.

Напоследок очистим список пересекающих областей, чтобы он был готов к обработке следующего объекта.

Вот и все! В финальном виде функция должна выглядеть вот так:

Обнаружение столкновений между объектами

Прежде всего нам нужно убедиться, что мы вызываем UpdateAreas для всех игровых объектов. Мы можем делать это в главном цикле обновления, после вызова обновления каждого индивидуального объекта.

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

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

Данные, которые мы сохраняем, это ссылка на объект, с которым мы столкнулись, наложение, скорость обоих объектов в момент столкновения, их позиции, и также их позиции перед моментом столкновения.

Давайте перейдем к классу MovingObject и создадим контейнер для свежесозданных  данных о столкновении, которое нам нужно обнаружить.

Теперь давайте вернемся обратно к классу Map и создадим функцию CheckCollisions. Это будет наша сверхмощная функция, в которой мы будем обнаруживать столкновения между всеми игровыми объектами.

Чтобы обнаружить столкновения, мы будем перебирать все секции.

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

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

Теперь мы можем проверить, пересекаются ли AABB объектов друг с другом.

Вот что происходит в функции AABB OverlapsSigned.

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

В качестве последнего действия, когда столкновение обнаружено, мы вычисляем, как сильно AABB пересекается с другим AABB. Перекрытие имеет знак, поэтому в этом случае, если перекрывающийся AABB на правой стороне текущего AABB, перекрытие по оси x будет отрицательным, а если другой AABB на левой стороне текущего AABB, перекрытие по оси x будет положительным. Это облегчит позже выход из перекрытого положения, так как мы будем знать, в каком направлении нам нужно двигать объект.

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

Чтобы упростить вещи для нас, мы примем, что единицы (speed1, pos1, oldPos1) в структуре данных столкновений всегда ссылаются на владельца данных столкновения, а двойки - это данные, относящиеся к другому объекту.

Другой момент - перекрытие вычисляется с перспективы объекта obj1. Перекрытие объекта obj2 должно быть инвертированным, поэтому если obj1 должен двигаться влево, чтобы выйти из столкновения, obj2 должен двигаться вправо, чтобы выйти из этого же столкновения.

Остается побеспокоиться еще об одной маленькой вещи  -так как мы перебираем в цикле секции карты и один объект может находиться одновременно в нескольких секциях, до четырех в нашем случае, возможно, что мы обнаружим пересечение одних и тех же двух объектов до четырех раз.

Чтобы убрать такую возможность, мы просто проверяем, определяли ли мы уже столкновение между двумя объектами. Если это так, то мы пропускаем эту итерацию.

Функция HasCollisionDataFor реализуется следующим образом.

Она просто перебирает в цикле все структуры данных столкновения и ищет есть ли среди такие, которые принадлежат объекту, который мы собираемся проверить на столкновение.

Это нормально,  в основном пользоваться предположением, что мы не ожидаем столкновения объекта со множеством других объектов, поэтому просмотр списка будет проходить быстро. Однако при другом сценарии возможно будет лучше заменить список CollisionData словарем, тогда вместо перебора в цикле мы сможем сразу сказать, находится в нем уже элемент, или нет.

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

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

Теперь давайте вызовем функцию, которую мы только что закончили, в главном цикле игры.

Вот и все! Теперь все наши объекты имеют данные о столновениях.

Чтобы проверить, все ли работает как надо, давайте сделаем так, что если персонаж сталкивается с объектом, спрайт персонажа будет становиться полупрозрачным.

Reviewing Collisions via Animation

Как видите, похоже, что обнаружение прекрасно работает!

Заключение

Вот и закончилась очередная часть серии уроков по физике простого двумерного платформера. Нам удалось реализовать простой механизм деления пространства и обнаружения столкновения между всеми объектами.

Если у вас есть вопрос, подсказка, как сделать что-либо лучше, или просто у вас есть свое мнение об уроке, не стесняйтесь пользоваться секцией комментариев, чтобы донести это до меня!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.