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

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

Министерство образования и науки РФ

Брянский государственный технический университет

Кафедра: «Компьютерные технологии и системы»

Дисциплина: «Языки программирования»

КУРСОВОЙ ПРОЕКТ

на тему:

Выбор оптимального маршрута для строительства дороги

Выполнил Хорахонов В.А.

студент группы 15-ИАС:

Преподаватель: Леонов Ю.А.

Брянск 2015

ОГЛАВЛЕНИЕ

• ВВЕДЕНИЕ
• ТЕХНИЧЕСКОЕ ЗАДАНИЕ
• 1. АНАЛИТИЧЕСКИЙ РАЗДЕЛ
• 1.1 Обзор и анализ существующих программных решений
• 1.2 Определение функциональных требований к разрабатываемой программной системе
• 2. КОНСТРУКТОРСКИЙ РАЗДЕЛ
• 2.1 Обоснование выбора языка и среды программирования
• 2.2 Функциональная схема работы программы
• 2.3 Организация данных и проектирование интерфейсов обмена данными в программной системе
• 2.4 Описание используемых методов и алгоритмов
• 2.5 Выбор графического и пользовательского интерфейса
• 3. ТЕХНОЛОГИЧЕСКИЙ РАЗДЕЛ
• 3.1 Определение структуры и состава программной системы
• 3.2 Разработка алгоритма отдельной подзадачи
• 3.3 Руководство пользователя
• 4. ЭКСПЕРИМЕНТАЛЬНЫЙ РАЗДЕЛ
• 4.1 Виды контроля качества разрабатываемого ПО
• 4.2 Методика проведения и результаты тестирования
• 4.3 Методы и способы устранения ошибок
• 4.4 Отладка выявленных ошибок, обнаруженных при тестировании
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• ПРИЛОЖЕНИЯ

Введение

В данном курсовом проекте по дисциплине «Языки программирования» описаны алгоритмы функционирования разрабатываемой программы.

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

Процесс подготовки и решения задачи состоит из нескольких этапов:

· постановка задачи;

· построение модели;

· разработка алгоритма;

· написание и отладка программы на языке программирования;

· тестирование программы.

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

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

ТЕХНИЧЕСКОЕ ЗАДАНИЕ

На курсовой проект по дисциплине «Языки программирования»

Студент Хорахонов В.А. Группа 15-ИАС

Тема «Выбор оптимального маршрута для строительства дороги»

Общая формулировка задания

Необходимо разработать программу реализации выбора оптимального маршрута для строительства дороги с использованием языка программирования C#.

Требования к графическому и пользовательскому интерфейсам:

· программа должна работать в графическом режиме;

· обеспечить понятный и простой интерфейс программы;

· в программе должны использоваться визуальные элементы управления (графическое меню, кнопки).

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

· должен быть реализован алгоритм установки опорных пунктов маршрута;

· должна присутствовать возможность перехода от карты местности к карте стоимостей;

· необходимо реализовать изменение стоимости определенного вида объекта;

· должен быть реализован алгоритм нахождения кратчайшего маршрута между двумя опорными пунктами;

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

Руководитель Рощин С.М.

1. Аналитический раздел

1.1 Обзор и анализ существующих программных решений

Из доступных программных решений можно выделить пару программ.

Первая программа

SusaninLab 1.2 - программа для решения и визуализации задач коммивояжера - поиска кратчайшего пути между несколькими точками (городами, станциями и т.п.) и построения связующего дерева с минимальной стоимостью (рис. 1.1).

SusaninLab 1.2 представляет собой набор из двух ActiveX компонентов - ELGraphVisio (создание и редактирование графика в режиме конструктора, добавление и удаление узлов и ребер) и ELSusaninPath (поиск кратчайшего пути между несколькими узлами и создание связующего дерева), которые позволят решить задачи оптимизации и логистики.

Рис. 1.1 Интерфейс программы SusaninLab 1.2

Вторая программа

Поиск кратчайшего пути в лабиринте с использованием Delphi (рис. 1.2).

