eu_tomat

Писать программу на двух носителях я бы тоже не стал: закинул бы стандартный LuaBIOS, да разместил свой код в init.lua. Полностью готовых алгоритмов у меня нет, и сейчас я могу поделиться лишь набросками. Если и будет что-то готовое, то, скорее всего, не в виде копалок, а в виде таблицы руд на входе и алгоритма расчёта движений. Теперь о задаче коммивояжёра. Наш робот когда-то решал эту задачу послойной копкой, но неоптимально. Потом @artem211 оптимизировал перемещения, используя жадный алгоритм, который сейчас применяешь и ты. Логично предположить, что возможна и другая оптимизация. Идеал за разумное время, разумеется, недостижим, но достижимы лучшие эвристики. Вопрос лишь в том, насколько очередная эвристика хороша. Подробнее: Да, Монте-Карло очень компактен, это его единственное достоинство. Его логическим продолжением являются генетические алгоритмы, обладающие лучшей сходимостью. В ГА сложен не программный код, а поиск удачного способа кодирования генома. На данный момент я так и не нашёл идеального способа кодирования последовательностей: либо мутация в одном из генов вызывает цепную реакцию вторичных мутаций, либо один и тот же ген в разных последовательностях несёт разный смысл, что лишает ГА преимуществ в сравнении со случайным подбором. На данный момент лучшее, что я смог придумать на этой основе, оперирование одним мутирующим геномом. Мутация сводится к переворачиванию одного случайного участка цепи, изначально построенной жадным алгоритмом. Эффективность не проверялась, но это всяко эффективнее бездумного применения Монте-Карло. Более сходимым мне кажется муравьиный алгоритм. Он тоже легко реализуется, но требует много памяти в процессе работы. Подбор оптимальных коэффициентов под нашу задачу требует труда на этапе исследований. Оптимальным решением мне видится такой: составляем кратчайший маршрут жадным алгоритмом, потом прогоняем итерацию (или несколько, тут надо подумать) всех муравьёв, и отбираем лучший результат. Сравниваем его с текущим, вычисляем сэкономленное время со временем вычислений. При наличии выгоды повторяем цикл, пока в очередном цикле выгода не станет отрицательной. Продолжительность каждого цикла итераций не велика, и небольшой уход в минус на последнем шаге не сильно испортит статистику. Впрочем, минус на текущем шаге не означает плюса на следующем, но есть тенденция к постепенному уменьшению выгоды, а переход через ноль является хорошим индикатором. Примерный маршрут проложен. Теперь можно уточнить конкретные движения робота. Начать можно с наиболее очевидных оптимизаций. Например, если робот должен переместиться на северовосток, и сейчас он ориентирован на север или запад, то движение в северном направлении следует осуществить до поворота на восток. Если робот ориентирован на восток или юг, то начинать нужно с восточного направления. Если можно добыть блок, не перемещаясь в него, то следует остановиться в ближайшем смежном блоке, т.к. есть шанс необходимости возврата робота назад. Кстати, ближайших смежных блоков может существовать до трёх штук, и это знание нам пригодится чуть позже. Далее труднее. Можно оптимизировать добычу нескольких ближайших в цепочке целей, особенно целей в общем кластере. Если кластер крупный, то не будет лишним отобрать несколько ближайших целей и полным перебором найти наилучший путь к некоторым из них. Добыв первый блок из этого набора, а также попутные блоки, можно определить следующие ближайшие цели, построить новый маршрут и снова добыть блок. Например, можно выбрать все цели, расположенные не далее 5 блоков и перебрать все тройки блоков из этого набора. А может, и вообще не надо никаких муравьёв. Будем, например, тупо выбирать не один самый близкий блок, а несколько (три вполне реально) и так же тупо выполнять полный перебор для их добычи, находя блок-лидер и смежный к нему блок, из которого робот сможет его добыть. После добычи блока-лидера и сопутствующих по пути блоков снова повторяется отбор наиболее близких целей для робота в текущей позиции. Интересно было бы анализировать куб 5x5x5 вокруг роботом, это позволило бы при необходимости копать очень эффективно, но полный перебор в этом случае затруднён. Тут нужен новый трюк. Также нужно помнить, что глубокая оптимизация при перемещении между кластерами не принесёт большой пользы. Зато в плотном кластере оптимизацией можно выйти на эффективнность копки трёх блоков за одно движение. Обожаю Майнкрафт за такие задачи. А казалось бы, простая игра для детишек.

