Comments 26
Ого, я написал практически такой же алгоритм. Только у меня не нужна матрица и ответвление может быть в любом месте. Так же если нужен другой тип лабиринта — не «один правильный путь к выходу и несколько ложных» а просто разветвленный лабиринт то это легко сделать немного модифицировав алгоритм. Надо просто рыть не один путь, а сразу в нескольких направлениях.
«Рисунки», которые получилось на решенных лабиринтах, отдалённо напоминают фрактал Мандельброта, если его приблизить. Красиво получилось.
Практически такой же алгоритм писал на PHP для расчета последовательности маршрута.
Только вот матрица смежности выходит краеугольным камнем.
Только вот матрица смежности выходит краеугольным камнем.
UFO just landed and posted this here
По умолчанию входом всегда считается левая верхняя точка, а выходом — правая нижняя. А так, выбрать можно любые две точки и прикрутить соответствующую визуализацию, на алгоритм это никак не повлияет.
Речь идет о поиске пути между двумя любыми точками, а что это за точки — остается на усмотрение читателя)
Речь идет о поиске пути между двумя любыми точками, а что это за точки — остается на усмотрение читателя)
UFO just landed and posted this here
UFO just landed and posted this here
Да, лабиринт соответствует определению «идеального лабиринта» — ни циклов, ни изолированных областей, между двумя точками есть путь и притом только один.
UPD: Добавить циклов и вариативности прохождения довольно просто: достаточно выбить некоторое количество рандомных стенок.
UPD: Добавить циклов и вариативности прохождения довольно просто: достаточно выбить некоторое количество рандомных стенок.
UFO just landed and posted this here
Вы имеете в виду, можно ли задать длину пути между двумя точками?
Теоретически, да — построить сначала минимальное основное дерево нужной длины, представляющее собой путь между двумя точками, а потом достроить вокруг остальной лабиринт.
Практически — не пробовал, но учту, в следующей статье вместе с поиском в ширину постараюсь осветить этот момент.
Теоретически, да — построить сначала минимальное основное дерево нужной длины, представляющее собой путь между двумя точками, а потом достроить вокруг остальной лабиринт.
Практически — не пробовал, но учту, в следующей статье вместе с поиском в ширину постараюсь осветить этот момент.
А можно поподробней, как задается выходная вершина? А то я так понял, что по алгоритму мы роем в случайном направлении до тех пор, пока можем, и только упершись так, что рыть больше некуда, возвращаемся и начинаем рыть уже ответвления. То есть конечная вершина может меняться в зависимости от рандома.
Изначальное количество клеток на нулевом шаге не уменьшается после генерации.
Мы как имели 25 клеток в самом начале, отделенные стенками, так и будем их иметь после генерации. Соответственно, любые из них можно выбрать как начальную\конечную. Алгоритм покрывает все клетки и из любой из них можно пройти в любую. То есть остовное дерево от «входа» до «выхода» можно построить от любой клетки до любой.
Мы как имели 25 клеток в самом начале, отделенные стенками, так и будем их иметь после генерации. Соответственно, любые из них можно выбрать как начальную\конечную. Алгоритм покрывает все клетки и из любой из них можно пройти в любую. То есть остовное дерево от «входа» до «выхода» можно построить от любой клетки до любой.
Все равно не понял, Вы задали начальную вершину, рандом решил начертить такую вот карту.
Что мы дальше с ней делаем? Если карта уже готова, то выход очевидно не в правом нижнем углу, как хотелось бы. Потому что как алгоритм ищет путь именно до нужной вершины я не нашел, а судя по вашим утверждениям он это всё же делает.
Что мы дальше с ней делаем? Если карта уже готова, то выход очевидно не в правом нижнем углу, как хотелось бы. Потому что как алгоритм ищет путь именно до нужной вершины я не нашел, а судя по вашим утверждениям он это всё же делает.
Выход — всего лишь ТОЧКА. И она будет находиться там, где Вы захотите.
Это уже не относится к генерации. Хотите — делайте в левом углу, хотите — в точке, где происходит первый возврат по стеку.
Алгоритм поиска ищет путь от заданной начальной точки до заданной конечной.
В данном случае, я ставлю конец в самую дальнюю от выбранного мной входа точку, чтобы с большей степенью вероятности получить наиболее протяженный путь.
Несколькими комментариями выше я ответил на вопрос о контроле длинны пути от точки до точки.
Это уже не относится к генерации. Хотите — делайте в левом углу, хотите — в точке, где происходит первый возврат по стеку.
Алгоритм поиска ищет путь от заданной начальной точки до заданной конечной.
В данном случае, я ставлю конец в самую дальнюю от выбранного мной входа точку, чтобы с большей степенью вероятности получить наиболее протяженный путь.
Несколькими комментариями выше я ответил на вопрос о контроле длинны пути от точки до точки.
В английской Википедии есть и очень развернуто, предполагается, что созданиее лабиринта — это генерация остовного дерева (spanning tree), и несколько соответствующих алгоритмов генерации: поиск в глубину, алгоритм Крускала и алгоритм Прима и еще какие-то.
Первая ссылка хорошая. Там рассмотрено много методов генерации лабиринтов. Рекомендую.
Идеальный лабиринт, в котором клетка является «проходом» или «стеной»? Ну-ну.
Чтобы не быть голословным, отошлю вас к почти детской книжке Максима Мозгового «Занимательное программирование». Там неплохо объяснено, чем ваш вариант представления алгоритма плох.
Чтобы не быть голословным, отошлю вас к почти детской книжке Максима Мозгового «Занимательное программирование». Там неплохо объяснено, чем ваш вариант представления алгоритма плох.
Если там описываются альтернативные варианты представления лабиринта в памяти, с радостью подчерпну что-то новое.
Я нашел матрицу клеток самой оптимальной и удобной в использовании.
Опять же, идеальный он не потому что идеален эстетически, или с точки зрения сложности, просто определение такое.
Я нашел матрицу клеток самой оптимальной и удобной в использовании.
Опять же, идеальный он не потому что идеален эстетически, или с точки зрения сложности, просто определение такое.
Возьму на себя смелость скопировать фразу из главы о лабиринтах: «если разрушить любую стену в лабиринте, то образуется новая локация на месте разрушенной стены. При разрушении стены должен открываться проход, но никак не образовываться новая локация».
В принципе, это и на логическом уровне кажется очевидным. Но реализация как у вас, самая простая с точки зрения «рисования» лабиринта в блокноте.
В принципе, это и на логическом уровне кажется очевидным. Но реализация как у вас, самая простая с точки зрения «рисования» лабиринта в блокноте.
Хорошо, я учту для будущих статей.
Я считал что это вопрос скорее визуализации, правда.
Хм… Тогда реализация сильно приблизится к теоретической базе графов, что и так планировалось. Отлично)
Я считал что это вопрос скорее визуализации, правда.
Хм… Тогда реализация сильно приблизится к теоретической базе графов, что и так планировалось. Отлично)
Я думаю что в Вашей структуре при сносе стенки не образуется новая локация, т.к. стенки у вас в массиве стоят на чётных местах.
В упомянутой же книге предполагалось, что и стена и локация выражается одним числом.
Или я не прав?
В упомянутой же книге предполагалось, что и стена и локация выражается одним числом.
Или я не прав?
Образуется таки.
Алгоритм поиска, в текущем виде, считает все клетки равноправными(шаг равен одному).
То есть стенка при «сносе» заменяется клеткой, которая сразу отмечается посещенной, во избежании повторного прохода по ней.
Можно обойти это, используя шаг равный двум и проверяя есть ли стенка, как в функции removeWall. И соответственно отрисовывать только клетки, а стенки линиями по второй матрице, получаемой разложением по четности, но это уже лютые костыли и велосипеды…
Правильнее, и я так и буду делать в дальнейшем, использовать плотнее графы и работать непосредственно на матрице или списках смежности.
Алгоритм поиска, в текущем виде, считает все клетки равноправными(шаг равен одному).
То есть стенка при «сносе» заменяется клеткой, которая сразу отмечается посещенной, во избежании повторного прохода по ней.
Можно обойти это, используя шаг равный двум и проверяя есть ли стенка, как в функции removeWall. И соответственно отрисовывать только клетки, а стенки линиями по второй матрице, получаемой разложением по четности, но это уже лютые костыли и велосипеды…
Правильнее, и я так и буду делать в дальнейшем, использовать плотнее графы и работать непосредственно на матрице или списках смежности.
Sign up to leave a comment.
Генерация и решение лабиринта с помощью метода поиска в глубину по графу