Те, кто давно читают мой блог, наверное помнят, что я хотел написать гоночки. Изначально, это должна была быть открытая местность с проложенной дорогой, извивающейся в разных направлениях. Проблем на этом пути возникло ровно две: управление и обработка столкновений. Мной был разработан метод определения пересечения определённых ограничительных линий (пересечение линии и линии движения объекта), однако он имел ряд недостатков, поэтому было решено немного упростить игровой процесс, изменив начальную фабулу игры. В попытке решения задачи я так увлёкся сторонними проблемами, вроде способов загрузки ресурсов и управления игрой и попытке сделать всё это предельно универсальным, что забыл про изначальный план. Да, так бывает.
Но что я совершенно точно понял, так это главную игровую механику всех без исключения игр. Это - обработка столкновений объектов. Именно на ней строится любая игра, даже такая, как тетрис. Только в ней используется это немного иначе.
Итак, механика
Собственно, на этом месте заканчивается романтика и начинается математика, потому что определить столкновение 2 фигур - это задача, которую надо не просто решить, а решить быстро. Как мы знаем из азов программирования, операция ветвления - самая медленная операция. И чем больше их - тем медленней работает приложение. В идеале, обработка столкновений должна вообще обходиться без операции ветвления.
Есть ещё один немаловажный момент: сам факт столкновения двух объектов - влечёт разные следствия. Например, столкновение с преградой - должно запретить дальнейшее движение, а вот пересечение с неигровым персонажем или объектом - должно привести к иным последствиям (например, получение урона или возможность начать диалог). Иными словами, мы говорим про реакцию на столкновение.
Доступные способы обработки
Я искал разные способы обработки. И нашёл несколько. Но, для начала, входные данные. Изначально, мы исходим из соображения, что вся карта построена по принципу кубиков, то есть набора клеток, желательно одного размера, выступающих каркасом, на который накладывается изображение.
Далее, есть два типа объектов на карте: статичные и динамичные. Разница между ними определяется из наименования.
Статичные - всегда неподвижны (пол, стены, зоны бафа и дебафа итп), динамичные - могут менять свои координаты в пространстве.
Каждый объект имеет свою "коробку" - то есть 2 набора координат, описывающий левый верхний и правый нижний угол (для 3д карт немного сложней, но это уже выходит за рамки моих исследований).
Итак, чтобы определить столкновение, есть несколько способов, для объектов А и Б.
Пересечение по граням
Это самый очевидный и самый гибкий способ. Смысл сводится к многочисленному набору условий (столь нелюбимой мной операции ветвления).
Расчёт такой: y-координата верхней или нижней точки объекта Б должна быть между y-координатами объекта А либо y-координата верхней или нижней точки объекта А должна быть между y-координатами объекта Б. А также x-координата верхней или нижней точки объекта Б должна быть между x-координатами объекта А либо x-координата верхней или нижней точки объекта А должна быть между x-координатами объекта Б.
Запутанно получилось, да. Но всё сводится к проверке, что есть пересечение по y-координатам и x-координатам.
Из хорошего - полная универсальность данного метода. Из недостатков - жуткая ресурсоёмкость. Особенно, если надо проводить сравнение с многочисленными объектами. Также, из данного вычисления совершенно непонятно, как сформировать инструкцию на реакцию, т.к. неясно, с какой стороны произошло столкновение и требуется ещё несколько раз провести сравнение, чтобы понять, что делать.
Коробочное пересечение
Данный метод существенно проще. Для определения способа пересечения двух объектов - достаточно выполнить следующее:
- Найти самую верхнюю-левую и правую-нижнюю точку у двух объектов;
- Рассчитать длину и высоту получившейся большой коробки;
- Сравнить её длину и высоту с суммой длин и высот проверяемых коробок;
- Если длина большой коробки меньше сумм длин, а высота большой коробки - меньше сумм высот коробок проверяемых объектов - значит пересечение есть.
Как видно, данный метод существенно проще предыдущего. Но он, всё так же, не предлагает управляющего воздействия (с какой стороны столкновение - надо выяснять отдельно). Кроме того, когда идёт определение пересечения сразу с несколькими объектами одновременно, может быть случай, когда реакция на пересечение с одним объектом приводит к усугублению пересечения с другим.
Простое пересечение
Тут необходимо сделать небольшое пояснение. Изначально, мы говорили о том, что надо определить столкновение. Но это не совсем так. Нам надо не просто определить столкновение, а сделать это в интересах игры, которую пишем. А тут, очевидно, есть ещё набор входных данных. В частности, ради основной механики, мы можем пойти по пути упрощения карты - и сведению её исключительно к набору равновеликих квадратиков, каждый из которых - всего один блок карты.
Далее, стены и потолок, зачастую - неподвижны и именно с ними происходит наибольшее количество столкновений (и, следовательно, проверок); динамические объекты требуют незначительное количество проверок, по сравнению со статичными.
Итак, основное правило таково:
- Статичные объекты имеют фиксированные координаты, разнесённые по карте с определённым шагом (т.е. есть сетка, внутри которой размещены статичные объекты и указав номер блока по горизонтали и вертикали - можно получить координаты этого объекта);
- Динамические объекты имеют координаты, не привязанные к изначальной сетке;
- Каждый объект, используемый в игре, состоит из некоторого количества квадратов, с габаритами, используемыми при построении карты (например, бегущий персонаж - два квадрата, присевший - 1 квадрат);
- Допускается наличие объектов нестандартных габаритов, но взаимодействие с ними обрабатывается по-другому.
Что нам это даёт? А очень многое! Зная габариты проверяемого объекта (1, 2 или более клеток), мы можем получить координаты коробки каждой из них в новой позиции, на которую должен сместиться объект. По данным координатам можно вычислить, есть ли в этом месте статичный объект, с которым нельзя пересекаться (пол, потолок или стена) и если есть - исправить координаты таким образом, чтобы пересечения не произошло.
Для простоты такого исправления, сперва можно провести сравнение по вертикали, потом по горизонтали или наоборот (например, упершись в стенку можно продолжать лететь вверх).
Более того, зная координаты своего объекта и вычислив его положение на карте, можно производить проверку столкновения лишь с ближайшими объектами (например, плюс-минус одну-две клетки карты во все стороны от текущих габаритов).
Однако, есть и минусы. Такой фокус пройдёт со статичными объектами и позволит легко внести коррективу в координаты, однако для работы с динамичными объектами такой способ не годится: динамичный объект может в процессе движения находиться на 4 и более клетках одновременно, поэтому для таких объектов лучше использовать иные методы.
Заключение
Непросто получилось для понимания, однако, с другой стороны, когда пытаешься реализовать механику столкновений без такой теории - увязаешь во многочисленных частных случаях, требующих длинный набор ветвлений ЕСЛИ-ТО, которые, к слову, не гарантируют того, что всё будет работать как надо.
Кстати, есть неплохая статья, если кому интересно и есть готовность читать по-английски. Но она несколько выходит за рамки того, о чём пишу я. Сильно выходит.