Поиск осуществляется с применением рекурсивного алгоритма, сам лабиринт легко нарисовать в текстовом файле, а затем загрузить в программу.

Рис. 1.2 Интерфейс программы

1.2 Определение функциональных требований к разрабатываемой программной системе

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

· программа должна иметь простой, но в то же время понятный и наглядный интерфейс, который не должен перегружать ресурсы компьютера;

· программа должна создавать массив карты из файла;

· в программе должна производиться прорисовка карт стоимостей;

· пользователь должен иметь возможность перехода между двумя картами;

· необходимо очищать предыдущую карту при переходе на следующую карту;

· необходимо определять позицию ячейки, а также индексы строки и столбца;

· программа должна прорисовывать опорные точки маршрута (начало и конец пути);

· пользователь должен иметь возможность изменения стоимостей объектов местности;

· программа должна вычислять расстояние между опорными пунктами;

· должно происходить определение доступных вершин на игровом поле для совершения хода;

· в данной программе должен быть реализован метод нахождения кратчайшего пути с помощью заданного алгоритма;

· программа должна прорисовывать оптимальный путь на карте;

· работоспособность приложения в среде Windows.

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

2. Конструкторский раздел

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

Для реализации данного курсового проекта был выбран язык программирования Visual C#. Язык основан на строгой компонентной архитектуре и реализует передовые механизмы обеспечения безопасности кода. Язык программирования C# объединил лучшие черты целого ряда предшественников, а именно Basic, C, C++.

От языка программирования C++ языком C# унаследованы следующие механизмы: "перегруженные" операторы, небезопасные арифметические операции с плавающей точкой, а также ряд других особенностей синтаксиса.

Но, несмотря на то, что целый ряд конструктивных синтаксических механизмов и особенностей реализации унаследован языком программирования C# от прародителей (C++ и Java), возможности этого нового языка программирования не ограничиваются суммой возможностей его исторических предшественников.

К числу принципиально важных решений, которые реализованы корпорацией Microsoft в языке программирования C#, можно отнести следующие:

· компонентно-ориентированный подход к программированию;

· свойства как средство инкапсуляции данных (характерно также в целом для ООП);

· обработка событий (имеются расширения, в том числе в части обработки исключений, в частности, оператор try);

· унифицированная система типизации;

· делегаты (delegate - развитие указателя на функцию в языках C и C++);

· индексаторы (indexer - операторы индекса для обращения к элементам класса-контейнера);

· перегруженные операторы (развитие ООП);

· оператор foreach (обработка всех элементов классов-коллекций, аналог Visual Basic);

· механизмы boxing и unboxing для преобразования типов;

· атрибуты (средство оперирования метаданными в COM-модели);

· прямоугольные массивы (набор элементов с доступом по номеру индекса и одинаковым количеством столбцов и строк).

Приведенные выше особенности языка C# повлияли на выбор языка программирования и соответственно среды Visual Studio для программы.

2.2 Функциональная схема работы программы

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

Рис. 2.1 Функциональная схема

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

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

Массив данных определяется для функции прорисовки карты.

После всего этого осуществляется функция вывода конечного результата.

2.3 Организация данных и проектирование интерфейсов обмена данными в программной системе

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

Выводимые данные это то, что сообщается пользователю. Входные данные это то, что пользователь сообщает программе.

Выводимые данные в программе представлены в виде графического отображения окна программы (рис. 2.2).

Рис. 2.2 Окно программы

Входные данные представлены в виде программного кода, который необходимо выполнить при определенных действиях пользователя, а именно:

· нажатие клавиш мыши;

· ввода значений;

· работа пользователя с кнопками на форме.

2.4 Описание используемых методов и алгоритмов

В данном пункте нужно проанализировать используемый алгоритм поиска кратчайшего пути.

Алгоритм Дейкстры

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

