Алгоритмирование "рудная жила"

[artem211 428]

  Простите что опять без картинок и проч красивостей(ну не умею я) да и пост сугубо по делу, а не развлеченья для.

 

Так вот, уже второй вечер пытаюсь измыслить новый тип геомайнера, использующего geolyzer.scan(), майнера под geolyzer.analyze()  - уже написал и отладил, пользуюсь, не выкладывал, т.к. народ не считает карьер "1 через 2" с использованием геолайзера оправданным. 

 

К делу: задумал разбивать указанный карьер(ширина,длинна) на кластеры(чанки) 20х20х20(вроде у геолайзера по горизонтали помех нет, потому границы по горизонтали можно так не ограничивать, но это потом решать буду).

 

В общем имеем заданный кластер объемом 20х20х20 блоков, просвеченный геолайзером на предмет руд, по сути имеем 3д массив(может проще будет обычный тейбл с 3 координатами в ячейке, опять же не суть) в данном объеме есть некоторое количество рудных жил, например 5, кататься в цикле к каждому блоку в слое - не рационально вообще никак, будет бегать от одной жилы к другой.

 

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

 

Получается нужно побить массив рудных блоков на несколько групп, в данном случае на 5. Какой избрать алгоритм? Проверить все рудные блоки между собой и все, на расстоянии 0 блоков друг от друга определить в одну жилу? При проверке первый же блок руды кидать в подмассив "жила номер раз" с указанием 3 координат, каждый следующий блок сравнивать по координатам со всеми блоками в во всех жилах, разница соответствующих координат с которыми равна 1  - приписывать найденный блок к этой жиле...хмм может сработать.

 

Есть идеи? Может свой вариант?

 

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

[NEO 541]

От самого верха до низа записать координаты, и пройтись по ним.

[artem211 Автор вопроса 428]

От самого верха до низа записать координаты, и пройтись по ним.

очень содержательно и очень эффективно.

[Doob 2 749]

В ComputerCraft есть библиотеки GPS и Vector, можно перенести на OpenComputers, поставить навигационные вышки на микроконтроллерах, конвертировать относительные координаты в абсолютные и гонять робота между ближайшими необходимыми блоками и будет не важно, находятся они в одной жиле или в разных.

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

[artem211 Автор вопроса 428]

В ComputerCraft есть библиотеки GPS и Vector, можно перенести на OpenComputers, поставить навигационные вышки на микроконтроллерах, конвертировать относительные координаты в абсолютные и гонять робота между ближайшими необходимыми блоками и будет не важно, находятся они в одной жиле или в разных.

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

 

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

[Doob 2 749]

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

 

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

Изменено 19 июня, 2015 пользователем Doob

[artem211 Автор вопроса 428]

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

Нет не спорт, просто эффективный карьер с геосканером и мозгами, который будет копать все в заданном объёме, а не делать туннель бессмысленный и беспощадный) а вообще разрабатываемый алгоритм будет универсальным, хочешь туннель, хочешь шахта, а хочешь огромный плоский пласт от 0 до 20 уровня не останется ни блока руды. По мне - так туннель и рядом не стоит по эффективности

[SergOmarov 34]

Ну при использовании геосканера - возможно. Когда будете тестировать, советую делать это в своей сборке с модом x-ray, очень наглядно...

[artem211 Автор вопроса 428]

Ну при использовании геосканера - возможно. Когда будете тестировать, советую делать это в своей сборке с модом x-ray, очень наглядно...

лень сборку отдельную делать,лазер и креативка мне помогут. Или стекло и искусственные жилы

)

[swg2you 403]

"Задача о кратчайшем пути"

[artem211 Автор вопроса 428]

"Задача о кратчайшем пути"

И? Мне путь находить не требуется, задача состоит не в этом

[swg2you 403]

И? Мне путь находить не требуется, задача состоит не в этом

Разве?

 

Строишь граф:

Блоки руды = узлы

Вес рёбер = количество энергии для перемещения робота в узел

 

