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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

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

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

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

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

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

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

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

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

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

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

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

Самара 2014



Содержание

Введение

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

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

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

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

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

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

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

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

1.3.1 Игра Pac-Man

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

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

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

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

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

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

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

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

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

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

2.4.1 Язык UML

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

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

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

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

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

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

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

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

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

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

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

3.2 Диаграммы реализации

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

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

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

Заключение

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

Приложение А

Приложение Б



Введение

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

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

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

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

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

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

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

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

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

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



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

Лабиримнт (др.-греч. лбвэсйнипт) - какая-либо структура (обычно в двухмерном или трёхмерном пространстве), состоящая из запутанных путей к выходу (и/или путей, ведущих в тупик). Под лабиринтом у древних греков и римлян подразумевалось более или менее обширное пространство, состоящее из многочисленных залов, камер, дворов и переходов, расположенных по сложному и запутанному плану, с целью запутать и не дать выхода несведущему в плане лабиринта человеку [3].

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

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

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

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

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



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

Шхеры - архипелаг, состоящий из мелких скалистых островов, разделённых узкими проливами и покрывающих значительную часть прибрежной морской полосы, окаймляя берега фьордового типа. Каждый из таких островков в отдельности называется «шхера». Пример шхер изображен на рисунке 2.

Рисунок 2 - Пример шхер

Муравейники. На рисунке 3 хорошо видно, что ходы в муравейнике образуют своеобразный лабиринт.

Рисунок 3 - Пример муравейника в разрезе



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

Существуют лабиринты и искусственного происхождения, созданные человеком вольно или невольно. Чаще всего под словом "Лабиринт" подразумевают искусственное, специально созданное, чрезвычайно сложное сооружение. К таким лабиринтам относятся:

Различные шахты, рудники, каменоломни, называемые общим словом «Катакомбы». Пример изображен на рисунке 4.

Рисунок 4 - Пример катакомб

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

Игровые лабиринты. К этим лабиринтам можно отнести игровые аттракционы (например, зеркальный лабиринт, изображенный на рисунке 6). Также лабиринт часто является частью компьютерных игр, выполненных в 2D и 3D графике. Примеры таких игр изображены на рисунках 7 и 8.



Рисунок 5 - Пример дернового лабиринта

Рисунок 6 - Пример зеркального лабиринта

Рисунок 7 - Пример лабиринта в 2D - игре



Рисунок 8 - Пример лабиринта в 3D - игре

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

В данном курсовом проекте необходимо реализовать два алгоритма поиска пути: алгоритм «одной руки» и волновой алгоритм.

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

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

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

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

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

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

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

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

Рисунок 9 - Схема алгоритма "правой руки"

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

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

Волновой алгоритм позволяет построить путь между двумя элементами в любом лабиринте [5]. Сам процесс можно разделить на 2 этапа:

1) Из начального элемента распространяется в 4-х направлениях волна. Элемент, в который пришла волна, образует фронт волны. На рисунке цифрами обозначены номера фронтов волны.

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

2) Строится сама трасса. Её построение осуществляется от конечного элемента к начальному.

Достоинство алгоритма в том, что он позволяет найти путь в любом лабиринте (при условии, что путь существует). Но главный недостаток этого алгоритма в том, что при построении трассы требуется большой объем памяти.

Рисунок 10 - Пример работы волнового алгоритма

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

Существует множество различных игровых систем, разработанных на основе лабиринта. Рассмотрим некоторые из них.

1.3.1 Игра Pac-Man

На рисунке 11 изображение популярной игры Pac-Man [6]. Pac-Man ? круглое жёлтое существо только с одним ртом.

Задача игрока ? собрать (съесть) все белые точки на уровне, избегая столкновений с привидениями. Уровень заканчивается, когда съедены все точки. Привидения в начале уровня находятся в центре экрана в небольшой комнате, откуда они выходят по одному, а одно привидение начинает уровень вне комнаты. Каждое привидение обладает индивидуальными характеристиками. Если Pac-Man «съест» большую белую точку ? «энерджайзер», то на несколько секунд привидения становятся уязвимыми и сами избегают встречи с Pac-Man-ом. Съеденные в такой ситуации привидения не исчезают, но возвращаются в центр экрана, а игроку начисляются дополнительные очки, которые возрастают вдвое после поедания каждого привидения. Если войти в коридор, ведущий направо или налево за границу экрана, то Pac-Man выйдет с противоположной стороны (это могут сделать и привидения, однако, перед заходом в коридор они замедляются, Pac-Man же сохраняет скорость). Также на уровне могут появляться различные бонусы ? фрукты, съев которые, игрок получает дополнительные очки.

