Odnajdywanie ścieżki typu A* dla początkujących

Autor: Patrick Lester (ostatnia modyfikacja 18. lipiec 2005r.)
Tłumaczenie z angielskiego na polski: Zbigniew Wielgosz (10 listopad 2006 r.)

Ten artykuł został przetłumaczony na języki: Albański, Chiński, Francuski, Niemiecki, Grecki, Portugalski, Rosyjski, Hiszpański i Polski. Tłumaczenia na inne języki będą mile widziane. Na końcu tego artykułu znajduje się odpowiedni adres e-mail.

Algorytm A* (A-star) może być skomplikowany dla początkujących. Jest wiele artykułów dostępnych w sieci, które wyjaśniają działanie algorytmu A*, lecz w większości napisane są dla ludzi znający już podstawy. Ten artykuł jest skierowany do prawdziwych początkujących.

Ten artykuł nie ma na celu zdefiniować rozwiązania dla konkretnego problemu. W istocie ma opisać podstawy i przygotować was do przeczytania innych materiałów i przyswojenia wiedzy w nich opisanych. Linki do kilku najlepszych z nich są umieszczone na końcu tego artykułu.

Podsumowując, ten artykuł nie jest ukierunkowany na konkretny program. Powinniście móc zaadaptować to co tu znajdziecie do dowolnego języka programowania. Jednak, jak mogliście się spodziewać, dołączyłem link do przykładowego programu na końcu tego artykułu. Skompresowany plik zawiera dwie wersje kodów źródłowych programu: jedna w C++, a druga w Blitz Basic’u oraz pliki wykonywalne prezentujące działanie algorytmu A*. 

Zacznijmy od początku...

Wprowadzenie: Przestrzeń Poszukiwań

Przyjmijmy, że mamy kogoś kto chce przejść z pkt. A do pkt. B. Przyjmijmy, że oba punkty oddziela mur. Tą sytuację zilustrowano poniżej. Na zielono oznaczono pkt. A, na czerwono pkt. B, a niebieskie pola oznaczają mur między nimi.

   
[Rysunek 1]

Pierwszą rzeczą którą powinniście odnotować to, że przestrzeń poszukiwań podzielona jest na siatkę kwadratowych pól. Takie uproszczenie przestrzeni poszukiwań jest pierwszym krokiem odnajdywania ścieżki. Omawiana metoda redukuje przestrzeń poszukiwań do prostej dwuwymiarowej tablicy. Każda komórka tablicy reprezentuje jedno pole siatki, a jej status został opisany jako MOŻNA lub NIE-MOŻNA przejść. Ścieżka zostanie wytyczona poprzez oznaczenie tych pól które powinniśmy przejść by przedostać się z pkt. A do pkt. B. Kiedy ścieżka zostanie znaleziona, osoba będzie przechodzić z centrum pierwszego kwadratu do centrum następnego do momentu, gdy cel zostanie osiągnięty.

Te centralne punkty nazywane są "węzłami" (ang. ”nodes”). Jeśli czytaliście już gdzieś o odnajdowaniu ścieżek, to pewnie często napotykaliście się na dyskusje o węzłach. Dlaczego nie nazwać ich po prostu kwadratami? Ponieważ istnieje możliwość, że przestrzeń poszukiwań zostanie podzielona inaczej niż w siatkę kwadratów. Równie dobrze to może być siatka prostokątów, sześciokątów, trójkątów lub jakikolwiek innych kształtów, a węzły mogą być umieszczone we wnętrzu każdego kształtu - w centrum, na jednej z krawędzi lub gdziekolwiek indziej. My używamy siatki kwadratów, ponieważ to jest najprostsze.

Początek poszukiwań

Skoro już uprościliśmy nasze pole poszukiwań do dających się zarządzać węzłów, poprzez nałożenie siatki kwadratów, to następnym krokiem będzie przeprowadzenie poszukiwań najkrótszej ścieżki. Zrobimy to rozpoczynając od punktu startowego A, sprawdzając przyległe kwadraty, a generalnie prowadząc poszukiwania w kierunku zewnętrznym do, momentu odnalezienia celu (pkt B).

Rozpoczynamy poszukiwania postępując zgodnie z następującymi punktami:

1.    Zaczynamy w punkcie startowym A i dodajemy go do "Listy Otwartych" - pól oczekujących na sprawdzenie. Lista Otwartych jest czymś w rodzaju listy zakupów. W tym momencie jest tylko jedna pozycja na liście, ale później będzie ich więcej. Lista Otwartych zawiera pola które mogą zawierać się w poszukiwanej ścieżce (tworzyć ją), ale nie koniecznie. Po prostu, to jest lista pól, które wymagają sprawdzenia.

2.     Szukamy wszystkich osiągalnych pól oznaczonych jako MOŻNA, przyległych do pola startowego (pkt. A), ignorując te z murami, wodą lub inne oznaczone jako NIE-MOŻNA. Dodajemy je do Listy Otwartych. Dla każdego z tych pól zachowujemy pkt. A jako "pole rodzica". To działanie jest ważne ze względu na możliwość podążania po wyznaczonej ścieżce, co zostanie wyjaśnione później.

3.    Usuwamy pole startowe A z Lisy Otwartych i dodajemy je do Lisy Zamkniętych, by zaznaczyć, że nie musimy sprawdzać go ponownie.