Смысл этого способа заключается в том, что обходятся все вершины, начиная с заданной, при этом каждой присваивается метка с некоторым значением. Затем в результат войдут те вершины, метки которых минимальны. На первом шаге исходной вершине присваивается метка со значением 0. Затем рассматриваются все следующие вершины, то есть те, в которые можно попасть из исходной. Им присваиваются метки, значение которых определяется как сумма исходника и веса пути. Из вершин следующего шага выбирается та, что имеет наименьшее значение метки, и изучаются все вершины, в которые из нее можно пройти, не используя промежуточных вершин. Определяется новое значение метки, равное метке вершины - исходника плюс вес пути. Если полученное значение меньше, чем метка вершины, то метка изменяется. В противном случае остается исходное значение. При этом в отдельном массиве, размерность которого равна количеству вершин графа, сохраняется результат оптимизации, по которому и определяется путь.

Главным достоинством алгоритма является простота реализации.

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

2.5 Выбор графического и пользовательского интерфейса

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

Рассмотрев несколько вариантов пользовательского интерфейса представленных на рисунках 2.3 и 2.4, был выбран наиболее оптимальный для простого пользователя (рис. 2.4).

Рис. 2.3 Первый вариант интерфейса

Достоинствами первого варианта являются визуально легко-воспринимаемое представление элементов управления и компактность.

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

Рис. 2.4 Второй вариант интерфейса

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

программный алгоритм маршрут дорога

3. Технологический раздел

3.1 Определение структуры и состава программной системы

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

Поля данных:

· public int countRow, countCol - переменные для хранения количества строк и столбцов;

· int cellWidth, cellHeight - переменные для хранения ширины и высоты ячейки;

· int[,] map - массив для создания и заполнения карты местности;

· int[,] mapCost - массив для создания и заполнения карты стоимостей;

· int startX, startY - переменные для хранения начальных значений x и y;

· public int Row, Col - переменные структуры Checkpoint для хранения строк и столбцов соответственно;

Структуры:

· public struct Checkpoint - структура контрольных точек;

· public struct Vertex - структура вершин.

Конструктор:

· public RoadOptimal(string pathFile, PictureBox pb, int costPath, int costGrass, int costForest, int costHome, Checkpoint? startPoint, Checkpoint? endpoint, bool curMap) - конструктор, который создает массив “map” из файла.

Методы:

· private void GetPos(int x, int y, out int row, out int col) - метод для определения позиции (row, col) ячейки;

· public int GetRow(int x, int y) - метод для определения индекса строки;

· public int GetCol(int x, int y) - метод для определения индекса столбца;

· private void GetPosForm(int row, int col, out int x, out int y) - метод для определения координат левого верхнего угла ячейки;

· private int GetX(int row, int col) - метод для определения координаты x;

· private int GetY(int row, int col) - метод для определения координаты y;

· public void DrawPoint(bool start) - метод прорисовки опорной точки (начала или конца пути);

· public void DrawMapCost() - метод прорисовки карты стоимостей;

· public void ClearMap() - метод очистки карты;

· public void DrawMap() - метод прорисовки карты;

· private double Distance(Vertex p1, Vertex p2) - метод вычисления расстояния между двумя точками, координаты row,col;

· private List<Vertex> GetAvailablePositions(List<Vertex> listLastVertex, Vertex c) - метод определения доступных вершин на игровом поле для совершения хода;

· private Vertex? GetNextStep(List<Vertex> listLstVertex, Vertex curPos, Vertex end) - метод для определения следующего хода;

· public List<Vertex> FindOptimalPath(Vertex srart, Vertex end) - метод нахождения кратчайшего пути с помощью алгоритма Дейкстры;

· public void DrawOptimalPath(List<Vertex> list) - метод прорисовки оптимального пути на карте местности.

3.2 Разработка алгоритма отдельной подзадачи

Разработаем алгоритм одного из основных методов, используемого в данной программе.

private void pictureBox1_MouseDown(objects sender, MouseEventArgs e)

Представим основной алгоритм работы метода в виде блок-схемы (рис. 3.1):

Рис. 3.1 Блок-схема алгоритма

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

Для начала в файл “map1.txt” записываем массив, состоящий из 0,1 и 2. Данные цифры означают объекты: трава, лес и горд соответственно (рис. 3.2).



Рис. 3.2 Работа с файлом “map1.txt”

