Математика в Майнкрафте
Здравствуй, брат автоматизатор.
Надеюсь, ты помнишь, что всеми нами любимый брат qwertyMAN порадовал нас своей охранной системой турелей. И казалось бы, всё замечательно: турельки бьют прицельно, гриферы боятся, а мобы рассыпаются в лут. Но как всегда я нашел, к чему придраться. Не смотря на прицельный огонь, направление турели на цель вычисляется по очень неэффективному алгоритму.
Весь код охранной системы я разбирать не буду, сосредоточусь только на математике.
Остаток от деления
Начнем с такого фрагмента:
local function kostil(x) while true do if x>=360 then x = x - 360 elseif x<0 then x = x + 360 else break end end return xend
По названию функции видно, что автор осознавал ущербность этого кода, но лучшего решения не знал или забыл. Разберемся, что делает этот код. В цикле вычитает 360 из аргумента, если он больше или равен 360, или добавляет 360, если меньше нуля. А по сути, приводит значение угла к диапазону [0,360). Зачем это делается? Ведь, например, углы и -90˚ и 270˚ указывают одинаковое направление. Сколько бы полных оборотов (360˚) в какую бы сторону мы не совершили, направление от этого не изменится.
Тем не менее турель из OpenSecurity не принимает угол, выходящий за границы диапазона [0..360]. Приведение угла к нужному диапазону называют нормализацией. Угол можно нормализовать и в других диапазонах с полным углом, например [-180,+180]. Но наша турель требует диапазон [0,360]. Как же эффективно произвести нормализацию?
Лучшим решением является операция взятия остатка от деления. Заглянем в справочник:
a % b == a — math.floor(a/b)*b
Не сложно увидеть, что a % b дает нам ровно тот же результат, что и костыль qwertyMAN'а, но код сильно сократился и стал выполняться быстрее. qwertyMAN с этого костыля быстро спрыгнул, и в следующей версии упростил свой код, но поверь мне, брат, на форуме есть много таких костылей, и калеки не спешат с них слезать.
Вот, например, фрагмент кода, до которого я уже давно хотел докопаться. Код слишком длинный не только для своего функционала, но и для этой статьи, поэтому я спрячу его в спойлер:
function smartTurnLeft() robot.turnLeft() if direct=='N' then direct='W' elseif direct=='W' then direct='S' elseif direct=='S' then direct='E' elseif direct=='E' then direct='N' endend function smartTurnRight() robot.turnRight() if direct=='N' then direct='E' elseif direct=='E' then direct='S' elseif direct=='S' then direct='W' elseif direct=='W' then direct='N' endend function smartTurnAround() robot.turnAround() if direct=='N' then direct='S' elseif direct=='W' then direct='E' elseif direct=='S' then direct='N' elseif direct=='E' then direct='W' endend
Можно ли этот код упростить? Легко. Для начала заменим строки числами, например, по такой схеме: N=0; W=1; S=2; E=3
После чего становится очевидным такое решение:
function smartTurnLeft() robot.turnLeft(); N=(N+1)%4; endfunction smartTurnRight() robot.turnRight(); N=(N-1)%4; endfunction smartTurnAround() robot.turnAround(); N=(N+2)%4; end
С какой стороны света начинать отсчет, и в каком направлении, это уже другой вопрос, но принцип остается неизменным.
Главное, что код упростился, он не занимает огромное место в памяти и быстро выполняется.
Конечно, при использовании некоторых приближенных к машинным языков и при определенных условиях работы алгоритма использование деления может оказаться менее эффективным, чем проверки условий с последующим сложением/вычитанием. Но интерпретируемые языки, к которым относится Lua, это преимущество нивелируют. Поэтому по возможности используй операцию взятия остатка от деления при обсчете всяких циклических значений. Это удобно и эффективно.
Тригонометрия
Теперь взгляни на эту функцию
local function pointer(x,y,z) local distXY = math.sqrt(x^2+z^2) local distDY = math.sqrt(y^2+distXY^2) local outX = math.deg(math.acos(x/distXY))+90 local outY = 90-math.deg(math.acos(y/distDY)) if z<0 then outX = kostil(180-outX) end return outX,outYend
Что она делает? Понять не сложно: вычисляет угловые координаты цели: азимут и угол места в градусах.
Что тут не так?
1) присутствует acos с последующим добавлением/вычитанием 90˚, хотя известно, что и синус и косинус при добавлении/вычитании 90˚ преобразуются друг в друга. На этом я задерживаться не буду, формулы и их вывод есть в любом учебнике.
2) использование только asin или только acos тоже является не лучшей идеей: asin имеет низкое разрешение по углу в окрестности +/-90˚, а acos – в области 0 ˚и 180˚, снижая точность наведения, и для ее повышения потребуется использовать asin в окрестностях 0 ˚и 180˚ и acos в окрестности +/-90˚.
3) вычисление синусов и косинусов требует вычисления расстояния до цели r=sqrt(x*x+z*z), а, например, вычисление тангенса не требует.
4) область значений asin, acos и atan не покрывает полный оборот в 360˚, поэтому приходится прибегать к дополнительным вычислениям, как, например, это сделал автор: if z<0 then outX = (180-outX)%360 end.
5) не сошелся свет клином на всем известных со школы синусах, косинусах и тангенсах. Уделив несколько минут чтению списка математических функций, можно обнаружить такую красоту:
В геометрии об этом не рассказывают, но такая функция имеется в стандартной библиотеке, пожалуй, любого высокоуровневого языка программирования. С ее помощью мы находим азимут цели единственной строкой azimuth=math.atan2(x, -z). Осталось только выполнить преобразование в градусы, да скорректировать возвращаемый диапазон углов c [-180,+180] на принимаемый турелью [0..360], с чем мы уже разобрались.
math.atan2(x, y)
Возвращает арктангенс x/y (в радианах), но использует знаки обоих параметров для вычисления «четверти» на плоскости. (Также корректно обрабатывает случай когда y равен нулю.)
Теперь надо правильно заполнить аргументы функции atan2. Для этого приведем всё, что у нас имеется, к картинке из школьного учебника.
Во-первых, на картинках в школьном учебнике угол растет при повороте от оси X, к оси Y, и тангенс угла вычисляется как tg(α) = y/x.
В справочнике же к atan2 указаны аргументы atan2(x, y) для вычисления арктангенса x/y. То есть, нам следует поменять аргументы местами. Имеем: math.atan2(y, x)
Теперь разберемся с координатами мира Майнкрафта, положением турели, и тоже приведем их к картинке из школьного учебника. Сначала нарисуем координаты Майнкрафта при обращении лицом на север, вид сверху. Ось X направлена на восток, ось Z – на юг. Азимут поворота турели отсчитывается от северного направления по часовой стрелке.
Прошу простить мне изображение угла прямой линией, а не дугой. Надеюсь, это не сильно помешает пониманию выполненных преобразований.
X, Z – координаты мира Майнкрафта;
R – вектор на цель;
α – небольшой положительный угол между нулевым положением турели и вектором на цель.
На первом рисунке изображены исходные координаты майна и поворота турели.
На втором – поворот рисунка на 90˚ по часовой стрелке.
На третьем – отражение рисунка по вертикали (как бы взгляд на плоскость карты не сверху, а снизу, из-под земли). В принципе, можно было бы обойтись без второго рисунка, отразив первый по диагонали, идущей из правого верхнего угла, но для улучшения восприятия я привел оба рисунка.
На четвертом рисунке выполняется инверсия оси Z.
Важно понять, что от всех этих преобразований координаты совершенно не меняются, меняется лишь их представление. И вообще следует помнить, что координаты не существуют в реальности и являются лишь математической абстракцией, которую легко можно вывернуть наизнанку в отличие от реальных объектов. Как ни вращай мир Майнкрафта на рисунках, он от этого не сдвинется и не изменится. Меняется лишь твоя точка зрения, но она-то и позволяет тебе упростить программу, избавившись от бесполезных вычислений.
Все совершённые преобразования были нужны лишь для наглядности, и из них можно вывести более простое правило. Тригонометрия из школьного учебника основана на росте угла от оси X к оси Y. Но аналогичные формулы применимы при росте угла от оси -Z к оси X при соответствующих заменах в формулах. То есть, надо всего лишь знать от какой оси начинается рост угла и к какой оси происходит движение.
В результате выполненных преобразований ты можешь легко заметить, что координаты из учебника (x,y) соответствуют координатам Майнкрафта (-z,x).
В нашем случае:
sin(α) = y/r → sin(α) = x/rcos(α) = x/r → cos(α) = -z/rtg(α) = y/x → tg(α) = x/-z
Таким образом наш код приобретает вид: math.atan2(x, -z)
Осталось лишь преобразовать радианы в градусы и нормализовать их в диапазоне [0..360]: azimuth=math.deg(math.atan2(x,-z))%360
Аналогичным образом вычисляется и угол места с той разницей, что ему не требуется нормализация. Вращать координаты тоже не надо. Но есть небольшой нюанс: угол места вычисляется относительно горизонтальной плоскости, для чего требуется найти расстояние до цели по горизонтали, и оно легко вычисляется по теореме Пифагора:
Теперь тело функции, вычисляющей углы направления турели, умещается в три строки.
local azimuth=math.deg(math.atan2(x,-z))%360local elevation=math.deg(math.atan2(y,math.sqrt(x*x+z*z)))return azimuth, elevation
Или даже в одну, если не создавать промежуточные переменные и сразу возвращать результат.
Вот так благодаря математике мы смогли сократить код программы на полтора десятка строк, а заодно и ускорили программу, избавившись от лишних вычислений. Кроме того сам код стал более понятным и наглядным.
Не спеши кодить, подумай о математике, брат
-
13
15 комментариев
Рекомендуемые комментарии