W tym momencie przyda się poniższa ilustracja. Zielone pole w środku jest punktem startowym A. Otoczono je jasnoniebieską obwódką, co oznacza, że zostało dodane do Listy Zamkniętych. Wszystkie przyległe pola są obecnie na Liście Otwartych, oczekując na sprawdzenie, a oznaczono je jasnozieloną obwódką. Każde z pól przyległych posiada szary wskaźnik, wskazujący na kwadrat rodzicielski, którym w tym przypadku jest pkt. A.


[Rysunek 2]

Następnie wybieramy jeden z przyległych kwadratów z Listy Otwartych i mniej więcej powtarzamy opisany wyżej proces. Ale który kwadrat wybrać? Ten, którego koszt F jest najniższy.

Szacowanie Ścieżki

Wybór pól wyznaczających poszukiwaną ścieżkę, determinuje poniższe równanie:

F = G + H 

gdzie:

Nasza ścieżka jest generowana przez powtarzanie przeglądania Listy Otwartych i wybieranie spośród jej zawartości pól o najniższym koszcie F. Proces ten zostanie opisany bardziej szczegółowo w dalszej części tego artykułu. Na początek przyjrzyjmy się bliżej sposobowi obliczania równania.

Jak opisano powyżej, G jest kosztem przejścia z punktu startowego do aktualnego pola, via wygenerowaną dotychczas ścieżkę. W tym przykładzie, ustalimy 10 jako koszt każdego poziomego lub pionowego kroku, a 14 jako koszt każdego kroku na skos. Użyjemy tych liczb, ponieważ odległość w ruchu na skos dla siatki kwadratów jest równy pierwiastkowi kwadratowemu z kosztu ruchu w pionie lub w poziomie. Pierwiastek kwadratowy z K jest w przybliżeniu równy iloczynowi K i 1,414. My użyjemy wartości 10 i 14 dla uproszczenia. Stosunek wielkości pozostanie prawidłowy, a dzięki temu unikniemy obliczania pierwiastków i pracy na liczbach zmiennoprzecinkowych. Nie zrobimy tego, bo po prosu jesteśmy głupi, leniwi i nie lubimy matematyki. Użycie liczb całkowitych znacznie przyspiesza pracę komputera. Szybko się zorientujecie, że odnajdywanie ścieżki może być bardzo wolne, jeśli nie wykorzystacie skrótów podobnych temu.

Aby wyznaczyć koszt przejścia wytyczoną ścieżką do aktualnej pozycji G, sumujemy koszt G pola rodzica z liczbą 10 lub 14 w zależności od kierunku ruchu z pola rodzica do aktualnego pola. Potrzeba zastosowania tej metody staje się bardziej oczywista w dalszym przebiegu tego przykładu, kiedy aktualna pozycja będzie w większej odległości niż jedno pole do punktu startowego.

H może być wyznaczone na wiele sposobów. Metoda zastosowana przez nas nosi nazwę Manhattan. Polega ona na obliczeniu całkowitej ilości pól koniecznych do przejścia od aktualnej pozycji do celu (pkt. B), dla ruchu poziomego i pionowego, nie wykorzystując ruchu po skosie oraz ignorując wszelkie przeszkody jakie mogą wystąpić na trasie. Następnie wynik mnożymy przez 10 (koszt kroku w pionie lub poziomie). Nazwa metody (prawdopodobnie) pochodzi od miejskiego sposobu obliczania liczby bloków między jednym miejscem a drugim, kiedy nie możesz przeciąć bloku na skos.

Czytając ten opis, możecie przypuszczać, że heurystyka jest po prostu niedokładnym przybliżeniem pozostałego dystansu w linii prostej pomiędzy polem aktualnym a polem docelowym. Nie w tym przypadku. W rzeczywistości staramy się oszacować pozostały dystans wzdłuż ścieżki (który jest zwykle większy). Przybliżając nasze oszacowanie pozostałego dystansu, przyspieszamy działanie algorytmu. Jeśli jednak przeszacujemy ten dystans, nie będziemy mieć gwarancji że otrzymamy najkrótszą ścieżkę. W większości przypadków, będziemy mieli to co nazwa się niedopuszczalną heurystyką (ang. “inadmissible heuristic”).

Technicznie rzecz biorąc, w tym przypadku, metoda Manhattan jest niedopuszczalną, ponieważ przeszacowuje w niewielkim stopniu pozostały dystans. Jednakże będziemy jej używać, bo jest znacznie łatwiejsza do zrozumienia i wystarczy na nasze potrzeby, a poza tym przeszacowuje tylko troszkę. W niewielu przypadkach może się zdążyć, że otrzymamy ścieżkę, która nie będzie najkrótszą z możliwych, jednak będzie bardzo bliska najkrótszej. Jeśli chcecie wiedzieć więcej, tu możecie znaleźć równania i dodatkowe informacje nt. heurystyki.

F jest sumą G i H. Rezultat naszego pierwszego kroku są widoczne na poniższym rysunku. Punktacja F, G i H są zapisane w każdym polu. Tak jak to pokazano w polu umiejscowionym na prawo od pola startu, punktacja F jest wyświetlana w lewym górnym rogu, G w lewym dolnym, a H w prawym dolnym.

[Rysunek 3] 

