Лидеры

Методика ускоренного вычисления константы шума геосканера Предлагаю ознакомиться с методикой, позволяющий максимально быстро и абсолютно точно вычислить константу шума геосканера (geolyzerNoise в config/OpenComputers.cfg). Методика и скрипты тестировались в среде OpenComputers-MC1.7.10-1.7.5.1290-universal.jar. Сохранит ли эта методика свою актуальность в будущем, вселцело зависит от авторов мода. Зачем знать константу шума геосканера? Не на всех серверах параметр geolyzerNoise сохраняет значение по умолчанию. Алгоритмы же поиска руд, использующие для своей работы геосканер, в большинстве своём эффективны лишь при определённых параметрах шума. При увеличении или уменьшении зашумлённости будут эффективны другие алгоритмы. Поэтому знание точных параметров шума геосканера поможет использовать наиболее эффективные алгоритмы поиска руд на конкретном сервере в конкретных условиях шума. Традиционный алгоритм Традиционный алгоритм использует выполнение многократного сканирования плотности блока, поиск минимального и максимального значений и вычисление разницы между ними. Плюсом алгоритма является его простота. Минусом является низкая точность. Для повышения точности используется увеличение кратности сканирования, но даже очень большая кратность не даёт гарантии абсолютной точности. Всегда есть небольшой шанс, что шум окажется немного больше найденного алгоритмом. Дискретная структура шума Как было обнаружено в недавнем обсуждении про вычисление погрешности геосканера, шум имеет дискретную природу. Согласно коду OpenComputers для каждого из сканируемых расстояний существует 256 возможных значений шума. Знание этого факта позволяет нам считать результат достигнутым, как только сканер выдаст 256 уникальных значений плотности одного и того же блока. Плюсом такого подхода будет абсолютная точность. Главный же минус заключается в том, что получение всех 256 значений может занять даже больше времени, чем получение реальных минимума и максимума плотности. В моих экспериментах на получение всех 256 значений уходит примерно 10-20k попыток сканирования. Вот скрипт для наглядности: -- демонстрация: шум геосканера имеет 256 фиксированных значений -- установка: любой блок, сверху блок геосканера, на него спавним комп /oc_sc local scan = require'component'.geolyzer.scan local uniqTbl = {} local uniqCnt = 0 local v for i=1,1e4 do v = scan(0,0,-1, 1,1,1)[1] if not uniqTbl[v] then uniqTbl[v] = true uniqCnt = uniqCnt + 1 print(("try: %d, uniqCnt: %d"):format( i, uniqCnt )) end os.sleep(0) -- ^C для останова end Наблюдая за скриптом, легко заметить, как медленно добираются последние из оставшихся уникальных значений. Алгоритм абсолютно точен, но неоптимален. Оптимизация поиска Оптимизировать вычисления нам поможет знание о том, что все 256 значений шума расположены равномерно, расстояния между смежными значениями одинаковы, и они ровно в 256 раз меньше расстояния между максимальным и минимальным из значений. В пределах погрешности вычислений, разумеется. Это значит, что для вычисления константы шума достаточно найти любые два смежных значения и вычислить разницу между ними. Но смежными эти значения должны быть в своей полной таблице из 256 значений, в то время как в целях оптимизации рабочая таблица должна быть заполнена как можно меньшим количеством данных, и поэтому соседство значений в рабочей таблице не означает обязательности их соседства в полной. Уменьшать количество значений в рабочей таблице следует ровно до того момента, пока это не мешает обнаружению двух смежных значений. Можно сказать и наоборот: пополнять таблицу новыми значениями следует ровно до тех пор, пока смежные значения не удаётся обнаружить с абсолютной точностью. Самое очевидное, что приходит в голову, это набрать ровно 129 уникальных значений, и найти среди них ближайших соседей. Почему 129, а не 128? Потому что при 128 уникальных значениях возможна редкая ситуация, когда эти найденные значения находятся в полной таблице ровно через одно. Это маловероятно, но возможно. Зачем рисковать? Тем более, 129 элементов почти всегда находятся примерно за 200 попыток сканирований, что можно увидеть, наблюдая за работой демонстрационного скрипта. Но внимательный читатель наверняка заметит, что может быть достаточно использовать и 128 значений при условии, что они размещены неравномерно относительно друг друга. Почти всегда 129-ое значение оказывается необязательным. И если развить эту мысль, то выяснится, что и 127 значений почти всегда будет достаточно при введении дополнительных условий. Тем же путём можно перейти к 126 значениям и т.д. В итоге окажется, что роль играет не равномерность расположения значений относительно друг друга, а расстояние между крайними элементами и между двумя ближайшими. А для этой цели может быть достаточно даже трёх найденных значений. В лучшем случае. Но в худшем могут потребоваться и все 129 значений. Оптимальный алгоритм В общем виде алгоритм сводится к циклическому получению очередного значения от геосканера и поиску разницы между всеми найденными значениями. И если соотношение максимальной разницы к минимальной превысит 128, то результат достигнут: минимальная разница между найденными значениями обязана быть равной разнице между смежными значениями в полной таблице. Результатом умножения минимальной разницы на 128*33 будет искомая нами константа geolyzerNoise из файла конфигурации. Результирующий код может выглядеть, например, так: -- измеритель шума геосканера (константы geolyzerNoise в config/OpenComputers.cfg) -- установка: любой блок, сверху блок геосканера, на него спавним комп /oc_sc local abs = require'math'.abs local scan = require'component'.geolyzer.scan -- округление до сотых долей для сокрытия погрешностей local function round( v ) return (v*1e2+0.5)//1/1e2 end -- множитель для восстановления значения шума до справочного local mul = 128*33 local uniqTbl = {} local uniqCnt = 0 -- текущее значение, разница с другим значением, минимальная и максимальная разница local val, dif, min, max -- флаг обновления экстремумов local fUpd for i=1,99 do os.sleep(0) val = scan(0,0,-1, 1,1,1)[1] fUpd = false -- обрабатывать только новые уникальные значения if not uniqTbl[val] then -- обновить информацию о минимальной и максимальной разнице for v,_ in pairs(uniqTbl) do dif = abs( val-v ) if not min or min>dif then min=dif fUpd=true end if not max or max<dif then max=dif fUpd=true end end -- пополнить таблицу уникальных значений uniqTbl[val] = true uniqCnt = uniqCnt + 1 end -- при обновлении вывести информацию на экран if fUpd then print(("uniq:%2d/%2d | min:%7.3f | max:%7.3f | max/min:%7.3f"):format( uniqCnt,i, round(min*mul), round(max*mul), round(max/min) )) end -- закончить по достижении результата if fUpd and max/min > 128 then break end end -- сообщить результат if fUpd and max/min > 128 then print(("Congratulations! geolyzerNoise = %f"):format( round(min*mul) )) else print("Failure! Tray again please!") end Результат Знание об особенностях генерации шума геосканера, позволило достичь абсолютно точных результатов при очень малом времени сканирования при вычислении константы шума геосканера. В лучшем случае результат можно получить за три сканирования. В типичном случае требуется около 20 сканирований, что требует около одной секунды времени. Самый худший случай не ограничен ничем, но использованное в моём скрипте ограничение в 99 сканирвоаний ни разу не было достигнуто за несколько сотен попыток. И это ещё не всё, что может дать знание о шуме геосканера. Пошумим, брат!

