¶ Коллизии
Посмотрим на один из появившихся вопросов.
¶ Что такое коллизия?
Это столкновение. К примеру, столкновение двух объектов - персонажа и стены. Если оно произошло, то персонаж не должен проходить сквозь неё. Или должен разрушить стену. Или стена должна нанести ему урон. Неважно. Но важно то, что произошло столкновение. И вопрос определения столкновения довольно проблематичен.
¶ 2D
Если мы работаем с 2D графикой, то попиксельная проверка столкновений — это перебор миллионов пикселей каждый кадр. Плюс нужно понять, какие объекты вообще могут столкнуться — проверять все пары тоже дорого (игрок и стена рядом, а стена и сундук на разных концах карты — зачем их сравнивать?). Поэтому используют упрощённые формы — хитбоксы.
¶ 3D
К тому же, если вспоминать 3D графику, где у нас объекты представлены не в виде простых пикселей, а полигонов, которые затем проходят кучу всевозможных процессов, включая растеризацию - грубо говоря, проекция 3D модели на плоскость монитора с определением того, какой цвет должен быть у пикселя изображения в данном кадре - то … все усложняется.
Не забывайте, что мониторы состоят из отдельных точек - физических пикселей, имеющих какой-то цвет. Они не прямо соответствуют точкам изображения в памяти компьютера.
¶ Hitbox
Начнем с самого простого, но оптимального варианта - введения hitbox'ов. Hitbox - упрощённая геометрическая фигура, заменяющая объект для проверки на коллизии и, как правило, невидимая на экране.
В том числе чрезмерно упрощенная - до примитивов: прямоугольника, круга. Т.е. идея заключается в том, что мы хитрим - мы подменяем объект, который имеет большое количество пикселей, сложную форму, из-за чего мы не можем использовать какие-то простые геометрические формулы, элементарной фигурой, рассчитываем столкновения с ней, а результат применяем к оригинальному объекту. Выглядит это так:
- Можно заметить, что небольшая часть объекта вышла за пределы хитбокса.
Другой вариант:
- А тут наоборот, лишнее пространство включено в хитбокс.
Поэтому мы можем использовать другой примитив, например, окружность:
Или же мы можем использовать несколько примитивов:
И если хотя бы один из них пересекается с хитбоксом другого объекта - произошла коллизия.
А уже как просчитать пересечение двух примитивов - вопрос простой геометрии.
Например, для двух окружностей: достаточно посчитать расстояние между их центрами. Если оно меньше суммы радиусов - окружности пересекаются.
Т.е. условие столкновения: d <= r1 + r2, где d - расстояние между центрами, r1 и r2 - радиусы.
Причём расстояние считается по теореме Пифагора: d = √((x2-x1)² + (y2-y1)²). Но корень - операция дорогая, а проверка коллизий происходит часто. Можно сравнивать квадраты: (x2-x1)² + (y2-y1)² <= (r1+r2)². Результат тот же, но быстрее.
def circles_collide(x1, y1, r1, x2, y2, r2):
dx = x2 - x1
dy = y2 - y1
dist_sq = dx * dx + dy * dy
radii_sum = r1 + r2
return dist_sq <= radii_sum * radii_sum
public static bool CirclesCollide(float x1, float y1, float r1,
float x2, float y2, float r2)
{
float dx = x2 - x1, dy = y2 - y1;
float distSq = dx * dx + dy * dy;
float radiiSum = r1 + r2;
return distSq <= radiiSum * radiiSum;
}
¶ AABB
При использовании хитбоксов мы можем взять алгоритм AABB - Axis-Aligned Bounding Box - выровненный по оси ограничивающий прямоугольник.
Как можно догадаться по названию, в качестве хитбокса используется прямоугольник, параллельный какой-либо оси на координатной плоскости. Что нам это дает? Простое понимание, пересекаются ли два хитбокса или нет:
Как проверить пересечение двух AABB? Подойдем от обратного. Два прямоугольника не пересекаются, если один полностью левее, правее, выше или ниже другого. Если ни одно из этих условий не выполняется - они пересекаются.
Допустим, у каждого прямоугольника есть координаты левого верхнего угла (x, y) и размеры (w, h). Тогда столкновение есть, если одновременно:
- Левый край первого левее правого края второго: x1 <= x2 + w2
- Правый край первого правее левого края второго: x1 + w1 >= x2
- И то же самое по вертикальной оси: y1 <= y2 + h2 и y1 + h1 >= y2
Четыре условия. Если хотя бы одно не выполняется - объекты не пересекаются. Реализовать это в коде - одна функция с четырьмя сравнениями.
def aabb_collide(x1, y1, w1, h1, x2, y2, w2, h2):
return (x1 <= x2 + w2 and
x1 + w1 >= x2 and
y1 <= y2 + h2 and
y1 + h1 >= y2)
public static bool AABBCollide(float x1, float y1, float w1, float h1,
float x2, float y2, float w2, float h2)
{
return x1 <= x2 + w2 &&
x1 + w1 >= x2 &&
y1 <= y2 + h2 &&
y1 + h1 >= y2;
}
¶ Вращение и AABB
Ок, AABB прост и быстр. Но что, если объект вращается? Прямоугольник-то выровнен по осям — он не умеет поворачиваться.
Простое решение: пересчитывать AABB под повёрнутый объект. Берём оригинальные размеры w × h, угол поворота θ, и считаем новый AABB, который гарантированно вмещает повёрнутую фигуру:
import math
def rotated_aabb(w, h, angle_rad):
cos_a = abs(math.cos(angle_rad))
sin_a = abs(math.sin(angle_rad))
new_w = w * cos_a + h * sin_a
new_h = w * sin_a + h * cos_a
return new_w, new_h
public static (float w, float h) RotatedAABB(float w, float h, float angleRad)
{
float cosA = MathF.Abs(MathF.Cos(angleRad));
float sinA = MathF.Abs(MathF.Sin(angleRad));
return (w * cosA + h * sinA, w * sinA + h * cosA);
}
При угле 0° AABB совпадает с оригиналом. При 45° — максимально раздувается. При 90° — w и h просто меняются местами. Проверка столкновений — всё тот же aabb_collide, но с пересчитанными размерами. Быстро, просто, без новой математики.
Минус: AABB всегда больше реальной фигуры (кроме 0° и 90°). Это значит ложные срабатывания - объекты "сталкиваются", хотя визуально не касаются. Для большинства игр это допустимо. Но если нужна точность - используйте OBB (Oriented Bounding Box) с проверкой через SAT (Separating Axis Theorem): проецирование углов на оси обоих прямоугольников. Сложнее, но точнее.
¶ Тайлы и коллизии
Хм. А что, если вспомнить про то, что мы уже разбивали на квадраты (тайлы) наш ландшафт? Возможно, получится использовать это разбиение?
Использовать тайлы как набор AABB, отслеживая, какие из них заняты нашим объектом. Но в таком случае, для проверки на столкновение придется перебирать все занятые тайлы? Не факт, это истинно в том случае, если мы храним занятые тайлы в виде списка.
Но есть более эффективные структуры для подобного, например, BSP, QuadTree, Sparse Grid, позволяющие хранить элементы с учетом координат, например, по близости/удаленности. Сетка, QuadTree и пространственное хеширование разобраны в пространственных структурах данных.
А как проверить, может ли объект переместиться в новую позицию, не врезавшись в стену? Зная координаты объекта в пикселях и размер тайла, мы можем вычислить, в каких тайлах находятся его углы. Если хотя бы один угол попадает в тайл-стену - перемещение невозможно.
Т.е. задача сводится к: координата в пикселях / размер тайла = индекс в матрице. Получили индекс - посмотрели, что в этой ячейке. Стена? Столкновение. Проверили все четыре угла хитбокса объекта - и знаем, можно ли туда двигаться.
def can_move_to(x, y, w, h, level, tile_size):
# check all four corners of the hitbox
corners = [
(x, y), # top-left
(x + w - 1, y), # top-right
(x, y + h - 1), # bottom-left
(x + w - 1, y + h - 1), # bottom-right
]
for cx, cy in corners:
col = int(cx) // tile_size
row = int(cy) // tile_size
if level[row][col] == 1: # 1 = wall
return False
return True
public static bool CanMoveTo(float x, float y, float w, float h,
int[,] level, int tileSize)
{
(float cx, float cy)[] corners = {
(x, y),
(x + w - 1, y),
(x, y + h - 1),
(x + w - 1, y + h - 1),
};
foreach (var (cx, cy) in corners)
{
int col = (int)cx / tileSize;
int row = (int)cy / tileSize;
if (level[row, col] == 1) // 1 = wall
return false;
}
return true;
}
Проверка четырёх углов - упрощение. Если объект больше одного тайла, между углами может быть стена, которую мы не заметим. В этом случае стоит проверять не только углы, но и промежуточные точки вдоль каждой стороны хитбокса.
¶ Отсечение геометрии
Подобные структуры можно будет применить также и в отсечении геометрии - Culling. Ведь нам не нужно отображать то, что мы не видим.
Например, герой находится в темном подземелье, держит в руках факел. Все, что освещено - должно быть видно. Как понять, что освещено - тема освещения. Здесь нас интересует то, что все объекты, которые находятся за стеной, не освещены и находятся вдалеке от игрока, не должны быть отображены на экране вовсе.
И, к примеру, BSP может помочь с отсечением невидимой геометрии от видимой.
Подробнее об отсечении в контексте камеры: Камера и отсечение.
¶ Что дальше?
| Что | Где подробнее |
|---|---|
| Пространственные структуры (Grid, QuadTree) для ускорения коллизий | Пространственные структуры |
| Туннелирование и порядок обновления физики | Порядок обновления |
| Тайлы и граф уровня | Уровни и поиск путей |
| Камера и отсечение невидимых объектов | Камера |
| ИИ врагов: коллизия как условие атаки | ИИ врагов |
| Частицы и столкновения с миром | Система частиц |