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

РЕФЕРАТ Записка пояснительная к курсовой работе: 23c., 1 рис., 5 разделов, 1 приложение, 4 источника.

Объект исследования — методы поиска путей в лабиринте.

Цель работы — разработать программу которая бы наглядно продемонстрировала 2 метода поиска пути в лабиринте.

Метод исследования — изучение литературы, составление и отладка программ на компьютере, проверка решений.

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

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

Программа написана на языке С++ и в среде Visual C++. Это программа нахождения пути. СИСТЕМА, АЛГОРИТМ, ФУНКЦИЯ, ОПРЕДЕЛИТЕЛЬ, МАТРИЦА, ЗАГОЛОВОЧНЫЕ ФАЙЛЫ, ОПЕРАТОРЫ, ПАРАМЕТРЫ, ПРОТОТИП, ОПРЕДЕЛЕНИЕ, РАСШИРЕННАЯ МАТРИЦА, МЕТОД.

СОДЕРЖАНИЕ Вступление

1. Постановка задачи и сфера ее использования

2. Теоретическая часть

2.1 Метод волны

2.2 Метод приоритетов

3. Особенности работы в среде Visual C++

4. Программная реализация

4.1 Описание алгоритма и структуры программы

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

4.3 Описание разработанных функций

5. Инструкция пользователя Выводы Список литературы Приложение Текст программы алгоритм лабиринт программа пользователь

ВСТУПЛЕНИЕ В одном энциклопедическом словаре по поводу того, что такое язык, сказано следующее:

" ЯЗЫК, 1) естественный язык, важнейшее средство человеческого общения. Я. неразрывно связан с мышлением; является социальным средством хранения и передачи информации, одним из средств управления человеческим поведением. Я. возник одновременно с возникновением общества в процессе совместной трудовой деятельности первобытных людей. Возникновение членораздельной речи явилось мощным средством дальнейшего развития человека, общества и сознания. Реализуется и существует в речи. Я. мира различаются строением, словарным составом и др., однако всем Я. присущи некоторые общие закономерности, системная организация единиц языка (например, парадигматические и синтагматические отношения между ними) и др. Я. изменяется во времени (см. Диахрония), может перестать использоваться в сфере общения (мёртвые Я.). Разновидности Я. (нац. Я., лит. Я., диалекты, Я. культа и др.) играют различную роль в жизни общества. 2) Любая знаковая система, напр. Я. математики, кино, Я. жестов. См. также Искусственные языки, Язык программирования. 3)…"

C++ также является языком. Его так и называют «язык программирования C++». Это формальный язык. Он служит для описания данных и алгоритмов их обработки на ЭВМ.

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

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

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

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

1. ПОСТАНОВКА ЗАДАЧИ И СФЕРА ЕЕ ИСПОЛЬЗОВАНИЯ Цель работы — разработать программу которая бы наглядно продемонстрировала 2 метода поиска пути в лабиринте.

Метод исследования — изучение литературы, составление и отладка программ на компьютере, проверка решений.

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

2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ В данной программе иследуется 2 способа поиска пути в лабиринте.

1) «Метод волны» — нахождение минимально пути между точками в лабиринте, предпологается что лабиринт известен.

2) «Метод приоритетов» — нахождение пути между точками. Данный алгоритм не находит кратчайшего пути, зато он применим если лабиринт неизвестен.

2.1 Метод волны Решение этой зaдaчи пришло к нaм из тaкой дaлекой, кaзaлось бы, от игр облaсти кaк электроникa. A именно — рaзводкa печaтных плaт.

Существует большое количество трaссировщиков (прогрaмм для рaзводки плaты), основaнных нa не меньшем количестве рaзличных методов, зaнимaющихся соединением двух контaктов единым проводником. Hо мы рaссмотрим только один из них, сaмый простой (a знaчит, сaмый нaдежный и сaмый популярный) — волновой трaссировщик.