Зря ты передёргиваешь. Копать весь чанк слоем через два я не предлагал. Считаю, что текущий жадный алгоритм можно улучшить, вложив часть времени в расчёты. TLWY вообще не помеха, Монте-Карло не самый лучший алгоритм решения задачи коммивояжёра, есть алгоритмы с лучшей сходимостью, в которых на каждой итерации возможно сравнение затраченного и сэкономленного времени, чтобы не доводить процесс оптимизации до абсурда. А раздутие кода мне кажется самым неудачным из аргументов. Как по мне, проще добавить ещё один апргейд инвентаря и выбросить алгоритм упаковки, впихнув на его место оптимизацию пути. Да и жёсткий диск можно впихнуть. Или загружать программу с планшета. Но это уже вкусовщина, и вопрос лишь в том, на каком решении интереснее лично тебе сосредоточиться, и интересно ли тебе видеть в комментариях к этой записи блога альтернативные идеи.

Похоже, не будет оно копать слой через два. Если только в редком случае, когда робот подойдёт к пласту сбоку, ровно по центру. В остальных, может быть, удастся срезать по два слоя и то, в лучших случаях. Штрафами такое не исправить. Я тут попытался хоть как-то решить задачу поиска оптимального пути, но количество рудных блоков в чанке около 600 штук в сочетании с ограничениями на максимальный объём памяти не позволяют приблизиться к решению. Но я выполнил кластеризацию, и количество объектов уменьшилось до 75 с максимальным количеством до 35 блоков. А это уже реальная задача оптимизации.

@Doob, я поспешил с плотностью алмаза. Сейчас посмотрел твою таблицу плотностей, и даже не поверил. Запустил Майн, проверил. Таблица верна. То ли Алекс накрутил плотность в одной из старых сборок, то ли мне это приснилось. Я был уверен, что алмаз имел более высокую плотность, чем другие руды, а уран с большим отрывом имел плотность 9 или около того.

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

Именно так. robot.swing() в библиотеке копает только вперёд, а для копки вверх и вниз имеются robot.swingUp() и robot.swingDown(). Компонент же располагает единственной функцией, направление задаётся аргументом.

Наиболее интересной мне показалась эта идея: Хорошая эвристика. В идеале хорошо было бы найти такие штрафы на перемещения во вертикали (а также на повороты), чтобы при плотном расположении руд робот перемещался по кластеру как в классической копалке "слой через два". Мои идеи в этом направлении пока что сводятся к увеличению глубины поиска ближайших целей.

Спасибо за пояснения, основные идеи понятны. Далее я сосредоточусь на менее однозначных моментах. На определённом этапе игры основной интерес для игрока могут представлять только уран и алмазы, имеющие высокую плотность. Причём, алмазы чаще всего востребованы в мультиплеере как наиболее ценная валюта сервера. А уран как источник энергии востребован почти всегда и везде, а иногда и как валюта. В общем, "выковыривание изюма" может иметь смысл. Тогда даже многократное дальнее сканирование может окупиться экономией времени. А так как количество найденных узлов не велико, то может окупиться даже алгоритм более сложный чем "идти к ближайшему блоку". Как видишь, везде своя специфика. Что накрутит админ, это проблема игроков, адаптирующих свои алгоритмы. Тут не всё однозначно. С одной стороны, некоторые правки конфигов затрудняют внедрение роботов, что становится проблемой. А другие же правки конфигов вынуждают программистов искать новые алгоритмы, что повышает их интерес к игре. При разработке более-менее универсальной копалки полезно иметь в виду весь спектр сценариев. Идеальную копалку на все случаи жизни вряд ли удастся создать, зато можно оговорить граничные условия её применения. Бывает и так, тут наши интересы не сошлись. Упаковщик оказался для меня наименее интересным аспектом твоей копалки, и я, по правде говоря, читал про него очень быстро и невнимательно. Меня больше интересуют алгоритмы сканирования и оптимальной копки. Попробую почитать внимательнее, но хороших идей не обещаю.

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

