🌀 Генератор Лабіринтів

Кожен ідеальний лабіринт — це кістяке дерево решітки клітин: між будь-якими двома клітинами існує рівно один шлях. Чотири алгоритми генерують дерева з дуже різним «відчуттям»: DFS (рекурсивний обхід) дає довгі звивисті коридори; Прим росте кристалом із безліччю коротких гілок; Вілсон (стирання петель) еквівалентно рівномірний за всіма кістяковими деревами; Крускал видаляє стіни у випадковому порядку через структуру union-find. Після генерації натисніть «Знайти шлях (BFS)». 🇬🇧 English

Алгоритм

Клітин—
Відвідано—
Довжина шляху—
СтатусГотово

Порівняння алгоритмів

Усі чотири генерують ідеальні лабіринти (кістякові дерева), але з різних імовірнісних розподілів. DFS перевантажує довгі прямі ходи (зміщення існує). Прим генерує лабіринти з безліччю коротких тупиків (легко зміщений). Крускал близький до рівномірного по ребрах. Алгоритм Вілсона є точно рівномірним по всіх кістякових деревах — математично доведено — але може бути повільним при малій кількості непосіщених клітин.

Про цю симуляцію

Цей симулятор генерує «ідеальний лабіринт» — кістякове дерево сітки, у якому між будь-якими двома клітинками існує рівно один шлях, — за допомогою одного з чотирьох класичних алгоритмів на графах: рекурсивного обходу з поверненням (DFS), рандомізованого алгоритму Прима, стирання петель Вілсона або алгоритму Крускала на основі структури union-find. Після генерації пошук у ширину (BFS) розв'язує лабіринт, підсвічуючи гарантовано найкоротший шлях.

🔬 Що показано

Стіни зникають по одній у міру того, як обраний алгоритм досліджує сітку, тож видно, як кістякове дерево росте клітинка за клітинкою. Після завершення кнопка «BFS шлях» накладає гарантовано найкоротший маршрут від початкової клітинки у верхньому лівому куті до кінцевої в нижньому правому.

🎮 Як користуватися

Оберіть алгоритм у випадаючому списку, встановіть Розмір сітки (від 5 до 60 клітинок) і Швидкість анімації двома повзунками, а тоді натисніть «Генерувати», щоб побачити побудову покроково, або «Миттєво», щоб одразу отримати готовий лабіринт. Кнопка «BFS шлях» після цього малює найкоротший маршрут.

💡 Чи знали ви?

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

Поширені запитання

Що робить лабіринт «ідеальним»?

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

Як алгоритм рекурсивного обходу (DFS) будує лабіринт?

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

Чому лабіринти Прима й Вілсона виглядають зовсім інакше, ніж лабіринти DFS?

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

Що саме знаходить «BFS шлях»?

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

Чому алгоритм Вілсона іноді генерує лабіринт повільніше за інші?

Його випадкові блукання зі стиранням петель можуть тривати довго, перш ніж натраплять на вже відвідану клітинку, особливо на початку, коли лабіринту належить ще мало клітинок. Цей змінний час виконання — плата за унікальну гарантію справді рівномірного випадкового лабіринту, а не зміщеного.