5 октября 2026
Как компьютер строит лабиринты
В игре Astray нет заранее нарисованных уровней. Каждый раз, когда шарик выкатывается наружу, программа строит новый лабиринт, на две клетки больше предыдущего. Как это сделать так, чтобы выход всегда был достижим, а лабиринт не превратился в пустую комнату?
Идеальный лабиринт
Программисты называют идеальным лабиринт, в котором между любыми двумя клетками есть ровно один путь. В нём нет замкнутых петель и нет отрезанных участков. Если представить клетки точками, а проходы линиями, получится дерево: связная схема без циклов. Поэтому почти все алгоритмы генерации на самом деле строят случайное дерево на сетке.
Поиск в глубину с возвратом
Самый популярный способ легко описать словами. Встаём в стартовую клетку и отмечаем её посещённой. Выбираем случайного соседа, в котором ещё не были, ломаем стену между клетками и переходим туда. Повторяем. Если все соседи уже посещены, возвращаемся на шаг назад и пробуем оттуда. Когда возвращаться больше некуда, лабиринт готов.
Такой лабиринт получается с длинными извилистыми коридорами: алгоритм уходит далеко, прежде чем повернуть назад. Именно так работает Astray. В его коде лабиринт хранится как квадратная сетка нечётного размера, где клетки и стены чередуются, и алгоритм прыгает сразу на две клетки, пробивая стену посередине.
Другие алгоритмы
- Алгоритм Прима. Лабиринт растёт из одной клетки во все стороны сразу: на каждом шаге к нему присоединяется случайная соседняя клетка. Получается много коротких тупиков, и такой лабиринт кажется запутанным, хотя решается быстрее.
- Алгоритм Краскала. Сначала все клетки отдельные, затем стены убираются в случайном порядке, если они разделяют ещё не связанные области. Вид у результата похож на лабиринты Прима.
- Алгоритм Уилсона. Строит лабиринт из случайных блужданий. Он медленнее, зато выбирает любое из возможных деревьев с одинаковой вероятностью, без перекоса в длинные или короткие коридоры.
Как выбраться
Самый известный способ: положить руку на стену и идти, не отрывая её. В идеальном лабиринте это правило всегда приводит к выходу, если он находится на внешней стене, хотя путь может оказаться очень длинным. А вот в лабиринтах с петлями можно бесконечно ходить по кругу вокруг отдельно стоящего участка стены.
Для таких случаев есть метод Тремо: отмечайте каждый коридор, по которому прошли, и никогда не входите в коридор, отмеченный дважды. Он гарантированно находит выход в любом лабиринте.
В Astray камера показывает только ближайшие коридоры, поэтому правило руки здесь вполне рабочее: выход всегда находится в правой внешней стене, у верхнего угла, по диагонали от старта.