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


Определение арктангенса: в прямоугольном треугольнике arctan вычисляет один из непрямых углов, используя в качестве входных данных длину стороны, противоположной этому углу, разделённую на длину прилежащей стороны. В случае Star Versus сторонами треугольника являются расстояния X/Y между двумя объектами, например, снарядом и кораблём, а угол — это направление, в котором должен двигаться первый, чтобы достичь второго.



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

Реализация

Важным упрощением в Star Versus является то, что направление не непрерывно, а дискретно. Объекты могут двигаться только в 24 возможных направлениях. Перемещение вправо соответствует 0, вверх — 6, влево — 12, а вниз — 18. Каждый инкремент направления представляет собой угол в τ / 24 радиан. (τ — это фундаментальная константа окружности, равная 6.2831853…)

После выполнения кода распознавания коллизий у нас уже есть дельты позиций X/Y для функции arctan. Нам достаточно одних знаков, чтобы понять, в каком из четырёх квадрантов находится результат, поэтому остальная часть кода должна выяснить при помощи абсолютных значений дельт, какое из 6 направлений квадранта является правильным.

Процессор 6502 слишком медленный, чтобы вычислять arctan при помощи стандартных способов, например рядов Тейлора, но поскольку результат должен быть правильным в рамках τ / 24, мы можем сжульничать и использовать аппроксимацию. В целом план заключался в том, чтобы сначала найти соотношение X/Y, затем представить набор линий, разделяющих пространство в соответствии с возможными направлениями, затем найти наклон этих линий, и сравнить соотношение, чтобы понять, к какому из направлений угол ближе всего.


Нам нужно быть внимательными к тем углам, которые равномерно делят пространство на области, окружающие направления, которые должен возвращать arctan. Это τ/48, 3τ/48, 5τ/48, … 11τ/48. Тангенс каждого из них равен:

tan( 1 * τ / 48) = 0.131652497587
tan( 3 * τ / 48) = 0.414213562373
tan( 5 * τ / 48) = 0.767326987979
tan( 7 * τ / 48) = 1.30322537284
tan( 9 * τ / 48) = 2.41421356237
tan(11 * τ / 48) = 7.59575411273

Поскольку у процессора 6502 нет команд умножения и деления, дробные значения нежелательны. Однако у него есть битовые сдвиги, с помощью которых можно малозатратно делить или умножать на 2. К счастью, три значения тангенсов выше диагонали довольно близки к 1.25, 2.5 и 7.5, а эти значения довольно легко найти при помощи битовых сдвигов [1]. Другие углы ниже диагонали просто являются их отражениями, поэтому мы можем найти их, поменяв местами X и Y.



Сравнивая соотношение X/Y с этими значениями, мы получим номер области от 0 и 3. Будет ли эта область находиться над диагональю, зависит от того, поменяли ли мы местами X и Y. Вот псевдокод алгоритма:

small, large = x, y
if y < x:
    small, large = y,x
half = small / 2
// compare to 2.5 slope
if small * 2 + half > large:
    // compare to 1.25
    quarter = half / 2
    if small + quarter > large:
        region = 1
    else:
        region = 0
else:
  // compare to 7.5
  if small * 8 - half > large:
    region = 3
  else:
    region = 2
// Use region, whether X/Y were swapped, and quadrant in a lookup table.

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

Применение

После реализации arctan он применяется во всех аспектах игры. Кроме коллизий мечей нужно также рассчитывать движение бомб, которые должны попадать в свои цели. Для этого они периодически проверяют направление в сторону движения к другому кораблю, и изменяя его, если отклонились от курса [2]. Почти так же arctan используется при стрейфе по кругу, поворачивая корабль в направлении другого корабля, пока он движется вбок, создавая круговое движение. Хотя реализация arctan неидеальна, на практике погрешность достаточно мала, поэтому самонаведение бомб и круговой стрейф работают хорошо.

При создании кампании на одного игрока arctan очень пригодился для создания вражеского ИИ. В базовом поведении врагов присутствует стрельба по игроку, и arctan определяет, как это нужно делать. У разных врагов есть различные паттерны разлёта пуль, но все они основаны на arctan.



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

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

Примечания

[1] Умножение меньшего числа вместо деления большего имеет и ещё одно полезное преимущество — оно позволяет избежать числовых искажений, снижая вероятность ошибок.

[2] Самонаводящиеся снаряды не меняют своё направление в каждом кадре и не меняют его, если слишком отклонились от цели. В противном случае они были бы слишком точными, что отрицательно сказалось бы на игровом балансе.