Szybkie odnajdywanie drogi

    -- Sebastian Pawlak, 1997, PCkurier 3/1999.


Gry to obecnie olbrzymia część rynku komputerowego. Potrzeba tworzenia coraz doskonalszych produkcji powoduje szybki rozwój technik ich programowania. Lecz ten, kto chce zaszokować jakimś rewelacyjnym pomysłem powinien najpierw opanować podstawowe algorytmy. Celem tego artykułu jest właśnie uzupełnienie fundamentalnej wiedzy programisty. Algorytm poszukiwania najkrótszej drogi z punktu A do B jest ważnym elementem wielu gier. W grach strategicznych (np. WarCraft) służy do automatycznego omijania przeszkód terenowych przez poruszającą się postać. Zastosowanie tego algorytmu można znaleźć w przygodówkach i strzelankach 3D. Przedstawiony tu algorytm, w niektórych przypadkach nie wyszukuje najkrótszej ścieżki, ale jest bardzo szybki i dlatego nadaje się do zastosowania w grze komputerowej. Oto pobieżny opis algorytmu szukania drogi z punktu A do B: 


1. Wpisujemy:
   - pozycję startową (X,Y) do tablicy WezlyPoz [0],
   - wyliczoną odległość (odcinek między A i B) do
     LenWezly [0],
   - "zajmujemy" aktualną komórkę poprzez wpisanie 0 do
     LenMapa [X,Y].
2. Przeszukujemy tablicę LenWezly pod kątem ustalenia
   komórki K leżącej najbliżej punktu B.
3. Badamy sąsiadujące komórki dla aktualnej pozycji K
   (góra, prawo, dół, lewo, góra-lewo, góra-prawo,
    dół-prawo, dół-lewo).
4. Jeśli znajdziemy pustą komórkę to wpisujemy:
   - do LenMapa [x,y] (pusta komórka) dane z tablicy
     LenMapa [X,Y]+1 (komórka K),
   - do tablicy WezlyPoz pozycję pustej komórki,
   - do LenWezly odległość od pustej komórki do punktu B
5. Powtażamy 3-4 dla wszystkich wolnych komórek wokół
   podstawowej K.
6. Powtażamy 2-5 aż dojdziemy do punktu B.
7. Teraz według uzyskanej mapy (LenMapa) z drogami do
   przejścia od A do B szukamy najkrótszej drogi.

Na rysunku przedstawiam przykładowy efekt działania programu. Cyfry w komórkach pochodzą z tablicy LenMap. 




Oto wydruk programu gotowego do uruchomienia:


{Poszukiwanie ścieżki z punktu A do B}
{autor: Sebastian Pawlak}

Uses crt,graph;

Type PozInfo=Record
 X,Y :word;
End;

Const komorka=20; {rozmiar pojedynczej komórki w pikselach}
      szer=640 div komorka-1; {ilość komórek w poziomie}
      wys=480 div komorka-1;  {ilość komórek w pionie}

Var Mapa :array [0..szer,0..wys] of byte;
    LenMapa :array [0..szer,0..wys] of word;

    i,j :word;
    PozycjaStart :PozInfo;
    PozycjaKoniec :PozInfo;
    Pos :PozInfo;
    NrWezla :word;
    NajkrotszaDroga :word;
    NajkrKrok :word;
    NajkrPos :PozInfo;
    Step :byte;

