Во-первых, алгоритм Ли основан на поиске в ширину, а на данной картинке при наполовину исследованном лабиринте в самом начале остаются неисследованные пути. При использовании алгоритма Ли так не бывает.
Во-вторых, можно просто внимательно присмотреться к картинке - там на развилке выбирается случайный путь, в случае тупика идёт возврат к последней развилке и выбирается другой путь. Это и называется поиск в глубину.
Такие штуки алгоритмически проще всего решаются графами, для которых ещё и алгоритмов тьма-тьмущая под любые цели. И кучу готовых реализаций этих алгоритмов на разных языках можно нагуглить.
Недавно вот тоже мучился с хитрожопым поиском по файлу с данными несколько дней. А теперь поиск в сведённом к графу файле и с использованием алгоритма Краскала занимает строчек 50 кода.
Двумерный лабиринт он конечно граф. Но больно специальный, двунаправленный, невзвешенный, у вершины не более четырех ребер. Из-за этих ограничений, для таких графов часто есть специальные, более простые в написании или более быстрые алгоритмы.
Присмотрись он иногда делает пропускает левые повороты. Это реально поиск в глубину, но в случае развилки (вполне возможно) приоритет обхода определяется эвристикой (скорее всего) или случайно. Во всяком случае приоритет точно не фиксированный (если писать код по тупому обычно получается фиксированный, из-за последовательных условий: если можно вверх - идем вверх. если можно вправо - идем вправо и так далее). В одной из первых развилок он предпочитает шаг влево, шагу вниз, а в следующей уже наоборот, шаг вниз шагу влево.
Чойто такое припоминаю. Помню целый час по одному лабиринту ходил во тьме и с минимумом монстров (они вродь быстро закончились а вот лабиринт нет) потом плюнул и удалил игру.
А уж если вспомнить лабиринты в майнкрафте то ваще ужос правда там всегда можно забить на подземелье и с помощью кирки пробить путь наверх.
А там всё совсем классно. Какой-то из лабиринтов сломан и не проходится даже по карте. Я так ушёл в пустоту и потом минут 10 искал выход хотя бы в лабиринт.
если долго и пристально смотреть можно видеть разные узоры
я например вижу листву, морских звезд, человеческие уши, мозг, кресты
еще каких-то пауков, пальцы, горы-холмы, животных...
Залил контур -- два верных пути (без возвратов) по границе цветов. Если залился какой-то участок, то, очевидно, он цельный, его не пересечь, только в обход. Интересно, насколько паинтовская "заливка" оптимальна для поиска выхода из таких рандомных лабиринтов :)
нинасколько, зальётся весь лабиринт за исключением тех участков, которые "герметичны" и в которые никак не попасть (а в хорошем лабиринте таких должно быть как можно меньше)
Это клево, но алгоритм был бы проще если бы распознавались стены. В любом простом лабиринте при входе в него можно выбрать правую или левую стену и идти вдоль нее все время. рано или поздно приведет к выходу
Могу ошибаться.
Насколько вижу, все неправильные пути довольно коротки. Алгоритм просто проводит путь во все направления, и довольно быстро упирается в стенку. А что, если провести два длинных пути через лабиринт, но один будет с тупиком в конце?
Эту фигню проходят в магистратуре...
Во-вторых, можно просто внимательно присмотреться к картинке - там на развилке выбирается случайный путь, в случае тупика идёт возврат к последней развилке и выбирается другой путь. Это и называется поиск в глубину.
Недавно вот тоже мучился с хитрожопым поиском по файлу с данными несколько дней. А теперь поиск в сведённом к графу файле и с использованием алгоритма Краскала занимает строчек 50 кода.
А уж если вспомнить лабиринты в майнкрафте то ваще ужос правда там всегда можно забить на подземелье и с помощью кирки пробить путь наверх.
действуй ;)
я например вижу листву, морских звезд, человеческие уши, мозг, кресты
еще каких-то пауков, пальцы, горы-холмы, животных...
Насколько вижу, все неправильные пути довольно коротки. Алгоритм просто проводит путь во все направления, и довольно быстро упирается в стенку. А что, если провести два длинных пути через лабиринт, но один будет с тупиком в конце?