Перейти к содержимому

eutomatic blog

  • записей
    10
  • комментариев
    57
  • просмотров
    34 015

Математика в Майнкрафте

eu_tomat

5 814 просмотра

Здравствуй, брат автоматизатор.

Надеюсь, ты помнишь, что всеми нами любимый брат 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) не сошелся свет клином на всем известных со школы синусах, косинусах и тангенсах. Уделив несколько минут чтению списка математических функций, можно обнаружить такую красоту:


math.atan2(x, y)
Возвращает арктангенс x/y (в радианах), но использует знаки обоих параметров для вычисления «четверти» на плоскости. (Также корректно обрабатывает случай когда y равен нулю.)
В геометрии об этом не рассказывают, но такая функция имеется в стандартной библиотеке, пожалуй, любого высокоуровневого языка программирования. С ее помощью мы находим азимут цели единственной строкой 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 – на юг. Азимут поворота турели отсчитывается от северного направления по часовой стрелке.
blogentry-13296-0-64746300-1456004244_thumb.png
Прошу простить мне изображение угла прямой линией, а не дугой. Надеюсь, это не сильно помешает пониманию выполненных преобразований.

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


Аналогичным образом вычисляется и угол места с той разницей, что ему не требуется нормализация. Вращать координаты тоже не надо. Но есть небольшой нюанс: угол места вычисляется относительно горизонтальной плоскости, для чего требуется найти расстояние до цели по горизонтали, и оно легко вычисляется по теореме Пифагора:
blogentry-13296-0-72447800-1456004250_thumb.png
Теперь тело функции, вычисляющей углы направления турели, умещается в три строки.

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 комментариев


Рекомендуемые комментарии

О, моя костыльная функция для робота.

Даже три функции. Твой код меня поразил еще летом, но тогда я внезапно выпал из проекта.

Сейчас же твой код пришелся очень кстати. Шедевральная избыточность.

Поделиться комментарием


Ссылка на комментарий

Даже три функции. Твой код меня поразил еще летом, но тогда я внезапно выпал из проекта.

Сейчас же твой код пришелся очень кстати. Шедевральная избыточность.

А может он, избыточностью - помехоустойчивость улучшал ? :D

Поделиться комментарием


Ссылка на комментарий

А может он, избыточностью - помехоустойчивость улучшал ? :D

Жизнь – борьба. Одни создают помехоустойчивый код, другие его расшатывают.

Поделиться комментарием


Ссылка на комментарий

На самом деле дельные советы по математике (ведь мои знания математики увы остались на уровне 9 класса и дальше не развивались), а так же моя самая ненавистная тема была тригонометрия. Кроме того что я лишь любитель, а не специалист в математике, то я ради математических экспериментов влез в программирование. Наверное для того чтобы найти практическое применение моего любимого предмета. И в программировании я так же не мастер, а лишь любитель. И конечно же не знал всяких хитроумных применений оператора % который не разу не юзал. Спасибо что рассказал про оптимизацию кода, довольно полезно узнать что то новое.

 

Но неужели была такая необходимость расписывать длиннопост и повторять то что уже ранее говорил в чате? Так и хочется сказать - это баян. Но сейчас речь не об этом.

 

Странно было сравнивать мой код где я нубил в математике, с кодом где нубят в программировании. К чему это??? Я смотрел чужой код чтобы обучится оптимизации кода и не пишу подобных костылей.

 

И самое интересное. Ты докапываешься ко всем подряд прогам. Может уже начнёшь выкладывать свои на форум? Я вообще не в курсе пишешь ли ты проги, такое ощущение что ты только как обсуждать проги ничего и не можешь.

 

На будущее, раз тебе так нравится докапываться к чужому коду, то посмотри код моей игры Cube. Вот он: http://computercraft.ru/topic/1378-igra-kvantovyi-labirint-kvantovyi-kub-os/ Воттам реально походу нужна оптимизация. Хотя всё и работает как надо, у меня остаётся ощущение что там возможно что то оптимизировать. Так ли это и что можно оптимизировать посмотри.

 