Procedure Grafika;
Var a,b,c :integer;
Begin
 a:=0; b:=0;
 InitGraph (a,b,'c:\tp\bgi\'); {włącza tryb graficzny}

 SetColor (blue);
 {obramowanie planszy}
 For a:=0 to szer do Mapa [a,0]:=1;
 For a:=0 to szer do Mapa [a,wys]:=1;
 For a:=0 to wys do Mapa [0,a]:=1;
 For a:=0 to wys do Mapa [szer,a]:=1;

 For a:=2 to wys do Mapa [14,a]:=1;

 For a:=0 to szer do
  For b:=0 to wys do
  Begin
   Rectangle (a*komorka,b*komorka,a*komorka+komorka,
              b*komorka+komorka);
   If Mapa [a,b]<>0 then
   Begin
    SetColor (green);
    For c:=b*komorka+1 to b*komorka+komorka-1 do
     Line (a*komorka+1,c,a*komorka+komorka-1,c);
    SetColor (blue);
   End;
  End;

  SetColor (10);
  For a:=0 to Komorka div 3 do
   Circle (PozycjaStart.x*komorka+komorka div 2,
           PozycjaStart.y*komorka+komorka div 2,a);
  SetColor (11);
  For a:=0 to komorka div 3 do
   Circle (PozycjaKoniec.x*komorka+komorka div 2,
           PozycjaKoniec.y*komorka+komorka div 2,a);
End;

{Główna procedura odnajdywania ścieżki}
Procedure FindPath;
Var WezlyPoz :array [0..500] of PozInfo;
    LenWezly :array [0..500] of word;

{"zerowanie" tablicy LenWezly}
Procedure Czysc;
Var a,b:integer;
Begin
 For a:=0 to szer do
  For b:=0 to wys do
   LenMapa [a,b]:=$FFFF;
End;

{tworzy węzeł - punkt pretendujący do ścieżki}
Procedure TworzWezel (x,y:integer);
Var s :string;
Begin
 If ((LenMapa[Pos.X+x,Pos.Y+y]=$FFFF) AND
     (Mapa[Pos.X+x,Pos.Y+y]=0)) then
 Begin
  LenMapa [Pos.X+x,Pos.Y+y]:=LenMapa [Pos.X,Pos.Y]+1;
  WezlyPoz [NrWezla].X:=Pos.X+x;
  WezlyPoz [NrWezla].Y:=Pos.Y+y;
  {tu obliczana jest odległość z punktu A do B;}
  {zastosowane jest tu Tw. Pitagorasa, ale bez wyciągania}
  {pierwiastka z całości ; otrzymana wartość określa}
  {odległość z A do B, a komputer nie musi tracić czasu}
  {na pierwiastkowanie}
  LenWezly [NrWezla]:=((Pos.X+x)-PozycjaKoniec.X)*((Pos.X+x)
    -PozycjaKoniec.X)+((Pos.Y+y)-PozycjaKoniec.Y)*((Pos.Y+y)
    -PozycjaKoniec.Y);
  Inc (NrWezla);

  {poniższe 3 funkcje weź w nawias klamrowy, aby nie były}
  {wyświetlane na rysunku numery z tablicy LenMapa}
  Str (LenMapa [Pos.X+x,Pos.Y+y],s);
  SetColor (15);
  OutTextxy ((Pos.x+x)*komorka+(komorka div 2-length (s)
             *8 div 2)+1,(Pos.y+y)*komorka+7,s);
 End;
End;

{Sprawdza, który punkt leży bliżej celu}
Procedure Sprawdz (x,y:integer);
Begin
 If LenMapa[Pos.X+x,Pos.Y+y]<NajkrKrok then
 Begin
  NajkrKrok:=LenMapa[Pos.X+x,Pos.Y+y];
  NajkrPos.X:=Pos.X+x;  NajkrPos.Y:=Pos.Y+y;
 End;
End;

Begin
 Czysc;

 {wpisanie do listy pozycji startowej}
 WezlyPoz [0]:=PozycjaStart;
 LenWezly [0]:=(PozycjaStart.X-PozycjaKoniec.X)
                *(PozycjaStart.X-PozycjaKoniec.X)
                +(PozycjaStart.Y-PozycjaKoniec.Y)
                *(PozycjaStart.Y-PozycjaKoniec.Y);
 LenMapa [PozycjaStart.X,PozycjaStart.Y]:=0;

 NrWezla:=1;
 Repeat
  NajkrotszaDroga:=0;
  For i:=0 to NrWezla-1 do
   If (LenWezly [i]<LenWezly [NajkrotszaDroga]) then
       NajkrotszaDroga:=i;

  Pos:=WezlyPoz [NajkrotszaDroga];
  WezlyPoz [NajkrotszaDroga]:=WezlyPoz [NrWezla-1];
  LenWezly [NajkrotszaDroga]:=LenWezly [NrWezla-1];
  Dec (NrWezla);

  TworzWezel (0,-1); {góra}
  TworzWezel (1,0);  {prawo}
  TworzWezel (0,1);  {dół}
  TworzWezel (-1,0); {lewo}
  TworzWezel (1,-1); {prawy-górny}
  TworzWezel (1,1);  {prawy-dolny}
  TworzWezel (-1,1); {lewy-dolny}
  TworzWezel (-1,-1);{lewy-górny}
 Until ((Pos.X=PozycjaKoniec.X)
        AND(Pos.Y=PozycjaKoniec.Y))OR(NrWezla=0);

 If NrWezla<>0 then
 Begin
  Pos := PozycjaKoniec;
  step:=0;
  While NOT ((Pos.X=PozycjaStart.X)
             AND (Pos.Y=PozycjaStart.Y)) do
  Begin
   Inc (Step);
   NajkrKrok := $FFFF;

   Sprawdz (0,-1); {góra}
   Sprawdz (1,0);  {prawo}
   Sprawdz (0,1);  {dół}
   Sprawdz (-1,0); {lewo}
   Sprawdz (1,-1); {prawy-górny}
   Sprawdz (1,1);  {prawy-dolny}
   Sprawdz (-1,1); {lewy-dolny}
   Sprawdz (-1,-1);{lewy-górny}

   Pos:=NajkrPos;

   SetColor (6);
   Circle (NajkrPos.X*komorka+komorka div 2,
           NajkrPos.Y*komorka+komorka div 2,
           komorka div 2-1);
   Circle (NajkrPos.X*komorka+komorka div 2,
           NajkrPos.Y*komorka+komorka div 2,
           komorka div 2-2);

   End;
 End
 Else OutTextxy (3,3,'Brak przejscia !!!!');
End;

Begin
 PozycjaStart.X:=3;  PozycjaStart.Y:=10;
 PozycjaKoniec.X:=25;  PozycjaKoniec.Y:=6;

 Grafika;
 FindPath;

 ReadKey;
 CloseGraph;
End.

Są jeszcze inne metody badania ścieżki, z punktu A do B, o których informacje można uzyskać w internecie.

w3cw3c
automatyka przemysłowa