Sources
Delphi Russian Knowledge Base
DRKB - это самая большая и удобная в использовании база знаний по Дельфи в рунете, составленная Виталием Невзоровым

Алгоритм Ли (поиск пути на карте)

01.01.2007
Виды поиска пути на карте

2.1. Волновой алгоритм (Алгоритм Ли)

Волновой алгоритм является одним из самых уникальных алгоритмов трассировки. Он позволяет построить трассу(путь) между двумя элементами в любом лабиринте.

Рис 1.

Из начального элемента распространяется в 4-х направлениях волна (рис1.). Элемент в который пришла волна образует фронт волны.На рисунках цифрами обозначены номера фронтов волны.

Рис2.

Каждый элемент первого фронта волны является источником вторичной волны (рис 2.). Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор пока не будет достигнут конечный элемент.

На втором этапе строится сама трасса. Её построение осуществляется в соответствии со следующими правилами:

·Движение при построении трассы осуществляется в соответствии с выбранными приоритетами.
·При движении от конечного элемента к начальному номер фронта волны (путевые координаты) должны уменьшатся.

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

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

2.2. Маршрутный алгоритм

 

Маршрутный алгоритм имеет две разновидности:

·Основанный на вычислении расстояния между точками;
·Основанный на рекуррентном соотношении.
Маршрутный алгоритм получил свое название, потому что осуществляет одновременно и формирование фронта и прокладывание трассы. Источником волны на каждом шаге является конечный элемент участка трассы проложенной на предыдущих шагах.

 

2.2.1. Маршрутный алгоритм основанный на вычислении расстояния между точками.

Работа алгоритма начинается от начального элемента. При этом вокруг начального элемента рассматривается 8-ми элементная окрестность. От каждого элемента окрестности до конечного элемента оценивается длина пути. При этом расстояние между точками вычисляется по формуле:

D=|Xi-XB|+|Yi-YB|,

где (Xi, Yi) – Координаты точки окрестности. (XВ, YВ)- Координаты конечного элемента.

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

 

2.2.2. Маршрутный алгоритм основанный на рекуррентном соотношении.

Маршрутный алгоритм можно построить на основе следующего рекуррентного соотношения:

y(x) = 2y(x + h) + y(x + 2h) + d,

где x, y(x) - абсцисса и ордината элемента занимаемого трассой на данном шаге.

(x + h) - ордината элемента занимаемого трассой на предыдущем шаге.

(x + 2h) - ордината элемента отстоящего от вычисляемого на 2 шага.

h - величина изменения абсциссы на каждом шаге.

d (delta) - это функция определяющая вид трассы. Если d=0 то строится прямолинейная трасса, если d=const то строится параболическая трасса.

Ордината очередного элемента трассы вычисляется по рекуррентной формуле, а абсцисса трассы вычисляется по формуле :

D=Xn=Xn-1+h

Знак "+" или "-" в рекуррентной формуле выбирается исходя из того откуда начинается построение трассы, из начального элемента "+", и соответственно из конечного "-".

По этой формуле чтобы вычислить 3-й элемент трассы необходимо знать два предыдущих. Первым элементом является исходный элемент A(XA,YA), тогда ордината второго элемента вычисляется по формуле :

Y(X)=Y(XA)+ ((Y(XA)-Y(XB))/(XA-XB))*h

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

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

 

 

3. Алгоритм нахождения пути на карте

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

 

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

Алгоритм нахождения крaтчaйшего мaршрутa между двумя точками для такой задачи:

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) по следующим правилам:
1.Если поле P(i,j) непроходимо, то R(i,j):=255;
2.Если поле P(i,j) проходимо, то R(i,j):=254;
3.Если поле P(i,j) является целевой (финишной) позицией, то R(i,j):=0;
4.Если поле P(i,j) является стaртовой позицией, то R(i,j):=253.
Этaп "Рaспрострaнения волны". Вводим переменную Ni - счётчик итерaций (повторений) и присвaивaем ей нaчaльное знaчение 0.

