Я ищу алгоритм генерации лабиринта, который может генерировать лабиринты без мертвых концов, но только начало и конец. Вот так:
Изображение из http://www.astrolog.org/labyrnth/maze/unicursl.gif
Где я могу найти или продолжить построение такого алгоритма генерации лабиринта?
Похоже, вы хотите, чтобы кривая заполнения псевдослучайного пространства (например, см. Контекстные кривые заполнения пробелов -EUROGRAPHICS 2000 (формат PDF, 1.1 MB))
Посмотрите Кривую заполнения пробела.
Я подозреваю, что вы можете применить некоторую случайность к построению одного из них для достижения того, чего вы хотите.
Я бы старался начать с абсолютно черного (полного) квадрата и попытаться выкопать путь. Во время рытья вы легко обеспечиваете отсутствие тупиков, просто продолжайте движение. Используйте обратный трассировку, алгоритм поиска первого уровня. Выполняйте "случайное блуждание" - на каждом шаге произвольно решайте, следует ли сохранять направление или изменять его. Проверьте состояние тупика - если вы застряли, вы можете сказать "хорошо, я закончил, я нахожусь в финише", или, если вы считаете, что лабиринт еще не выкован, просто отступите. Всегда помните, что вы делали раньше, и произвольно производите некоторые другие действия. Вероятно, используйте некоторую эвристику, чтобы предпочесть определенные направления, например, всегда держать свободное пространство перед уклонением от стены, сначала попробовать ходить по стенам и т.д. - таким образом вы могли бы найти нужное решение, которое бы заполнило всю площадь намного быстрее.
Я не думал об этом, просто идея:
"Произвольный" процесс выбора для новых бит стены может начинаться с попытки "вырастить" прямые участки, перпендикулярные внешней стенке, а затем на какой-то стадии переключиться на заполнение, где это возможно.
Вероятно, ему понадобится возможность отступить, если он застрянет.
Возможно, это не слишком эффективно.
В примере, который вы даете, есть только один фактический путь от начала до конца. Если это все, что вы хотите, я думаю, вы можете использовать случайные блуждания!
Концепция проста: учитывая внешние границы лабиринта, начальную точку и конечную точку, напишите функцию для генерации случайных блужданий из начальной точки, которые в конечном итоге заканчиваются в конечной точке. Условия состоят в том, что наш "случайный ходок" может двигаться только вверх, вниз, вправо или влево от предыдущего квадрата и не может находиться в пределах одного квадрата ранее пройденного квадрата (это создает стены).
Как я вижу, здесь есть две алгоритмические проблемы. Во-первых, выясняется, находимся ли мы в пределах одного квадрата ранее пройденного квадрата (коллизии). Возможно, мы могли бы вести список пройденных квадратов (их координаты) и границ лабиринта, а для каждого нового квадрата оценивать расстояние от каждого квадрата в списке. Однако это не очень эффективно.
Другая проблема заключается в достижении конечной точки нашим случайным блужданием. Если бы столкновения с ранее пройденными квадратами не были проблемой, мы были бы обязаны в конечном итоге достичь конечной точки, но с ними у нас возникла проблема, что мы могли бы стянуть себя от конечной точки. Способ избежать этого - проверить и избежать ввода петель. Если мы не будем вводить петли, образованные пройденным путем и/или границами лабиринта, то мы поддерживаем возможный путь к конечной точке. Что же касается фактического расчета, если мы находимся в цикле... Мех, это тяжело.
Если у вас уже есть алгоритм решения лабиринта, вы можете запускать его всякий раз, когда у вас есть возможное столкновение, чтобы узнать, существует ли путь от вашего текущего квадрата до конечной точки. Когда вы запустите его, подумайте, что все ранее пройденные квадраты - это стены, а также их границы.
Ahh - Я нашел гораздо более простой способ создания однонаправленного лабиринта.
Начните с пустой сетки и заполните ее небольшими петлями 2x2. Если сетка нечетна по четности, вам нужно будет смешать несколько циклов 2x3, и если это будет странно, вам придется оставить один квадрат свободным - я обычно оставляю незаполненный угол.
Далее, произвольно соедините петли вместе, чтобы сформировать более крупные циклы - так (например) 2 2x2 петли становятся одиночным циклом 4x2. Продолжайте делать это, убедившись, что вы не присоединяетесь к циклу к себе.
В конце концов вы получите один цикл, который использует все ячейки, занятые исходной фермой циклов. Разрыв этого цикла в любом положении, и у вас есть unicursal лабиринт, где начальное и конечное местоположения находятся рядом друг с другом.
Теперь вы можете переместить конечные точки вокруг сетки, сформировав и разбив небольшие петли - зацепите конец в другую точку в лабиринте, а затем сломайте Т-образную перемычку на противоположной стороне, чтобы повторно сформировать свою единственную часть струны с новым конечным местоположением.
Если вы работаете над нечетным лабиринтом, используйте этот последний метод, чтобы червь один из ваших концов переместился в незаполненный угол, чтобы завершить свой лабиринт.
Я думаю, что нашел другой метод, но я еще не тестировал его широко.
См. https://twitter.com/tdhooper/status/340853820584230915/photo/1
Слева направо:
Создайте не-unicursal лабиринт, как описано здесь https://en.wikipedia.org/wiki/File:Prim_Maze.svg, я думаю, что это алгоритм Prim
Завершить выход
Нарисуйте путь, который посещает каждую точку в лабиринте (т.е. попытайтесь ее решить)
Сделайте этот путь стеной
Когда "ходьба" сохраняет изменения, сделанные на каждом шаге в стеке, таким образом, вы можете посмотреть x шагов вперед, а затем на каждом этапе, чтобы вы не могли предпринять дальнейших шагов (зашли в угол или спираль, как прогулка) вытащите стопку до тех пор, пока у вас нет жизнеспособной пешеходной дорожки, и продолжайте идти оттуда до тех пор, пока стек не будет пустым (т.е. вы пополняете стоп назад, потому что на каждом предыдущем шаге не было жизнеспособного соседа). Затем примените преобразования к структуре данных лабиринта.
Я работаю над этим на данный момент... Начиная с края, я случайно перемещаюсь по квадратному массиву, отмечая ячейки с длиной пути, когда я проходил через них.
Когда вы застреваете (и вы это сделаете), создайте Т-образное соединение, образуя цикл с самым последним рядом с вами (но см. ниже). Затем я возвращаюсь по существующему пути к другой стороне Т-перехода и разбиваю петлю. Этот обвисший хвост затем формирует вашу новую "голову" случайного блуждания (не забудьте пересчитать длину пути от источника пути), и вы можете продолжить.
Эксперименты показывают, что, делая это, он не (или еще не видел - см. ниже) попал в цикл создания новых хвостов, если ваш новый "хвост" попал в ловушку, вы не просто бездумно переформатируйте ссылку с той ячейкой, которую вы только что отделили, если она самая последняя, выберите второй самый последний в этом случае.
Заканчивая дело, когда вы получаете "застряли" в краевом элементе, и вы заполнили массив (длина пути такая же, как область массива) - все готово. Ваша начальная точка ведет к вашей конечной точке.
Кажется, есть две возможные неэффективности и потенциальные икоты с этим (я играю с алгоритмом на данный момент). Иногда вы заходите в угол, и единственный способ продолжить - это переформировать ссылку цикла с тем, что вы только что сломали. Затем последовательность обратных дорожек через все петли, которые вы ранее делали до точки, в которой вы изначально застряли. Если это не может пойти нигде (это другой угол), тогда вы просто подпрыгнете между ними. Есть способы обойти это, но это означает сохранение своего рода списка зацикленных ячеек, только очистка его, когда вы на самом деле устанавливаете новый путь.
Другим является то, что он кажется склонным оставлять лишний квадрат незаполненным, особенно когда ваш массив нечетно. Я не полностью исследовал, почему это так, и когда это происходит, что предыдущая проблема угла кажется особенно распространенной. Работа продолжается...
