а моделювання) - стандартний інструмент для розробки «креслень» програмного забезпечення. Його можна використовувати для візуалізації, специфікації, конструювання та документування артефактів програмних систем. UML підходить для моделювання будь-яких систем - від інформаційних систем масштабу підприємства до розподілених Web-додатків і навіть вбудованих систем реального часу. Мова UML надає стандартний спосіб написання проектної документації на системи, включаючи концептуальні аспекти, такі як бізнес-процеси і функції системи, а також конкретні аспекти, такі як вираження мов програмування, схеми баз даних і повторно використовувані компоненти ПЗ.
1. Опис предметної області
лабіри? нт (др.-греч. lt;http://ru.wikipedia/wiki/%D0%94%D1%80%D0%B5%D0%B2%D0%BD%D0%B5%D0%B3%D1%80%D0%B5%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BAgt; ??????????) - Яка-небудь структура (зазвичай в двовимірному чи тривимірному просторі), що складається із заплутаних шляхів до виходу (і/або шляхів, що ведуть в тупик). Під лабіринтом у стародавніх греків lt; https: //ru.wikipedia/wiki/%D0%93%D1%80%D0%B5%D1%86%D0%B8%D1%8Fgt; і римлян lt; https: //ru.wikipedia/wiki/%D0%A0%D0%B8%D0%BCgt; малося на увазі більш-менш велике простір, що складається з численних залів, камер, дворів і переходів, розташованих по складному і заплутаному планом, з метою заплутати і не дати виходу необізнаній в плані лабіринту людині [3].
.1Классіфікація лабіринтів
За своїм походженням всі лабіринти можна розділити на дві категорії: природні та штучні.
.1.1Естественние лабіринти
Природний лабіринт - лабіринт, до створення якого людина не має ніякого відношення, всі вони були створені природою. До таких лабіринтах можна віднести:
Природні печери. У природі існує багато підземних печер з величезною кількістю ходів, перехресть і тупиків. Приклад зображений на малюнку 1.
Рисунок 1 - Приклад природного печери
Шхери - архіпелаг lt; https: //ru.wikipedia/wiki/%D0%90%D1%80%D1%85%D0%B8%D0%BF%D0%B5%D0%BB%D0 % B0% D0% B3 gt ;, що складається з дрібних скелястих островів lt; https: //ru.wikipedia/wiki/%D0%9E%D1%81%D1%82%D1%80%D0%BE%D0% B2 gt ;, розділених вузькими протоками lt; https: //ru.wikipedia/wiki/%D0%9F%D1%80%D0%BE%D0%BB%D0%B8%D0%B2gt; і покривають значну частину прибережної морської смуги, облямований берега фьордового lt; https: //ru.wikipedia/wiki/%D0%A4%D1%8C%D0%BE%D1%80%D0%B4gt; типу. Кожен з таких острівців окремо називається «шахраям». Приклад шхер зображений на малюнку 2.
Малюнок 2 - Приклад шхер
Мурашники. На малюнку 3 добре видно, що ходи в мурашнику утворюють своєрідний лабіринт.
Малюнок 3 - Приклад мурашника в розрізі
1.1.2Іскусственние лабіринти
Існують лабіринти і штучного походження, створені людиною вільно чи мимоволі. Найчастіше під словом Лабіринт подразумевают штучне, спеціально створене, надзвичайно складна споруда. До таких лабіринтах відносяться:
Різні шахти, рудники, каменоломні, звані загальним словом «Катакомби». Приклад зображений на малюнку 4.
Малюнок 4 - Приклад катакомб
Дернові лабіринти. Приклад таких лабіринтів зображений на малюнку 5. У XIII-XIX століттях лабіринтами називали особливого роду садові прикраси, що складаються з більш-менш високих живоплотів або з трельяжів, обсаджені рослинами, які розташовані так, що між ними утворюються доріжки, що ведуть до одного центру, але изгибающиеся в різні боки і сполучені між собою настільки хитромудро, що гуляє нелегко дістатися до цього центру, також як і знайти зворотний шлях.
Ігрові лабіринти. До цих лабіринтах можна віднести ігрові атракціони (наприклад, дзеркальний лабіринт, зображений на малюнку 6). Також лабіринт часто є частиною комп'ютерних ігор, виконаних в 2D і 3D графіку. Приклади таких ігор зображені на малюнках 7 і 8.
Малюнок 5 - Приклад дернового лабіринту
Малюнок 6 - Приклад дзеркального лабіринту
Малюнок 7 - Приклад лабіринту в 2D - грі
Рисунок 8 - Приклад лабіринту в 3D - грі
. 2 Опис алгоритмів пошуку шляху
У даному курсовому проекті необхідно реалізувати два алгоритму пошуку шляху: алгоритм «однієї руки» і хвильової алгоритм.
. 2.1Алгорітм «однієї руки»
Одним з найпростіших правил для проходження лабіринту є правило однієї руки raquo ;: рухаючись по лабіринту, треба весь час стосуватися правою чи лівою рукою його стіни [4]. Цей алгоритм, ...