How it works (ru)
Лабиринт - структура, состоящая из запутанных путей. Лабиринт можно рассматривать как логическую головоломку, решение которой заключается в поиске пути от входа к выходу. Составление или генерация лабиринтов возможна с помощью различных алгоритмов. Рассмотрим алгоритм, основанный на теории графов.
Лабиринт состоит из стен. Стены формируют комнаты, между некоторыми из пар соседних комнат есть переходы. Эти переходы формируют всевозможные пути внутри лабиринта, среди которых есть путь от входа к выходу.
В плоскости теории графов стены будут являться рёбрами графа, комнаты - гранями, вершины - точками соединения стен.
Генерация лабиринта начинается с начального графа, который содержит в себе набор стен-граней между вершинами. Пути в таком графе нет, он будет сформирован при удалении определённых стен. Задача алгоритма в том, чтобы удалять стены, формируя при этом сложный и запутанный путь от входа к выходу.
Рассмотрим граф, на основе которого будет построен простой квадратный лабиринт размером 5x5. Начальная конфигурация стен представляет из себя квадратную решётку по 6 вершин в высоту и ширину, которая формирует квадрат из граней размером 5x5.
Первым шагом алгоритма является выявление всех комнат (граней), переходы между которыми будут формировать путь лабиринта. С этой целью для начального графа стен необходимо построить двойственный граф. В теории графов двойственным графом называется такой граф, каждая вершина которого соответствует грани внешнего графа, а рёбра соединяют вершины, соответствующие граням, имеющие одно или более общих рёбер. Построим двойственный граф для имеющегося начального графа.
В полученном двойственном графе заключены всевозможные переходы между гранями начального графа стен. Чтобы быть сложным, путь внутри лабиринта должен ветвиться, включать в себя много тупиков и не содержать петель. В теории графов существует понятие остовного дерева. Остовное дерево графа A содержит в себе все его вершины, и такое подмножество рёбер, что между любыми двумя его вершинами можно пройти единственным способом, двигаясь по рёбрам. Можно сделать вывод, что путём лабиринта должно являться остовное дерево для двойственного графа полученного на шаге 1. Построение остовного дерева с большим количеством тупиков и ветвлений усложнит поиск пути в лабиринте. Такое дерево для графа, полученного на шаге 1, представлено на картинке ниже.
Подграфом графа A называется граф, содержащий в себе подмножество вершин и рёбер родительского графа. Построим такой подграф для начального графа, где удалены все рёбра, пересечённые рёбрами остовного дерева - графа пути. Полученный граф и будет являться сгенерированным лабиринтом. Дополнительно удалены рёбра, являющиеся входом и выходом из лабиринта.
Универсальность даёт возможность строить лабиринты на основе произвольных начальных конфигураций стен. На картинках ниже представлены лабиринты для круглого и треугольного графа стен, а форма других возможных лабиринтов, которые можно построить с помощью этого алгоритма, ограничена только фантазией.
