Генератор лабіринтів і гра

Як користуватися генератором лабіринтів

1. Задайте Ширину (стовпців) і Висоту (рядків) від 4 до 60 клітинок кожну, виберіть Алгоритм і натисніть Новий лабіринт.
2. Ваша позиція – крапка на зеленому вході вгорі ліворуч. Дістаньтеся до червоного виходу внизу праворуч.
3. Рухайтеся стрілками або клавішами WASD. Утримуйте Shift разом зі стрілкою, щоб пробігти коридором до наступного перехрестя. На телефоні чи планшеті проведіть пальцем по лабіринту, щоб бігти в цьому напрямку, або торкайтеся кнопок зі стрілками під ним для окремих кроків.
4. Таймер запускається з вашого першого ходу й зупиняється на виході. Ваш слід малюється позаду; якщо піти назад, він стирається, тож завжди показує маршрут, яким ви йдете.
5. Застрягли? Показати розв’язок малює найкоротший шлях звідти, де ви стоїте, до виходу. На початок повертає вас до входу зі скиданням таймера.
6. Щоб грати на папері, натисніть Друк або Завантажити PDF. Спершу позначте Додати сторінку з розв’язком, якщо потрібна відповідь на другій сторінці.

Як поділитися лабіринтом за кодом

Кожен лабіринт має Код лабіринту, наприклад b20x15-k3j9x2: літера алгоритму (b, p або k), ширина × висота та випадкове початкове число. Той самий код завжди відтворює точнісінько той самий лабіринт на будь-якому пристрої, тож можна запропонувати другові побити ваш час на такому самому плані. Введіть або вставте код і натисніть Відкрити код чи скористайтеся кнопкою Копіювати посилання, щоб поділитися веб-адресою, яка відкриває цей лабіринт одразу.

Три алгоритми генерації

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

• Рекурсивний із поверненням (довгі коридори) блукає випадково від клітинки до клітинки, руйнуючи стіни, і відступає, коли натрапляє на глухий кут. Виходять довгі звивисті проходи з невеликою кількістю відгалужень: розв’язок зазвичай довгий і веде через більшу частину сітки.
• Прима (багато коротких глухих кутів) розростає лабіринт від випадкової клітинки, щоразу додаючи випадкову прикордонну клітинку. Ви отримуєте багато коротких бічних гілок: лабіринт здається заплутаним, але головний шлях легше помітити.
• Крускала (рівномірний, розгалужений) видаляє випадково вибрані стіни між клітинками, які ще не з’єднані (це відстежується за допомогою структури «об’єднання-пошук»). Результат розгалужений рівномірно скрізь, без помітної точки старту.

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

Як знаходиться розв’язок

Розв’язок знаходить пошук у ширину (BFS): починаючи з вашої клітинки, він обходить усіх сусідів на відстані одного кроку, потім двох і так далі, доки не досягне виходу. Оскільки кожен крок коштує однаково, BFS завжди знаходить найкоротший шлях. В ідеальному лабіринті цей шлях також єдиний без повернень. Якщо під час проходження розв’язок було показано, ваш час не зберігається як найкращий.

Поради щодо друку

Друковані версії та PDF малюють чіткі чорні стіни на білому тлі, а код лабіринту стоїть у заголовку, щоб ви могли знову знайти той самий лабіринт. Розміри близько 15 × 15 підходять маленьким дітям; 30 × 30 і більше – повноцінна головоломка для дорослих. Дуже великі лабіринти (50 × 60) мають тонкі коридори на аркуші А4, тому друкуйте їх у повний розмір сторінки.