Запускаем программу «Выбор оптимального маршрута для строительства дороги» (рис. 3.3).

Рис. 3.3 Запуск программы «Выбор оптимального маршрута для строительства дороги»

Затем пользователь выбирает стоимости подготовки и прокладки дороги (рис. 3.4).

Рис. 3.4 Выбор стоимости подготовки и прокладки дороги

После этого пользователь проставляет опорные пункты на карте местности (начальная и конечная точки маршрута). После данной операции на карте сразу рисуется оптимальный путь, заданный алгоритмом (рис. 3.5).

Рис. 3.5 Проставление опорных пунктов, прорисовка пути

Следующим действием является переход на карту стоимостей, получение конечного результата (рис. 3.6).

Рис. 3.6 Получение конечного результат

4. Экспериментальный раздел

4.1 Виды контроля качества разрабатываемого ПО

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

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

Основные принципы организации тестирования:

· необходимой частью каждого теста программы должно являться описание ожидаемых результатов работы программы, чтобы можно было быстро выяснить наличие или отсутствие ошибки в ней;

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

· подробное изучение результатов каждого теста, чтобы не пропустить малозаметную на поверхностный взгляд ошибку в программе;

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

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

4.2 Методика проведения и результаты тестирования

При разработке данной программы были допущены следующие синтаксические ошибки:

· неправильное использование операторов присваивания;

· неверное объявление циклов.

При тестировании были выполнены следующие принципы:

· тщательность подбора данных для теста программы, не только для правильных (предусмотренных) входных данных, но и для неправильных (непредусмотренных);

· доскональное изучение результатов тестирования.

4.3 Методы и способы устранения ошибок

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

· узнавать текущие значения переменных;

· выяснять, по какому пути выполнялась программа.

Существуют две взаимодополняющие технологии отладки:

· использование отладчиков -- программ, которые включают в себя пользовательский интерфейс для пошагового выполнения программы: оператор за оператором, функция за функцией, с остановками на некоторых строках исходного кода или при достижении определённого условия;

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

Отладка состоит из следующих этапов:

1. Воспроизведение дефекта (любым из доступных способов);

2. Анализ дефекта (поиск причины возникновения дефекта);

3. Дизайн исправления дефекта;

4. Кодирование исправления дефекта;

5. Валидация исправления;

6. Интеграция исправления в кодовую базу или целевую систему;

7. Дополнительные валидации после интеграции.

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

4.4 Отладка выявленных ошибок, обнаруженных при тестировании

Все синтаксические ошибки были исправлены при компиляции проекта, учитывая синтаксические особенности среды программирования.

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

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

ЗАКЛЮЧЕНИЕ

При написании программного комплекса курсовой работы использовался язык C Sharp, среда программирования - Microsoft Visual Studio.

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

Достоинства:

· был создан удобный и понятный интерфейс, понятный даже пользователю, не имеющему опыт работы с подобными программами;

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

Недостатки:

· работоспособность приложения только в среде Windows.

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

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

Список использованных источников

1. Павловская Т.А. C#. Программирование на языке высокого уровня. Изд.: Питер, 2009. - 432 с.

2. Дейтел Х. C# в подлиннике. Наиболее полное руководство. - Изд.: БХВ-Петербург, 2008. - 1056 с.

3. Троелсен Э. Язык программирования C# 2010 и платформа .NET 4. - Изд.: Вильямс, 2011. - 1392 с.

4. Нейгел К., Ивьен Б., Глинн Д., Уотсон К., Скиннер М. C# 4.0 и платформа .NET 4 для профессионалов. - Изд.: Питер, 2011. - 1440 с.

ПРИЛОЖЕНИЕ 1

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

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.IO;

using System.Windows.Forms;

using System.Drawing;

namespace SearchOptimalPathOnRoad

