Правило правої руки в лабіринті, коли воно працює і як генерують лабіринти
· 6 хв читання · Команда Тямки
Чому правило правої руки гарантовано виводить із одних лабіринтів і водить по колу в інших, як програми будують лабіринти і чому одні здаються важчими за інші.
Правило правої руки знають майже всі. Покладіть руку на стіну і йдіть, не відриваючи її, і рано чи пізно вийдете. Це правда, але не для кожного лабіринту, і навіть там, де правило працює, воно не найшвидше. Гарантія залежить від того, як лабіринт побудовано. Приклади з гри лабіринт онлайн на цьому сайті, де кожен лабіринт генерується в мить, коли ви натискаєте «Почати».
Як працює правило правої руки
Ідете вздовж правої стіни і на кожній розвилці повертаєте праворуч, якщо можна. Якщо праворуч стіна — прямо. Якщо й прямо стіна — ліворуч. У глухому куті розвертаєтеся і йдете назад, рука так само на стіні. Ліва рука працює так само, головне — не міняти бік посередині шляху.
Правило обходить стіну, як обходять берег острова. Якщо всі стіни лабіринту зʼєднані між собою або із зовнішньою межею, то стіна одна, довга і звивиста, і, тримаючись її, ви обійдете весь лабіринт і десь по дорозі знайдете вихід. У статті Вікіпедії про розвʼязування лабіринтів такий лабіринт називають однозвʼязним, і саме для нього правило гарантоване.
Коли правило не спрацює
Правило може зламатися, коли в лабіринті є петлі, тобто до якогось місця можна дійти двома різними шляхами. Тоді частина стін утворює окремий острів, не повʼязаний з рештою. Якщо ви почали біля такого острова або вихід стоїть посередині, оточений петлями, рука на стіні може водити вас по колу нескінченно.
Для таких випадків є інші способи.
- Алгоритм Пледжа, названий на честь Джона Пледжа з Ексетера. Він для випадку, коли вихід на зовнішньому краї. Ви тримаєтеся обраного напрямку, рахуєте всі повороти і відходите від стіни, лише коли їхня сума знову нуль. Це не дає застрягнути навколо острова.
- Метод Тремо, за іменем Шарля Пʼєра Тремо. Працює в будь-якому лабіринті з чіткими проходами, але вимагає позначок на підлозі, щоб знати, де ви вже проходили і скільки разів.
Як генерують лабіринти
Щоб зрозуміти, чому в одних лабіринтах правило гарантоване, варто подивитися, як їх будують програми. Беруть прямокутник клітинок, у якому всі стіни на місці, і прибирають стіни між сусідніми клітинками, поки до кожної клітинки не можна буде дійти.
Якщо не прибирати жодної зайвої стіни, яка утворила б петлю, виходить ідеальний лабіринт. Між будь-якими двома клітинками рівно один шлях. Математики назвуть це кістяковим деревом сітки, де клітинки — це вершини, а проходи — ребра, і в сітці з n клітинок рівно n − 1 прохід. Петель немає, отже, всі стіни зʼєднані, і правило правої руки в такому лабіринті обходить кожну клітинку, перш ніж повернутися на старт. Саме воно не зупиниться, але повз вихід пройде неодмінно, навіть якщо вихід посередині.
Алгоритми різняться тим, яке саме дерево вони вибирають, і від цього залежить, який вигляд має лабіринт.
- Пошук у глибину (його ще називають рекурсивним поверненням). Ідете з клітинки до випадкового невідвіданого сусіда, пробиваючи стіну, а коли сусідів не лишилося, повертаєтеся своїм слідом до першого місця, звідки ще можна йти. Виходять довгі звивисті коридори і мало розвилок.
- Алгоритм Прима. Лабіринт росте з однієї клітинки, щоразу додається випадкова клітинка з межі вже прорубаного. Виходить густий кущ, багато розвилок і багато коротких глухих кутів завглибшки в одну-дві клітинки.
- Алгоритм Крускала. Стіни беруть у випадковому порядку і прибирають, якщо клітинки за ними ще не зʼєднані. Вікіпедія зауважує, що він дає досить рівномірні візерунки, які порівняно легко розвʼязувати.
- Алгоритми Вільсона і Олдоса–Бродера. Вони теж будують ідеальний лабіринт, але для них кожен можливий ідеальний лабіринт рівноймовірний. Вільсон робить це випадковими блуканнями зі стиранням петель. Решта алгоритмів тяжіє до певного вигляду лабіринту, і саме тому вони зручні для ігор.
Алгоритм зростального дерева, регулятор між Примом і пошуком у глибину
2011 року програміст Джеміс Бак описав у своєму блозі алгоритм growing tree, алгоритм зростального дерева. Є список активних клітинок. На кожному кроці береться клітинка зі списку, від неї пробивається прохід до невідвіданого сусіда, і сусід теж додається до списку. Клітинка, в якої невідвіданих сусідів не лишилося, зі списку випадає.
Усе залежить від того, яку клітинку брати. За словами Бака, якщо завжди брати найновішу, виходить пошук у глибину, а якщо завжди випадкову, виходить Прим. Змішавши, наприклад половину разів найновішу, а половину випадкову, отримуєте щось посередині.
Наш «Лабіринт» використовує саме цей регулятор. На рівнях з 1-го по 8-й найновішу клітинку беруть у чверті випадків, тож лабіринти ближчі до Прима, з безліччю коротких глухих кутів. З 9-го рівня частка найновішої росте і на 15-му сягає трьох чвертей, гілки стають довгими. Далі не йдемо навмисно. Чистий пошук у глибину дає так мало розвилок, що лабіринт перетворюється на прогулянку.
Чому в нашій грі правило правої руки не допоможе
Усі лабіринти в грі ідеальні, отже, правило правої руки гарантовано вивело б до кільця. Але воно заходить у кожну бічну гілку на своєму боці і вертається назад. А в «Лабіринті» крок у будь-яку бічну гілку коштує одне з трьох життів, і ви лишаєтеся на місці. У дереві кожна бічна гілка зрештою закінчується глухим кутом. І так на кожній глухій гілці на вашому боці до кільця, а три такі гілки закінчують рівень.
Гра задумана навпаки. Увесь лабіринт видно одразу після «Почати», стіни нічого не коштують, крок назад по шляху теж безкоштовний. Треба знайти маршрут очима і лише потім іти.
Як знайти шлях, коли видно весь лабіринт
- Засипайте глухі кути. Шукайте клітинки з трьома стінами, крім крапки і кільця. Кожна з них — глухий кут, і коридор до неї теж, аж до найближчої розвилки. Подумки зафарбуйте їх, і гілки скорочуватимуться, поки не лишиться сам маршрут. У Вікіпедії цей спосіб так і називається, заповнення глухих кутів, і він ніколи не відрізає старт від фінішу.
- Ведіть маршрут з обох кінців. Простежте шлях від крапки, а потім від кільця назад до крапки. Гілка, яка здається вдалою з одного боку, з іншого буває явно хибною.
- Оцінюйте розвилки заздалегідь. Де коридор розходиться, простежте кожну гілку очима, доки вона не скінчиться або не вийде на маршрут. На ранніх рівнях, ближчих до Прима, гілки здебільшого короткі.
- Ідіть відрізками. Коли коридор зрозумілий, пройдіть його одним рухом. Клавішу зі стрілкою можна утримувати, а стіни зупинять вас без жодних втрат.
Чому одні лабіринти важчі за інші
Розмір очевидний. «Лабіринт» росте від 5 × 5 на першому рівні до 14 × 14 на пʼятнадцятому. Довшає і маршрут. У всіх лабіринтів рівня маршрут однакової довжини, від 8 кроків на 1-му рівні до 44 на 15-му, тож кожна спроба рівня має ту саму кількість кроків з балами і той самий максимум.
Будова лабіринту важить не менше. У густих лабіринтах багато виборів, але кожен хибний короткий і його легко відкинути. У лабіринтах з довгими коридорами виборів менше, зате гілка може тягнутися через півполя, перш ніж виявиться глухою, і простежити її треба до кінця. Тому на пізніх рівнях регулятор зсувається до пошуку в глибину, а не лише росте сітка.
Є ще годинник. Ліміту часу немає, але лабіринт прихований до «Почати», тож час на обдумування теж враховується. Кожен новий крок до кільця дає 10 балів і бонус за швидкість, який тане, поки ви стоїте. Крок за 24 мілісекунди після попереднього дає повний бонус, прохід очевидним коридором по 8 клітинок за секунду зберігає більшу частину, а пауза в пів секунди лишає тільки базові бали. Пауза на розвилці коштує трохи балів на одному кроці. Хибний поворот коштує життя.
Що далі
Спробуйте «Лабіринт» і подивіться, як змінюються пізні рівні. Ще дві логічні гри мають свої статті, швидкий рахунок без калькулятора для «Більшої суми» і як розвʼязувати головоломку із сумами. Усі ігри на сторінці усі ігри.