Рисунок 11 - Игра «Pac-Man»

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

На рисунке 12 представлена популярная в 90-е годы игра «Мудрый крот». Игровое поле представляет собой лабиринт, в котором особым образом расположено некоторое количество ящиков и такое же количество специальных мест для их размещения. Это места на фоне лабиринта выделены цветом. В лабиринте также располагается крот. Управляя перемещением крота надо разместить ящики в отведенные для этого места. Одновременно крот может перемещать строго один ящик. Результат - функция количества шагов крота. Успешность решения задачи фиксируется в файле результатов [7].

Рисунок 12 - Игра «Мудрый крот»

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

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

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

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

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

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

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

Диаграмма объектов представляет статическую составляющую взаимодействующих между собой объектов, она должна включить в себя только те объекты предметной области, которые потом преобразуются в диаграмму классов. Связи между объектами показывают отношения между ними, при необходимости в диаграмме можно привести и атрибуты(свойства) объектов [2]. На рисунке 13 приведена диаграмма объектов для рассматриваемой системы.

Как видно из диаграммы, лабиринт представляет собой совокупность следующих объектов: сетки, на которой будут располагаться стены и проходы, которые подразделяются на обычные проходы между стенами, вход и выход из лабиринта; персонажа (курсор, движущийся объект и т.д.), который движется по проходу.

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

Перед авторами поставлена задача разработать автоматизированную систему генерирования лабиринта и поиска пути в нем.



Рисунок 13 - Диаграмма объектов предметной области

Для достижения поставленной цели необходимо решить следующие задачи:

Настройка параметров лабиринта. Задание параметров лабиринта производится вручную: пользователь должен задать размеры лабиринта по ширине и высоте (от 7 до 21 клетки), размер лабиринта должен быть нечетный; должен выбрать тему лабиринта (одну из четырех); должен определить местоположение входа и выхода из лабиринта, которые не должны совпадать и должны располагаться по периметру лабиринта. При этом система должна провести проверку правильности этой структуры и, в случае несоответствия, выдать предупредительное сообщение и обеспечить повторный ввод параметров.

Автоматическая генерация лабиринта. В системе будет использоваться два алгоритма генерации лабиринта: прореживания и «основного пути».

Работа с файлами. Пользователь должен иметь возможность сохранить лабиринт в файл и загрузить его из файла.

Поиск пути. Пользователь должен выбрать, с помощью какого алгоритма будет найден путь (волновой или «правой руки»).

Визуализация процессов работы с лабиринтом. Пользователь должен выбрать вид визуализации: статическая (с задержкой по времени) или динамическая (с оставлением следов).

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

Таким образом, система должна выполнять следующие функции:

Настройка параметров лабиринта:

задание размеров;

выбор темы;

расставление входа/выхода;

Автоматическое построение (генерация) лабиринта:

алгоритм прореживания;

алгоритм «основного пути»;

Поиск пути:

алгоритм «правой руки»;

волновой алгоритм;

Сохранение лабиринта в файл;

Загрузка лабиринта из файла;

Визуализация процессов работы с лабиринтом:

динамическая;

статическая;

Выдача справочной информации о системе.



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

Система (греч. «составленное из частей», «соединение» от «соединяю») множество элементов, находящихся в отношениях и связях друг с другом, которое образует определённую целостность, единство [2] .

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

Как следует из определения, отличительным (главным свойством) системы является ее целостность: комплекс объектов, рассматриваемых в качестве системы, должен обладать общими свойствами и поведением. Очевидно, необходимо рассматривать и связи системы с внешней средой. В самом общем случае понятие «система» характеризуется:

? наличием множества элементов;

? наличием связей между ними;

? целостным характером данного устройства или процесса.

Система должна представлять собой совокупность элементов (объектов, субъектов), находящихся между собой в определенной зависимости и составляющих некоторое единство (целостность), направленное на достижение определенной цели. Система может являться элементом другой системы более высокого порядка (надсистема) и включать в себя системы более низкого порядка (подсистемы). То есть систему можно рассматривать как набор подсистем, организованных для достижения определенной цели и описанных с помощью набора моделей (возможно, с различных точек зрения), а подсистему - как группу элементов, часть которых составляет спецификацию поведения, представленного другими ее составляющими [8].

На рисунке 14 приведена структурная схема системы.

В состав системы входят следующие подсистемы:

1) Подсистема управления, которая отвечает за взаимодействие подсистем между собой и представлена в виде иерархического меню;

2) Подсистема составления лабиринта, в состав которой входят:

a) подсистема настройки параметров, которая отвечает за ввод (выбор) значений параметров лабиринта и проверку корректности этих значений;

