Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Автоматизована система побудови лабіринту і пошуку виходу з нього

Реферат Автоматизована система побудови лабіринту і пошуку виходу з нього





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

Спробуємо описати робота, який діє відповідно до правилом правої руки .

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

) Після того як робот наткнувся на перешкоду, він починає пересуватися відповідно до правила правої руки .

) Рухаючись уздовж стіни, робот стежить, чи є прохід праворуч. Якщо прохід є, робот повинен йти по ньому, щоб не відірватися від стіни праворуч.

) Якщо проходу немає - попереду стіна - робот повертає ліворуч. Якщо проходу знову немає, він ще раз повертає ліворуч, таким чином розвертаючись на 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 - Гра «Мудрий кріт»


Назад | сторінка 3 з 18 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Опісові композіційно-мовленнєві форми в творах Т. Прохаська &З цього можна ...
  • Реферат на тему: Анексія Криму, як можна вірішіті Конфлікт України с Россией чі можна его ві ...
  • Реферат на тему: Мутації і нові гени. Чи можна стверджувати, що вони служать матеріалом Мак ...
  • Реферат на тему: Створення алгоритму пошуку високоінформативних діагностичних ознак захворюв ...
  • Реферат на тему: Ударні хвилі. Параметри ударної хвилі. Її вплив на людей, будівлі і спору ...