5 октября 2026

Как компьютер строит лабиринты

В игре Astray нет заранее нарисованных уровней. Каждый раз, когда шарик выкатывается наружу, программа строит новый лабиринт, на две клетки больше предыдущего. Как это сделать так, чтобы выход всегда был достижим, а лабиринт не превратился в пустую комнату?

Идеальный лабиринт

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

Поиск в глубину с возвратом

Самый популярный способ легко описать словами. Встаём в стартовую клетку и отмечаем её посещённой. Выбираем случайного соседа, в котором ещё не были, ломаем стену между клетками и переходим туда. Повторяем. Если все соседи уже посещены, возвращаемся на шаг назад и пробуем оттуда. Когда возвращаться больше некуда, лабиринт готов.

Такой лабиринт получается с длинными извилистыми коридорами: алгоритм уходит далеко, прежде чем повернуть назад. Именно так работает Astray. В его коде лабиринт хранится как квадратная сетка нечётного размера, где клетки и стены чередуются, и алгоритм прыгает сразу на две клетки, пробивая стену посередине.

Другие алгоритмы

Как выбраться

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

Для таких случаев есть метод Тремо: отмечайте каждый коридор, по которому прошли, и никогда не входите в коридор, отмеченный дважды. Он гарантированно находит выход в любом лабиринте.

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

Сыграть в Astray

Все статьи