b) подсистема генерирования, которая отвечает за автоматическое составление лабиринта;

3) Подсистема нахождения пути, которая отвечает за поиск пути в лабиринте в соответствии с выбранным алгоритмом;

4) Файловая подсистема, которая отвечает за хранение лабиринта в файле заранее определенного типа;

5) Подсистема визуализации, которая отвечает за корректное отображение лабиринта у пользователя и дает возможность выбора оформления;

6) Справочная подсистема, которая содержит сведения о системе (руководство пользователю) и ее об ее разработчиках.

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

Требования - это свойства, которыми должно обладать ПО для адекватного определения функций, условий и ограничений выполнения ПО, а также объемов данных, технического обеспечения и среды функционирования [2].

Программные требования (Software Requirements) - свойства программного обеспечения, которые должны быть надлежащим образом представлены в нём для решения конкретных практических задач [11]. Данная область знаний касается вопросов извлечения (сбора), анализа, специфицирования и утверждения требований к разрабатываемой ПС.

Спецификация требований к ПО (SRS) - процесс формализованного описания функциональных и нефункциональных требований, требований к характеристикам качества в соответствии со стандартом качества ISO/IEC 9126-94, которые будут отрабатываться на этапах жизненного цикла ПО. В спецификации требований отражается:

? структура ПО;

? требования к функциям, качеству и документации;

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

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

Функциональные требования задают то, что система должна делать; нефункциональные - с соблюдением «каких условий» (например, скорость отклика при выполнении заданной операции). При разработке этих требований в первую очередь необходимо учитывать потребности пользователя (заказчика). Пользовательские требования (User Requirements) - описывают цели/задачи пользователей системы, которые должны достигаться/выполняться пользователями при помощи создаваемой программной системы. Часто пользовательские требования представляют в виде сценариев (вариантов использования) [2].

Функциональная спецификация должна в полном объёме отображать информационные связи проектируемой системы как с внешним миром, так и между подсистемами. Перечень функций, выполняемых автоматизированной системой составления и разгадывания классического кроссворда содержится в таблице 1.

2.2.2 Перечень исключительных ситуаций

Исключительная ситуация - это ситуация, при которой система не может выполнить возложенных на нее функций или которая может привести к денормализации работы системы. Перечень исключительных ситуаций представлен в таблице 2.

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

Разработка спецификации качества сводится к построению своеобразной модели качества разрабатываемой ПС [2]. В этой модели должен быть перечень всех тех достаточно элементарных свойств, которые требуется обеспечить в разрабатываемом ПС и которые в совокупности образуют приемлемое для пользователя качество ПС. При этом каждое из этих свойств должно быть в достаточной степени конкретизировано с учетом определения требований к разрабатываемому ПС и возможности оценки его наличия у разработанного ПС или необходимой степени обладания им этим ПС.

Для конкретизации качества ПС по каждому из критериев используется стандартизованный набор достаточно простых свойств ПС однозначно интерпретируемых разработчиками.

В спецификации качества перечисляются основные требования по показателям качества:

описывается уровень надежности ПС;

формулируются требования по быстродействию;

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

Таблица 1 - Перечень функций, выполняемых системой

Название подсистемы	Название функции	Информационная среда
		Входные данные	Выходные данные
		Назначение (наименование)	Тип, ограничения	Назначение (наименование)	Тип, ограничения
1 Справочная	1.1 Выдать сведения о разработчиках	Сведения о разработчиках системы (ФИО, номер группы)	Текст (МЕМО)	Визуальное отображение информации	_
	1.2 Выдать сведения о системе	Файл справки	Текстовый (*.HTML)
				Код ошибки	Целое
2 Настройки параметров	2.1 Задать высоту лабиринта	Диапазон значений: минимальное максимальное	Целое 7 21	Текущее значение высоты	Целое, нечетное
	2.2 Задать ширину лабиринта	Диапазон значений: минимальное максимальное	Целое 7 21	Текущее значение ширины	Целое, нечетное
	2.3 Принять параметры лабиринта	Текущие значения высоты и ширины	Целые	Лабиринт (шаблон)	Объект, структура определяется в ходе проектирования
	2.4 Выбрать способ расстановки	Варианты расстановки	Ручной Автоматический	Текущий способ расстановки	перечислимый
	2.5 Поставить вход (для ручной расстановки)	Координаты клеток, текущие значения высоты и ширины	Целые, на периметре, не в углах	Лабиринт (шаблон)	Объект, структура определяется в ходе проектирования
Название подсистемы	Название функции	Информационная среда
		Входные данные	Выходные данные
		Назначение (наименование)	Тип, ограничения	Назначение (наименование)	Тип, ограничения