Алгоритм пробегает по этому графу и выдает "кратчайший" путь который и будет самой эффективной "жилой" с точки зрения затрат энергии.

 

Если нужно минимизировать время - то в качестве веса рёбер бери время телодвижений робота.

Если нужно минимизировать расстояние - то расстояние.

 

Какой параметр выберешь в качестве веса ребра по тому параметру и будет проводиться оптимизация.

[artem211 Автор вопроса 428]

 

 

Разве?
 
Строишь граф:
Блоки руды = узлы
Вес рёбер = количество энергии для перемещения робота в узел
 
Алгоритм пробегает по этому графу и выдает "кратчайший" путь который и будет самой эффективной "жилой" с точки зрения затрат энергии.
 
Если нужно минимизировать время - то в качестве веса рёбер бери время телодвижений робота.
Если нужно минимизировать расстояние - то расстояние.
 
Какой параметр выберешь в качестве веса ребра по тому параметру и будет проводиться оптимизация.

 

зачем каждый раз искать кратчайший путь после каждого блока? Я лучше жилами оперировать буду, 1 раз обсчитаю и поеду. А вообще - не хочу чужого кода и терпеть не могу в нем разбираться

 

Хотя мысль я думаю верная, на точке Старта проанализировать весь массив блоков руды, компаратором их отсортировать про признаку расстояния у первой от робота у всех прочих - от каждой следующей

[eu_tomat 2 153]

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

[LeshaInc 625]

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

[artem211 Автор вопроса 428]

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

Суть - сканируем заданный объем, по горизонтали границы мануальны, границы по вертикали во избежание критических помех - 10 вниз от робота и 10 вверх - 21 блок. Блоки руды фильтруются из массива данных и переносятся в таблицу с координатами для системы перемещений робота, далее спецсортировка массива с блоками руд - алгоритм таков первым ставится ближайший к текущим координатам робота, каждый следующий блок руды - ближайший к предыдущему, выстраивается в нужном порядке, далее просто по циклу весь массив точек передается роботу - на съедение. Пока все реализовано топорно - в каждый блок руды робот просто едет(хотел потестить чтоб работало хоть как то) нет системы интеллектуальной копки(что то вроде если дотянуться до блока с рудой может - значит копаем, а не ездим в каждый блок лично), нету обработки нижней границы, тоесть бедрока. Думаю просто при появлении отрицательной плотности(бедрок), отрезать массив руд по этой границе и глубже не ходить - так проще и легче для робота. Думаю что будет актуально при задании большой площади - бить ее на сектора и с каждым в отдельности делать то что описал выше, но это для глубокой разработки, пока не обдумывал. Написать бы еще быстрый сортировщик для выстраивания цепочки руд. Из серьезных недостатков, если жила крупная, а вплотную еще ода, или две робот может пройти по краю жилы всю ее выедая и оказаться у дальнего конца цепочки жил, потом возвращается обратно за оставленным хвостом, как решить даже в теории не представляю, разве что делать какие то ключевые точки и сортировать ближайшие блоки руд относительно такой ключевой точке, чтоб далеко не уезжал не выбрав всю жилу. Тоесть нужна в сортировке система предпочтений...а как реализовать не понимаю пока.

[eu_tomat 2 153]

artem211, я долго не отвечал, т.к. при внимательном рассмотрении задача оказалась значительно сложнее, чем вчера, когда ты меня спросил о ней.

 

Нет не спорт, просто эффективный карьер с геосканером и мозгами, который будет копать все в заданном объёме, а не делать туннель бессмысленный и беспощадный) а вообще разрабатываемый алгоритм будет универсальным, хочешь туннель, хочешь шахта, а хочешь огромный плоский пласт от 0 до 20 уровня не останется ни блока руды. По мне - так туннель и рядом не стоит по эффективности

Я понял, что эффективность является главным для тебя ориентиром. И тут надо задаться по крайней мере двумя вопросами, что лучше:

1) Тупая копалка, роющая пласт через два за полчаса, или же гипотетеческий алгоритм, выкапывающий все руды за 5 минут, но перед этим три часа вычисляющий оптимальный маршрут.

