Ця симуляція будує ідеальний лабіринт на квадратній сітці й анімує процес прокладання ходів у реальному часі. Кожна клітинка зберігає відкриті проходи у вигляді 4-бітної маски (північ, схід, південь, захід), а алгоритм вирішує, які стіни знести. Усі чотири методи породжують покрівне дерево над сіткою — лабіринт, у якому між будь-якими двома клітинками існує рівно один шлях і немає циклів. Ви можете спостерігати, як структура зростає клітинка за клітинкою.
Селектор алгоритму дозволяє обрати між рекурсивним обходом у глибину (DFS), рандомізованим алгоритмом Пріма, рандомізованим алгоритмом Крускала та петельно-стертим випадковим блуканням Вілсона. Повзунок розміру сітки задає розміри W×H (від 5 до 60), а Швидкість визначає, скільки кроків прокладання виконується за кадр. Після генерації функція «Розв'язати» запускає пошук у ширину, щоб знайти найкоротший маршрут від входу у верхньому лівому куті до виходу у нижньому правому. Алгоритми лабіринтів лежать в основі генерації ігрових рівнів, планування маршрутів у робототехніці та викладання теорії графів.
Що таке генератор лабіринтів?
Це програма, яка перетворює сітку клітинок на зв'язану мережу проходів і стін. Ця версія створює ідеальні лабіринти — між будь-якими двома точками існує рівно один шлях і жодних замкнених циклів. Результат математично є покрівним деревом, накресленим поверх сітки.
Чим відрізняються чотири алгоритми?
DFS-обхід прокладає довгі звивисті коридори; рандомізований алгоритм Пріма розростається від межі й формує короткі розгалужені гілки; алгоритм Крускала об'єднує випадкові роз'єднані області, створюючи рівномірну текстуру; а Вілсон будує незміщений лабіринт, де кожне можливе розташування однаково ймовірне. Усі вони будують один і той самий тип лабіринту, але з дуже різним візуальним характером.
Як розв'язувач знаходить шлях?
Натискання «Розв'язати» запускає пошук у ширину від стартової клітинки (верхній лівий кут), записуючи попередника кожної клітинки. Оскільки BFS досліджує клітинки в порядку відстані, перший раз, коли він досягає виходу (нижній правий кут), він знаходить найкоротший шлях, який потім відстежується назад і малюється зеленим кольором.
Розмір сітки задає ширину й висоту квадратного лабіринту — від 5×5 до 60×60 клітинок, тому загальна кількість клітинок дорівнює квадрату цього значення. Швидкість відповідає розкладу кроків на кадр (1, 1, 2, 4, 8, 15, 30, 60, 150, 500), що дозволяє сповільнити прокладання до мінімуму або завершити великий лабіринт майже миттєво.
Ідеальний лабіринт є повністю зв'язаним і не містить циклів, тому між будь-якою парою клітинок існує рівно один маршрут. У термінах теорії графів це покрівне дерево графа сітки: кожна клітинка досяжна, і видалення будь-якого проходу призведе до роз'єднання лабіринту.
Алгоритм Вілсона використовує петельно-стерті випадкові блукання: він рухається випадковим чином від невідвіданої клітинки, поки не досягне існуючого лабіринту, стираючи будь-які петлі, що утворюються. Ця процедура рівномірно вибирає з усіх можливих покрівних дерев, тому кожен лабіринт такого розміру однаково ймовірний. Дейвід Вілсон опублікував його у 1996 році.
Він починає з клітинки, позначає її відвіданою й послідовно переміщується до випадкового невідвіданого сусіда, прокладаючи стіну між ними й додаючи клітинку до стека. Коли клітинка не має невідвіданих сусідів, алгоритм повертається назад, витягуючи клітинку зі стека. Це дослідження в глибину породжує довгі звивисті коридори, типові для DFS-лабіринтів.
Кожна клітинка містить однобайтову бітову маску, де біти позначають відкриті проходи на північ, схід, південь і захід (значення 1, 2, 4 і 8). Прокладання стіни встановлює відповідний біт в обох сусідніх клітинках. Рендерер зчитує ці біти для малювання з'єднувальних містків між клітинками, а розв'язувач — щоб знати, які переміщення дозволені.
Так. Кожен алгоритм реалізовано точно: DFS — з явним стеком, Прім — з випадковою межею, Крускал — зі змішаним списком ребер і структурою union-find, Вілсон — зі справжніми петельно-стертими блуканнями. Розв'язувач BFS є стандартним пошуком найкоротшого шляху, тому виділений маршрут завжди оптимальний для ідеального лабіринту.
Крускал перемішує всі стіни й розглядає їх по одній, прокладаючи стіну лише тоді, коли дві клітинки, які вона розділяє, належать до різних областей. Структура union-find (роз'єднані множини) відстежує, які клітинки вже з'єднані, щоб алгоритм міг уникнути циклів під час злиття сітки в єдине дерево.
Вони використовуються в генерації рівнів відеоігор і підземель, процедурних інструментах створення контенту, а також як класичні навчальні приклади для обходу графів і покрівних дерев. Ті самі ідеї поширюються на робототехніку й мережеву маршрутизацію, де знаходження зв'язаних шляхів без циклів через простір є ключовим завданням.
Генеруйте та вирішуйте лабіринти за допомогою різних алгоритмів: від рекурсивного поділу до алгоритму Прима. Спостерігайте у реальному часі, як BFS, DFS та A* шукають шлях.
Різні алгоритми генерують лабіринти з різними характеристиками: рекурсивний поділ дає довгі коридори; алгоритм Прима — більш розгалужені. BFS знаходить найкоротший шлях; DFS часто знаходить довгий звивистий шлях.
Виберіть алгоритм генерації та клацніть «Генерувати». Виберіть алгоритм розв'язання і натисніть «Розв'язати». Перегляньте покрокову анімацію пошуку.
Алгоритм A* (A-зірочка), розроблений у 1968 р., є основою пошуку шляхів у мільйонах відеоігор сьогодні. Він об'єднує реальну вартість Дейкстри з евристичною оцінкою майбутньої вартості для ефективного пошуку.