2 Настройки параметров	2.6 Поставить выход (для ручной расстановки)	Координаты клеток, текущие значения высоты и ширины	Целые, на периметре, не в углах, не совпадает с входом	Лабиринт (шаблон)	Объект, структура определяется в ходе проектирования
	2.7 Сгенерировать лабиринт	Лабиринт (шаблон)	Объект, структура определяется в ходе проектирования	Лабиринт	Объект, структура определяется в ходе проектирования
	2.8 Выбрать оформление	Варианты оформления	Лето Осень Зима Весна	Текущая тема оформления	Перечислимый
3 Файловая	3.1 Сохранить лабиринт в файл	Лабиринт	Объект, структура определяется в ходе проектирования	Файл	Файл, структура определяется в ходе проектирования
		Имя файла	Строка, *.lab
	3.2 Загрузить лабиринт из файла	Имя файла	Строка, *.lab	Лабиринт	Объект, структура определяется в ходе проектирования
Название подсистемы	Название функции	Информационная среда
		Входные данные	Выходные данные
		Назначение (наименование)	Тип, ограничения	Назначение (наименование	Тип, ограничения
4 Визуализация	4.1 Отобразить текущее состояние лабиринта	Лабиринт	Объект, структура определяется в ходе проектирования	Визуальное отображение лабиринта	-
		Текущее оформление	Перечислимый
	4.2 Отобразить путь (для волнового алг.)	Путь	Массив целых чисел	Визуальное отображение пути	-
	4.3 Отобразить текущее состояние клетки	Лабиринт	Объект, структура определяется в ходе проектирования	Визуальное отображение клетки	-
		Координаты клетки	Целые
		Статус клетки	Стена Проход След Персонаж
5 Нахождения пути	5.1 Выбрать алгоритм	Список алгоритмов	Волновой Одной руки	Текущий алгоритм	Перечислимый
	5.2 Найти путь (для волнового алгоритма)	Лабиринт	Объект, структура определяется в ходе проектирования	Путь	Массив целых чисел
Название подсистемы	Название функции	Информационная среда
		Входные данные	Выходные данные
		Назначение (наименование)	Тип, ограничения	Назначение (наименование)	Тип, ограничения
5 Нахождения пути	5.3 Определить статус текущей клетки	Координаты клетки	Целые	Статус текущей клетки	Стена Проход След Персонаж
		Лабиринт	Объект, структура определяется в ходе проектирования

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Таблица 2 - Перечень исключительных ситуаций

Название подсистемы	Название исключительной ситуации	Реакция системы
1 Справочная	1.1 Не возможно открыть файл справки	Выдача сообщения «Файл справки поврежден»
	1.2 Не возможно найти файл справки	Выдача сообщения «Отсутствует файл справки»
2 Файловая	2.1 Попытка открытия файла с несобственным форматом	Выдача сообщения «Файл поврежден или недопустимого формата»
	2.2 Файл с заданным именем не существует	Выдача аналогичного сообщения
	2.3 Недопустимое имя файла	Выдача сообщения «Неверное имя файла»

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

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

Интерфейс является основной и наиболее важной частью программы. Поскольку пользователь управляет программой и данными именно через интерфейс, мы уделяем большое внимание понятности и простоте интерфейсов в разработанных нами программах [2].

Для выполнения начальной фазы разработки необходимо погрузиться целиком в задачи пользователей и создать бумажный прототип интерфейса.

При запуске программы будет появляться главное окно программы, представленное на рисунке 14.

При нажатии на кнопку «X» основная форма будет закрываться. При нажатии кнопки «Файл», когда никакой лабиринт еще не будет сгенерирован, пользователю будет предложено загрузить лабиринт из файла. При нажатии кнопки «Справка» справочное окно, содержащее информацию об авторах и документацию.

Сначала пользователь выбирает тему оформления лабиринта по своему желанию (по умолчанию выбрана тема «Лето»). В полях «Высота» и «Ширина» пользователь должен будет задать соответствующие значения будущего лабиринта. При нажатии кнопки «Создать шаблон» на поле справа появляется сетка для будущего лабиринта заданных размеров.

Рисунок 14 - Интерфейс (главное окно программы)

Область «Вход/выход» становится доступной на этом шаге. Пользователю предложено выбрать один из способов расстановки входа выхода. После нажатия кнопки «Расставить» вход и выход расставляются соответствующим способом и появляется кнопка «Сгенерировать лабиринт». После ее нажатия, на поле справа появляется лабиринт, в меню «Файл» появляется возможность сохранить лабиринт и становится доступным поле «Поиск пути».

Пользователь выбирает способ, которым программа будет находить путь в лабиринте и нажимает кнопку «Искать путь». В зависимости от выбранного алгоритма, на поле отображается найденный путь.

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

Одной из широко используемых методик документирования требований является построение ряда моделей системы. Эти модели используют графические представления, показывающие решения как исходной задачи, так и разрабатываемой системы [2]. Как правило, графическое представление более понятно, чем описание требований на естественном языке.

Моделирование - это устоявшаяся и повсеместно принятая инженерная методика. Модели являются связующим звеном между процессом анализа и процессом проектирования системы. Модель - это упрощенное представление реальности, по существу - это «чертеж» системы: в нее может входить как детальный план, так и более абстрактное представление системы «с высоты птичьего полета». Хорошая модель всегда включает элементы, которые существенно влияют на результат, и не включает те, которые малозначимы на данном уровне абстракции. Модель строится для того, чтобы лучше понимать разрабатываемую систему. Моделирование позволяет решить четыре различные задачи:

Визуализировать систему в ее текущем или желательном для нас состоянии;

Описать структуру или поведение системы;

Получить шаблон, позволяющий сконструировать систему;

Документировать принимаемые решения, используя полученные модели.

2.4.1 Язык UML

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

Язык UML не является языком программирования (он инвариантен к языкам программирования).

В нотации языка UML определены следующие виды канонических диаграмм:

вариантов использования (use case diagram);

классов (class diagram);

кооперации (collaboration diagram);

последовательности (sequence diagram);

состояний (statechart diagram);

деятельности (activity diagram);

компонентов (component diagram);

развертывания (deployment diagram).

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

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

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

? Определить общие границы и контекст моделируемой предметной области на начальных этапах проектирования системы.

? Сформулировать общие требования к функциональному поведению проектируемой системы.

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

? Подготовить исходную документацию для взаимодействия разработчиков системы с ее заказчиками и пользователями.

Актер (actor) - согласованное множество ролей, которые играют внешние сущности по отношению к вариантам использования при взаимодействии с ними (это может быть любой объект, субъект или система, взаимодействующая с моделируемой бизнес-системой извне, т.е. человек, техническое устройство, программа и т.п.) .

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

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

На рисунке 15 приведена диаграмма вариантов использования для разрабатываемой системы (она соответствует функциональной спецификации, приведенной в таблице 1).

В возможности пользователя входит:

создать лабиринт. Чтобы создать лабиринт, пользователь должен задать соответствующие параметры, такие как ширина, высота, тема оформления лабиринта. Также, необходимым условием является расставление входа и выхода (автоматически или вручную);

найти путь. Пользователь может осуществить поиск пути из лабиринта в соответствии с выбранным алгоритмом;

сохранить лабиринт в файл;

загрузить лабиринт из файла;

просмотр справочной информации о системе и об авторах.

Сценарий - определенная последовательность действий, которая описывает действия актеров и поведение моделируемой системы в форме обычного текста.

В контексте языка UML сценарий используется для дополнительной иллюстрации взаимодействия актеров и вариантов использования.

Рассмотрим сценарии варианта использования «Установить параметры лабиринта» и «Поиск пути» для автоматизированной системы построения лабиринта и поиска выхода из него.

Вариант использования: Установить параметры лабиринта.

Краткое описание. Даёт возможность пользователю задать параметры лабиринта, которые будут использованы при дальнейшей работе программы.

Рисунок 15 - Диаграмма вариантов использования системы

Актант. Пользователь.

Предусловия. Компьютер пользователя включён, приложение «Лабиринт» запущено. На экране - окно приложения с блоками «Параметры лабиринта», «Поиск пути» и полем для лабиринта.

Основной поток событий.

1 В лабиринте находятся активный блок «тема» (лето, осень, зима, весна), поле «высота», поле «ширина», кнопка «создать шаблон», неактивные блоки «расстановка входа/выхода» и «поиск пути», кнопки «расставить», «сгенерировать», «искать путь». Пользователь выбирает тему, задает высоту и ширину и щелкает кнопку «Создать шаблон».

А1: Щёлкнута кнопка « ».

2 Система создает шаблон лабиринта и отображает его на поле, блок «расстановка входа/выхода» и кнопка «расставить» становятся активными.

3 Пользователь выбирает способ расстановки входа и выхода «Автоматически» и щелкает кнопку «Расставить».

А2: Пользователь расставляет вход и выход вручную.

4 Система определяет координаты входа и выхода и отображает их на поле (по периметру и не в углах). Кнопка «Сгенерировать» становится активной.

5 Пользователь щелкает кнопку «Сгенерировать».

6 Система генерирует лабиринт на поле. Вариант использования завершается успешно.

Альтернативы.

А1: Щёлкнута кнопка « ».

А1.1 Система закрывает окно приложения и выводит на экран главное окно операционной системы. Вариант использования завершается.

А2: Пользователь расставляет вход и выход вручную.

А 2.1 Пользователь устанавливает вход в лабиринт.

А 2.2 Пользователь устанавливает выход из лабиринта.

А 2.3 Система проверяет расстановку входа и выхода.

А 2.3.1 Вход и выход успешно расставлены. Осуществляется переход к п.5 основного потока событий.

А 2.3.2 Вход и выход расставлены неверно.

А 2.3.2.1 Система выводит сообщение о неверной расстановке и просит повторить попытку.

А 2.3.2.2 Осуществляется переход к п.3 основного потока событий.

Постусловия. При успешном завершении на экране - главная форма приложения с лабиринтом, сгенерированным в соответствии с заданными пользователем параметрами.

Вариант использования: Поиск пути

Краткое описание. Даёт возможность пользователю найти путь в лабиринте, сгенерированном пользователем или загруженном из файла.

Актант. Пользователь.

Предусловия. Компьютер пользователя включён, приложение «Лабиринт» запущено. На экране - окно приложения с блоками «Параметры лабиринта», «Поиск пути» и сгенерированным лабиринтом.

Основной поток событий.

1 В блоке «поиск пути» отображены доступные алгоритмы «Волновой» и «Одной руки». Пользователь выбирает один из алгоритмов и щелкает кнопку «Искать путь».

2 Система осуществляет поиск пути, и в соответствии с выбранным алгоритмом отображает его на лабиринте. Вариант использования завершается успешно.

Постусловия. При успешном завершении на экране - главная форма приложения с лабиринтом, сгенерированным в соответствии с заданными пользователем параметрами, на котором отображен путь, найденный в соответствии с выбранным алгоритмом.

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

Диаграмма состояний описывает процесс изменения состояний только одного класса, а точнее - одного экземпляра определенного класса, т. е. моделирует все возможные изменения в состоянии конкретного объекта. [2]

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

На рисунке 16 представлена диаграмма состояний системы, на которой изображены все возможные состояния и переходы. После запуска приложения пользователь может либо загрузить лабиринт, либо перейти непосредственно к созданию лабиринта. Для этого он должен задать параметры лабиринта, после чего создать шаблон, расставить вход и выход и сгенерировать лабиринт. После генерации пользователь может сохранить лабиринт либо продолжить работу с ним и найти путь в нем. Вызов справочной информации доступен на любом этапе работы программы.

Рисунок 16 - Диаграмма состояний системы

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

Диаграммы деятельности - это один из пяти видов диаграмм, применяемых в UML для моделирования динамических аспектов поведения системы. Диаграмма деятельности - это, по существу, блок-схема, которая показывает, как поток управления переходит от одной деятельности к другой. Как правило, они применяются, чтобы промоделировать последовательные (а иногда и параллельные) шаги вычислительного процесса. Диаграммы деятельности могут использоваться самостоятельно для визуализации, специфицирования, конструирования и документирования динамики совокупности объектов, но они пригодны также и для моделирования потока управления при выполнении некоторой операции.

На рисунке 17 представлена диаграмма деятельности, соответствующая варианту использования «Установить параметры лабиринта». Чтобы сгенерировать лабиринт, пользователь должен: выбрать тему оформления, задать высоту и ширину лабиринта, выбрать способ расставления входа и выхода (автоматически или вручную).

Рисунок 17 - Диаграмма деятельности для варианта использования «Установить параметры лабиринта»

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

Диаграмма последовательности (sequence diagram) - диаграмма, на которой показаны взаимодействия объектов, упорядоченные по времени их проявления.

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

На рисунке 18 представлена диаграмма последовательности для варианта использования «Установить параметры лабиринта».

Пользователь задает параметры (тема оформления, высота, ширина) на форме задания параметров лабиринта, после чего нажимает кнопку «Создать шаблон». Этот шаблон создается в классе лабиринт и отображается на поле для лабиринта. Затем происходит возврат на форму задания параметров, где пользователь выбирает способ расстановки входа и выхода (автоматически или вручную). Координаты входа/выхода передаются в класс лабиринт, после чего на поле происходит отображение координат на поле. Далее пользователь нажимает кнопку «Сгенерировать лабиринт», в классе происходит его создание.



Рисунок 18 - Диаграмма последовательности для варианта использования «Установить параметры лабиринта»

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

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

Для реализации проекта по созданию автоматизированной системы построения лабиринта и поиска выхода из него, языком программирования был выбран С#, среда разработки Visual Studio 2013.

Среда разработки Visual Studio, поставляемая вместе с .NET, предоставляет необходимый инструментарий для эффективного и быстрого создания приложений с графическим интерфейсом.

Появление технологии .NET повлекло за собой массовую реконструкцию некоторых языков программирования, стремящихся использовать те или иные возможности платформы, такие как C++ и Visual Basic. Microsoft решили предложить разработчикам альтернативу - язык, ориентированный специально .NET и создали C#. Сами разработчики языка описывают его, как простой, современный, объектно-ориентированный и безопасный язык программирования. Синтаксически C# напоминает C++ и Java, что позволило программистам за достаточно короткое время изучить тонкости нового языка.

Несмотря на то, что C# и .NET предназначены в первую очередь для веб-разработки, их также активно применяют для создания приложений, которые должны устанавливаться на машине конечного пользователя, где и будет выполняться вся обработка данных. Разработку таких приложений обеспечивает библиотека Windows Forms, позволяющая проектировать графический интерфейс. Система, описанная в данной работе, разработана именно с помощью библиотеки Windows Forms.

Обоснование выбора языка программирования

Язык программирования C# претендует на подлинную объектную ориентированность.

Язык программирования C# призван реализовать компонентно-ориентированный подход к программированию, который способствует меньшей машинно-архитектурной зависимости результирующего программного кода, большей гибкости, переносимости и легкости повторного использования программ.

Принципиально важным отличием от предшественников является изначальная ориентация на безопасность кода.

Расширенная поддержка событийно-ориентированного программирования.

Язык программирования C# является «родным» для создания приложений в среде Microsoft .NET, поскольку наиболее тесно и эффективно интегрирован с ней.

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

Разрабатываемая программная система будет поддерживаться на операционных системах семейства Windows. К основным преимуществам Windows относят:

1) Единый пользовательский интерфейс;