2) Прямо сейчас пользоваться уже существующим относительно простым и довольно эффективным алгоритмом, либо 10 лет искать идеальный алгоритм, ничего не копая и не разрабатывая других более-менее эффективных алгоритмов. Последний путь, кстати, не так плох, и при удачном стечении обстоятельств может привести к награждению какой-нибудь математической премией.

 

Цитата:

"Задача о кратчайшем пути"

А если подумать, то задача коммивояжёра.

 

Интересны две цитаты:

• Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
• Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжера.

Не вкурил, как в нашей задаче применить метод отсечений, но метод ветвей и границ в нашем случае как раз и будет разбиением на жилы или другие области. Я бы не стал зацикливаться на жилах, а искал бы рудные скопления, хотя формализовать поиск непрерывной жилы гораздо проще, для начала можно и так. Перебрать все варианты для 100 точек очень затратно, но перебрать сначала все варианты для 10 скоплений, а потом все варианты для 10 точек в каждом из скоплений значительно быстрее.

 

Теперь комментарии по имеющемуся алгоритму.

• В качестве расстояния, надеюсь, используешь не физическое расстояние, а прямоугольную метрику. Ее можно дополнительно улучшить, добавив затраты на поворот.
• Действительно, хорошей мыслью является рубка руды вперед, вверх и вниз, не обязательно перемещаясь в блок с рудой. Но алгоритм и без того сложный.
• На начальном этапе я бы не стал заморачиваться на выковыривании руды из бедрока. Отрезать по границе отрицательной плотности – хорошая мысль. Если очень надо, я бы вычищал бедрок отдельным алгоритмом. Добавил бы точки входа в определенные зоны бедрока в основном алгоритме, через эту же точку осуществлялся бы выход из бедрока, чтобы не усложнять. А по лабиринту бедрока проходим вспомогательным алгоритмом, учитывающим непроходимые блоки.
• Кстати, непроходимым может оказаться спонтанный коблоген. Тут тоже есть, над чем подумать.
• Сыпучка проходится легко. Можно сделать, как у Totoro, но я бы добавил задержку, чтобы робот не лупил еще не упавший гравий, а немного подождал, чтобы не создавать лишнюю нагрузку в цикле.
• В игровом чате мы обсуждали, стоит ли двигаться и сканировать только зону вперед и вправо. Тогда я сказал, что алгоритм обхода играет бОльшую роль. Сейчас думаю, что при существующем алгоритме лучше сканировать и обходить по всем сторонам света. При сплошной добыче это почти не играет роли, но в твоем алгоритме лучше двигаться от центра и возвращаться в центр.
• Предварительное построение цепочек руд – хорошая идея, которая может значительно сократить вычислительную сложность задачи.

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

 

Какие мысли возникают:

• Если руды мало, то можно воспользоваться полным перебором всех возможных маршрутов. До какого числа точек это оправдано, можно проверить экспериментально.
• Если точек слишком много, я бы искал скопления руд.
• Если скоплений руд мало, расстояния между ними большие, в первую очередь оптимизировал бы перемещения между скоплениями.
• Если скопления руд плотные и крупные, то внутри скоплений можно вообще использовать тупую копку ряд через два. Если нет, то разделяем их на скопления средних размеров.
• Средние скопления я бы разбил на малые суб-скопления.
• Оптимальный путь внутри малых скоплений можно находить полным перебором.
• Можно попробовать выполнять не полный перебор всех возможных точек, а только достаточно близких. Можно даже самых близких равноудаленных. Пока не знаю, насколько сильным будет отклонение маршрута от идеального, это надо проверять практически. Но могу сказать определенно: выбор в качестве следующей точки самой близкой из имеющихся не всегда даст оптимальный маршрут.
• Как разделять весь массив руд на скопления, пока не знаю. Я бы для начала взял результат сканирования по нескольким чанкам, нашел бы расстояния от каждой точки до каждой и построил бы гистограмму всех расстояний. Возможно, я бы там ничего не увидел, но попытаться стоит. Еще можно позаимствовать подход, аналогичный вычислению фрактальной размерности: внутри исследуемой области находим все возможные кубы со сторонами [1..n] и вычисляем среднюю плотность во всех кубах, содержащих хоть какие-то руды и опять же строим гистограмму, соотнося с расчетной средней плотностью. Так мы хотя бы получим представление о размерах скоплений, их количестве и плотности.
• Еще можно выбирать для сканирования и добычи площадь достаточно малую, чтобы выполнить полный перебор маршрутов. То есть, мы разбиваем задачу на более мелкие, конечно же, несколько теряя в эффективности полученного суммарного маршрута.
• В дополнение к предыдущему пункту можно добавить разбивку по высоте. Например, роем вертикальную шахту, выполняя сканирование каждого уровня. А потом поднимаемся вверх, заодно выкапывая всю отсканированную руду. Например, находясь на глубине 64 блоков, мы ищем оптимальный путь выработки 12 уровней, но достигнув 8-ого, производим пересчет верхних 12-и и снова проходим 8 уровней.

