Приветствую Вас, дорогие читатели! Сегодня мы рассмотрим принцип работы и реализацию волнового алгоритма. Сначала я думаю, стоит сказать пару слов о сути волнового алгоритма (алгоритма ли) ну и о его применение.
Суть его чрезвычайно проста: он находит кратчайший путь между двумя точками на двумерном клетчатом поле(если это возможно), а используется он чаще всего в тактических играх. Сформулируем условие задания:Дан массив целых чисел, размерностью N, упорядоченный по возрастанию. Некоторые элементы в массиве повторяются. Необходимо вывести только уникальные элементы(встречающиеся один раз).У нас имеется игровое поле(массив размерностью MxN). Каждая клетка нашего игрового поля может быть либо проходимой, либо непроходимой. Также имеется две точки A и B. А –стартовая точка, В – конечная точка. Необходимо попасть из точки A в точку B за наименьшее количество шагов, если это возможно. Условимся, что перемещаться можно только в 4 направлениях (вверх, вниз, влево, вправо).Теперь перейдем к пошаговому алгоритму решения данного задания.
1. Нам нужно два массива одинаковой размерности MxN. Первый массив содержит игровое поле, в котором указаны свойства всех клеток поля (проходимы они или нет). Второй массив(рабочий), над которым будут производиться в дальнейшем различные манипуляции. В самом начале он содержит те же данные, что и массив с игровым полем. Давайте условимся, что: если точка является проходимой, то элемент массива будет содержать число равное MxN+1; если точка непроходима, то MxN+2; если это стартовая точка, то MxN; если конечная точка, то 0. Для наглядности того, что я здесь пишу к каждому шагу я буду прилагать код на с++:
// 0 – конечная точка
// 51 – непроходимая точка
// 50 – проходимая точка
// 49 –начальная точка
// инициализируем массив с игровым полем
int M=7;
int N=7;
int POLE[M][N]={
51, 51, 51, 51, 51, 51, 51,
51, 49, 50, 50, 50, 51, 51,
51, 50, 50, 51, 50, 50, 51,
51, 51, 50, 50, 50, 0, 51,
51, 50, 50, 50, 51, 50, 51,
51, 50, 51, 50, 50, 50, 51,
51, 51, 51, 51, 51, 51, 51,
};
// инициализируем рабочий массив
int RAB[M][N]={
51, 51, 51, 51, 51, 51, 51,
51, 49, 50, 50, 50, 51, 51,
51, 50, 50, 51, 50, 50, 51,
51, 51, 50, 50, 50, 0, 51,
51, 50, 50, 50, 51, 50, 51,
51, 50, 51, 50, 50, 50, 51,
51, 51, 51, 51, 51, 51, 51,
};2. Инициализируем переменную iter=0 отвечающую за количество итераций. Этот этап обычно называют этапом распространения волны. Здесь главное запомнить что этап распространения волны начинается с конечной точки.
1 int iter(0);
3.Теперь определяем константную переменную iterk равную максимальному числу итераций. Эта переменная необходима, чтобы наша программа не зациклилась. Например, если между начальной и конечной точкой лежит препятствие, которое невозможно преодолеть. Также эта переменная не должна быть больше размера начальной точки(в нашем случае 49).
1 int iterk(49);
4.Тепрь мы должны создать цикл с предусловием (iter<iterk) Внутри него расположить два вложенных друг в друга цикла для построчного просмотра нашего массива. Внутри них определить условие, что если элемент рабочего массива равен количеству итераций, то просматриваются соседние элементы RAB(i+1,j), RAB(i-1,j), RAB(i,j+1), RAB(i,j-1) по следующему правилу(рассмотрим данное правило на примере RAB(i-1,j)): 1) Если RAB(i-1,j)==50 , то есть точка является проходимой то RAB(i-1,j)=iter+1 2)Если RAB(i-1,j)==49, то выходим из данного, так как мы дошли до начальной точки. Аналогично и с другими элемента то есть у вас должно получиться в общей сумме 8 условий. После того, как мы покидаем построчный просмотр массива мы должны увеличить количество итераций на 1
5. Если iter>iterk, то нахождений кратчайшего пути невозможно, следовательно, волновой алгоритм не выполняется для введенных точек и нужно покинуть программу, ну и в следующий раз указать уже другие точки. 6. Теперь мы переходим к построению пути перемещения. Инициализируем четыре переменные X и Y соответствующие координатам стартовой точки и X1 и Y1 координаты перемещения. Также определяем переменную min==51(дальше вы поймете для чего она).
1 int X(1),Y(1),X1(0),Y1(0);
2
3 int min(51);
7. Далее в цикле просматриваем окрестность(RAB[X+1][Y], RAB[X-1][Y], RAB[X][Y+1], RAB[X][Y-1]) стартовой точки RAB[X][Y] и ищем элемент с наименьшим значением. Как только мы его находим, то присваиваем его координаты переменным X1 и Y1. Условием выхода из цикла и следовательно завершением нахождения кратчайшего пути является нахождение конечной точки (RAB[X1][Y1]==0).
8. Ну а теперь давайте взглянем на кратчайший путь, который проложил нам волновой алгоритм:
for(int i=0;i<M;i++)
{
for(int j=0;j<N;j++)
{
switch(POLE[i][j]){
case 51:
{cout<<setw(3)<<'#';
break;}
case 50:
{cout<<setw(3)<<'.';
break;}
case 49:{cout<<setw(3)<<'A';
break;}
case 0:{cout<<setw(3)<<'B';
break;}
case -1:{cout<<setw(3)<<'>';
break;}
}
}
cout<<endl;
}В итоге мы получим следующее:
Надеюсь, что моя статья помогла Вам понять волновой алгоритм, ну или хотя бы приблизила Вас к его пониманию