Посмотрим на один из появившихся вопросов.
¶ Что такое коллизия?
Это столкновение. К примеру, столкновение двух объектов - персонажа и стены. Если оно произошло, то персонаж не должен проходить сквозь неё. Или должен разрушить стену. Или стена должна нанести ему урон. Неважно. Но важно то, что произошло столкновение. И вопрос определения столкновения довольно проблематичен.
¶ 2D
Если мы работаем с 2D графикой и пикселями, то в какой-то момент придем к тому, что пискелей на экране слишком много, и проверка “в лоб”, пересекаются ли они, очень медленная. Ведь при подготовке каждого кадра нам нужно проверить пиксель каждого объекта на столкновение с пикселем всех других объектов (просто так понять, что игрок и стена рядом, а стена и сундук - далеко - проблематично). И этот процесс хочется ускорить и упростить.
¶ 3D
К тому же, если вспоминать 3D графику, где у нас объекты представлены не в виде простых пискелей, а полигонов, которые затем проходят кучу всевозможных процессов, включая растеризацию - грубо говоря, проекция 3D модели на плоскость монитора с определением того, какой цвет должен быть у пикселя изображения в данном кадре - то … все усложняется.
Не забывайте, что мониторы состоят из отдельных точек - физических пикселей, имеющих какой-то цвет. Они не прямо соответствуют точкам изображения в памяти компьютера.
¶ Hitbox
Начнем с самого простого, но оптимального варианта - введения hitbox'ов. Hitbox - это хитбокс, упрощенная версия объекта, используемая для проверки на коллизии и, как правило, невидимая на экране.
В том числе чрезмерно упрощенная - до примитивов: прямоугольника, круга. Т.е. идея заключается в том, что мы хитрим - мы подменяем объект, который имеет большое количество пикселей, сложную форму, из-за чего мы не можем использовать какие-то простые геометрические формулы, элементарной фигурой, рассчитываем столкновения с ней, а результат применяем к оригинальному объекту. Выглядит это так:
- Можно заметить, что небольшая часть объекта вышла за пределы хитбокса.
Другой вариант:
- А тут наоборот, лишнее пространство включено в хитбокс.
Поэтому мы можем использовать другой примитив, например, окружность:
Или же мы можем использовать несколько примитивов:
И если хотя бы один из них пересекается с хитбоксом другого объекта - произошла коллизия.
А уже как просчитать пересечение двух примитивов - вопрос простой геометрии.
¶ AABB
При использовании хитбоксов мы можем взять алгоритм AABB - Axis-Aligned Bounding Box - выровненный по оси ограничивающий параллелограмм.
Как можно догадаться по названию, в качестве хитбокса используется параллелограмм, параллельный какой-либо оси на координатной плоскости. Что нам это дает? Простое понимание, пересекаются ли два хитбокса или нет:
Естественно, такой вариант не очень хорошо работает при вращении оригинального объекта. В этом случае мы можем взять - OBB - Oriented Bounding Box - направленный ограничивающий параллелограмм. Все то же самое, только направление хитбокса совпадает с направлением объекта.
¶ Тайлы и коллизии
Хм. А что, если вспомнить про то, что мы уже разбивали на квадраты (тайлы) наш ландшафт? Возможно, получится использовать это разбиение?
Использовать тайлы как набор AABB, отслеживая, какие из них заняты нашим объектом. Но в таком случае, для проверки на столкновение придется перебирать все занятые тайлы? Не факт, это истинно в том случае, если мы храним занятые тайлы в виде списка.
Но есть более эффективные структуры для подобного, например, BSP, QuadTree, Sparse Grid, позволяющие хранить элементы с учетом координат, например, по близости/удаленности.
¶ Отсечение геометрии
Подобные структуры можно будет применить также и в отсечении геометрии - Culling. Ведь нам не нужно отображать то, что мы не видим.
Например, герой находится в темном подземелье, держит в руках факел. Все, что освещено - должно быть видно. Как понять, что освещено - тема освещения. Здесь нас интересует то, что все объекты, которые находятся за стеной, не освещены и находятся вдалеке от игрока не должны быть отображены на экране вовсе.
И, к примеру, BSP может помочь с отсечением невидимой геометрии от видимой.