2) Многозадачность;

3) Стабильность работы;

4) Удобство пользовательского интерфейса;

5) Большое количество поддерживаемых приложений;

6) Распространенность ОС.



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

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

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

На рисунке 19 представлен вид главной формы приложения.

Рисунок 19 - Главная форма приложения

На основной форме приложения существуют поля, необходимые для создания лабиринта. Пока не создан шаблон лабиринта, остальные пункты на панели пользователю недоступны. Для создания шаблона необходимо задать параметры лабиринта и щелкнуть по кнопке «Создать шаблон».

Для того, чтобы расставить вход/выход, необходимо выбрать соответствующий способ их расстановки и нажать кнопку «Расставить». После этого нужно нажать кнопку «Сгенерировать» для генерации лабиринта на поле справа.

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



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

Меню приложения «Файл» включает следующие пункты:

«Сохранить лабиринт»;

«Загрузить лабиринт»

Меню приложения «Справка» включает следующие пункты:

«Сведения о системе»;

«Информация о разработчиках».

При выборе пункта «Загрузить лабиринт» откроется диалоговое окно для загрузки существующих файлов с лабиринтом. Пункт меню «Сохранить лабиринт» недоступен, если никакой лабиринт еще не создан.

При выборе пункта меню «Сведения о системе» откроется справка в формате html с кратким описанием программы. При выборе пункта меню «Информация о разработчиках» на экран будет выведена справка о разработчиках программы в формате rtf.

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

