Генерация лабиринта

[artcraft]

Сообщение от ProxyGreen

Хмм... Лабиринт ведь концептуально состоит из: начала, конца, коридоров, поворотов, развилок/перекрёстков и тупиков. Можно сначала рандомно выстроить истинный путь, без тупиков, а потом достроить тупиковые ветки. Так можно будет отделить модель лабиринта от его представления. Нарисовать круглый лабиринт например. Или нет?

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

 _ _
|   | |
| | | |
| |х| |
| |_ _|

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

[crazyone]

А зачем в точке х добавлять закоулок? Нужно добавлять закоулки там, где не занято.

[artcraft]

Сообщение от crazyone

А зачем в точке х добавлять закоулок? Нужно добавлять закоулки там, где не занято.

если изначально принять решение что мне нужен лабиринт размерами 8х8 в котором будет 7 перекрёстков, 25 поворотов, 3 способа решения, 6 тупиков, и расстояние от входа до выхода минимум 40 шагов, то нет гарантии что такой лабиринт вобще возможно создать

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

[Parez]

Сообщение от wvxvw

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

На счёт заполнение доски с помощью шума не совсем понятно... Шум же имеет плавные переходы, а здесь всё должно быть чётко.

Пока реализовал алгоритм генерации с помощью Depth-first search из википедии. В принципе, уже нормально. Единственное, что не устраивает - у лабиринта только одно решение и нет лупов. В принципе, это можно исправить убрав некоторые стены, но возникает вопрос - какие именно стены следует убирать?