Лидеры

Здравствуй, брат автоматизатор. Надеюсь, ты помнишь, что всеми нами любимый брат 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 с этого костыля быстро спрыгнул, и в следующей версии упростил свой код, но поверь мне, брат, на форуме есть много таких костылей, и калеки не спешат с них слезать. Вот, например, фрагмент кода, до которого я уже давно хотел докопаться. Код слишком длинный не только для своего функционала, но и для этой статьи, поэтому я спрячу его в спойлер: Можно ли этот код упростить? Легко. Для начала заменим строки числами, например, по такой схеме: 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], с чем мы уже разобрались. Теперь надо правильно заполнить аргументы функции 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 Или даже в одну, если не создавать промежуточные переменные и сразу возвращать результат. Вот так благодаря математике мы смогли сократить код программы на полтора десятка строк, а заодно и ускорили программу, избавившись от лишних вычислений. Кроме того сам код стал более понятным и наглядным. Не спеши кодить, подумай о математике, брат