Рассмотрим в качестве примера создание лабиринта размерами 21х21 клетку и поиск пути в нем с помощью алгоритма «правой руки».

Для создания шаблона необходимо задать данные размеры в соответствующих полях ширины и высоты, которые отмечены на рисунке 20, и нажать кнопку «Создать шаблон». На поле справа появляется сетка размерами 21х21 клетку, а поле вход/выход становится доступным.

После создания шаблона для того, чтобы перейти непосредственно к генерации лабиринта, необходимо выбрать способ расстановки и расставить на поле вход и выход из лабиринта.



Рисунок 20 - Создание шаблона лабиринта

Для этого выбираем нужный способ расстановки на поле, отмеченном на рисунке 21 и нажимаем кнопку «Расставить».

Рисунок 21 - Расстановка входа/выхода

После того как на поле расставлены вход и выход, в меню становится доступной кнопка «Сгенерировать лабиринт». Нажимаем эту кнопку и получаем сгенерированный лабиринт, изображенный на рисунке 22.



Рисунок 22 - Генерация лабиринта

После того как сгенерирован лабиринт, становится доступным поле поиска пути. В соответствии с заданным примером выбираем алгоритм «Одной руки» и получаем в результате путь, изображенный на рисунке 23.

Рисунок 23 - Результат работы алгоритма «Одной руки».