Постaвим перед волновым трaссировщиком зaдaчу в терминaх решаемой нами задачей: Имеется игровое поле Р (MxN), где M и N, соответственно, рaзмер поля по вертикaли и горизонтaли. Попросту, это мaссив рaзмерностью MxN. Кaждaя клеткa поля (элемент мaссивa) может облaдaть большим количеством свойств, но для нaс вaжно только одно — ето проходимость (или непроходимость). Дaльше: имеется некоторaя стaртовaя точкa и конечнaя точкa. Условимся покa-что тем что передвижение возможно только по четырем нaпрaвлениям (чего требует от нaс клaссический волновой метод) — впрaво, влево, вперед, нaзaд. Hеобходимо переместить героя от местa стaртa к финишу зa нaименьшее количество ходов, если тaкое перемещение вообще возможно.

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

Координаты выхода не требуются, главное, чтобы было ясно, что является выходом. Сам алгоритм прост, сначала смотрим вокруг и в какой клетке мы были меньше всего раз и идем туда, прибавляя к той, где стояли 1. Так повторяем пока не найдем выход.

Это алгоритм обхода местности. Поиск не оптимален. Фактически поиск ведется по фронту волны. При добавлении эвристики (учет направления до цели), возможно улучшение оптимальности. Главное, что затраты на поиск по времени минимальны!

3. ОСОБЕННОСТИ РАБОТЫ В СРЕДЕ VISUAL C++

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

С++ - это язык программирования общего назначения, хорошо известный своей эффективностью, экономичностью, и переносимостью. Указанные преимущества С++ обеспечивают хорошее качество разработки почти любого вида программного продукта. Использование С++ в качестве инструментального языка позволяет получать быстрые и компактные программы. Во многих случаях программы, написанные на С++, сравнимы по скорости с программами, написанными на языке ассемблера.

Перечислим некоторые существенные особенности языка С++:

-С++ обеспечивает полный набор операторов структурного программирования;

-С++ предлагает необычно большой набор операций. Многие операции С++ соответствуют машинным командам и поэтому допускают прямую трансляцию в машинный код. Разнообразие операций позволяет выбирать их различные наборы для минимизации результирующего кода;

-С++ поддерживает указатели на переменные и функции. Указатель на объект программы соответствует машинному адресу этого объекта. Посредством разумного использования указателей можно создавать эффективно выполняемые программы, т.к. указатели позволяют ссылаться на объекты тем же самым путем, как это делает ЭВМ. С++ поддерживает арифметику указателей, и тем самым позволяет осуществлять непосредственный доступ и манипуляции с адресами памяти.

4. ПРОГРАМНАЯ РЕАЛИЗАЦИЯ

4.1 Описание алгоритма и структуры программы

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

Создается массив для хранения лабиринта labirint и массив для прорисовки лабиринта labSet. Генерация лабиринта происходит автоматически. С помощью функции Volna создается массив lb и ряд вспомогательных переменных для вычисления минимального пути, «методом волны», между заданными точками в лабиринтемассив. С помощью функции Prior реализуется «метода приоритетов», там также создается вспомогательная функция lb. В обе эти функции передается адрес исходного лабиринта и количество входов-выходов.

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

Общий принцип алгоритма волны:

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

1. Снaчaлa необходимо создaть рaбочий мaссив R (MxN), рaвный по рaзмеру мaссиву лабиринта P (MxN).

2.Кaждому элементу рaбочего мaссивa R (i, j) присвaивaется некоторое знaчение в зaвисимости от свойств элементa игрового поля P (i, j) по следующим правилам:

a) Если поле P (i, j) непроходимо, то R (i, j)=255;

б) Если поле P (i, j) проходимо, то R (i, j)=254;

в) Если поле P (i, j) является целевой (финишной) позицией, то R (i, j)=0;

г) Если поле P (i, j) является стaртовой позицией, то R (i, j)=253.

