🏗️ Генератор Лабіринту

Це програма, яка прокладає сітку клітинок у зв'язану мережу проходів і стін. Ця версія створює ідеальні лабіринти, тобто між будь-якими двома точками існує рівно один шлях і немає замкнених петель. Результат математично є кістяковим деревом, накресленим на сітці.

DFS-відкат прокладає довгі звивисті коридори; випадковий метод Прима росте з фронту й дає короткі, розгалужені гілки; метод Крускала з'єднує випадкові розрізнені області для однорідної текстури; а метод Вілсона створює неупереджений лабіринт, де всі можливі варіанти однаково ймовірні. Вони будують той самий тип лабіринту, але з дуже різним візуальним характером.

Клік по Solve запускає пошук у ширину від стартової клітинки (верхній лівий кут) назовні, записуючи попередника кожної клітинки. Оскільки BFS досліджує в порядку відстані, перший раз, коли він досягає виходу (нижній правий кут), він знайшов найкоротший шлях, який потім відстежується назад і малюється зеленим.

Grid size задає одразу ширину й висоту квадратного лабіринту, від 5×5 до 60×60 клітинок, тож загальна кількість клітинок дорівнює цьому значенню в квадраті. Speed відповідає розкладу кроків за кадр (1, 1, 2, 4, 8, 15, 30, 60, 150, 500), дозволяючи сповільнити прокладання до повзання або завершити великий лабіринт майже миттєво.

Ідеальний лабіринт повністю зв'язаний і не містить петель, тож між будь-якою парою клітинок існує рівно один маршрут. У термінах теорії графів це кістякове дерево графа сітки: кожна клітинка досяжна, і видалення будь-якого проходу роз'єднає лабіринт.

Алгоритм Вілсона використовує випадкові блукання зі стиранням петель: він блукає випадково від невідвіданої клітинки, доки не досягне наявного лабіринту, стираючи по дорозі будь-які утворені петлі. Ця процедура вибирає рівномірно випадково з-поміж усіх можливих кістякових дерев, тож кожен лабіринт даного розміру однаково ймовірний. Девід Вілсон опублікував цей метод у 1996 році.

Він починає з клітинки, позначає її відвіданою й повторно переходить до випадкової невідвіданої сусідньої клітинки, прокладаючи стіну між ними і кладучи клітинку в стек. Коли клітинка не має невідвіданих сусідів, він відкочується, знімаючи зі стеку. Це дослідження в глибину створює довгі, звивисті коридори, типові для DFS-лабіринтів.

Кожна клітинка містить однобайтову бітову маску, де біти представляють відкриті проходи на північ, схід, південь і захід (значення 1, 2, 4 і 8). Прокладання стіни встановлює відповідний біт в обох сусідніх клітинках. Рендерер зчитує ці біти, щоб намалювати з'єднувальні містки між клітинками, а розв'язувач зчитує їх, щоб знати, які ходи дозволені.

Так. Кожен алгоритм реалізовано вірно: DFS з явним стеком, метод Прима з випадковим фронтом, метод Крускала з перетасованим списком ребер і зв'язністю через систему непересічних множин, а метод Вілсона зі справжніми блуканнями зі стиранням петель. Розв'язувач BFS — це стандартний пошук найкоротшого шляху, тож підсвічений маршрут завжди оптимальний для ідеального лабіринту.

Метод Крускала перетасовує кожну стіну й розглядає їх по одній, прокладаючи стіну лише тоді, коли дві клітинки, які вона розділяє, належать до різних областей. Структура непересічних множин (union-find) відстежує, які клітинки вже з'єднані, тож алгоритм може уникати створення петель, зливаючи сітку в єдине дерево.

Вони застосовуються в дизайні рівнів і підземель відеоігор, інструментах процедурного контенту та як класичні навчальні приклади обходу графів і кістякових дерев. Ті самі ідеї поширюються на робототехніку й маршрутизацію мереж, де знаходження зв'язних шляхів без петель у просторі є важливим.