{

public struct Checkpoint

{

private int row, col;

private bool have;

public int Row

{

get { return row; }

set { row = value; have = true; }

}

public int Col

{

get { return col; }

set { col = value; have = true; }

}

public bool Have

{

get { return have; }

set { have = value; }

}

public Checkpoint(int row, int col)

{

this.row = row;

this.col = col;

have = true;

}

public Checkpoint(bool have)

{

this.row = 0;

this.col = 0;

this.have = have;

}

}

//

public struct Vertex

{

public int Row { get; set; }

public int Col { get; set; }

public Vertex(int row, int col) : this()

{

Row = row;

Col = col;

}

}

//...............

class RoadOptimal

{

public bool curMap;

public int countRow, countCol;

int cellWidth, cellHeight;

int[,] map;

int[,] mapCost;

int startX = 0, startY = 0;

PictureBox pb;

Graphics g;

public Bitmap bm;

Pen pen;

Font font, fontPoint;

Brush brush;

public Checkpoint startPoint, endPoint; // координаты (row, col) начальной

и конечных точек

Bitmap imgGrass, imgForest, imgHome;

List<Vertex> listLastVertex;

int costPath;

//......................................................................

// Конструктор, который создает массив "map" из файла

//......................................................................

public RoadOptimal(string pathFile, PictureBox pb,

int costPath, int costGrass, int costForest, int costHome,

Checkpoint? startPoint, Checkpoint? endPoint, bool curMap)

{

this.curMap = curMap;

this.pb = pb;

this.costPath = costPath;

StreamReader sr = new StreamReader(pathFile);

List<string> list = new List<string>();

// Подсчитываем количество строк (row) и столбцов (col) карты

string s = "";

countCol = 0;

countRow = 0;

while (sr.Peek() >= 0)

{

s = sr.ReadLine();

list.Add(s);

if (s.Trim().Length > 0) countRow++;

}

countCol = s.Length;

sr.Close();

// Создание и заполнение карт местности и стоимостей

map = new int[countRow, countCol];

mapCost = new int[countRow, countCol];

for (int i = 0; i < list.Count; i++)

{

for (int j = 0; j < list[i].Length; j++)

{

map[i, j] = int.Parse(list[i][j].ToString());

switch (map[i, j])

{

case 0: mapCost[i, j] = costGrass; break; // трава

case 1: mapCost[i, j] = costForest; break; // лес

case 2: mapCost[i, j] = costHome; break; // город

default: mapCost[i, j] = costForest; break; // лес

}

}

}

// Вычисляем ширину и высоту одной ячейки

cellWidth = pb.Width / countCol;

cellHeight = pb.Height / countRow;

if (cellWidth < cellHeight) cellHeight = cellWidth;

else cellWidth = cellHeight;

bm = new Bitmap(pb.Width, pb.Height);

g = Graphics.FromImage(bm);

pen = new Pen(Color.Gray, 3);

// Вычисляем размер шрифта

double sizeFont = 12.0 / 50 * cellWidth;

if (sizeFont <= 6) sizeFont = 6;

font = new Font("Times New Roman", (float)sizeFont);

fontPoint = new Font("Times New Roman", (float)sizeFont * 2,

FontStyle.Bold);

brush = new SolidBrush(Color.Black);

if (startPoint != null) this.startPoint = (Checkpoint)startPoint;

else this.startPoint = new Checkpoint(false);

if (endPoint != null) this.endPoint = (Checkpoint)endPoint;

else this.endPoint = new Checkpoint(false);

//

Bitmap bm1 = new Bitmap("image/grass.png");

imgGrass = new Bitmap(bm1, cellWidth, cellHeight);

Bitmap bm2 = new Bitmap("image/forest.png");

imgForest = new Bitmap(bm2, cellWidth, cellHeight);

Bitmap bm3 = new Bitmap("image/home.png");

imgHome = new Bitmap(bm3, cellWidth, cellHeight);

listLastVertex = new List<Vertex>();

}

//......................................................................

// Метод для определения позиции (row, col) ячейки

//......................................................................

private void GetPos(int x, int y, out int row, out int col)

{

row = (y - startY) / cellHeight;

col = (x - startX) / cellWidth;

}

//......................................................................

// Метод для определения индекса строки

//......................................................................

public int GetRow(int x, int y)

{

return (y - startY) / cellHeight;

}

//......................................................................

// Метод для определения индекса столбца

//......................................................................

public int GetCol(int x, int y)

{

return (x - startX) / cellWidth;

}

//......................................................................

// Метод для определения координат левого верхнего угла ячейки

//......................................................................

private void GetPosForm(int row, int col, out int x, out int y)

{

x = startX + col * cellWidth;

y = startY + row * cellHeight;

}

//......................................................................

// Метод для определения координаты x

//......................................................................

private int GetX(int row, int col)

{

return startX + col * cellWidth;

}

//......................................................................

// Метод для определения координаты y

//......................................................................

private int GetY(int row, int col)

{

return startY + row * cellHeight;

}

//......................................................................

// Метод прорисовки опорной точки (начала или конца пути)

//......................................................................

public void DrawPoint(bool start)

{

Brush brushRed = new SolidBrush(Color.Red);

Bitmap bitmap;

string s = "";

// Если точка есть, то ее удаляем (восстанавливаем изображение на

месте точки)

Checkpoint curPoint = start ? startPoint : endPoint;

if (curPoint.Have && curMap)

{

switch (map[curPoint.Row, curPoint.Col])

{

case 0: bitmap = imgGrass; break;

case 1: bitmap = imgForest; break;

case 2: bitmap = imgHome; break;

default: bitmap = imgForest; break;

}

g.FillRectangle(new SolidBrush(Color.White), GetX(curPoint.Row,

curPoint.Col), GetY(curPoint.Row, curPoint.Col), cellWidth, cellHeight);

}

if (curPoint.Have && !curMap)

{

s = mapCost[curPoint.Row, curPoint.Col].ToString();

Brush bGrenYellow = new SolidBrush(Color.GreenYellow); // трава

Brush bGreen = new SolidBrush(Color.Green); // лес

Brush bGray = new SolidBrush(Color.Gray); // дом

Brush b = bGrenYellow;

switch (map[curPoint.Row, curPoint.Col])

{

case 0: b = bGrenYellow; break; // трава

case 1: b = bGreen; break; // лес

case 2: b = bGray; break; // дом

}

g.FillRectangle(b, GetX(curPoint.Row, curPoint.Col), GetY(curPoint.Row,

curPoint.Col), cellWidth, cellHeight);

}

s = (start) ? "A" : "B";

g.DrawString(s, fontPoint, brushRed, GetX(curPoint.Row, curPoint.Col) +

cellWidth / 2 - fontPoint.SizeInPoints / 2.0f - 3, GetY(curPoint.Row,

curPoint.Col) + cellHeight / 2 - fontPoint.SizeInPoints / 2.0f - 1);

if (start) startPoint = curPoint;

else endPoint = curPoint;

this.pb.Image = this.bm;

}

//......................................................................

// Метод прорисовки карты стоимостей

//......................................................................

public void DrawMapCost()

{

ClearMap();

Brush bGrenYellow = new SolidBrush(Color.GreenYellow); // трава

Brush bGreen = new SolidBrush(Color.Green); // лес

Brush bGray = new SolidBrush(Color.Gray); // дом

// Выводим карту на форму

for (int i = 0; i < countRow; i++)

{

for (int j = 0; j < countCol; j++)

{

string s = mapCost[i, j].ToString();

Brush b = bGrenYellow;

switch (map[i, j])

{

case 0: b = bGrenYellow; break; // трава

case 1: b = bGreen; break; // лес

case 2: b = bGray; break; // дом

}

g.FillRectangle(b, GetX(i, j), GetY(i, j), cellWidth, cellHeight);

g.DrawString(s, font, brush, GetX(i, j) + cellWidth / 2 - font.SizeInPoints /

2.0f - 3, GetY(i, j) + cellHeight / 2 - font.SizeInPoints / 2.0f - 1);

}

}

this.pb.Image = this.bm;

}

//......................................................................

// Метод очистки карты

//......................................................................

public void ClearMap()

{

g.Clear(Color.White);

}

//......................................................................

// Метод прорисовки карты

//......................................................................

public void DrawMap()

{

ClearMap();

// Выводим карту на форму

for (int i = 0; i < countRow; i++)

{

for (int j = 0; j < countCol; j++)

{

Bitmap bm;

switch (map[i, j])

{

case 0: bm = imgGrass; break;

case 1: bm = imgForest; break;

case 2: bm = imgHome; break;

default: bm = imgForest; break;

}

g.DrawImage(bm, startX + j * cellWidth, startY + i * cellHeight, cellWidth,

cellHeight);

}

}

this.pb.Image = this.bm;

}

//......................................................................

// Метод вычисления расстояния между двумя точками, координаты

row, col

//......................................................................

private double Distance(Vertex p1, Vertex p2)

{

double temp = Math.Pow(Math.Abs(p1.Col - p2.Col), 2) +

Math.Pow(Math.Abs(p1.Row - p2.Row), 2);

if (temp <= 0) return -1;

return Math.Sqrt(temp);

}

//......................................................................

// Метод определения доступных вершин на игровом поле для

совершения хода

//......................................................................

private List<Vertex> GetAvailablePositions(List<Vertex> listLastVertex,

Vertex c)

{

List<Vertex> list = new List<Vertex>();

Vertex v1 = new Vertex(c.Row - 1, c.Col - 1);

Vertex v2 = new Vertex(c.Row - 1, c.Col);

Vertex v3 = new Vertex(c.Row - 1, c.Col + 1);

Vertex v4 = new Vertex(c.Row, c.Col + 1);

Vertex v5 = new Vertex(c.Row + 1, c.Col + 1);

Vertex v6 = new Vertex(c.Row + 1, c.Col);

Vertex v7 = new Vertex(c.Row + 1, c.Col - 1);

Vertex v8 = new Vertex(c.Row, c.Col - 1);

// Если текущая вершина не найдена в списке посещенных вершин, то

добавляем в список доступных вершин

if (listLastVertex.IndexOf(v1) < 0) list.Add(v1);

if (listLastVertex.IndexOf(v2) < 0) list.Add(v2);

if (listLastVertex.IndexOf(v3) < 0) list.Add(v3);

if (listLastVertex.IndexOf(v4) < 0) list.Add(v4);

if (listLastVertex.IndexOf(v5) < 0) list.Add(v5);

if (listLastVertex.IndexOf(v6) < 0) list.Add(v6);

if (listLastVertex.IndexOf(v7) < 0) list.Add(v7);

if (listLastVertex.IndexOf(v8) < 0) list.Add(v8);

for (int i = 0; i < list.Count; i++)

{

// Удаляем те вершины, которые вышли за пределы игрового поля

if (list[i].Row < 0 || list[i].Row >= countRow || list[i].Col < 0 || list[i].Col >=

countCol)

{

list.RemoveAt(i);

if (list.Count <= 0) break;

i--;

}

}

return list;

}

//......................................................................

// Метод для определения следующего хода

//......................................................................

private Vertex? GetNextStep(List<Vertex> listLastVertex, Vertex curPos,

Vertex end)

{

List<Vertex> listAvailable = GetAvailablePositions(listLastVertex, curPos);

double min = double.MaxValue;

Vertex? minVertex = null;

for (int i = 0; i < listAvailable.Count; i++)

{

double curDistance = mapCost[listAvailable[i].Row, listAvailable[i].Col] +

Distance(listAvailable[i], end) * costPath;

if (curDistance < min) {

min = curDistance;

minVertex = listAvailable[i];

}

}

return minVertex;

}

//......................................................................

// Метод нахождения кратчайшего пути с помощью алгоритма

Дейкстры

//......................................................................

public List<Vertex> FindOptimalPath(Vertex start, Vertex end)

{

List<Vertex> path = new List<Vertex>();

Vertex? curPos = start;

path.Add(start);

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

пока не зашли в тупик (ни одной соседней вершины не найдено)

do

{

curPos = GetNextStep(path, (Vertex)curPos, end);

if (curPos == null) break;

Vertex v = (Vertex)curPos;

if (curPos != null) path.Add(v);

if (v.Row == end.Row && v.Col == end.Col) break;

}

while (curPos != null);

return path;

}

//......................................................................

// Метод прорисовки оптимального пути на карте местности

//......................................................................

public void DrawOptimalPath(List<Vertex> list)

{

pen = new Pen(Color.Red, 3);

Vertex vLast = list[0];

for (int i = 1; i < list.Count; i++)

{

g.DrawLine(pen, GetX(vLast.Row, vLast.Col) + cellWidth / 2,

GetY(vLast.Row, vLast.Col) + cellHeight / 2,

GetX(list[i].Row, list[i].Col) + cellWidth / 2, GetY(list[i].Row, list[i].Col) +

cellHeight / 2);

vLast = list[i];

}

}

}

}

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace SearchOptimalPathOnRoad