A teraz popatrzy na inne pola. W polu zawierającym litery G = 10, ponieważ jest ono tylko jedno pole od pola startowego w kierunku poziomym. Pola bezpośrednio nad, pod i po lewej stronie pola startowego mają taką samą wartość G = 10. Pola położone na skos od pola startowego mają wartość G = 14.

Wartości H są obliczane przez oszacowywanie metodą Manhattan odległości do czerwonego pola celu, przy ruchu tylko poziomym lub pionowym i ignorowaniu muru stojącego na drodze. Używając tej metody, pole bezpośrednio na prawo od pola startowego jest położone 3 pola od czerwonego, co daje wartość H = 30. Pole bezpośrednio powyżej tego pola jest oddalone o 4 pola (pamiętajcie, ruch odbywa się jedynie poziomo i pionowo), co daje wartość H = 40. Pewnie już wiecie jak obliczono wartości H pozostałych pól. Wartość F dla każdego pola jest obliczana przez dodanie do siebie wartości G i H.

Kontynuacja poszukiwań

By kontynuować poszukiwania, po prostu wybieramy pole o najniższej wartości F spośród wszystkich na Liście Otwartych. Z wybranym polem postępujemy zgodnie z poniższą instrukcją:

4.    Usuwamy pole z Listy Otwartych i dodajemy je do Listy Zamkniętych.

5.    Sprawdzamy wszystkie przyległe pola. Ignorując wszystkie z Listy Zamkniętych lub oznaczonych jako te których NIE-MOŻNA przejść (mury, woda itp.), dodajemy pola do Listy Otwartych, jeśli jeszcze ich tam nie ma. Wybrane pole ”Z” wskazujemy jako “pole rodzica” dla nowych pól na Liście Otwartych.

6.    Jeśli przyległe pole ”X” było już wcześniej dodane do Listy Otwartych, sprawdzamy czy ścieżka o aktualnym przebiegu do tego pola jest lepszą. Innymi słowy, sprawdzamy czy wielkość G pola ”X” jest mniejsza, jeśli użyjemy aktualnego pola ”Z” by się dostać na pole ”X”. Jeśli nie, nie wykonujemy dodatkowych działań. W przeciwnym przypadku, jeśli wielkość G dla nowej ścieżki jest mniejsza, zmieniamy wskazanie ”pola rodzica” dla przyległego pola ”X” na aktualne pole ”Z” (na rysunku wyżej, zmieniamy kierunek wskaźnika by wskazywał wybrane pole). Na koniec, przeliczamy ponownie wartości F i G dla tego pola ”X”. Jeśli to wydaje się zagmatwane, nie martwcie się – zagadnienie zilustrowano poniżej.

OK, zobaczmy jak to działa. Z naszych początkowych 9 pól, zostało nam 8 na Liście Otwartych, po przeniesieniu pola startowego na Listę Zamkniętych. Jedno z nich, o najniższej wartości F = 40, leży bezpośrednio na prawo od pola startowego. Więc wybieramy to pole jako nasze następne (aktualne). Podświetlono je na niebiesko na poniższym rysunku.

[Rysunek 4]

Na początku usuwamy aktualne pole z Listy Otwartych i dodajemy je do Listy Zamkniętych (to dlatego jet teraz podświetlony na jasnoniebiesko). Następnie sprawdzamy pola przyległe. Pole bezpośrednio na prawo jest murem, więc to ignorujemy. Pole bezpośrednio na lewo jest polem startowym i znajduje się na Liście Zamkniętych, wiec też je ignorujemy. 

Pozostałe cztery pola są już na Liście Otwartych, więc musimy sprawdzić czy ścieżki do to tych pól będą trochę lepsze (krótsze), jeśli ścieżki będą prowadzić przez aktualne pole. Zrobimy to używając wartości G jako wyznacznika. Popatrzmy na pole bezpośrednio powyżej aktualnego pola - jego obecna wartość G = 14. Jeśli ścieżka do tego pola prowadziłaby przez aktualne pole, jego wartość G byłaby równa 20 (G = 10 aktualnego pola plus 10 za przejście z pionowe przejście z aktualnego pola w górę). Ponieważ 20 to więcej niż 14, uznajemy, że to nie byłaby lepsza ścieżka. Spojrzenie na rysunek może ułatwić zrozumienie. Lepiej (krócej) będzie dostać się tam w jednym ruchu na skos, niż w dwóch – jednym w poziomie i drugim w pionie.

Gdy powtórzymy proces dla 4 przyległych pól znajdujących się na Liście Otwartych, stwierdzimy, że żadna ze ścieżek nie zostałaby ulepszona gdyby przechodziła przez aktualne pole, więc niczego nie zmieniamy. Teraz wykonaliśmy już wszystkie czynności z aktualnym polem i jesteśmy gotowi by przejść do następnego.

Skoro tak, przeglądamy pozostałe 7 poł znajdujących się na Liście Otwartych i wybieramy jeden z najniższa wartością F. W tym ciekawym przypadku, znajdują się tam 2 pola z wartością G = 54. Więc który mamy wybrać? To naprawdę to nie ma znaczenia. Mając na względzie szybkość, wybieramy ostatnie jakie dodaliśmy do Listy Otwartych. To skłonność poszukiwań do akceptowania pól znalezionych najpóźniej, kiedy znajdujemy się bliżej celu. Ale to nie ma znaczenia. (Tak selektywne traktowanie węzłów może być przyczyną dla której inna wersja algorytmu A* może zwrócić inną ścieżkę o takiej samej długości.)