Накопал табличку твёрдости ванильных блоков. Возможно, кому-то будет полезно и кроме меня.

Попробовал написать что-то такое. Сам файл лежит в онлайн-эмуляторе (ocelot.fomalhaut.me) по пути /home/.mt.lua . Вкратце результат: Ocelot Online гораздо лучше соответствует таймингам Minecraft, чем OCEmu. Но в обоих эмуляторах есть баги. Тесты: тест 1 - генерация 10 тысяч псевдослучайных чисел тесты 2-4 - отрисовка случайного текста на экране тест 5 - испытание гуделки случайными звуками (computer.beep) тест 6 - проверка, все ли компоненты имеют методы по документации тест 7 - проверка файловой системы на чтение-запись тест 8 - проверка Интернета тесты 9,10 - проверка сетевой и соединённой карты соответственно тест 11 - проверка EEPROM на чтение-запись Результаты: Minecraft 1.7.10 (компьютер tier 3) тест 1 - 0,05 с тест 2 - 1,3 с (рендер идёт постоянно) тест 3 - 1,8 с тест 4 - 2,5 с тест 5 - 13,5 с тест 6 - без предупреждений тест 7 - предупреждение, что временная файловая система не найдена тест 8 - без предупреждений тест 9 - 1,15 с; предупреждение, что никто на пинг не ответил тест 10 - не проводился (не хватило места для соединённой карточки) тест 11 - 2,2 с Ocelot Online тест 1 - 0,05 с тест 2 - 1,9 с (рендер кусками) тест 3 - 2,65 с тест 4 - 3,7 с тест 5 - 13,5 с тест 6 - без предупреждений тест 7 - предупреждение, что временная файловая система не найдена; (баг эмулятора) на unmanaged диск ничего не записывается тест 8 - без предупреждений тест 9, 10 - не проводились тест 11 - 2,2 с OCEmu тест 1 - 0,02 с тест 2 - 0,37 с (рендер после coroutine.yield) тест 3 - 0,43 с тест 4 - 0,91 с тест 5 - 4,58 с тест 6 - без предупреждений тест 7 - предупреждение, что временная файловая система не найдена тест 8 - без предупреждений тест 9 - 1 с; (баг OCEmu) модем поймал своё сообщение тест 10 - не проводился тест 11 - 0,001 с Награду попрошу отдать на дальнейшую разработку Ocelot и фиксы багов.