3.Этaп «Рaспрострaнения волны». Вводим переменную Ni — счетчик итерaций (повторений) и присвaивaем ей нaчaльное знaчение 0.

4.Вводим констaнту Nк, которую устaнaвливaем рaвной мaксимaльно возможному числу итерaций.

5.Построчно просмaтривaем рaбочий мaссив R (т.е.оргaнизуем двa вложенных циклa: по индексу мaссивa i от 1 до М, по индексу мaссивa j от 1 до N).

6.Если R (i, j) рaвен Ni, то просмaтривaются соседние элементы R (i+1,j), R (i-1,j), R (i, j+1), R (i, j-1) по следующему прaвилу (в кaчестве примерa рaссмотрим R (i+1,j):

a) Eсли R (i+1,j)=253, то переходим к пункту 10;

б) Eсли R (i+1,j)=254, выполняется присвaивaние R (i+1,j)=Ni+1;

в) Во всех остaльных случaях R (i+1,j) остaется без изменений.

Aнaлогично поступaем с элементaми R (i-1,j), R (i, j+1), R (i, j-1).

7. По зaвершению построчного просмотрa всего мaссивa увеличивaем Ni нa 1.

8. Если Ni>Nк, то поиск мaршрутa признается неудачным. Выход из программы.

9.Переходим к пункту 5.

10.Этaп построения мaршрутa перемещения. Присвaивaем переменным Х и Y знaчения координaт стaртовой позиции.