P.S. и не пали мои бэкдоры плз. (если найдёшь)

Поделиться комментарием


Ссылка на комментарий

Но неужели была такая необходимость расписывать длиннопост и повторять то что уже ранее говорил в чате? Так и хочется сказать - это баян.

Ссылочкой на баян поделишься? В твоей теме я выложил результат, здесь же объяснил, как его достичь. Там же я пообещал выложить этот текст, и лайки, оставленные под обещанием, говорят, что необходимость есть.

 

Странно было сравнивать мой код где я нубил в математике, с кодом где нубят в программировании. К чему это??? Я смотрел чужой код чтобы обучится оптимизации кода и не пишу подобных костылей.

К чему это? К тому, что кодеров много, а ошибки одинаковые. Не ты первый, не ты последний. Подчистишь код, и все узреют его великолепие. Программирование очень тесно связано с математикой, не всегда можно отделить одно от другого, и оптимизация должна выполнятся на всех этапах. Если ты пренебрегаешь логикой и математикой, твой алгоритм будет плохим изначально, и даже виртуозное владение прикладным языком ему не поможет. Но и пренебрежение языком тоже способно сильно ухудшить готовый результат. Математика в алгоритме, математика в коде — все это говорит о том, что твоя программа написана в спешке, об этом мой пост. Про использование pcall, например, я не стал говорить. Может, потом расскажу, если буду часто видеть подобное.

 

И самое интересное. Ты докапываешься ко всем подряд прогам. Может уже начнёшь выкладывать свои на форум? Я вообще не в курсе пишешь ли ты проги, такое ощущение что ты только как обсуждать проги ничего и не можешь.

Неужели этот вопрос и вправду интересует тебя больше всего? Пишу ли я программы, играю ли я на сервере – это ни имеет никакого отношения к данному тексту. Как и все люди, я делаю, что могу, а что не могу – не делаю. Я даже в сингл редко захожу. А чтобы писать программы, требуется владение предметом.

Кстати, именно поэтому я и не докапываюсь, как ты выразился, «до всех программ» – у меня просто нет времени на изучение их всех. Мало прочитать код, требуется еще понимать механику Майнкрафта и модов. Кроме того, есть вещи, которые меня вообще не интересуют. Например, темы мини-игр, декора или графики я бегло просматриваю, просто пытаясь понять, что там обсуждается, и зачем оно нужно. Не понял – прохожу мимо. Да простит меня твой Cube, но и он меня не заинтересовал, я не знаю, зачем он нужен, и мне даже в голову не приходило заглянуть в его код.

 

Еще раз посмотри, до каких программ я докапывался: либо там откровенный тупняк новичка в десятке строк, либо меня заинтересовала идея программы, и в этом случае я готов читать код.

Так что, Cube пройдет мимо, не обижайся. Внезапно увлекшись турелями, я и так отложил рыбалку Asior'а, а там еще есть, с чем разобраться. Сам Asior не спешит с правками, поэтому поле свободно. Далее на очереди Quant с его модемом на редстоуне. Что поделать, тащат меня эти штуки. До них-то я и докопаюсь. Еще хочу докопаться до геошахтера Артема, но т. к. его самого уже нет на проекте, мне будет проще самому всё написать с нуля от логики до реализации. Вот, тогда-то ты и погрызешь мой код. А пока я буду всех радовать иными формами творчества.

 

P.S. и не пали мои бэкдоры плз. (если найдёшь)

Твори добро, брат, и тогда никто не помешает тебе дюпнуть чемодан с иридием.

Поделиться комментарием


Ссылка на комментарий

 

 

Про использование pcall, например, я не стал говорить. Может, потом расскажу, если буду часто видеть подобное.

Он используется чтобы комп не отрубался, когда сканер ищет координаты игрока/моба по нику/id, но не находит в радиусе действия. Баг сканера видимо. Прога просто отрубается с ошибкой что не найден игрок/моб, вместо того чтобы возвращать nil и продолжать работать.

Как по мне, так это странно что мод именно так работает.

 

 

Математика в алгоритме, математика в коде — все это говорит о том, что твоя программа написана в спешке, об этом мой пост.