Провел эксперимент, в котором нашел зависимость погрешности геосканера от расстояния между самим сканером и сканируемым блоком. Результаты Максимальная погрешность NMax строго пропорциональна расстоянию R, которую можно вычислить по формуле NMax = R/16.5 (более точный вариант: NMax = R*0.0606 - товарищи посмотрели в код и подсказали). При любом расположении сканируемого блока в зоне видимости сканера 65*65*64 (сканер находится в центре) расстояние можно вычислить по формуле: R = x^2 + y^2 + (z - 33)^2, где x и y - координаты сканируемого столба относительно сканера, а z - номер элемента в таблице, которую возвращает сканер. Применение Знание максимальной погрешности NMax для данного R позволяет нам рассчитать максимальное расстояние, на котором данным методом возможно первым же сканированием гарантированно отличить два блока с твердостями P1 и P2. Для этого требуется вычислить максимально допустимый шум N, при котором полученные со сканера значения точно не будут пересекаться. Получаем неравенство: P1 + N < P2 - N, имеем: N < (P2 - P1)/2. В итоге R = (P2 - P1)/(2*0.0606). Пример применения Допустим, мы хотим робота, добывающего нам алмазы. Для ускорения процесса средствами геосканера отличаем алмазную руду от камня, чтобы не тратить слишком много времени на его выкапывание. Дополнительное время могут занимать и лишние перемещения робота, а значит робот должен не путать руду с камнем и сканировать как можно большую площадь вокруг себя, следовательно подходящей фигурой для области сканирования будет цилиндр. Чтобы узнать его радиус и высоту, нужно узнать радиус описанной вокруг него сферы. Воспользуемся описанным выше методом: R = (3 - 1,5)/(2*0.0606) = 12.376 Алмазы генерируются до 16 высоты, а бедрок - до 5. Если руда не заспавнилась на 3 высоте, ниже копать скорее всего нечего. Отсюда высота цилиндра H = 16 - 3 = 13 блоков. Тогда максимальное расстояние до края цилиндра по вертикали h = (H - 1)/2. За теоремой Пифагора найдем радиус цилиндра r = (R^2 - h^2)^(1/2). Тогда за той же теоремой получаем, что r^2 = x^2 + y^2, где x и y - максимальные координаты сканирования относительно геосканера. Так мы узнаем, до каких x и y мы можем со 100% точностью отличить алмазную руду от камня. Сам эксперимент 1. Создавался кубоид 65*65*64 из обсидиана, так как это максимальная зона сканирования для геосканера. 2. Запихнул робота с геосканером в центр по горизонтали, на 33-ий блок по счету снизу по вертикали (можно было создать 33*33*33 и запихнуть робота в угол, но тогда надо будет определять, в какую сторону сканировать). 3. Загрузил в него с помощью дискеты программу, имеющую функцию "scan", которая многогратно сканирует один и тот же блок в определенных координатах, возвращает среднюю, минимальную и максимальную погрешность. local component = require "component" local io = require "io" local geolyzer = component.geolyzer local path = "/home/geoScanData.txt" local accuracy = 10 local hardness = geolyzer.analyze(3).hardness local radius = 32 local average, min, max = {}, {}, {} local function compareData (scanData, sum, min, max) local lMin, lMax = min, max if scanData < min then lMin = scanData end if scanData > max then lMax = scanData end return sum + scanData, lMin, lMax end local function scan(x, y, zMin, zMax, hardness, accuracy) local sum, min, max = 0, 2, 0 for i = 1, accuracy do local scanData = geolyzer.scan(x, y) for j = zMin, zMax do sum, min, max = compareData(math.abs(scanData[j]-hardness), sum, min, max) end end return sum/(accuracy*(zMax-zMin+1)), min, max end local function DGN(k, radius, x, y, z, hardness, accuracy) for i = 1, radius do average[i+k], min[i+k], max[i+k] = scan(i*x, i*y, 33-i*z, 33-i*z, hardness, accuracy) print(average[i+k].."\n"..min[i+k].."\n"..max[i+k].."\n"..i.."/"..radius.."/"..x+y+z.."\n") end end DGN(0, radius, 1, 0, 0, hardness, accuracy) DGN(radius, radius, 1, 1, 0, hardness, accuracy) DGN(radius*2, radius, 1, 1, 1, hardness, accuracy) print("Done!") file = io.open(path, "w") local len = #average for i = 1, len do file:write(average[i].."\n") end file:write("\n") for i = 1, len do file:write(min[i].."\n") end file:write("\n") for i = 1, len do file:write(max[i].."\n") end file:write("\n") io.close() Три вызова функции "DGN" вызывают функцию "scan" по порядку для каждого блока по определенной линии от робота до края кубоида. На изображении ниже робот находится в углу, а сканируемые блоки для первого, второго и третьего вызова окрашены в цвета, соответствующие окраскам номеров вызовов. Это сделано для того, чтобы проверить, можно ли вычислять расстояние до блока описанными выше формулами, влияет ли отклонение по нескольким осям на результат. В первом вызове проверяются блоки отдаленные только по одной оси, во втором - по двум, в третьем - по трем. Потом программа сохраняет все результаты в файл, после чего я ввожу данные в excel: GeolyzerNoise.xlsx. Первый график показывает зависимость максимальной погрешности от расстояния для 500 сканирований каждого блока. Таким образом расстояние до блока можно вычислять по указанной ранее формулой, результат не зависит от количества осей, по которым блок смещен относительно сканера. Отсюда я и получил константу 1/16.5 Второй график показывает то же самое для средних значений. Еще на нем видно, что даже 30 сканирований дают очень низкую точность, по этому вычислять твердость средним арифметическом невыгодно по затратам времени и энергии. Третий график показывает, что средняя арифметическая погрешность приблизительно в два раза меньше максимальной. Сам не знаю что с этим делать.