Если в инструкции написать, что робота всегда нужно ставить на блок и ни в коем случае не прилеплять его к потолку или стене, то будет работать, как и задумано. Иначе блока снизу может и не оказаться, и тогда энергозатраты на взмах киркой будут околонулевыми. Что нарушит всю точность.

Библиотека robot и компонент robot несколько отличаются. При использовании компонента в вызове robot.swing(3) следует указывать сторону, как в коде @Doob

Понятно, что потом всё учтётся. Но чтобы потом учесть, надо сначала измерить. При взмахах не только инструмент теряет заряд/прочность. Робот при взмахах тоже тратит некоторое количество своей энергии, но какое именно, на данном этапе неизвестно.

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

Сейчас сканирования, конечно, экономятся, но при отсутствии блоков робот всё равно уходит в бесконечный цикл вращения.

Возможно, речь идёт о нашем сервере EvilWorld. Если нет, то имеет смысл уточнить версию Minecraft и OpenComputers. По тому выводу на экран, что есть в программе, можно говорить лишь о значении переменной TimeOut в этом конкретном месте. И точно невозможно сказать, отличалось ли значение от нуля, например, перед этим участком: if (computer.uptime() - timestamp > TimeOut) and (TimeOut > 0) then ... ShowMenu(); А здесь переменная как раз и могла обнулиться. И почему исключается? Каким образом это проверяется? На отрисовку меню могли влиять ошибки в реализации GUI. Предлагаю на время отладки полностью отказаться от GUI и весь вывод переписать на print, или сигналить звуком, например, так: if TimeOut > 0 then computer.beep() end

Интересно будет взглянуть. Придумать концепцию универсальной копалки мне так и не удалось, т.к. каждый мод вносит свою уникальную специфику. Даже уровень шума геосканера сильно влияет на оптимальный стиль копки. А ещё могут внезапно обнаружиться неожиданные препятствия, например, в виде ульев Forestry, непроходимых с помощью бура IC2, как это было с @artem211. Или, например, сейчас на EvilWorld есть шанс запутаться в лабиринте из магического стекла, установленного другими игроками. Работа с инструментами тоже сильно отличается: ванильные, IC2, Tinkers Construct, ThaumCraft – все они производятся, ремонтируются или заряжаются специфическим образом. Я тоже думал про модульную копалку, но так и не смог систематизировать возможности модов. Поэтому с интересом буду следить за твоими успехами. Ограничения EEPROM обхожу следующим образом. Если копалка используется в единственном экземпляре, то, скорее всего, это универсальный, неспециализированный робот, предназначенный не только для копки, и потому имеющий монитор, клавиатуру и диск с системой. Если в копке задействованы одновременно несколько роботов, то для координации их работы в обязательном порядке используется радиоинтерфейс, по которому и загружается программа. Потеря программы при отключении роботов не страшна, т.к. их всё равно приходится будить по вайфайке. Будящему ничто не мешает заодно передать роботам и программу, хоть модулями, хоть одним куском.

Как борешься с шумами?