3.2 Диаграммы реализации

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

Диаграмма компонентов описывает особенности физической реализации системы в момент перехода от логического представления к конкретной реализации системы. Диаграмма компонентов позволяет определить архитектуру разрабатываемой системы, установив зависимости между программными компонентами, в роли которых может выступать исходный, бинарный и исполняемый код. Основными графическими элементами диаграммы компонентов являются компоненты, интерфейсы и зависимости между ними [3].

Диаграмма компонентов разрабатываемой системы представлена на рисунке 24. Главная форма приложения взаимодействует с классом лабиринт, с графическими файлами для оформления лабиринта и файлами со справочной информацией о разработчиках и системе.

Рисунок 24 - Диаграмма компонентов

3.2.2 Диаграмма развертывания

Диаграмма развертывания предназначена для визуализации элементов и компонентов программы, существующих лишь на этапе ее исполнения (runtime). Она содержит графические изображения процессоров, устройств, процессов и связей между ними. В отличие от диаграмм логического представления, диаграмма развертывания является единой для системы в целом, поскольку должна всецело отражать особенности ее реализации. Для реализуемой системы в качестве операционной системы может выступать Windows 7,8. (Рисунок 25)



Рисунок 25 - Диаграмма развертывания

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

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

К системе устанавливаются следующие требования:

