Нужен алгоритм прохождения лабиринта #720238

Нужен алгоритм прохождения лабиринта. Классический алгоритм дает решение для одного проходящего. В итоге имеем карту лабиринта. А мне нужен такой, когда проходящих несколько (как-бы распараллеливание процесса составление карты лабиринта).

один идет левой рукой стену касается, другой правой(в разные стороны по одной стене) можно по разным стенам

не знаю как работает классический, в школе решал через рекурсию

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

это программная задача или жизненная   в любом случае интересны детали

жизненная конечно, потерялся чувак :)

...проходящих несколько... а сколько входов/выходов?

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

нельзя, круги может начать внутри лабиринта нарезать

есть еще алгоритм Заполнения или поиска в ширину

Если "ходок" может себя "клонировать", то на каждом перекрестке клонируем по количеству доступных путей - 1, отмечаем перекресток как посещенный и каждый идет своим путем до следующего перекрестка. Там операцию повторяем. Кто-то найдет выход, остальные либо упрутся в тупик, либо будут ходить по кругу.

Точнее не так: если один из клонов попал в тупик или на посещенный перекресток, то он аннигилируется.

Как отличить ходящего по кругу от не ходящего, но пока не дошедшего до выхода?

из следует, что в "живых" останется только нашедший выход

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

тогда раздать всем маркеры - красный и цветной каждому свой. Коридор по еоторому вошли отмечаем красным, коридор куда уходим отмечаем своим цветом. Если попали в тупик, то возвращаемся назад на шаг. Если есть незакрашенные коридоры, идем туда, если нет - садимся и плачем.

А мне бы наоборот. Алгоритм создания лабиринта, с тонкими стенками, не по клеточкам.

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

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

Это же задача поиска путей в графе :-)

волновой алгоритм поиска пути подойдёт ?

ну так "лабиринт" сказано - чтоб не распугать публику.

сейчас посмотрю

в школе заставляли его писать

был еще какой-то алгоритм, тоже простецкий, не помню.

а как его распараллелить?

ну, запускать несколько волн с разных точек, только зачем ? Когда он один сам всё найдёт (выход, т.е)

ну, а если дырку (выход) заткнуть - "заполнит" весь лабиринт

Ищи многопоточный обход дерева

Кстати правило правой руки не всегда решает лабиринт

А если Лабиринт зациклен? :)

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

+ т.е. я имею в виду, что вариант полностью правильный и зациклиться не получится)))

А волновой алгоритм не проще сюда присобачить?

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

стобовых = "столбовых"

+37 ну, разве что оставить заметный след, чтоб не повторять путь

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

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

это зависит от того, когда человек, вошедший в лабиринт, опроблемился выходом :) если зашел глубоко - замучится искать стенку :)

проходится и по левой руке и по правой.

а, если точка "входа" в лабиринт произвольная - то только маркировка

Алгоритмов обхода лабиринта в общем случае всего два 1) Поиск в ширину; 2) Поиск в глубину. Если иследователи лабиринта могут телепоритроваться в любую точку лабиринта, то поиск в ширину вполне подходит. В противном случае, придется использовать поиск в глубину. Но в этом случае, придется мириться, что на исследователей выпадет различная нагрузка. кто то быстро закончит свою часть исследований, а кто то будет долго блуждать по лабиринту.

куда этому горемыке податься? :)

вот так он пойдет по правой руке с раскраской

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

Кстати, распараллелить можно простейшим способом на два потока, используя метод встречной волны. А если есть waypoint'ы то и на большее количество потоков.

Еще для разнообразия добавить условие,  на какое расстояние видит поисковик или можно видеть на несколько клеток? )))

алгоритм построения лабиринта куда интереснее, имхо

Что-то не догоняю в чем проблема? Ищем путь через рекурсию с сохранением координат прохода, когда наткнулись на тупик или на место где уже были прекращаем итерацию рекурсии. В итоге или найдем выход или определим что выхода нет. (естественно если лабиринт без телепортов и постоянен во времени) Проход по левую руку, это повыпендриваться перед 5 летним ребенком:) Реально этот метод не работает.

+(и если одноэтажный лабиринт)

такие тоже есть, даже с реализацией..

Алгоритм A*

Киньте на другой файлообменник, а то инфостарт не удобный.

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

Если мы применяем правило правой или левой руки при выходе из лабиринта (когда мы неизвестно как попали в какую-то точку), то в случае наличия в лабиринте циклов правило может не позволит выйти. Если же мы применяем правило на входе в лабиринт, то даже если в нём и есть циклы и несвязные области, то мы всегда останемся в той области, которая выходит на границу - другими словами - всегда выйдем наружу снова, но или через данный вход или через другой.

Если мы можем запоминать координаты лабиринта и "возвращаться" в нужную точку, то можно хоть построчно его анализировать - такая задача ничего общего с прохождением лабиринта не имеет. P.S. конечно, следует понимать, что лабиринт плоский и не имеет ходов на разных уровнях по высоте - задача прохождения трёхмерного лабиринта кардинально отличается о  прохождения двухмерного (хотя, в случае, с возможностью "запоминания" маршрута можно делать что угодно.