Вообще так и было. Это же бета версия. Поторопился в первые дни после выхода мода запилить ПО для турели пока никто до меня это не сделал. Выложил сырую бета версию. Как в прочем и с играми сделал, их я тоже изначально сырыми выкладывал, чтобы игроки могли посмотреть над чем я работаю. А потом допиливал до полноценной первой версии.

Поделиться комментарием


Ссылка на комментарий

Он используется чтобы комп не отрубался, когда сканер ищет координаты игрока/моба по нику/id, но не находит в радиусе действия. Баг сканера видимо. Прога просто отрубается с ошибкой что не найден игрок/моб, вместо того чтобы возвращать nil и продолжать работать.

Как по мне, так это странно что мод именно так работает.

OpenPeripheral? Тогда это баг вашего мозга.

Поделиться комментарием


Ссылка на комментарий
OpenPeripheral? Тогда это баг вашего мозга.

 

Чего вы налетели-то на парня? Кодит себе человек спокойно - и пусть кодит, через некоторое время проведет работу над ошибками и начнет писать более красивый код, откуда столько агрессии, злости? Шли бы лучше сами что-то годное наскриптили, выложили бы на форум, а мы бы пообсуждали - и мир стал бы чуточку прекраснее.

 

К слову, сканер из OpenPeripheral действительно выдает сообщение об ошибке вида error("Entity not found"), тем самым осуществляя принудительный выход из программы. Сомневаюсь, что это баг мода - просто автор так задумал. Ну, а если вы знаете другой способ решения данной проблемы, кроме как использовать pcall, то расскажите людям с "багованным мозгом", интересно будет узнать.

Поделиться комментарием


Ссылка на комментарий

Чего вы налетели-то на парня? Кодит себе человек спокойно - и пусть кодит, через некоторое время проведет работу над ошибками и начнет писать более красивый код, откуда столько агрессии, злости? Шли бы лучше сами что-то годное наскриптили, выложили бы на форум, а мы бы пообсуждали - и мир стал бы чуточку прекраснее.

 

К слову, сканер из OpenPeripheral действительно выдает сообщение об ошибке вида error("Entity not found"), тем самым осуществляя принудительный выход из программы. Сомневаюсь, что это баг мода - просто автор так задумал. Ну, а если вы знаете другой способ решения данной проблемы, кроме как использовать pcall, то расскажите людям с "багованным мозгом", интересно будет узнать.

Preconditions.checkNotNull(mob, DONT_EVER_CHANGE_THIS_TEXT_OTHERWISE_YOU_WILL_RUIN_EVERYTHING);.

private static final String DONT_EVER_CHANGE_THIS_TEXT_OTHERWISE_YOU_WILL_RUIN_EVERYTHING = "Entity not found";.

Действительно, поторопился, прошу простить. Перед тем ответом читнул исходный код по-диагонали, но из-за странной надписи ДОНТЕВЕРЧАНЖЗИЗТЕКСТ не заметил.

 

 

 

другой способ решения данной проблемы

xpcall .-.

Ну вообще, да, только пиколлом тогда.

 

 

 

Чего вы налетели-то на парня? Кодит себе человек спокойно

Вот именно, что он не спокойно кодит, а флудит и хейтерит.

Поделиться комментарием


Ссылка на комментарий
Preconditions.checkNotNull(mob, DONT_EVER_CHANGE_THIS_TEXT_OTHERWISE_YOU_WILL_RUIN_EVERYTHING);. private static final String DONT_EVER_CHANGE_THIS_TEXT_OTHERWISE_YOU_WILL_RUIN_EVERYTHING = "Entity not found";

 

М-м-м, какой красивый код! Добросовестного и грамотного программиста видно издалека :D

Поделиться комментарием


Ссылка на комментарий

@eu_tomat можешь, пожалуйста, в статьях пофиксить \n, слетевшие после обновлений форума несколько лет назад? Кинул человеку статью эту почитать, а тут всё слилось в однострочники.

Поделиться комментарием


Ссылка на комментарий
Гость
Добавить комментарий...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...