тип ЭВМ - IBM PC совместимый;

монитор с разрешающей способностью не ниже 800 х 600;

манипулятор - мышь;

технические характеристики определяются в процессе выполнения курсового проекта.

Должно быть установлено следующее программное обеспечение:

тип операционной системы - Windows 98 и выше, Windows 7, 8.

язык программирования - С#;

среда программирования - Visual Studio 2013;

среда проектирования - StarUML 5.0.



Заключение

В соответствии с техническим заданием был произведен анализ предметной области, реализовано программное и информационное обеспечение, подготовлены контрольные примеры и произведены тестирование и отладка автоматизированной системы генерации лабиринта и поиска выхода из него.

Спроектированная система имеет интуитивно понятный интерфейс для пользователя, проста в использовании, не требует серьезных аппаратных затрат.

При выполнении работы использовалась методология объектно-ориентированного анализа и проектирования, кроме того применялась технология быстрой разработки приложений RAD.



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

Профессиональный подход. Алгоритмы построения и прохождения Лабиринтов [Электронный ресурс] - http://zxpress.ru/article.php?id=1782 (дата обращения 17.09.2014 г.);

Методические указания к лабораторному практикуму по дисциплине «Программная инженерия» [Электронный ресурс]. - Мин-во обр. и науки РФ, Самар. гос. аэрокосм. ун-т им. С. П. Королева (нац. исслед. ун-т). - Самара, 2013.

Википедия [Электронный ресурс] - http://ru.wikipedia.org/wiki/ Лабиринт (дата обращения 11.10.2014 г.);

Прохождение лабиринта: Правила и алгоритмы [Электронный ресурс] - http://myrobot.ru/articles/logo_mazesolving.php (дата обращения 17.11.2014 г.);

Обход препятствий: волновой алгоритм (Алгоритм Ли) [Электронный ресурс] -http://suvitruf.ru/2012/05/13/1176/ (дата обращения 25.10.2014 г.)

Википедия [Электронный ресурс] - http://ru.wikipedia.org/wiki/ Pac-Man (дата обращения 26.10.2014 г.);

Индивидуальные задания на практику [Электронный ресурс] - http://rguitp-pi.narod.ru/practice/indzadan.htm (дата обращения 26.10.2014 г.);

Объектная декомпозиция. Рекомендации к объектной декомпозиции [Электронный ресурс] - http://proger.org.ua/index.php/oop/114-obektnaya-dekompozitsiya-rekomendatsii-k-obektnoj-dekompozitsii (дата обращения 5.11.2014 г.)



Приложение А

Руководство пользователя

А.1 Назначение системы

Данное приложение представляет собой программу, реализующую автоматизированную систему генерации лабиринта и поиска выхода из него.

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

А.2 Условия работы системы

Для корректной работы системы необходимо наличие соответствующих программных и аппаратных средств.

Требования:

персональный компьютер с ОС Windows XP или выше;

не менее 1425 Мб оперативной памяти;

10,4322 Гб на жестком диске;

дисплей с разрешением не менее 1024 x 768 пикселей;

клавиатура или иное устройство ввода;

мышь или иное манипулирующее устройство.

А.3 Установка системы

Запускаемым файлом системы является файл labirint.exe. Его можно открыть без использования дополнительных программ.