Wybierzmy więc pole zaraz pod spodem aktualnego i na skos w kierunku prawo-dół, jak pokazuje poniższy rysunek.

[Rysunek 5] 

Tym razem, gdy sprawdzamy przyległe pola, znajdujemy jedno bezpośrednio po prawej stornie aktualnego, na którym jest mur, więc je ignorujemy. To samo robimy z polem usytuowanym na skos w górę po prawej od aktualnego, na którym również znajduje się mur. Również ignorujemy pole leżące na skos w dół po prawej od aktualnego. Dlaczego? Ponieważ nie można się dostać na to pole bezpośrednio z pola aktualnego bez “ścinania” narożnika muru. Aby się tam dostać, na początek należy przejść na pole bezpośrednio na dole, by następnie przejść bezpośrednio na prawo, omijając narożnik muru. (Notka: Reguła dot. zakazu “ścinania” narożników jest oczywiście opcjonalna. Jej użycie zależy od tego, jak rozłożyliście węzły.)

Pozostało pięć innych pól. Następnych dwóch pól po aktualnym nie maj jeszcze na Liście Otwartych, więc je do niej dodajemy, a aktualne pole czynimy ich “polem rodzica”. Z pozostałych trzech pól dwa są już na Liście Zamkniętych (pole startowe i to bezpośrednio nad aktualnym polem, oba zaznaczone jasnoniebieską obwódką), więc je ignorujemy. Co do ostatniego pola (bezpośrednio na lewo od aktualnego) sprawdzamy czy jego wartość G będzie mniejsza, jeśli dostaniemy się do niego przechodząc przez aktualne pole. Nie tym razem. Tak więc skończyliśmy z tym polem i jesteśmy gotowi do zajęcia się następnym z naszej Listy Otwartych. 

Powtarzamy ten proces do momentu dodania pola docelowego do listy zamkniętych, co w naszym przypadku wygląda tak, jak przedstawiono to na poniższym rysunku.

[Rysunek 6]

Zauważcie, że “pole rodzica” dla pola znajdującego się dwa pola poniżej pola startowego zostało zmienione. Porównajcie z poprzednim rysunkiem. Przed zmianą wartość G = 28, a wskaźnik kierował do pola na skos w górę po prawej. Teraz ma wartość G = 20, a wskaźnik kieruje do pola bezpośrednio nad nim. Zmianę wykonano w trakcie poszukiwań ścieżki, kiedy wartość G została sprawdzona i poprawiona na niższą, dzięki użyciu nowej (krótszej) ścieżki, efektem czego było wskazanie nowego “pola rodzica” oraz przeliczenie wartości G i F. Ta zmiana nie wydaje się być istotną w tym przypadku, lecz istnieje wiele możliwych sytuacji, gdzie takie stałe sprawdzanie owocuje zauważalnymi różnicami w wyznaczaniu najkrótszej ścieżki do pola docelowego.

A w jaki sposób wyznaczamy ścieżkę? Otóż, startując z czerwonego pola docelowego, przesuwamy się z jednego pola na drugie, będące jego “polem rodzica”, podążając za wskaźnikami. W taki sposób dostaniemy się z powrotem do pola startowego, poruszając się właśnie po poszukiwanej ścieżce. Przedstawiono to na poniższym rysunku. Przemieszczenie się z pola startowego A do pola docelowego B jest prostym przesuwaniem się z centrum każdego pola (węzła) do centrum następnego pola, znajdującego się na ścieżce, aż do osiągnięcia celu.

[Rysunek 7]

Podsumowanie metody A*

OK, przebrnęliśmy już przez wszystkie wyjaśnienia. Zbierzmy w jednym miejscu wszystkie kroki algorytmu:

1)    Dodajemy pole startowe (lub węzeł) do Listy Otwartych.

2)    Powtarzamy następujące:

a)    Szukamy pola o najniższej wartości F na Liście Otwartych. Czynimy je aktualnym polem.

b)    Aktualne pole przesuwamy do Listy Zamkniętych.

c)    Dla każdego z 8 przyległych pól (Xn) do pola aktualnego (Z) sprawdzamy:

·       Jeśli NIE-MOŻNA go (Xn) przejść lub jest już na Liście Zamkniętych ignorujemy je. W innym przypadku sprawdzamy:           

·       Jeśli pole (Xn) nie jest jeszcze na Liście Otwartych, dodajemy je do niej. Aktualne pole (Z) przypisujemy mu (Xn) jako “pole rodzica” i zapisujemy jego (Xn) wartości F, G i H. 

·       Jeśli pole (Xn) było już na Liście Otwartych, sprawdzamy czy aktualna ścieżka do tego pola (Xn) (prowadząca przez Z) jest lepsza (krótsza), poprzez porównanie jego (Xn) wartości G dla starej i aktualnej ścieżki. Mniejsza wartość G oznacza, że ścieżka jest krótsza. Jeśli tak, zmieniamy przypisanie “pole rodzica” na aktualne pole (Z) i przeliczamy wartości G i F dla pola (Xn). Jeśli wasza Lista Otwartych jest posortowana pod kątem wartości F, trzeba ją ponownie przesortować po wprowadzonej zmianie.

