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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

Профессиональный подход. Алгоритмы построения и прохождения Лабиринтов [Электронный ресурс] - #"791993.files/image026.jpg">

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

При нажатии на кнопку «X» основная форма закрывается.

А.4.2 Установка параметров лабиринта и создание шаблона

Чтобы создать лабиринт в данной программе, необходимо, в первую очередь, выбрать желаемую тему оформления и настроить параметры лабиринта. Для этого в специально отведенных полях нужно задать ширину и высоту будущего лабиринта, и нажать кнопку "Создать шаблон". На поле слева появится сетка заданных размеров, изображенная на рисунке А.2.

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

А.4.3 Расстановка входа и выхода

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

Рисунок А.3 - Расстановка входа и выхода

А.4.4 Генерация лабиринта

После расставления входа и выхода необходимо нажать кнопку "Сгенерировать лабиринт". Готовый лабиринт изображен на рисунке А.4.

Рисунок А.4 - Пример генерации лабиринта

А.4.5 Поиск пути

Поиск пути в лабиринте осуществляется в данной программе одним из двух алгоритмов: волновым и "правой руки" (на выбор).

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

Рисунок А.5 - Волновой алгоритм

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

Рисунок А.6 - Алгоритм правой руки

А.4.6 Работа с файлами

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

Рисунок А.7 - Пункт меню «Файл»

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

Рисунок А.8 - Ошибка загрузки файла

А.4.7 Справочная информация о системе

При выборе из пункта меню «Справка» пункт «Сведения о системе» открывается справочное окно, содержащее информацию об авторах и документацию. Данное окно изображено на рисунке А.9.

Рисунок А.9 - Справка о системе

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

Приложение Б

Листинг программы

// основной класс Лабиринт

using System;System.Collections.Generic;System.Linq;System.Text;System.Data;System.Drawing;System.Windows.Forms;System.Diagnostics;System.Threading;System.IO;labirint

