Привет всем. Я действительно изо всех сил пытаюсь понять логику с этим и надеялся, что ты поможешь мне. Прежде чем продолжить, я просто хочу сообщить вам, что я программист-любитель и начинающий в этом, без какого-либо официального обучения информатике, поэтому, пожалуйста, потерпите меня. : D Кроме того, я использую Python, но я мог бы использовать Java или что-то подобное.
Как бы то ни было, я ищу реализацию Region Growing для использования в элементарном Drawbot.
Вот статья о выращивании региона: http://en.wikipedia.org/wiki/Region_growing
То, как я это представляю, изображение, на котором основана ничья, будет соответствовать следующим критериям:
Изображение будет иметь размер не более 3х3 дюймов при произвольной глубине цвета
Изображение будет черной непрерывной формы на белом фоне
Форма может быть расположена в любом месте на заднем плане.
Я рассмотрел следующие решения этой проблемы. В то время как некоторые работают в определенной степени, у каждого есть некоторые существенные недостатки в их производительности или возможности (по крайней мере, они не кажутся мне осуществимыми). Кроме того, поскольку это Drawbot, это нужно сделать одной сплошной линией. Это не означает, однако, что я не могу вернуться назад, это только исключает возможность множественных начальных точек (семян).
Рассмотренные подходы:
Случайная прогулка:
Моим первым инстинктом было решение этой проблемы случайным блужданием. Программа случайного блуждания, выполняющая это, я бы выглядела примерно так:
псевдо-питон ...
Cells To Visit = Number of Black Cells
Cells Visited = 0
MarkColor = red
While Cells Visited < Cells To Visit:
if currentcell is black:
Mark Current Cell As Visited #change pixel to red
Cells Visited +=1
neighbors = Get_Adjacent_Cells() #returns cells either black or red
next cell = random.choose(neighbors)
currentCell = next cell
Хотя я полагаю, что это выполнимо, мне кажется, что оно крайне неэффективно и не гарантирует хороших результатов, но в интересах реального выполнения чего-то я могу в конечном итоге попробовать это ... Моя логика в псевдокоде даже смутно правильно?
Схема подметания:
Этот метод мне показался наиболее тривиальным для реализации. Моя идея здесь заключается в том, что я мог бы выбрать начальную точку в одном крайнем случае формы (например, в самой нижней самой левой точке). Оттуда он будет рисовать вправо, двигаясь только по оси х, пока не достигнет белого пикселя. Отсюда он будет двигаться вверх на один пиксель по оси Y, а затем двигаться влево по оси X, пока не достигнет белого пикселя. Если пиксель прямо над ним оказался белым, возвращайтесь назад по оси x, пока не найдете черный пиксель над ним.
Этот метод при дальнейшей проверке имеет некоторые существенные недостатки.
Когда сталкиваешься с такой формой:
Результат будет выглядеть так:
И даже если бы я сказал, чтобы он начал подметать через некоторое время, среднюю ногу все равно не заметили бы.
4/8 Подключенный район:
http://en.wikipedia.org/wiki/8-connected_neighborhood
Этот метод представляется мне наиболее мощным и эффективным, но на данный момент я не могу понять его полностью, и при этом я не могу думать о том, как бы я реализовал его, не оставляя потенциально пропущенные области
В каждой ячейке я смотрел на соседние черные клетки, придумывал какой-то метод для определения того, какой из них мне следует посетить первым, посещал все из них и повторял процесс, пока все ячейки не будут покрыты.
Проблемы, которые я мог видеть здесь, в первую очередь касаются структуры данных, необходимой для достижения этой цели, а также просто выяснения логики, стоящей за ней.
Это лучшие решения, которые я смог придумать. Спасибо, что нашли время, чтобы прочитать это, я понимаю, что это долго, но я подумал, что должен сделать это как можно более явным. Будем весьма благодарны за любые предложения ... Спасибо!
Edit:
Я также изучал алгоритмы генерации и решения лабиринтов, но не знал, как реализовать это здесь. Мое понимание алгоритмов решения лабиринта состоит в том, что они полагаются на проходы лабиринта равной ширины. Конечно, я могу ошибаться.