ймовірно, був відомий ще древнім грекам. Доведеться пройти довгий шлях, заходячи в усі тупики, але в підсумку мета буде досягнута.
Спробуємо описати робота, який діє відповідно до правилом правої руки .
) На початку своєї роботи робот повинен знайти стіну, за якою він буде слідувати. Для цього він може просто рухатися вперед, поки не упреться в перешкоду.
) Після того як робот наткнувся на перешкоду, він починає пересуватися відповідно до правила правої руки .
) Рухаючись уздовж стіни, робот стежить, чи є прохід праворуч. Якщо прохід є, робот повинен йти по ньому, щоб не відірватися від стіни праворуч.
) Якщо проходу немає - попереду стіна - робот повертає ліворуч. Якщо проходу знову немає, він ще раз повертає ліворуч, таким чином розвертаючись на 180 градусів, і йде у зворотному напрямку.
Якщо ж лабіринт містить окремо стоять стінки, то, застосовуючи правило однієї руки raquo ;, не завжди можна пройти всі коридори і тупики. Лабіринти з окремо розташованими стінками і з замкнутими маршрутами називаються багатозв'язними. При цьому багатозв'язкові лабіринти можна розділити на дві групи: без петлі навколо мети (замкнутий маршрут не проходить навколо мети) і із замкнутою петлею навколо мети (мета можна обійти по замкнутому маршруту).
Рисунок 9 - Схема алгоритму правої руки
У багатозв'язних лабіринтах другої групи правило однієї руки не працює і, застосовуючи його, досягти мети неможливо. Але й ці лабіринти можна пройти, покладаючись на точний алгоритм.
. 2.2 Хвильовий алгоритм
Хвильовий алгоритм дозволяє побудувати шлях між двома елементами в будь-якому лабіринті [5]. Сам процес можна розділити на 2 етапи:
) З початкового елемента поширюється в 4-х напрямках хвиля. Елемент, в який прийшла хвиля, утворює фронт хвилі. На малюнку цифрами позначені номери фронтів хвилі.
Кожен елемент першого фронту хвилі є джерелом вторинної хвилі. Елементи другого фронту хвилі генерують хвилю третього фронту і т.д. Процес продовжується до тих пір, поки не буде досягнутий кінцевий елемент, або поки не стане ясно, що його не досягти.
) Будується сама траса. Її побудова здійснюється від кінцевого елемента до початкового.
Гідність алгоритму в тому, що він дозволяє знайти шлях в будь-якому лабіринті (за умови, що шлях існує). Але головний недолік цього алгоритму в тому, що при побудові траси потрібен великий обсяг пам'яті.
Рисунок 10 - Приклад роботи хвильового алгоритму
. 3Обзор існуючих систем-аналогів
Існує безліч різних ігрових систем, розроблених на основі лабіринту. Розглянемо деякі з них.
. 3.1 Гра Pac-Man
На малюнку 11 зображення популярної гри Pac-Man [6]. Pac-Man? кругле жовте істота тільки з одним ротом.
Завдання гравця? зібрати (з'їсти) всі білі точки на рівні, уникаючи зіткнень з привидами. Рівень закінчується, коли з'їдені всі точки. Привиди на початку рівня знаходяться в центрі екрану в невеликій кімнаті, звідки вони виходять по одному, а один привид починає рівень поза кімнати. Кожне привид володіє індивідуальними характеристиками. Якщо Pac-Man «з'їсть» велику білу крапку? «Енерджайзер», то на кілька секунд привиди стають вразливими і самі уникають зустрічі з Pac-Man-ом. З'їдені в такій ситуації привиди не зникають, але повертаються в центр екрану, а гравцеві нараховуються додаткові очки, які зростають удвічі після поїдання кожного привиди. Якщо увійти в коридор, що веде направо або наліво за кордон екрану, то Pac-Man вийде з протилежного боку (це можуть зробити і привиди, однак, перед заходом в коридор вони сповільнюються, Pac-Man ж зберігає швидкість). Також на рівні можуть з'являтися різні бонуси? фрукти, з'ївши які, гравець отримує додаткові очки.
Малюнок 11 - Гра «Pac-Man»
. 3.2 Гра «Мудрий кріт»
На малюнку 12 представлена ??популярна в 90-і роки гра «Мудрий кріт». Ігрове поле являє собою лабіринт, в якому особливим чином розташована деяка кількість ящиків і така ж кількість спеціальних місць для їх розміщення. Це місця на тлі лабіринту виділені кольором. У лабіринті також розташовується кріт. Керуючи переміщенням крота треба розмістити ящики у відведені для цього місця. Одночасно кріт може переміщати строго один ящик. Результат - функція кількості кроків крота. Успішність вирішення завдання фіксується у файлі результатів [7].
Рисунок 12 - Гра «Мудрий кріт»