{labirint

{int[, ,] lab = new int[100, 100, 3]; // лабиринт: [i,j,0] - ячейки лабиринта, [i,j,1] - для волнового метода - длина волны, для однорукого метода - путь персонажа

public int[,] path = new int[10000, 2]; // обратный путь для волнового методаint countpath = 0; // количество шагов в пути волнового методаint xcells; // ячеек по горизонталиint ycells; // ячеек по вертикалиint xstart; // координаты стартовой позицииint ystart; // координаты стартовой позицииint xstop; // координаты конечной позицииint ystop; // координаты конечной позицииint tx; // текущее положение при одноруком методеint ty; // текущее положение при одноруком методеint way; // направление движения при одноруком методеint len; // текущая длина пути при одноруком методеint vert_rating=50; // вероятность в % создания вертикальной стенки в алгоритме Эйлераint hor_rating=50; // вероятность в % создания горизонтальной стенки в алгоритме Эйлераint state; // текущее состояние лабиринта:

// 0 - пуст, 1 - создан шаблон, 2 - расставлен вход, 3 - расставлены вход/выход, 4 - сгенерирован лабиринт

// 5 - выполняется поиск пути волновым методом, 6 - путь найден волновым методом

// 7 - выполняется поиск пути одноруким методом, 8 - путь найден одноруким методом

// 0 - пуст, 1 - создан шаблон, 2 - расставлены вход/выход, 3 - сгенерирован лабиринт

// генерация лабиринта алгоритмом Эйлера

// Достоинства алгоритма Эйлера:

// 1. отсутствуют зацикливания (имеется только один путь между двумя точками)

// 2. отсутствуют изолированые области

// 3. Из любой точки лабиринта в любую другую точку всегда существует путь

// 3. очень быстр

// 4. использует память эффективнее, чем другие популярные алгоритмы

public void generate_eiler()

{rnd = new Random();i, j, k, xx, yy, x1, tt, cn, tmn;

int mn = 0;

// очистим все ячейки лабиринта

for (i = 1; i < xcells - 1; i++)

{(j = 1; j < ycells - 1; j++)

{[i, j, 0] = 0;

}

}

// пройдем по строкам

for (j = 0; j < (ycells - 1) / 2; j++)

{= j * 2 + 1;

// присвоим ячейкам, не входящим ни в какое множество, свое уникальное множество

for (i = 0; i < (xcells - 1) / 2; i++)

{= i * 2 + 1;(lab[xx, yy, 0] == 0)

{[xx, yy, 0] = ++mn;

}

}

// пройдем слева направо по строке и расставим правые границы

for (i = 0; i < (xcells - 1) / 2; i++)

{= i * 2 + 1;(lab[xx, yy, 0] == lab[xx+2, yy, 0]) // текущая ячейка и ячейка справа принадлежат одному множеству

{[xx + 1, yy, 0] = 1; // поставим границу между ними[xx + 1, yy+1, 0] = 1;

}

{

// решим создавать правую границу между ячейками или нет

tt = rnd.Next(0, 100);(tt > vert_rating) // не создаем границу

{[xx+1, yy, 0] = 0;[xx+2, yy, 0] = lab[xx, yy, 0]; // объединим множества

}// создаем границу

{[xx + 1, yy, 0] = 1;

lab[xx + 1, yy + 1, 0] = 1;[xx + 1, yy - 1, 0] = 1;

}

}

}

// пройдем слева направо по строке и расставим нижние границы

for (i = 0; i < (xcells - 1) / 2; i++)

{= i * 2 + 1;= lab[xx, yy, 0];

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

cn = 0;(k = 0; k < (xcells - 1) / 2; k++)

{= k * 2 + 1;((lab[x1, yy, 0] == tmn) && (lab[x1, yy+1, 0]==0))

{++;

}

}(cn > 1) // если в текущем множестве ячейка с нижней границей не одна (больше)

{

// решим создавать нижнюю границу между ячейками или нет

tt = rnd.Next(0, 100);(tt > hor_rating) // не создаем границу

{[xx, yy+1, 0] = 0;

}// создаем границу

{[xx, yy + 1, 0] = 1;[xx + 1, yy + 1, 0] = 1;

lab[xx - 1, yy + 1, 0] = 1;

}

}

}

// скопируем текущую строку в следующую

for (i = 0; i < (xcells - 1) / 2; i++)

{= i * 2 + 1;[xx, yy + 2, 0] = lab[xx, yy, 0]; // скопируем ячейки

lab[xx, yy + 3, 0] = lab[xx, yy+1, 0]; // скопируем нижние границы[xx+1, yy + 2, 0] = 0; // удалим все правые границы(lab[xx, yy + 3, 0] == 1) // если ячейка имеет нижнюю границу

{[xx, yy + 2, 0] = 0; // удалим ее из множества

}[xx, yy + 3, 0] = 0; // удалим все нижние границы

}

}

// обработка последней строки= ycells - 2;

// скопируем текущую строку в следующую(i = 0; i < (xcells - 1) / 2; i++)

{= i * 2 + 1;[xx, yy, 0] = lab[xx, yy-2, 0]; // скопируем ячейки[xx+1, yy, 0] = lab[xx+1, yy-2, 0]; // скопируем правые границы[xx, yy + 1, 0] = lab[xx, yy - 1, 0]; // скопируем нижние границы(lab[xx, yy + 1, 0] == 1) // если ячейка имеет нижнюю границу

{[xx, yy, 0] = ++mn; // отнесем ее к новому множеству

}

}(i = 0; i < (xcells - 1) / 2; i++)

{= i * 2 + 1;

// если текущая ячейка и ячейка справа члены разных множеств

if (lab[xx, yy, 0] != lab[xx + 2, yy, 0])

{

// удалим правую границу[xx + 1, yy, 0] = 0;

// объединим множества= lab[xx + 2, yy, 0];

tt = lab[xx, yy, 0];= 0;(k = 0; k < (xcells - 1) / 2; k++)

{= k * 2 + 1;(lab[x1, yy, 0] == tmn)

{[x1, yy, 0] = tt;

}

}

}

}

// очистим проходы(j = 0; j < (ycells - 1) / 2; j++)

{= j * 2 + 1;(i = 0; i < (xcells - 1) / 2; i++)

{= i * 2 + 1;[xx, yy, 0] = 0;

}

}

// восстановим границы по периметру(i = 0; i < xcells; i++)

{[i, 0, 0] = 1;[i, ycells - 1, 0] = 1;

}(i = 0; i < ycells; i++)

{[0, i, 0] = 1;[xcells - 1, i, 0] = 1;

}[xstart-1, ystart-1, 0] = 2;[xstop-1, ystop-1, 0] = 3;

// с соседней (с входом) ячейки уберем стенку

if (xstart == 1) lab[xstart, ystart - 1, 0] = 0;(ystart == 1) lab[xstart - 1, ystart, 0] = 0;(xstart == xcells) lab[xstart - 2, ystart - 1, 0] = 0;(ystart == ycells) lab[xstart - 1, ystart - 2, 0] = 0;

// с соседней (с выходом) ячейки уберем стенку

if (xstop == 1) lab[xstop, ystop - 1, 0] = 0;(ystop == 1) lab[xstop - 1, ystop, 0] = 0;(xstop == xcells) lab[xstop - 2, ystop - 1, 0] = 0;(ystop == ycells) lab[xstop - 1, ystop - 2, 0] = 0;

}

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

// Ипользуется в процессе поиска выхода из лабиринта

public void Volna()

{i, j;

// элементы массива lab[i,j,1] содержат значение длины волны лабиринта

// инициализируем их значениями -1(i = 0; i < xcells; i++)

{(j = 0; j < ycells; j++)

{[i, j, 1] = -1;

}

}[xstart - 1, ystart - 1, 1] = 0; // на входе в лабиринт длина волны =0lastwave = -1; // номер текущей волныcou = 1; // количество ячеек, которые накрыла предыдущая волнаfound = false; // волна достала до выхода?(!found && (cou > 0)) // пока волна не дошла до выхода и пока предыдущая волна накрыла хоть сколько-нибудь ячеек

{= 0; // количество ячеек, которые накрыла волна

lastwave++; // номер текущей волны(i = 0; i < xcells; i++)

{(j = 0; j < ycells; j++)

{

// если

// существует ячейка сверку от текущей

// никакая предыдущая волна ее не накрывала

// и в этой ячейке не стена

if ((j > 0) && (lab[i, j - 1, 1] < 0) && (lab[i, j - 1, 0] != 1))

{[i, j - 1, 1] = lastwave + 1; // накрываем эту ячейку следующей волной++; // количество ячеек, которые накрыла волна

// если накрытая волной ячейка это выход, то включаем признак того, что волна достигла выхода

if (lab[i, j - 1, 0] == 3) found = true;

// на ячейке напишем номер волны, которой ее накрыло

/// gfr.DrawString(Convert.ToString(lastwave + 1), new Font("Tahoma", 8), Brushes.Gray, new Point((int)i * sizecell + sizecell / 3, (int)(j - 1) * sizecell + sizecell / 3));

}

// если

// существует ячейка снизу от текущей

// никакая предыдущая волна ее не накрывала

// и в этой ячейке не стена

if ((j < ycells - 1) && (lab[i, j + 1, 1] < 0) && (lab[i, j + 1, 0] != 1))

{[i, j + 1, 1] = lastwave + 1; // накрываем эту ячейку следующей волной++; // количество ячеек, которые накрыла волна

// если накрытая волной ячейка это выход, то включаем признак того, что волна достигла выхода

if (lab[i, j + 1, 0] == 3) found = true;

// на ячейке напишем номер волны, которой ее накрыло

/// gfr.DrawString(Convert.ToString(lastwave + 1), new Font("Tahoma", 8), Brushes.Gray, new Point((int)i * sizecell + sizecell / 3, (int)(j + 1) * sizecell + sizecell / 3));

}

// если

// существует ячейка слева от текущей

// никакая предыдущая волна ее не накрывала

// и в этой ячейке не стена

if ((i > 0) && (lab[i - 1, j, 1] < 0) && (lab[i - 1, j, 0] != 1))

{[i - 1, j, 1] = lastwave + 1; // накрываем эту ячейку следующей волной++; // количество ячеек, которые накрыла волна

// если накрытая волной ячейка это выход, то включаем признак того, что волна достигла выхода

if (lab[i - 1, j, 0] == 3) found = true;

// на ячейке напишем номер волны, которой ее накрыло

/// gfr.DrawString(Convert.ToString(lastwave + 1), new Font("Tahoma", 8), Brushes.Gray, new Point((int)(i - 1) * sizecell + sizecell / 3, (int)j * sizecell + sizecell / 3));

}

// если

// существует ячейка справа от текущей

// никакая предыдущая волна ее не накрывала

// и в этой ячейке не стена

if ((i < xcells - 1) && (lab[i + 1, j, 1] < 0) && (lab[i + 1, j, 0] != 1))

{[i + 1, j, 1] = lastwave + 1; // накрываем эту ячейку следующей волной++; // количество ячеек, которые накрыла волна

// если накрытая волной ячейка это выход, то включаем признак того, что волна достигла выхода

if (lab[i + 1, j, 0] == 3) found = true;

// на ячейке напишем номер волны, которой ее накрыло

/// gfr.DrawString(Convert.ToString(lastwave + 1), new Font("Tahoma", 8), Brushes.Gray, new Point((int)(i + 1) * sizecell + sizecell / 3, (int)j * sizecell + sizecell / 3));

}

}

}

}

/// pictureBox1.Refresh(); // обновить изображение pictureBox1 на форме

/// Thread.Sleep(100); // сделаем паузу на указанное количество миллисекунд