Выводы: задача имеет огромную вычислительную сложность. Единственным способом решить ее за разумное время будет разбитие на независимые участки. В простейшем случае по площади и по уровням. В более сложном -- по жилам и иным скоплениями руд. Изменено 21 июня, 2015 пользователем eu_tomat

[Doob 2 749]

Велосипеды изобретаете. Все уже изобретено до нас. Какие коммивояжеры? Какие вычисления?

Берем GPS API, берем Vector API, сканируем, перебором вычисляем рудные жилы (условие: несколько блоков ожидаемой плотности), заносим рудные жилы по-блочно в массив, в цикле трилатерируем ближайший нужный блок, едем в него, удаляем его из массива. И так далее, до каждого блока.

[eu_tomat 2 153]

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

Велосипеды изобретаете. Все уже изобретено до нас. Какие коммивояжеры? Какие вычисления? Берем GPS API, берем Vector API, сканируем, перебором вычисляем рудные жилы (условие: несколько блоков ожидаемой плотности), заносим рудные жилы по-блочно в массив, в цикле трилатерируем ближайший нужный блок, едем в него, удаляем его из массива. И так далее, до каждого блока.

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

[swg2you 403]

Велосипеды изобретаете. Все уже изобретено до нас. Какие коммивояжеры? Какие вычисления?

Берем GPS API, берем Vector API, сканируем, перебором вычисляем рудные жилы (условие: несколько блоков ожидаемой плотности), заносим рудные жилы по-блочно в массив, в цикле трилатерируем ближайший нужный блок, едем в него, удаляем его из массива. И так далее, до каждого блока.

Это "алгоритм ближайшего соседа" решающий "задачу коммивояжера" которая, в свою очередь, является частным случаем "задачи о кратчайшем пути". Так что насчет велосипедов - неясно )

 

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

[artem211 Автор вопроса 428]

Томат не стоит сканировать все кластеры продвигаясь по вертикали. Вчера ночью с фингером проводили стресс-испытания уже реализованного алгоритма, при выборки 21к блоков(32х32х21 максимальный на данный момент охват(четверть макс охвата)) робот обрабатывает(т2 робот с т2 процем и 2 т2 планками) от минуты до двух. После обработки на уровне с 28 до 7, проходка заняла порядка 45-50 минут, при этом 1 возврат к сундуку, так как полезным лутом было занято более 80% инвентаря(всего 16 слотов). Бур используемый при этом(обычный ИК алмазный бур) разрядился едва на пару тысяч единиц, из 45к, пройденное расстояние я пока не вычислял, думаю стоит для статистики ввести калькуляцию найденных руд и суммарный пробег в блоках. Сегодня напишу отсечной алгоритм для бедрока и думаю дробление больших заданий(свыше 32х32) на более мелкие. Не уверен в целесообразности задействовать оставшиеся 3 четверти охвата геолайзера, время обработки резко возрастет, а объемы хранимых в памяти данных я не берусь исчислять.