3.Вводим констaнту Nк,которую устaнaвливaем рaвной мaксимaльно возможному числу итерaций.
4.Построчно просмaтривaем рaбочий мaссив R (т.е.оргaнизуем двa вложенных циклa: по индексу мaссивa i от 1 до М, по индексу мaссивa j от 1 до N).
5.Если 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):
1.Eсли R(i+1,j)=253, то переходим к пункту 10;
2.Eсли R(i+1,j)=254, выполняется присвaивaние R(i+1,j):=Ni+1;
3.Во всех остaльных случaях R(i+1,j) остaётся без изменений.
Aнaлогично поступaем с элементaми R(i-1,j), R(i,j+1),R(i,j-1).

6.По зaвершению построчного просмотрa всего мaссивa увеличивaем Ni нa 1.
7.Если Ni>Nк,то поиск мaршрутa признаётся неудачным. Выход из программы.
8.Переходим к пункту 5.
9.Этaп построения мaршрутa перемещения. Присвaивaем переменным Х и Y знaчения координaт стaртовой позиции.
10.В окрестности позиции R(Х,Y) ищем элемент с нaименьшим знaчением (т.е.для этого просмaтривaем R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координaты этого элементa зaносим в переменные X1 и Y1.
11.Совершaем перемещение объектa (робота) по игровому полю из позиции [X,Y] в позицию [X1,Y1]. (По желaнию, вы можете предвaрительно зaносить координaты X1,Y1 в некоторый мaссив, и, только зaкончив построение всего мaршрутa,зaняться перемещением героя нa экрaне).
12.Если R(X1,Y1)=0,то переходим к пункту 15.
13.Выполняем присвaивaние X:=X1,Y:=Y1. Переходим к пункту 11.
14.Конец.

Вид программы на этапе построения препятствия

 

 

Нахождение пути

unit fMain;
 
interface
 
………………
type
 
TfmMain = class(TForm)
    ScrollBox1
: TScrollBox;
    Image1
: TImage;
………………….
 
private
   
FNowDraw : Boolean;
 
public
 
 
end;
 
const
 
GridSize = 64;
 
var
  fmMain
: TfmMain;
  aR
, aP : array[0..GridSize-1,0..GridSize-1] of byte;
 
Ni: Integer = 0;
 
Nk: Integer = 300;
 
Xglob,Yglob : Integer;
  X
,Y,X1,Y1 : Integer;
 
implementation
 
 
procedure
TfmMain.bStartClick(Sender: TObject);
var
  i
: Integer;
begin
  Image1
.Canvas.Brush.Color := clWhite;
  Image1
.Canvas.FillRect(rect(0,0,GridSize*5,GridSize*5));
  Image1
.SetBounds(0,0,GridSize*5,GridSize*5);
  Image1
.Canvas.Pen.Color := clLtGray;
 
for i := 1 to GridSize do
   
begin
      Image1
.Canvas.MoveTo(i*5,0);
      Image1
.Canvas.LineTo(i*5,GridSize*5);
      Image1
.Canvas.MoveTo(0,i*5);
      Image1
.Canvas.LineTo(GridSize*5,i*5);
   
end;
 
Ni := 0;
 
Nk := 300;
end;
 
procedure
TfmMain.Image1MouseDown(Sender: TObject; Button: TMouseButton;
 
Shift: TShiftState; X, Y: Integer);
begin
   
if tbEdit.Down then
   
case Button of
     mbLeft
:
           
begin
             
FNowDraw := True;
             Image1
.Canvas.Brush.Color := clBlack;
           
end;
     mbRight
:
       
begin
         
Xglob := X;
         
Yglob := Y;
         
FNowDraw := False;
         pmPoint
.Popup(Image1.ClientToScreen(point(x,y)).X,
                       Image1
.ClientToScreen(point(x,y)).Y);
       
end;
   
end;
end;
 
procedure
TfmMain.N2Click(Sender: TObject);
var
  i
, j: integer;
begin
 
if dlgOpen.Execute
   
then
     
begin
       
Ni := 0;
       
Nk := 300;
        Image1
.Picture.LoadFromFile(dlgOpen.FileName);
        Image1
.Height := Image1.Picture.Height;
        Image1
.Width  := Image1.Picture.Width;
       
for i :=0 to GridSize-1 do
         
for j :=0 to GridSize-1 do
           
begin
             
case Image1.Canvas.Pixels[i*5+1,j*5+1] of
                clBlack
: aP[i][j] := 255; //непроходимо
                clWhite
: aP[i][j] := 254; //проходимо
                clRed  
:
                 
begin
                    aP
[i][j] := 253; //старт
                    X
:= i;
                    Y
:= j;
                 
end;
                clGreen
: aP[i][j] := 0;   //финиш
             
end;
           
end;
     
end;
end;
 
procedure
TfmMain.N4Click(Sender: TObject);
begin
 
if dlgSave.Execute then
    Image1
.Picture.SaveToFile(dlgSave.FileName);
end;
 
procedure
TfmMain.Image1MouseUp(Sender: TObject; Button: TMouseButton;
 
Shift: TShiftState; X, Y: Integer);
begin
 
FNowDraw := false;
end;
 
procedure
TfmMain.Image1MouseMove(Sender: TObject; Shift: TShiftState; X,
  Y
: Integer);
begin
 
if FNowDraw then
    Image1
.Canvas.FillRect(rect((X div 5) *5+1,(y div 5) *5+1,(X div 5) *5+5,(y div 5) *5+5));
end;
 
procedure
TfmMain.N5Click(Sender: TObject);
begin
  Image1
.Canvas.Brush.Color := clRed;
  Image1
.Canvas.FillRect(rect((Xglob div 5) *5+1,(Yglob div 5) *5+1,(Xglob div 5) *5+5,(Yglob div 5) *5+5));
end;
 
procedure
TfmMain.N6Click(Sender: TObject);
begin
  Image1
.Canvas.Brush.Color := clGreen;
  Image1
.Canvas.FillRect(rect((Xglob div 5) *5+1,(Yglob div 5) *5+1,(Xglob div 5) *5+5,(Yglob div 5) *5+5));
end;
 
procedure
TfmMain.ToolButton2Click(Sender: TObject);
var
  i
, j : Integer;
  min
: Byte;
  ni
: byte;
begin
 
for Ni := 0 to 253 do
 
for i := 0 to GridSize-1 do
   
for j := 0 to GridSize-1 do
     
begin
       
if aP[i,j] = Ni then
         
begin
           
case aP[i+1,j] of
             
253: break;
             
254: aP[i+1,j] := Ni+1;
           
end;
           
case aP[i-1,j] of
             
253: break;
             
254: aP[i-1,j] := Ni+1;
           
end;
           
case aP[i,j+1] of
             
253: break;
             
254: aP[i,j+1] := Ni+1;
           
end;
           
case aP[i,j-1] of
             
253: break;
             
254: aP[i,j-1] := Ni+1;
           
end;
         
end;
     
end;
  Image1
.Canvas.Brush.Color := clBlue;
 
while aP[x1,y1] <> 0 do
   
begin
     
Application.ProcessMessages;
      min
:= aP[x+1,y];
     
if aP[x-1,y] < min then min := aP[x-1,y];
     
if aP[x,y-1] < min then min := aP[x,y-1];
     
if aP[x,y+1] < min then min := aP[x,y+1];
     
if min = aP[x,y-1] then begin x1:=x; y1:=y-1;  end;
     
if min = aP[x,y+1] then begin x1:=x; y1:=y+1;  end;
     
if min = aP[x+1,y] then begin x1:=x+1; y1:=y;  end;
 
     
if min = aP[x-1,y] then begin x1:=x-1; y1:=y;  end;
      x
:= x1;
      y
:= y1;
      Image1
.Canvas.FillRect(rect(X  *5+1,Y  *5+1,X *5+5,Y  *5+5));
      Image1
.Update;
   
end;
end;
 
end.