d)    Zatrzymujemy się, gdy:

·       Dodano pole docelowe do Listy Zamkniętych. W tym przypadku ścieżka została odnaleziona (popatrzcie na notkę poniżej) lub

·       Lista Otwartych jest pusta. W tym przypadku nie znaleziono pola docelowego, a ścieżka nie istnieje.   

3)    Zapisujemy ścieżkę. Krocząc w kierunku od pola docelowego (pkt. B) do startowego (pkt. A), przeskakujemy z kolejnych pól na im przypisane ”pola rodziców”, aż do osiągnięcia pola startowego. To jest wasza ścieżka.

Notka: We wcześniejszej wersji tego artykułu sugerowałem, że możecie zakończyć algorytm, kiedy pole docelowe (lub węzeł) zostało dodane do Listy Otwartych, a nie do Listy Zamkniętych. Ten sposób będzie szybszy i prawie zawsze da najkrótszą ścieżkę, ale nie zawsze. Różnice mogą powstać w sytuacji, gdy koszt przejścia z przedostatniego pola (węzła) na ostatnie (docelowe) jest bardzo duży, na przykład w przypadku, gdy między ostatnim a przedostatnim węzłem przepływa rzeka.

Mała dygraesja 

Warto wspomnieć, że kiedy czytaliście dyskusje na różnych forach w sieci nt. odnajdywania ścieżki A*, mogliście się okazjonalnie natknąć na czyjeś wypowiedzi opisujące jakiś kod jako algorytm A*, który nim nie jest. Aby użyć metody A*, musicie zawrzeć w kodzie elementy opisane wcześniej – szczególnie listy otwartych i zamkniętych, Wartościowanie ścieżki wielkościami F, G i H. Istnieje wiele algorytmów poszukiwania ścieżki, ale te inne metody nie są A*, który jest generalnie uznawany za najlepszy. Bryan Stout omówił wiele z nich w artykułach, do których odsyłacze zamieszczono na końcu, opisując ich zalety i wady. Czasami alternatywne algorytmu są lepsze ze względu na szczególne okoliczności, jednak zawsze należy zrozumieć sposób działania wykorzystywanego kodu.

Uwagi do implementacji

Już poznaliście podstawową metodę. W tym rozdziale przedstawiono dodatkowe wątki, które warto przemyśleć, przy tworzeniu swojego własnego programu. Niektóre z poniższych materiałów odnoszą się do programu, który napisałem w C++ i Blitz Basic’u, ale główne ich punktu są równie właściwe w innych językach programowania.