{

public partial class Form1 : Form

{

RoadOptimal roadOpt;

public Form1()

{

InitializeComponent();

InitRoad();

}

private void radioButton3_CheckedChanged(object sender, EventArgs e)

{

if (rb_Map.Checked) { roadOpt.curMap = rb_Map.Checked;

roadOpt.DrawMap(); }

else { roadOpt.curMap = rb_Map.Checked; roadOpt.DrawMapCost(); }

}

private void InitRoad()

{

Checkpoint? startPoint = null, endPoint = null;

if (roadOpt != null)

{

startPoint = roadOpt.startPoint;

endPoint = roadOpt.endPoint;

}

bool curMap = rb_Map.Checked;

roadOpt = new RoadOptimal("map1.txt", pictureBox1,

(int)numericUpDown1.Value, (int)numericUpDown2.Value,

(int)numericUpDown3.Value, (int)numericUpDown4.Value,

startPoint, endPoint, curMap);

pictureBox1.Invalidate();

}

private void pictureBox1_MouseDown(object sender, MouseEventArgs e)

{

if (roadOpt.GetRow(e.X, e.Y) < 0 || roadOpt.GetRow(e.X, e.Y) >=

roadOpt.countRow) return;

if (roadOpt.GetCol(e.X, e.Y) < 0 || roadOpt.GetCol(e.X, e.Y) >=

roadOpt.countCol) return;

if (rb_StartPath.Checked) { roadOpt.startPoint = new

Checkpoint(roadOpt.GetRow(e.X, e.Y), roadOpt.GetCol(e.X, e.Y)); }

else roadOpt.endPoint = new Checkpoint(roadOpt.GetRow(e.X, e.Y),

roadOpt.GetCol(e.X, e.Y));

}

private void pictureBox1_Paint(object sender, PaintEventArgs e)

{

if (rb_Map.Checked) roadOpt.DrawMap();

else roadOpt.DrawMapCost();

// Если существуют начальная и конечная точки пути, то рисуем путь

if (roadOpt.startPoint.Have && roadOpt.endPoint.Have)

{

Vertex vStart = new Vertex(roadOpt.startPoint.Row,

roadOpt.startPoint.Col);

Vertex vEnd = new Vertex(roadOpt.endPoint.Row, roadOpt.endPoint.Col);

List<Vertex> listVertex = roadOpt.FindOptimalPath(vStart, vEnd);

roadOpt.DrawOptimalPath(listVertex);

}

if (roadOpt.startPoint.Have) roadOpt.DrawPoint(true);

if (roadOpt.endPoint.Have) roadOpt.DrawPoint(false);

}

private void numericUpDown2_ValueChanged(object sender, EventArgs e)

{

InitRoad();

}

private void numericUpDown3_ValueChanged(object sender, EventArgs e)

{

InitRoad();

}

private void numericUpDown4_ValueChanged(object sender, EventArgs e)

{

InitRoad();

}

private void numericUpDown1_ValueChanged(object sender, EventArgs e)

{

InitRoad();

}

private void Form1_Load(object sender, EventArgs e)

{

}

}

}

ПРИЛОЖЕНИЕ 2

Графический интерфейс программы

Рис. 1. Главное окно программы

Рис. 2. Выбор стоимости



Рис. 3. Выбор опорных пунктов

Рис. 4. Конечное окно программы

Размещено на Allbest.ru