11.В окрестности позиции R (Х, Y) ищем элемент с нaименьшим знaчением (т.е.для этого просмaтривaем R (Х+1,Y), R (Х-1,Y), R (Х, Y+1), R (Х, Y-1). Координaты этого элементa зaносим в переменные X1 и Y1.

12.Совершaем перемещение объектa по игровому полю из позиции [X, Y] в позицию [X1,Y1].

13.Если R (X1,Y1)=0,то переходим к пункту 15.

14.Выполняем присвaивaние X=X1,Y=Y1. Переходим к пункту 11.

15. Конец.

Общий принцип " метода приоритетов" :

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

2. Возвращаемся к пункту 1 пока не найдем выход.

a. Описание использованных программных средств В программе были использованы:

-#include-директива для подключения заголовочных файлов;

-" stdlib. h", «iostream.h» — заголовочные файлы, содержащий стандартные объекты и операции с потоками ввода/вывода;

— «time.h» — для возможности применения функции time (), чтоб сгенерированый лабиринт всегда отличался от придыдущего;

— «stdio.h» — заголовочный фаил, содержащий функции ввода/вывода в стиле С (printf и т. д.);

— cout<<-оператор для вывода данных на экран;

— cin>>-оператор для ввода данных (например с клавиатуры);

— rand () — оператор для генерации случайного числа;

— srand () — оператор для зависемости выдаваемых значений функцией rand от времени;

— printf — оператор для форматированого вывода данных;

— for — оператор итерационного цикла;

— const — ключевое слово для объявления константы;

— if — оператор, позволяющий проверить условие и изменить ход выполнения программы;

— else — оператор, служащий для разветвления (усложнения) оператора условия if;

— return — оператор для возвращения значения из функции;

— функции-подпрограммы, которые могут манипулировать данными и возвращать некоторое значение;

— а так же различные типы данных (int, void, bool), управляющие символы, математические операторы, операторы отношений, логические операторы и так далее.

b. Описание разработанных функций В программе были разработаны функции:

Volna — возвращает результат выполнения функции и принимает адрес лабиринта и количество входов-выходов. Используеться для расчета минимального пути между двумя точками в лабиринте (в данном случае лабиринт известен);

Prior — возвращает результат выполнения функции и принимает адрес лабиринта и количество входов-выходов. Используеться для расчета пути между двумя точками в лабиринте (в данном случае лабиринт неизвестен);

LabOut — не возвращает никаких значений, но принимает адрес лабиринта и адрес массива хранящего визуальное представление лабиринта. Используеться для вывода лабиринта на экран;

5. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ Для начала работы с программой надо запустить фаил Find. exe после чего на экране появятся сведения о том что программа сама сгенирирует лабиринт после нажатия клавиши «ENTER». Далее на экране вы увидите исходный лабиринт и визуализацию 2-х методов поиска пути между двумя точками лабиринта, если конечно этот путь существует.

ВЫВОДЫ На рисунке видно что данная программа корректно решает поставленую перед нами задачу. Результаты вычисления пути двумя методами предоставлены на рисунке ниже.

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

СПИСОК ЛИТЕРАТУРЫ

Павловская Т. А. С/C++.Программирование на языке высокого уровня-СПб:Издательство «Питер», 2008.-464с.

Керниган Б., Ритчи Д. Язык программирования Си: Пер. с англ.-М.:

Финансы и статистика, 2008.-272 с.

Глушаков С.В., Коваль А. В., Черпнин С. А. Программирование на Visual C++ 6.0: Издательство «Фолио», 2007. -721с. -(Учебный курс).

4. Бондарено В. М., Рублинецкий В. И., Качко Е. Г. Основы программировани: Издательство «Фолио», 2007. -368с.

Приложение, А Текст программы

#include «stdafx.h»

#include «iostream.h»

#include «time.h»

#include «stdlib.h»

#include «stdio.h»

//размер лабиринта

const int sX=15;

const int sY=30;

bool Volna (int* lab, int kol); //Ф-ция алгоритма «волны»

bool Prior (int* lab, int kol);//ф-ция алгоритма «метод приоритета» .

void LabOut (int* lab, char* bl);//вывод лабиринта

int main (int argc, char* argv[])

{

srand ((unsigned)time (NULL));

int stop, rnd, labirint[sX][sY];

char labSet[7]=" %M." ;//масив для визуаьного отображения лабиринта

printf («Nazhmite ENTER dlya dlya generacii labirinta.»);

stop = getchar ();

//генерация лабиринта

for (int i=0;i

for (int j=0;j

{ rnd=rand ()%4;

labirint[i][j]=rnd; }

for (int t=0;t<2;t++)labirint[rand ()%sX][rand ()%sY]=4;

cout<<" Imeem takoi labirint: n" ;

LabOut (&labirint[0][0], labSet);

cout<<" Nahozhdenie puti Volnovim metodom! n" ;

if (Volna (&labirint[0][0], 2))LabOut (&labirint[0][0], labSet);

else cout<<" Nevozmogno soedenit' eti tochki! n" ;

cout<<" Metod prioritetov (vpravo, vlevo, vniz, vverh):n" ;

if (Prior (&labirint[0][0], 2))LabOut (&labirint[0][0], labSet);

else cout<<" Nevozmogno soedenit' eti tochki za 250 shagov! n" ;

cin>>stop;

return 0;

}

bool Volna (int* lab, int kol)

{

int lb[sX][sY]; //модифицированая копия лабиринта

int Ni=0, x=0, y=0, copX, copY;//Ni — кольво итераций, x, y, copX, copY — для хранения координат

int min=300, copMin=300; //для поиска минимального пути

bool work=true; //для избежания зацикливания

//заполнения модифицированого лабиринта для волнового метода

for (int i=0;i

for (int j=0;j

{

if (*(lab+j+i*sY)/3==0)lb[i][j]=254;

if (*(lab+j+i*sY)==3)lb[i][j]=255;

if (*(lab+j+i*sY)==4)

{

if (kol==2)

lb[i][j]=253;

else

lb[i][j]=0;

kol—;

}

}

//формирование волны

while (work)

{

for (int k=0;k

for (int l=0;l

if (lb[k][l]==Ni)

{

if (l+1≠sY)

{

if (lb[k][l+1]==254)

lb[k][l+1]=Ni+1;

if (lb[k][l+1]==253){x=k;y=l+1;work=false;}

}

if (k+1≠sX)

{

if (lb[k+1][l]==254)

lb[k+1][l]=Ni+1;

if (lb[k+1][l]==253){x=k+1;y=l;work=false;}

}

if (l-1≠-1)

{

if (lb[k][l-1]==254)

lb[k][l-1]=Ni+1;

if (lb[k][l-1]==253){x=k;y=l-1;work=false;}

}

if (k-1≠-1)

{

if (lb[k-1][l]==254)

lb[k-1][l]=Ni+1;

if (lb[k-1][l]==253){x=k-1;y=l;work=false;}

}

}

Ni++;

if (Ni==250)work=false;

}

//поиск минимального пути

if (Ni≠250)

{

while (copMin≠0)

{

if (y+1≠sY)

if (min>lb[x][y+1])

{

min=lb[x][y+1];

copY=y+1;

copX=x;

}

if (y-1≠-1)

if (min>lb[x][y-1])

{

min=lb[x][y-1];

copY=y-1;

copX=x;

}

if (x+1≠sX)

if (min>lb[x+1][y])

{

min=lb[x+1][y];

copX=x+1;

copY=y;

}

if (x-1≠-1)

if (min>lb[x-1][y])

{

min=lb[x-1][y];

copX=x-1;

copY=y;

}

x=copX; y=copY; copMin=min; min=300; *(lab + y + x*sY)=5;

}

*(lab + y + x*sY)=4;

}

else return false;

return true;

}

void LabOut (int* lab, char* bl)

{

for (int i=0;i

{

for (int j=0;j

cout<

cout<

}

cout<<" ————————————————————————————————————————" ;

}

bool Prior (int* lab, int kol)

{

int x, y, startX, startY, copX, copY, stop=0; //хранение координат

int lb[sX][sY]; //модифицированая копия лабиринта

int min=300;//для нахождения минимального приоритета

bool work=true;//для избежания зацикливания

//создания модифицированого лабиринта под метод приоритетов

for (int i=0;i

for (int j=0;j

{

if ((*(lab+j+i*sY)/3==0) || (*(lab+j+i*sY)==5)){lb[i][j]=0;*(lab + j + i*sY)=0;}

if (*(lab+j+i*sY)==3)lb[i][j]=255;

if (*(lab+j+i*sY)==4)

{

if (kol==2)

{

lb[i][j]=0;

startX=i;startY=j;

}

else

lb[i][j]=254;

kol—;

}

}

x=startX; y=startY;//хранение точки входа

//реализация алгоритма поиска

while (work)

{

if (y+1≠sY)

{

if (lb[x][y+1]==254)

{work=false; min=0;copY=y+1;copX=x;}

if (min>lb[x][y+1])

{min=lb[x][y+1]; copY=y+1;copX=x;}

}

if (y-1≠-1)

{

if (lb[x][y-1]==254)

{work=false; min=0;copY=y-1; copX=x;}

if (min>lb[x][y-1])

{min=lb[x][y-1]; copY=y-1; copX=x;}

}

if (x+1≠sX)

{

if (lb[x+1][y]==254)

{work=false; min=0;copX=x+1; copY=y;}

if (min>lb[x+1][y])

{min=lb[x+1][y]; copX=x+1; copY=y;}

}

if (x-1≠-1)

{

if (lb[x-1][y]==254)

{work=false; min=0;copX=x-1; copY=y;}

if (min>lb[x-1][y])

{min=lb[x-1][y]; copX=x-1; copY=y;}

}

stop++; lb[x][y]++; x=copX; y=copY; min=300; *(lab + y + x*sY)=5;

if (stop==250)work=false;

}

*(lab + startY + startX*sY)=*(lab + y + x*sY)=4;

if (stop==250)work=true;

return !work;

}