1.    Inne jednostki (unikanie kolizji): Jeśli zdarzy się wam przyjrzeć się bliżej mojemu przykładowemu kodowi, odnotujecie, że kompletnie ignoruje inne jednostki na ekranie. Jednostki przechodzą przez siebie nawzajem. W zależności od reguł gry, taki stan może być akceptowany lub nie. Jeśli chcecie uwzględniać inne jednostki w algorytmie odnajdywania ścieżki i zmuszać je do okrążania się nawzajem, sugeruję uwzględniać tylko te jednostki, które zatrzymują albo przylegają do jednostki poszukującej ścieżki, traktując ich obecne położenie jako pola których NIE‑MOŻNA przejść. Dla poruszających się przyległych jednostek, możecie unikać kolizji, poprzez ignorowanie węzłów należących do odpowiadających im ścieżek, zmuszając w ten sposób jednostkę poszukującą ścieżki do szukania alternatywnej trasy (więcej na temat pod #2).

Jeśli zechcecie uwzględniać inne jednostki, które się poruszają i nie są przyległe do jednostki poszukującej ścieżki, będziecie musieli wymyślić metodę przewidywania, gdzie będą się znajdować w dowolnym czasie, tak by były odpowiednio sprytne. W innym razie skończycie prawdopodobnie z dziwnymi ścieżkami, prowadzącymi zygzakiem, by wyminąć pola zajmowane kiedyś przez inne jednostki, których już tam nie będzie.

Oczywiście, będziecie również musieli wymyślić sposób na wykrywanie kolizji, ponieważ niezależnie od tego, jak dobrą była ścieżka w czasie jej wytyczania, sytuacja może się zmieniać w czasie. Kiedy nastąpi kolizja, jednostka musi wyznaczyć nową ścieżkę lub, jeśli druga jednostka porusza się i nie jest to kolizja czołowa, poczekać aż ta druga zejdzie jej z drogi.

Te wskazówki są prawdopodobnie wystarczające aby rozpocząć. Jeśli chcecie dowiedzieć się więcej, tu jest kilka odnośników, które mogą być pomocne:

·       Steering Behavior for Autonomous Characters (Sterowanie zachowaniem postaci autonomicznych): Praca Craig’a Reynold’a nt. sterowania zachowaniem; trochę różni się od odnajdywania ścieżki, ale może zostać z nim zintegrowane, dla stworzenia bardziej kompletnego systemu obsługi ruchu i kolizji.

·       The Long and Short of Steering in Computer Games (Długie i krótkie sterowanie w grach komputerowych): Interesujący przegląd literatury nt. sterowania i odnajdywania ścieżki. Plik PDF.

·       Coordinated Unit Movement (Skoordynowany ruch jednostki): Pierwszy z dwóch artykułów serii nt. formacji i ruchu grup autorstwa twórcy “Age of Empires” Dave’a Pottinger’a.

·       Implementing Coordinated Movement (Implementacja skoordynowanego ruchu): Drugi z dwóch artykułów autorstwa Dave’a Pottinger'a.

2. Zmienny Koszt Ruchu W Zależności Od Terenu: W tym przykładzie i w dołączonym przeze mnie programie teren może przyjmować jedynie dwa stany: MOŻNA lub NIE-MOŻNA przejść. A co zrobić, z terenem przez który MOŻNA przejść, ale koszt ruchu po nim jest wyższy? Bagna, wzgórza, schody w podziemiach itd. – wszystko to przykłady terenu, przez który MOŻNA przejść, ale koszt jego przejścia jest wyższy niż po płaskim lub otwartym terenie. Podobnie droga może mieć niższy koszt ruchu, niż otaczający ją teren.

Ten problem można łatwo rozwiązać, przez wprowadzenie zmiennej kosztu terenu do obliczeń wartości G kolejnych węzłów. Po prostu wprowadźcie dodatkową punktację dla każdego węzła. Algorytm A* ma już zaimplementowane odnajdywanie ścieżki o najniższym koszcie, wiec obsługa problemu zmiennego terenu nie powinna być żadnym problemem. W opisanym przeze mnie przykładzie, gdzie teren jedynie MOŻNA lub NIE-MOŻNA przejść, algorytm A* wyszykuje najkrótszej i najprostszej ścieżki. Jednak w środowisku o zmiennym koszcie terenu, imperatyw najniższego kosztu ścieżki może owocować powstaniem ścieżki o dłuższej trasie, dzięki czemu np. podróżująca jednostka wybierze drogę okrążającą bagna, zamiast przebyć je w pław.

Dodatkowym interesującym zagadnieniem jest coś, co profesjonaliści nazywają dynamiczną mapą (ang. ”influence mapping”). Tak, jak przy zmiennym koszcie terenu opisanym powyżej, powinniście stworzyć dodatkowy system punktacji i zastosować go w odnajdywaniu ścieżki. Wyobraźcie sobie, że macie mapę z gromadą jednostek broniących przełęczy w górskim regionie. Za każdym razem, kiedy komputer wysyła jednostkę ścieżką przechodząca przez przełęcz, jednostka jest niszczona. Jeśli chcecie, możecie stworzyć swojego rodzaju dynamiczną mapę, na której program będzie zaznaczał (jako niepożądane) węzły w pobliżu miejsc, gdzie miało miejsce sporo bezsensownych rzezi. To powinno nauczyć komputer faworyzowania bezpiecznych ścieżek i pozwoli mu unikać głupich sytuacji, kiedy wciąż wysyła jednostki bardzo niebezpieczną ścieżką tylko dlatego, że jest ona krótsza.

Jeszcze jednym możliwym zastosowaniem dynamicznych map jest zaznaczanie niedozwolonych węzłów należących do ścieżek poruszających się sąsiednich jednostek. Niedoskonałość algorytmu A* dobrze obrazuje przykład, kiedy grupa jednostek próbuje odnaleźć ścieżki do jednej lokacji lub bliskich sobie lokacji. Ścieżki wielu jednostek nakładają się na siebie, ponieważ przyjmują one podobne lub takie same trasy za najkrótsze do ich celów przeznaczenia. Wystrzeganie się węzłów już zajętych przez ścieżki innych jednostek, pomoże zapewnić wysoki stopień separacji i zredukować ilość kolizji. Jednak nie traktujcie zajętych węzłów jak tych, których NIE-MOŻNA przejść, ponieważ jednostki te nadal będą musiały przeciskać się przez wąskie przejścia (np. bramy), kiedy okaże się to konieczne. Ponadto, powinniście zastrzegać jedynie węzły w ścieżkach jednostek sąsiednich (a nie wszystkich) i tylko te z nich, które leżą na obecnej i przyszłych odcinkach ścieżek sąsiednich jednostek (lecz nie poprzednich, które zostały już odwiedzone).

3. Obsługa Nieodkrytych Terenów: Czy kiedykolwiek graliście z komputerem, który zawsze dokładnie wiedział jaką ścieżkę wybrać, nawet jeśli prowadziła ona przez nieodkryte jeszcze tereny? W zależności od gry, może się okazać, że zbyt dobre odnajdywanie ścieżki może będzie nierealistyczne. Na szczęście ten problem można zostać łatwo rozwiązany.

Odpowiedzią jest stworzenie oddzielnych tablic np. ”OznaczenieDostępnościPól” dla każdego z graczy i komputerowych przeciwników (każdego gracza, a nie jednostki – to zajęłoby znacznie więcej pamięci komputera). Każda z tablic będzie mapą zawierającą informacje o terenach odkrytych przez gracza, a reszta nieodkrytego terenu zostanie w niej zapamiętana jako taka, którą MOŻNA przejść, dopóki nie zostanie udowodnione co innego. Użycie tego rozwiązania, pozwoli jednostkom wchodzić w ślepe zaułki i dokonywać podobnych złych wyborów, do momentu odkrycia (odsłonięcia) właściwej drogi. Jednak, kiedy już mapa zostanie odkryta, algorytm odnajdywania ścieżki będzie działał normalnie.  

4. Ładniejsze Ścieżki: Algorytm A* dając najkrótsze i najszybsze (najmniej kosztowne) ścieżki, nie daje automatycznie ścieżek najbardziej wygładzonych (o najprostszej trasie, smuklejszych). Zwróćcie uwagę na ścieżkę wytyczoną w naszym przykładzie (Rysunek 7). Pierwszy krok jest w dół na prawo od pola startowego. Czyż nasza ścieżka nie byłaby ładniejsza, gdyby pierwszy krok kierował bezpośrednio w dół od pola startowego?

Jest kilka możliwości wyjścia z problemu. Kiedy wytyczacie ścieżkę, możecie wystrzegać się węzłów, które zmuszają do zmiany kierunku, dodając karne punkty do ich wartości G. Alternatywnie, możecie po wyznaczeniu ścieżki przebyć ją, poszukując miejsc, których sąsiednie węzły pozwoliłyby stworzyć ścieżkę wyglądającą lepiej. Więcej informacji na ten temat znajdziecie w Toward More Realistic Pathfinding – artykule (darmowym, lecz wymagającym rejestracji) w portalu Gamasutra.com autorstwa Marco Pinter’a.

5. Przestrzeń Poszukiwań Z Polami Niekwadratowymi: W naszym przykładzie użyliśmy prostej dwuwymiarowej siatki pól kwadratowych. Nie musicie stosować takiego podejścia; możecie użyć pól o nieregularnym kształcie. Pomyślcie o grze planszowej ”Risk” i krainach w niej występujących. Możecie obmyślić scenariusz odnajdywania ścieżki dla gier takich jak ta. Aby to zrobić, należy stworzyć tablicę przechowującą informację, które krainy przylegają do których, a wartość G należy uzależnić od przejścia z jednej krainy do drugiej. Będziecie także musieli zmodyfikować metodę wyznaczania wartości H. Wszystko inne powinno być obsłużone tak, jak w przytoczonym wyżej przykładzie. Zamiast używać przyległych pól, powinniście po prostu odnajdywać w tabeli przyległe krainy, kiedy dodajecie nowe pozycje do Listy Otwartych.

W podobny sposób możecie stworzyć siatkę punktów orientacyjnych (PO) dla ścieżek na mapie o ustalonym kształcie. PO są zwyczajnie położone na ścieżce, np. na drodze lub kluczowym tunelu w podziemiach. Jako twórcy gry możecie już na etapie projektowania mapy przypisać jej odpowiednie PO. Dwa PO powinny być uznane za sąsiednie (przyległe nawzajem do siebie), jeśli nie istnieje żadna przeszkoda na prostej linii ścieżki pomiędzy nimi. Jak w przykładzie gry ”Risk”, powinniście zachować informacje o sąsiedztwie PO w swojego rodzaju tablicy poszukiwań i wykorzystywać je podczas generowania pozycji na Liście otwartych. Powinniście także zachowywać przypisaną wartość G przejścia pomiędzy sąsiednimi PO (być może na podstawie dystansu w prostej linii między przypisanymi im węzłami) oraz przypisaną wartość H  dla wszystkich PO (być może na podstawie dystansu w prostej linii między przypisanym węzłem im węzłami a węzłem docelowym).

Amit Patel napisał artykuł opisujący kilka alternatyw. Inny przykład to odnajdywanie ścieżki na izometrycznej mapie RPG z niekwadratowymi polami w przestrzeni poszukiwań, który opisałem w artykule pt. Two-Tiered A* Pathfinding.

6. Kilka Porad Na Temat Prędkości: Kiedy już stworzycie swój własny program A* lub zaadaptujecie jeden z tu opisanych, możecie odkryć, że odnajdywanie ścieżki jest bardzo czasochłonne i zużywa sporą część czasu waszego procesora, szczególnie, jeśli macie sporą liczbę jednostek poszukujących ścieżek na dużej mapie. Jeśli czytaliście odpowiednie materiały w sieci, pewnie zauważyliście, że stanowi to problem także dla profesjonalistów, tworzących takie gry jak ”Starcraft” czy ”Age of Empires”. Jeśli zauważycie, że wszystko zaczyna zwalniać w trakcie poszukiwania ścieżek, spróbujcie wykorzystać kilka poniższych pomysłów przyspieszających działanie:

7. Działanie Listy Otwartych: To jeden z najbardziej czasochłonnych elementów algorytmu odnajdywania ścieżki A*. Za każdym razem, kiedy odwołujecie się do Listy Otwartych, musicie odnaleźć pole o najniższej wartości F. Jest kilka sposobów, by to uczynić. Możecie zapisywać elementy ścieżki wg kolejności ich występowania i zwyczajnie przeszukiwać całą listę, za każdym razem, kiedy potrzebujecie odnaleźć pole o najniższej wartości F. Ten sposób jest prosty, ale bardzo powolny dla długich ścieżek. Można go ulepszyć przez utrzymywanie listy posortowanej i proste pobieranie pierwszego elementu listy jako tego o najniższej wartości F. Kiedy pisałem mój program, to była pierwsza metoda której użyłem.

Takie rozwiązanie będzie działać stosunkowo dobrze dla małych map, lecz nie będzie najszybszym. Poważni programiści, chcący prawdziwej prędkości stosują coś co nazywa się ”stertą” (ang ”binary heap”) i tego właśnie użyłem w moim kodzie. Z mojego doświadczenia wynika, że to rozwiązanie będzie 2 do 3 razy szybsze w większości sytuacji, a szybkość rośnie geometrycznie (10 i więcej razy szybsze) dla dłuższych ścieżek. Jeśli macie motywację by dowiedzieć się więcej o stercie, sprawdźcie mój artykół pt: Using Binary Heaps in A* Pathfinding.

Następnym wąskim gardłem jest sposób w jaki czyścicie i utrzymujecie wasze struktury danych pomiędzy kolejnymi wywołaniami odnajdywania ścieżki. Osobiście preferuję przechowywanie wszystkiego w tablicach. Stwierdziłem, że gdy węzły są generowane, zapisywanie, utrzymywane i obsługiwane w dynamiczny i zorientowany obiektowo sposób, tworzenie i niszczenie takich obiektów, niepotrzebnie pochłania dość dużo czasu, spowalniając cały proces. Jednakże, jeśli użyjecie tablic, będziecie musieli czyścić ich elementy przed wywołaniem. W większości przypadków, ostatnią rzeczą jaką będziecie chcieli robić to marnowanie czasu na zerowanie wszystkiego, po wywołaniu odnajdywania ścieżki, szczególnie jeśli macie dużą mapę.

Unikam tego problemu przez czyszczenie dwuwymiarowej tablicy KtóraLita(X,Y) w której oznaczam węzły na mojej mapie, które znalazły się na Listach Otwartych i Zamkniętych. Po próbie odnajdywania ścieżki, nie zeruję tej tablicy. Zamiast tego, resetuję wartości ”naLiścieOtwartych” i ”naLiścieZamkniętych” w każdym wywołaniu odnajdywania ścieżki, zwiększając obie wartości o 5 lub podobną w każdej próbie odnajdywania ścieżki. W ten sposób algorytm może bezpiecznie ignorować (jako śmieci) wszystkie dane pozostałe z poprzedniego wywołania odnajdywania ścieżki. Takie wartości jak F, G i H również zapisuję w tablicach, ale w tym przypadku po prostu nadpisuje wszystkie pozostałe wartości i nie martwię się czyszczeniem tablic na końcu.

Przechowywanie danych w wielu tablicach pożera również dużo pamięci, więc musicie i to wziąć pod uwagę. Ostatecznie, powinniście użyć metody dla was najwygodniejszej.

8. Algorytm Dijkstr’y: O ile A* jest uznawany za najlepszy algorytm odnajdywania ścieżki (patrz opis powyżej), o tyle istnieje co najmniej jeden inny, często używany – algorytm Dijkstr’y. W istocie jest on taki sam jak A*, z tym wyjątkiem, że nie jest heurystyczny (H zawsze ma wartość 0). Ponieważ nie posiada heurystyki, poszukuje poprzez jednoczesną ekspansję we wszystkich kierunkach. Jak możecie sobie wyobrazić, z tego powodu ten algorytm zwykle kończy działanie po przeszukaniu znacznie większego obszaru niż A*, co generalnie czyni go wolniejszym.

Dlaczego więc go używać? Czasem nie wiemy gdzie znajduje się nasz punkt docelowy. Powiedzmy, że macie jednostkę zbierającą surowce, która musi iść zebrać trochę surowców jakiegoś rodzaju. Ona może wiedzieć gdzie są obszary poszczególnych surowców, ale chce dostać się do najbliższego. W tym przypadku algorytm Dijkstr’y jest lepszy od A*, ponieważ nie wiemy który z obszarów znajduje się najbliżej. Jedyną alternatywą byłoby wielokrotne użycie algorytmu A*, aby poznać dystans do każdego z obszarów i wtedy wybrać najkrótszą ścieżkę. Prawdopodobnie istnieje niezliczona ilość podobnych sytuacji, gdzie znamy rodzaj (cechy) lokacji, której poszukujemy i chcemy znaleźć najbliższą, ale nie wiemy gdzie jest lub która z wielu jest najbliższa.

Dodatki

OK, posiedliście już podstawy oraz znacie sens kilku zaawansowanych zagadnień i sposobów rozwiązań. W tym miejscu, sugeruję przebrnąć przez kody źródłowe mojego programu. Pakunek zawiera dwie wersje, jedna w C++ a druga w Blitz Basic’u. Obie wersje zostały opatrzone szczegółowymi komentarzami i powinny być stosunkowo łatwe do zrozumienia. Tu jest link: 

Jeśli nie macie dostępu do C++ lub Blitz Bazsic’a, możecie skorzystać z dwóch małych plików EXE, znajdujących się w katalogach wersji C++. Wersja w Blitz Basic’u działa pod darmową wersją demonstracyjną Blitz Basic 3D (nie Blitz Plus), możliwą do ściągnięcia na stronie Blitz Basic.

Powinniście także rozważyć przeczytanie poniższych stron internetowych. Teraz powinny być znacznie bardziej zrozumiałe.

Kilka innych stron wartych sprawdzenia:

Szczególnie rekomenduję poniższe książki, posiadające sporo artykułów nt. odnajdywania ścieżki i innych tematów sztucznej Inteligencji. Zawierają także CD-ROM’y z kodami źródłowymi przykładów. Posiadam je obie. Ponadto, jeśli kupicie je korzystając z tych linków, dostanę kilka groszy od Amazon :)

Powodzenia!