Не секрет, что практически любые игры, по большей части, это математика. И различные алгоритмы. Давайте рассмотрим, в общем виде разумеется, несколько алгоритмов, которые можно назвать не иначе, как опорные.
И хотя я рассказываю про игровые алгоритмы, на самом деле данный подход применяется много где. Хотя бы даже в SCADA системах - интерфейсах диспетчерского управления различными объектами (дороги, атомные станции и прочее).
Главная игровая механика и её алгоритмы
По большому счёту, совершенно неважно, в какую игру вы играете, почти со 100% вероятностью в ней будет задействован механизм пересечения фигур. Это может быть наведение курсора на нужный объект (персонаж, карта, цель) или пересечение двух фигур (столкновение машин на трассе).
Требования к алгоритмам
Функции, на основе таких алгоритмов, должны выполняться очень часто, значит крайней важно, чтобы они были предельно простыми, иначе в игру просто невозможно играть будет. На это я и постараюсь сделать ставку.
Пересечение двух квадратов
Это самый простой алгоритм и он (и его вариации) используется чаще всего в играх с видом сбоку.
Начальное условие - всё собирается из квадратиков и именно пересечение перспективного положения героя (где окажется персонаж на следующем такте отрисовки) с каким-то из "кирпичиков" карты (пол, потолок, другие игровые персонажи, враги) и является, фактически, игровым процессом.
Пересечение двух равновеликих квадратов (а они все имеют одинаковый размер всех размерностей) находится крайне просто:
|x1 - x2| <= L
|y1 - y2| <= L
Это работает крайне просто: если разницы смещений по двум осям меньше длины квадрата, значит они пересекаются.
А если добавить ещё одну ось (z) - можно уже определять пересечение кубов.
Оптимизация ненужных пересечений
Очевидно, что нет смысла проверять пересечения нашего персонажа со всеми объектами карты каждый кадр (с большинством из них он, даже теоретически, не может пересекаться).
Все объекты у нас, так или иначе, привязаны к координатам и, обычно, хранятся в упорядоченной структуре, привязанной к координатной сетке. Поэтому можно делать проверку лишь с теми объектами, которые находятся рядом.
Обычно, квадратики "ландшафта" имеют только смещение по осям (явное или вычисляемое), без привязки к координатам. А координаты персонажа можно, обратным вычислением перевести в смещение.
Оптимизация движения по прямой
В большинстве игр, персонаж двигается по горизонтальной прямой, но может прыгать и падать. С точки зрения логики игры, самым простым шагом будет добавить гравитацию, которая действует на персонажа, прижимая к полу. Просто, но не оптимально.
В таких случаях, самый простой способ обработки таких ситуаций - это зацеп. Работает он так: если ниже персонажа есть квадрат пола (у квадрата есть {ox, oy} смещение, у персонажа можно высчитать {ox, oy} смещение из его текущих координат), то y-координата фиксируется.
Хочу заметить, и это важно: {ox:oy} смещения - это просто смещение квадрата в сетке экрана, а вот {x:y} координаты - это реальные координаты на холсте экрана. При длине стороны квадрата, скажем, 10, для смещения {3:5} координаты составят {30:50}.
Если координаты персонажа не соответствуют шагу размера, то приведение выбирает ближайший квадрат ({33:55} =>{30:50}).
Зацеп персонажа с полом имеет несколько крутых оптимизирующих свойств:
- Пока снизу пол, y - координата легко высчитывается относительно фиксированной координаты пола;
- Можно двигаться по наклонной, изогнутой и даже волнистой поверхности: координата всегда будет высчитана правильно на любом этапе (но придётся немного доработать код, позволяя визуально смещать квадратики пола относительно базовой позиции);
- На время работы этого алгоритма, можно отключить проверку гравитации.
Отключение проверки гравитации, кстати, нередко очень полезная возможность. В ряде игр, при движениях на вертикальных платформах возникает "дребезг", когда персонаж, по мере движения, немного дрожит по высоте, либо же вообще, периодически, перерисовывается в спрайты падения.
Пересечения равных прямоугольников
По большому счёту, этот алгоритм является частным случаем пересечением квадратов, за исключением того, что теперь вместо одной константы-стороны появляется две: ширина и высота.
|x1 - x2| <= Lw(ширина)
|y1 - y2| <= Lh(высота)
Во всём остальном - то же самое.
Пересечение неравных прямоугольников
Тут, к сожалению, простого решения нет. Более того, используя такой игровой подход, придётся отказаться и от сетки. Самым простым решением будет сделать, всё же, игровую сетку из квадратов, а все прямоугольники сделать кратной стороне этого квадрата и делать массовое сравнение пересечения квадратов, принадлежавших прямоугольников.
Тем не менее, даже если такая возможность отсутствует, существует вполне рабочий способ найти пересечение.
Суть метода проста: нужно производить сравнение относительно того, который находится левее и выше. Потому что меньший прямоугольник, если он левее и выше может не попасть в пересечение с большим, а вот наоборот условие может и выполниться.
Пересечение сложных фигур
Наверное можно было бы поделить любую фигуру на несколько фигур попроще (скажем, треугольников) и сравнить, но это не столь простая задача, как может показаться, да и нельзя сказать, что это будет быстрый способ.
Впрочем, быстрый способ есть - цветовое сравнение. Работает это так: скажем, есть фигура А и для неё назначен технический цвет - красный, есть фигура Б с техническим цветом синим и стоит режим смешивания цветов (то есть при наложении этих двух цветов появится фиолетовый).
Параллельно с основным холстом, есть теневой холст, на котором рисуется исключительно игровой персонаж (фигура А) с некоторой границей. Если в это "окно" попадает какой-то другой объект (фигура Б) - то он тоже там отрисовывается.
Факт вхождения фигуры Б в окно персонажа определить несложно; если это произошло, то на каждом кадре отрисовки делается проверка на наличие в данном окне цвета смешения. Или цветов смешения, если в окно попалось несколько фигур, у каждой из которых может быть свой цвет.
Простой проверкой матрицы цветов можно определить не только пересечение двух объектов, но и то, на сколько процентов объекты перекрывают друг друга.
Это довольно эффективный способ, однако очевидно, что он весьма ресурсозатратен.
Реакции
Дело в том, что сам факт пересечения фигур - это только первый этап, но что же дальше?
А дальше, при обнаружении пересечения срабатывает его величество триггер, в котором и определяется, что же должно произойти.
- Столкновение со стеной должно остановить продвижение персонажа на границах стены;
- Получение урона, вероятно, отбросить назад и уменьшить величину здоровья;
- Соприкосновение с шипам - завершить игру и начать её опять с последней точки сохранения.
И так далее. Сложность заключается в том, что для выполнения ряд операций требуются некоторые метаданные или сохранённая информация про персонажа, которая позволяет управлять его отображением.
Например, для обработки столкновения со стенами, в некоторых играх используется смещения персонажа за некоторый интервал времени (нередко с сохранением номера спрайта). Если случится так, что персонаж сильно разбежится и глубоко залезет в стену (ошибка промежуточных проверок) - можно будет восстановить последний правильный кадр и вернуть его на правильную позицию.
К слову, эти дополнительные данные можно эффектно использовать. Скажем, в виде шлейфа персонажа.
Заключение
Начать свою игру кажется простым занятием, однако очень скоро начинаются приниматься решения, прямо-таки скажем, далёкие от оптимальных, т.к. работы много, а делается она медленно. Появляется большой соблазн взять нечто готовое (скажем Godot), но за это приходится платить свою цену - утерей контроля над частью своей разработки за прирост скорости.