Генерация лабиринтов
Алгоритмы — рекурсивный бэктрекер, Прима, Краскала, Вилсона, — которые прорезают в сетке «идеальный» лабиринт с ровно одним путём между любыми двумя точками.
«Идеальный» лабиринт — это остовное дерево на сетке: полностью связный, без петель, с единственным маршрутом между любой парой клеток. Рекурсивный бэктрекер (обход в глубину) даёт длинные извилистые коридоры; алгоритмы Прима и Краскала — более короткие и ветвистые; алгоритм Вилсона (случайное блуждание со стиранием петель) — совершенно несмещённый лабиринт. Каждый метод накладывает свой отпечаток на то, как читаются проходы.
Если нужны петли или комнаты, стены потом пробивают намеренно. Статьи Джейми Бака (Jamis Buck) сделали эти алгоритмы общеизвестными среди разработчиков игр.