Курсовая работа (т): Автоматизированная система построения лабиринта и поиска выхода из него

Автоматизированная система построения лабиринта и поиска выхода из него

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С. П. КОРОЛЁВА

(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)» Факультет          Информатики

Кафедра    Программных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

по теме «Автоматизированная система построения лабиринта и поиска выхода из него»

Студенты О.П.Казакова

А.В.Потапова

Руководитель Л.С.Зеленко

Самара 2014

Содержание

Введение

         Описание предметной области

.1      Классификация лабиринтов

.1.1   Естественные лабиринты

.1.2   Искусственные лабиринты

.2      Описание алгоритмов поиска пути

.2.1   Алгоритм «одной руки»

.2.2   Волновой алгоритм

.3      Обзор существующих систем-аналогов

.3.1   Игра Pac-Man

.3.2   Игра «Мудрый крот»

.4      Диаграмма объектов предметной области

.5      Постановка задачи

.        Проектирование системы

.1      Разработка структурной схемы

.2      Спецификация системы

.2.1   Функциональная спецификация

.2.3   Спецификация качества

.3      Проектирование интерфейса пользователя

.4      Информационно-логический проект системы

.4.1   Язык UML        

.4.2   Диаграмма вариантов использования

.4.3   Диаграмма состояний

.4.4   Диаграмма деятельности

.4.5   Диаграмма последовательности

.5      Выбор и обоснование комплекса программных средств

.5.1   Выбор языка программирования и среды разработки    

.5.2   Выбор операционной системы

         Реализация системы

.1      Разработка и описание интерфейса пользователя

.1.1   Разработка и описание пользовательского меню

.1.2   Описание контрольного примера

.2      Диаграммы реализации       

.2.1   Диаграмма компонентов

.3      Выбор и обоснование комплекса технических средств

.3.1   Минимальные требования, предъявляемые к системе      

Заключение

Список использованной литературы

Приложение А

Приложение Б

Введение

лабиринт алгоритм интерфейс

Слово "лабиринт" греческого происхождения, и переводится как подземные ходы или подземелье. В природе существует много подземных пещер с огромным количеством ходов, перекрестков и тупиков. Есть примеры и других природных лабиринтов, например, шхеры - множество мелких островков, составляющих единую группу. В шхерах десятки фарватеров, проливов, заливов, бухт, в которых нетрудно заблудиться [1].

Но существуют лабиринты и искусственного происхождения, созданные человеком вольно или невольно. Примером невольного создания лабиринтов являются различные шахты, рудники, каменоломни, называемые общим словом "Катакомбы". Чаще всего под словом "лабиринт" подразумевают искусственное, специально созданное, чрезвычайно сложное сооружение. Происхождение таких "лабиринтов" довольно древнее. Например, Геродот описывает египетский лабиринт, в котором было 5000 комнат. Сначала лабиринты носили религиозно-мистический характер, но в более поздние времена стали предметом развлечений, перейдя в сады и парки в виде живой изгороди сложной конфигурации. В наше время, по утверждению Мартина Гарднера, существует две области науки, в которых интерес к лабиринтам остается неизменно высоким: психология и конструирование вычислительных машин.

Однако существует еще одна область человеческой деятельности, в которой лабиринты являются необходимым атрибутом - это компьютерные игры. Действительно, почти все игры приключенческих жанров и аркады используют лабиринты. Встречаются они и в других жанрах: логические игры, экшен, изредка в симуляторах. В связи с этим у пользователя компьютера появляются две задачи: прохождение лабиринтов в игровых программах и создание лабиринтов для "своих" программ.

В курсовом проекте необходимо разработать автоматизированную систему построения односвязного лабиринта, в котором основная цель - дойти до конечной локации, при этом, кроме стен у игрока нет никаких других препятствий.

При реализации проекта будет использоваться методология быстрой разработки приложений RAD (Rapid Application Development - быстрая разработка приложений) [2]. Данная модель очень хорошо подходит к разработке учебных программ, т.к. включает в себя три составляющие:

−       небольшую команду программистов (от 2 до 4 человек);

−       короткий, но тщательно проработанный производственный график (от 2 до 4 мес.);

−       повторяющийся цикл, при котором разработчики по мере того, как приложение начинает обретать форму, запрашивают и реализуют в продукте требования, полученные через взаимодействие с заказчиком.

