Волновой алгоритм Ли
Волновой алгоритм является одним из самых уникальных алгоритмов трассировки.
Он позволяет построить трассу (путь) между двумя элементами в любом лабиринте .
|
Рис
1.
|
Из начального элемента распространяется в 4-х направлениях
волна (рис 1.). Элемент, в который пришла волна, образует фронт волны. На
рисунках цифрами обозначены номера фронтов волны.
|
|
Рис 2.
|
Каждый элемент первого фронта волны является источником вторичной
волны (рис 2.). Элементы второго фронта волны генерируют волну третьего
фронта и т.д. Процесс продолжается до
тех пор, пока не будет достигнут конечный элемент.
На втором этапе строится сама трасса. Её построение осуществляется в соответствии
со следующими правилами:
- Движение при
построении трассы осуществляется в соответствии с выбранными
приоритетами.
- При движении от
конечного элемента к начальному, номер фронта волны (путевые координаты)
должны уменьшатся.
|
Приоритеты направления движения выбираются на стадии разработки. В
зависимости от того какими задаются эти приоритеты получаются разные трассы, НО
длина трассы в любом случае остается одной и той же.
Преимущества волнового алгоритма в том, что с его помощью можно найти трассу
в любом лабиринте и с любым количеством запретных элементов (стен).
Единственным недостатком этого алгоритма является, то, что при построении
трассы требуется большой объем памяти.
Пример использования ВОЛНОВОГО АЛГОРИТМА :
|
Красным цветом отмечены запрещенные элементы. Серым цветом трасса после
действия алгоритма.
А - начальная точка, В - конечная.
Приоритеты движения ВЛЕВО, ВПРАВО, ВВЕРХ, ВНИЗ.
Построение трассы ведется от начальной точки к конечной. Приоритетные
направления показаны зелеными стрелками.
|
Один из вариантов реализации волнового алгоритма на Паскале
Program Voln;
Uses Crt;
Var XS, YS, XE, YE : Byte;
X, Y, I,n,m : Byte;
Map : array [1..10, 1..10] of
Byte; {Исходная
матрица}
MapM : array [1..10, 1..10] of
Byte; {Матрица покрытий}
Moves : Byte;
Procedure Next(Var X, Y : Byte);
Begin
If (X <n) and (MapM[X, Y] -
MapM[X + 1, Y] = 1) then
Begin
X := X + 1;
Exit;
End;
If (X >1) and (MapM[X, Y] -
MapM[X - 1, Y] = 1) then
Begin
X := X - 1;
Exit;
End;
If (Y <m) and (MapM[X, Y] -
MapM[X, Y + 1] = 1) then
Begin
Y := Y + 1;
Exit;
End;
If (Y >1) and (MapM[X, Y] -
MapM[X, Y - 1] = 1) then
Begin
Y := Y - 1;
Exit;
End;
End;
Begin
ClrScr;
writeln('n, m'); readln(n,m);
For Y := 1 to n do
Begin
For X := 1 to m do
read(Map[X, Y]);
End;
WriteLn('Please enter X and Y
of the start: ');
ReadLn(XS, YS);
WriteLn('Please enter X and Y
of the end: ');
ReadLn(XE, YE);
If (Map[XS, YS] = 1) or
(Map[XE, YE] = 1) then
Begin
WriteLn('Error!!!');
ReadLn;
Halt;
End;
MapM[XS, YS] := 1;
I := 1;
Repeat
I := I + 1;
For Y := 1 to n do
For X := 1 to m do
If MapM[X, Y] = I -
1 then
Begin
If (Y+1 <=m)
and (MapM[X, Y + 1] = 0)
and (Map[X, Y+1] = 0) Then MapM[X,
Y+1] := I;
If (Y-1 >=1)
and (MapM[X, Y-1] = 0) and (Map[X, Y-1] = 0) Then MapM[X, Y-1] := I;
If (X+1 <=n)
and (MapM[X+1, Y] = 0) and (Map[X+1, Y] = 0) Then MapM[X+1, Y] := I;
If (X-1 >=1)
and (MapM[X-1, Y] = 0) and (Map[X-1, Y] = 0) Then MapM[X-1, Y] := I;
End;
If I = n*m then
Begin
WriteLn('You
can''t go there!!!');
ReadLn;
Halt;
End;
Until MapM[XE, YE] >0;
Moves := I - 1;
X := XE;
Y := YE;
I := Moves;
Repeat
Next(X, Y);
I := I - 1;
Until (X = XS) and (Y = YS);
writeln ('Количество шагов',moves);
for y:=1 to n do
begin for x:=1 to m do
write(MapM[x,y],' ');
writeln;
end;
End.
Комментариев нет:
Отправить комментарий