Лабиринт

Идеальный лабиринт — такой, где из любой клетки в любую ведёт ровно один путь: нет ни колец, ни отрезанных закоулков. На языке математики это остовное дерево сетки: граф, который связывает все клетки и не содержит циклов. Деревьев у сетки астрономически много: у квадрата 20 × 20 их около 10¹⁸⁷ — несравнимо больше, чем атомов в видимой Вселенной. Хороший генератор должен выбирать среди них честно.

Как это устроено

У популярных алгоритмов есть перекос. Поиск в глубину тянет длинные коридоры с редкими развилками, алгоритм Прима сыплет короткими тупиками. Алгоритм Дэвида Уилсона выдаёт каждое остовное дерево с одинаковой вероятностью. Он начинает с одной клетки-корня и дальше повторяет: из случайной клетки, ещё не вошедшей в лабиринт, запускает случайное блуждание, пока оно не наткнётся на лабиринт, затем стирает все петли, которые блуждание успело накрутить, и пристраивает оставшийся путь. Стирание петель достаётся даром: в каждой клетке запоминается только последний выход, и старые петли исчезают сами.

В режиме тайла сетка свёрнута в тор: правый край склеен с левым, верхний с нижним, и лабиринт продолжается во все стороны без шва. «Петли» пробивают стену в части тупиков, охотнее — в соседний тупик, и дерево превращается в лабиринт с кольцевыми маршрутами. Раскраска «по расстоянию» — это поиск в ширину от корня: цвет растекается по ходам, как вода, и показывает, как далеко по коридорам лежат клетки, соседние на вид.

Немного истории

Петлестёртое случайное блуждание ввёл Грегори Лоулер в 1980 году. Равномерное остовное дерево умел строить и более ранний алгоритм Олдоса — Бродера, но медленно; Дэвид Уилсон в 1996 году показал, что стирание петель даёт в точности равномерное распределение и работает быстрее. Путь между двумя клетками равномерного лабиринта распределён так же, как петлестёртое блуждание, а в пределе мелкой сетки это фрактальная кривая размерности 5/4. Одед Шрамм в 2000 году связал её со стохастической эволюцией Лёвнера, а в 2004-м вместе с Лоулером и Венделином Вернером доказал её конформную инвариантность. А считать сами деревья умел ещё Густав Кирхгоф в 1847 году — через определитель матрицы.

Что покрутить

• «Сетка» «шестиугольная» даёт шесть выходов из клетки — коридоры становятся извилистее и живее.
• «Петли» 0,2–0,4 превращают дерево в лабиринт с кольцами: правило одной руки перестаёт гарантировать выход.
• «Раскраска» «по ветвям» красит сначала самые длинные ветви — видно, как устроено дерево.
• Большая «Ширина хода» и «Скругление» 1 превращают лабиринт в трубы или кораллы; «Вид» «стены» — в классическую головоломку из газеты.
• Положите сверху эффект «Растр» — лабиринт превратится в оттиск из точек.