При проектировании будет использоваться UML (Unified Modeling Language - унифицированный язык моделирования) - стандартный инструмент для разработки «чертежей» программного обеспечения. Его можно использовать для визуализации, спецификации, конструирования и документирования артефактов программных систем. UML подходит для моделирования любых систем - от информационных систем масштаба предприятия до распределенных Web-приложений и даже встроенных систем реального времени. Язык UML предоставляет стандартный способ написания проектной документации на системы, включая концептуальные аспекты, такие как бизнес-процессы и функции системы, а также конкретные аспекты, такие как выражения языков программирования, схемы баз данных и повторно используемые компоненты ПО.

1.      Описание предметной области

Лабири́нт (др.-греч. <https://ru.wikipedia.org/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%BA> λαβύρινθος) - какая-либо структура (обычно в двухмерном или трёхмерном пространстве), состоящая из запутанных путей к выходу (и/или путей, ведущих в тупик). Под лабиринтом у древних греков <https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B5%D1%86%D0%B8%D1%8F> и римлян <https://ru.wikipedia.org/wiki/%D0%A0%D0%B8%D0%BC> подразумевалось более или менее обширное пространство, состоящее из многочисленных залов, камер, дворов и переходов, расположенных по сложному и запутанному плану, с целью запутать и не дать выхода несведущему в плане лабиринта человеку [3].

.1Классификация лабиринтов

По своему происхождению все лабиринты можно разделить на две категории: естественные и искусственные.

.1.1Естественные лабиринты

Естественный лабиринт - лабиринт, к созданию которого человек не имеет никакого отношения, все они были созданы природой. К таким лабиринтам можно отнести:

Природные пещеры. В природе существует много подземных пещер с огромным количеством ходов, перекрестков и тупиков. Пример изображен на рисунке 1.

Рисунок 1 - Пример природной пещеры

Шхеры - архипелаг <https://ru.wikipedia.org/wiki/%D0%90%D1%80%D1%85%D0%B8%D0%BF%D0%B5%D0%BB%D0%B0%D0%B3>, состоящий из мелких скалистых островов <https://ru.wikipedia.org/wiki/%D0%9E%D1%81%D1%82%D1%80%D0%BE%D0%B2>, разделённых узкими проливами <https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%BB%D0%B8%D0%B2> и покрывающих значительную часть прибрежной морской полосы, окаймляя берега фьордового <https://ru.wikipedia.org/wiki/%D0%A4%D1%8C%D0%BE%D1%80%D0%B4> типа. Каждый из таких островков в отдельности называется «шхера». Пример шхер изображен на рисунке 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Алгоритм «одной руки»

Одним из самых простых правил для прохождения лабиринта является правило "одной руки": двигаясь по лабиринту, надо все время касаться правой или левой рукой его стены [4]. Этот алгоритм, вероятно, был известен еще древним грекам. Придется пройти долгий путь, заходя во все тупики, но в итоге цель будет достигнута.

Попробуем описать робота, действующего в соответствии с правилом "правой руки".

) В начале своей работы робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду.

) После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом "правой руки".

) Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа.

) Если прохода нет - впереди стена - робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.

Если же лабиринт содержит отдельно стоящие стенки, то, применяя правило "одной руки", не всегда можно пройти все коридоры и тупики. Лабиринты с отдельно стоящими стенками и с замкнутыми маршрутами называются многосвязными. При этом многосвязные лабиринты можно разделить на две группы: без "петли" вокруг цели (замкнутый маршрут не проходит вокруг цели) и с замкнутой "петлей" вокруг цели (цель можно обойти по замкнутому маршруту).

Рисунок 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 - Игра «Мудрый крот»

.4 Диаграмма объектов предметной области

Процесс представления предметной области задачи в виде совокупности объектов, обменивающихся сообщениями, называется объектной декомпозицией [8].

При объектной декомпозиции между объектами устанавливается отношения:

Использования - первый объект (активный) передает сообщение другому (пассивному), между ними могут быть объекты посредники.

Включения - если объект является результатов декомпозиции более сложного объекта.

Объектная декомпозиция, так же как и процедурная, может применяться многократно, или быть многоуровневой. Это значит, что каждый объект может рассматриваться как система, которая состоит из элементов, взаимодействующих друг с другом через передачу сообщений. При многоуровневой декомпозиции на каждом уровне мы получаем объекты с более простым поведением, что позволяет разрабатывать системы повышенной сложности по частям.

Объект - элемент системы, объединяющий в себе в себе данные и операции над ними, обладающий свойствами наследования, инкапсуляции и полиморфизма.