Как сгенировать лабиринт со стенами, что бы в этом лабиринте всегда был путь?

Question

[Тера Инкогнита]

Простой лабиринт генерируется из тайлов.


Генерация лабиринта со стенами иметь отличия . Есть теоретически два решения ,но которые проблематично применить на практике.
Язык программирования не важен.
Важно само решение ....... Задача построить генерируемый лабиринт со стенами где всегда есть вход и выход ...
У вас есть тайлы вертикальный и перпендикулярные.


проблема в том что у вас будет тупик ....
Как этого избежать и обеспечить поворот тайла ?

Нужно теоретическое решение ,которое реализуется программно ,с пошаговой пояснением теории

Answer 1

[Griboks]

Есть довольно простой и понятный алгоритм:
1) Становимся в начальную точку, смежную со входом.
2) Генерируем случайный тайл (г, -, +, т, ...) таким образом, чтобы у него был соединён вход и не блокирован (стенками лабиринта и других тайлов) хотя бы один выход.
3) Если такого выхода нет, генерируем новый тайл, чтобы был. Если всё равно нет, то переходим к пункту 5.
4) Перемещаемся к выходу текущего тайла. Теперь пустое место - это наша текущая точка.
5) Повторяем до тех пор, пока не упрёмся в тупик, т.е. не будет свободного выхода из текущего тайла.
6) Возвращаемся назад до первого ветвления и повторяем алгоритм.
7) Если опять тупики во всех ветках, то возвращаемся ещё дальше назад.
8) Если мы всё-таки вернулись ко входу в лабиринт, значит всё стираем и запускаем алгоритм по новой.

Comments

[Тера Инкогнита]

спасибо да должно сработать.... ( книксен) спасибо ..

Answer 2

[cicatrix]

В своё время делал довольно прямолинейно. На лабиринте генерил сначала путь из точки А в точку Б случайным образом и помечал эти клетки как проходные. А уж потом вокруг генерировал случайным образом весь остальной лабиринт.

Comments

[Тера Инкогнита]

не красиво получаетсья ....Я хочу такой как в играх Жадная пещера или The Wild Darkness

Answer 3

[Армянское Радио]

Таких статей довольно много

Comments

[Тера Инкогнита]

их много , но они бесполезны ....

Читаем
Создайте первую строку. Ни одна ячейка не будет являться частью ни одного множества.
Что это за бред написан?

мне нужно понятное пояснение ,что бы было понятно

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

А мне нужно что бы было не много ,а понятно ,что бы любой мог сделать и понять

То бишь мне нужен примитив

допустим у нас есть поле 9 на 9
Что бы построить лабиринт нам нужно
и пояснить что нужно? какие шаги нужно сделать?
ПОНЯТНЫМ, простым языком ,что бы такая как я могла понять . О себе,я тупая. Я готова учиться и добиться результата

Любая статья с Хабра, не несет полезной нагрузки, потому что 99% статей попросту не понятны .Это написано для умных и очень умных , но на общество приходиться всего 10 % максимум умных людей.
Потому если рассматривать в целом то хабр бесполезен для более чем 90 % людей.
Другое дело раздел вопросов ,вопросы полезнее Хабра тем,что я могу спросить то что не понятно, как жаль что те кто умеют ,не могут пояснить это простым языком что бы понял любой.

Я хочу понять ,а не получить готовое чужое сложное решение .
Я хочу получить максимально простое решение и максимально упрощенный вариант

[Rsa97]

Тера Инкогнита, И что непонятного? Для альтернативно одарённых даже пошаговый пример в этой статье есть.

[Тера Инкогнита]

Rsa97, Лабиринт слишком корявый выходит ....а я хочу как в Жадная пещера или The Wild Darkness

[Армянское Радио]

Тера Инкогнита,

Решите простую логическую задачку из ваших же цитат:

То бишь мне нужен примитив

Лабиринт слишком корявый выходит ....а я хочу как в Жадная пещера или The Wild Darkness

Как вы думаете, может ли примитивный алгоритм "на пальцАх" сравниться по качеству результата с коммерческой разработкой (которую могли три месяца тонко тюнить на фокус-группе, чтобы добиться играбельности)?

[Тера Инкогнита]

Aleksandr-JS-Developer, ну не очень сложный , такой как The Wild Darkness вполне устроить , и я почти добилась такого построения .....

[Тера Инкогнита]

Фокс Йовович, мне не нужно комерческое ...мне нужен примитив на пальцах который работает

Answer 4

[alexbprofit]

Это задание а не вопрос

Comments

[alexbprofit]

т.е нарушает правила Сервиса