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

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

Вопрос

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Рекомендуемые сообщения

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


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

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

 

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

Изменено пользователем Doob

Поделиться сообщением


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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


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

)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
И? Мне путь находить не требуется, задача состоит не в этом

Разве?

 

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

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

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

 

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

 

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

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

 

 

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

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

 

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

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

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

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

 

Цитата:

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

 

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

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

 

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

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

 

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

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

Гость
Ответить на вопрос...

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

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

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

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

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


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