Это сложнее. Тут появляется множество вариантов, эффективных в своих условиях и при этом неэффективных в других. И какие условия возникли конкретно у тебя, я не знаю. но я попробую объяснить суть проблемы. В случае генератора булыжника есть только один непрерывно добываемый малоценный ресурс. Если сундук находится над или под роботом, то оптимизация сводится к тому, чтобы перемещать ресурсы полными стаками. Робот перемещает хоть один предмет из слота, хоть полный стак за одинаковое время. А это значит, что выгодно перемещать наиболее полный стак. Заполнение слота легко отслеживается. Если сундук находится в стороне, и робот вынужден совершать поворот, то накладные расходы на освобождение инвентаря возрастают, и появляется смысл выгружать полностью заполненный инвентарь. Его заполнение тоже легко отследить. Гораздо больше вопросов вызывает перелопачивание руды киркой. С точки зрения оптимизации действий робота он должен выгружать свой инвентарь, когда хоть-что появится в последнем слоте. А если речь идёт о рудах GT, где может выпасть вторичный ресурс, то сигналом для выгрузки будет появление предмета в предпоследнем слоте. Если заранее знать, какая руда будет ломаться следующей, то в некоторых случаях можно ждать почти полного заполнения слотов с учётом максимального дропа с руды, но в данной схеме это возможно только в случае, если роботы будут обмениваться информацией по сети. Вообще говоря, для этой задачи использование двух роботов неоптимально, т.к. робот обычно ставит блок быстрее, чем его ломает второй, и если хочется повысить производительность, то лучше установить два однотипных робота на одну задачу, где каждый из них как устанавливает блок, так и ломает его. Так робот сам сможет знать, какой дроп ожидать при следующем взмахе киркой, и сможет лучше оптимизировать свою работу. Но тут возникает новый подводный камень. Эта схема удобна в случае огромного количества руды. У неё есть большой потенциал на поздних стадиях уже упомянутого GT. Но в начале игры, когда ресурсов мало, робот будет ждать полного заполнения своего инвентаря, долго не отдавая переработанные ресурсы, что неудобно. Есть компромиссный и при этом довольно эффективный вариант: робот берёт из верхнего сундука стаки руды, начиная от более полных к менее полным. Загрузив стак руды в свой инвентарь, робот устанавливает её перед собой и ломает, повторяя эти действия до полного исчерпания руды. После этого полностью освобождает инвентарь в сундук. некоторые из слотов могут оказаться недостаточно заполненными, и такая выгрузка будет не очень эффективной, но зато ценные ресурсы не будут надолго задерживаться в инвентаре робота и мешать получению других. Выработав стак руды, робот берёт следующий, один из наиболее полных, и продолжает работу, постепенно забирая и слабо заполненные стаки тоже. За время работы робота ресурсы в слотах входного инвентаря могут пополниться, поэтому имеет смысл отложить их использование до поры, пока не появится лучший выбор. Этот вариант тоже можно оптимизировать. В конечном итоге всё зависит от целей. На что должна быть ориентирована твоя программа? На максимальную скорость при быстрой подаче руд? На переработку руд в начале игры, чтобы ресурсы не задерживались в инвентаре робота? Или надо сделать хоть что-то, лишь бы оно работало с помощью максимально примитивного кода? От ответов на эти вопросы будет зависеть алгоритм работы.

А зачем там спойлер? Скриншот вообще не проясняет проблему и может быть безболезненно удалён. По теме: Какое значение имеет параметр bufferChanges?

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

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

Тогда понятно. Шина, стоящая сверху, быстро высасывает инвентарь робота, сразу как только выполнится перенос инструмента в инвентарь с помощью inv.equip(). И перенос инструмента в зарядник с помощью robot.drop() выполниться просто не успевает.

В этой программе я вообще не увидел кода для сброса содержимого инвентаря.

С каким буром? Буры из IC2 вроде без проблем определяются. И какая используется версия OpenComputers?

Для понимания причин проблемы следует для начала прочитать текст ошибки. Можно воспользоваться автоматическим переводчиком. Это поможет понять, что на строке 6 произошла попытка сравнения значения nil с числом, что недопустимо. Глядя на шестую строку, можно заметить условие robot.durability() <= 0.2, где явное число сравнивается с предположительным числом. Но функция может возвратить что-то иное, и, судя по всему, тот самый nil. Теперь следует задаться вопросом, в каком случае может быть возвращено значение nil. Логично предположить, что это возможно либо в случае полного отсутствия предмета в слоте инструмента, либо в слоте находится и не инструмент вовсе, что и подтверждается документацией https://ocdoc.cil.li/api:robot. Для решения проблемы следует либо дать роботу инструмент с ограниченной долговечностью, либо убрать условие проверки долговечности из программы.