Praktyczne planowanie �cie�ki

W cz�ci 5 zobaczy�e�, jak agenci mog� wykorzystywa� wykresy nawigacyjne do planowania �cie�ek mi�dzy lokalizacjami w �rodowisku. Jednak je�li chodzi o wdro�enie tej teorii w praktyce, przekonasz si�, �e istnieje wiele r�nych problem�w do rozwi�zania, zanim agenci zaczn� si� przemieszcza� tak, jak chcesz. Tu om�wimu=y wiele praktycznych problem�w napotkanych podczas projektowania modu��w planowania �cie�ek agent�w gier. Chocia� wersje demonstracyjne w tym rozdziale s� oparte na frameworku Raven, wi�kszo�� technik ma zastosowanie w wielu r�nych gatunkach gier.

Budowa wykresu nawigacyjnego

Aby wyznaczy� �cie�k� od A do B za pomoc� algorytmu wyszukiwania, �rodowisko gry musi zosta� podzielone na struktury danych, kt�re algorytmy mog� eksplorowa�: wykres nawigacyjny. Poniewa� istnieje wiele sposob�w reprezentowania geometrii, kt�ra sk�ada si� na �wiat gry - na przyk�ad na podstawie kafelk�w, wektor�w lub wielok�t�w - trudno si� dziwi�, �e istnieje wiele metod przekszta�cania istotnych informacji przestrzennych w struktur� danych podobn� do wykresu. Przeanalizujmy kilka popularnych metod stosowanych we wsp�czesnych grach.

Na podstawie kafelk�w

Gry oparte na kafelkach lub kom�rkach, takie jak gry obficie wyst�puj�ce w gatunkach RTS i gier wojennych, maj� du�e, a czasem z�o�one �rodowisko oparte na kwadratach lub heksach. Dlatego sensowne jest zaprojektowanie wykresu nawigacyjnego gry wok� tych kom�rek: ka�dy w�ze� wykresu reprezentuje �rodek kom�rki, a kraw�dzie wykresu oznaczaj� po��czenia mi�dzy s�siednimi kom�rkami. W grach tego typu od czasu do czasu manewrowanie jednostk� gry - jak czo�g lub �o�nierz - b�dzie si� wi�za� z r�nymi rodzajami terenu. Woda i b�oto s� przecie� o wiele trudniejsze do pokonania przez zbiornik Shermana ni� asfalt lub ubita ziemia. Poniewa� ka�da kom�rka zwykle przypisuje okre�lony typ terenu przez projektanta mapy, u�ywanie tej informacji do wa�enia kraw�dzi wykresu nawigacyjnego jest trywialne. Algorytmy zastosowane do przeszukiwania wykresu mog� wykorzysta� te dodatkowe informacje do ustalenia odpowiednich �cie�ek przez teren, takich, kt�re unikaj� wody i b�ota lub omijaj� wzg�rza, a nie ich wierzcho�ki. Wad� u�ywania kom�rek jako szkieletu dla grafu nawigacyjnego jest to, �e przestrzenie wyszukiwania mog� szybko sta� si� bardzo du�e. Nawet skromna mapa kom�rkowa 100 x 100 b�dzie wymaga�a wykresu z�o�onego z maksymalnie 10 000 w�z��w i 78 000 (lub wi�cej) kraw�dzi. Bior�c pod uwag�, �e gry RTS zwykle maj� jednocze�nie kilkadziesi�t, a nawet setki jednostek AI, przy czym wiele z nich ��da przeszukiwania wykres�w na ka�dym etapie aktualizacji, to cholernie du�o do zrobienia, nie wspominaj�c o zwi�zanych z tym kosztach pami�ci . Na szcz�cie dost�pnych jest wiele metod zmniejszania obci��enia, kt�re om�wimy w dalszej cz�ci

Punkty widoczno�ci

Wykres nawigacyjny punkt�w widoczno�ci (POV) jest tworzony przez umieszczenie w�z��w wykresu, zwykle r�cznie, w wa�nych punktach �rodowiska, tak aby ka�dy w�ze� wykresu mia� lini� widzenia co najmniej jednego innego. Umieszczone ostro�nie w�z�y wykresu utworz� wykres ��cz�cy wszystkie wa�ne obszary w geometrii �wiata. Rysunek poni�szt pokazuje prosty wykres POV utworzony dla mapy Raven (Raven_DM1).

Jedn� z cech wykres�w POV jest to, �e mo�na je �atwo rozszerzy�, aby zawiera�y w�z�y, kt�re podaj� informacje ponad danymi dotycz�cymi ��czno�ci. Na przyk�ad, w�z�y mo�na �atwo doda� do wykresu POV, aby reprezentowa� dobre pozycje snajperskie, os�onowe lub zasadzkowe. Minusem jest to, �e je�li mapa gry jest du�a i z�o�ona, projektant mapy mo�e po�wi�ci� bardzo du�o cennego czasu na opracowanie pozycji i ulepszenie wykresu. Wykres POV mo�e by� r�wnie� problematyczny, je�li planujesz do��czy� dowolny rodzaj funkcji generowania mapy, poniewa� musisz tak�e opracowa� zautomatyzowan� metod� generowania struktury wykresu POV, aby nowe mapy by�y przydatne. (Dlatego niekt�re gry nie maj� funkcji losowego generowania map.) Jednym z rozwi�za� tego problemu jest jednak stosowanie technik rozszerzonej geometrii.

Rozszerzona geometria

Je�li �rodowisko gry jest zbudowane z wielok�t�w, mo�na wykorzysta� informacje zawarte w tych kszta�tach, aby automatycznie utworzy� wykres POV, kt�ry w przypadku du�ych map mo�e by� oszcz�dno�ci� czasu. Osi�ga si� to najpierw poprzez rozszerzenie wielok�t�w o wielko�� proporcjonaln� do promienia ograniczaj�cego agent�w gry. Patrz rysunki A i B.

Wierzcho�ki definiuj�ce t� rozszerzon� geometri� s� nast�pnie dodawane jako w�z�y do wykresu nawigacyjnego. Na koniec uruchamiany jest algorytm w celu sprawdzenia linii wzroku mi�dzy wierzcho�kami, a kraw�dzie s� odpowiednio dodawane do wykresu. Rysunek C pokazuje gotowy wykres nawigacyjny. Poniewa� wielok�ty s� powi�kszane o kwot� nie mniejsz� ni� agent w promieniu ograniczaj�cym agent mo�e przeszukiwa� wynikowy wykres nawigacyjny, aby tworzy� �cie�ki, kt�re bezpiecznie negocjuj� otoczenie bez wpadania na �ciany.

NavMesh

Jednym z podej��, kt�re zyskuje na popularno�ci w�r�d tw�rc�w gier, jest wykorzystanie sieci wypuk�ych wielok�t�w, zwanych navmesh, w celu opisania dost�pnych obszar�w gry. Wypuk�y wielok�t ma t� cenn� w�a�ciwo��, �e umo�liwia swobodne przemieszczanie si� z dowolnego punktu wielok�ta do dowolnego innego. Jest to przydatne, poniewa� umo�liwia reprezentacj� �rodowiska za pomoc� wykresu, na kt�rym ka�dy w�ze� reprezentuje przestrze� wypuk�� (zamiast punktu). Rysunek pokazuje map� z rysunku pierwszego *podzielon� na partycje w taki spos�b.

Dlaczego to dobra rzecz? C�, navmeshes s� wydajne. Struktura danych wymagana do przechowywania jednej jest zwarta i mo�na j� bardzo szybko przeszuka�. Ponadto tam, gdzie �rodowiska zbudowane s� w ca�o�ci z wielok�t�w - podobnie jak wi�kszo�� gier typu 3D FPS - mo�liwe jest u�ycie algorytm�w do automatycznego podzia�u obszar�w dost�pnych na mapach.

Wykres nawigacyjny Raven

Poniewa� daj� mi najwi�ksz� mo�liwo�� wykazania r�norodnego zakresu technik, wykresy nawigacyjne dla map Raven s� tworzone przy u�yciu metody POV. Widzia�e� wcze�niej, w jaki spos�b nawigator pokazany na rysunku pierwszym zosta� utworzony przez r�czne pozycjonowanie w�z��w w edytorze map. W tym przyk�adzie niewielka liczba w�z��w zosta�a umieszczona na wa�nych skrzy�owaniach. Poniewa� ka�dy w�ze� skutecznie reprezentuje du�y obszar przestrzenny, mo�na powiedzie�, �e ten typ wykresu jest gruboziarnisty (lub ziarnisty). Gruboziarniste wykresy s� bardzo zwartymi strukturami danych. U�ywaj� bardzo ma�o pami�ci i s� szybkie do wyszukiwania i stosunkowo �atwe do utworzenia, chocia� maj� kilka ogranicze�. Rzu�my okiem na niekt�re z ich wad.

Gruboziarniste wykresy

Je�li gra ogranicza tylko agent�w do poruszania si� wzd�u� kraw�dzi wykresu nawigacyjnego, takich jak ruch postaci w gamie gier Pac-Man, w�wczas gruboziarnisty navgraph to �wietny wyb�r. Je�li jednak projektujesz grafik dla gry, w kt�rej postacie maj� wi�ksz� swobod�, zgrubne wykresy mog� by� zwiastunem r�nego rodzaju problem�w. Na przyk�ad wi�kszo�� gier RTS / RPG korzysta z systemu sterowania, w kt�rym u�ytkownik mo�e rozkazywa� postaciom, aby przej�� do dowolnego nawigowanego obszaru mapy. Zwykle odbywa si� to za pomoc� kilku klikni�� myszk�, jednego, aby wybra� NPC, a drugiego, aby wybra� pozycj�, w kt�rej powinien si� przenie��. Aby przenie�� NPC do pozycji AI musi wykona� nast�puj�ce kroki:

1. Znajd� najbli�szy widoczny w�ze� wykresu do bie��cej lokalizacji NPC, powiedzmy, w�ze� A.
2. Znajd� najbli�szy widoczny w�ze� wykresu do docelowej lokalizacji, powiedzmy, w�ze� B.
3. U�yj algorytmu wyszukiwania, aby znale�� cie�k� o najni�szych kosztach od A do B.
4. Przenie� NPC do w�z�a A.

5. Przesu� NPC wzd�u� �cie�ki obliczonej w kroku 3.
6. Przenie� NPC z B do miejsca docelowego.
Je�li po tych krokach pojawi si� gruboziarnisty wykres, taki jak pokazany wcze�niej, nieestetyczne �cie�ki b�d� si� regularnie pojawia�. Niekt�re z tych za�ama� mo�na usun�� za pomoc� algorytmu wyg�adzania �cie�ki, takiego jak ten om�wiony w dalszej cz�ci tego rozdzia�u, ale ze wzgl�du na zgrubno�� wykresu nawigacyjnego nadal b�dzie wiele sytuacji, w kt�rych agent zygzakuje nienaturalnie na pocz�tku i na ko�cu punkty �cie�ki. Co gorsza, w przypadku korzystania z gruboziarnistych wykres�w prawie zawsze istnieje kilka pozycji na mapie, do kt�rych nie ma linii wzroku z �adnego z w�z��w wykresu, co skutecznie czyni te obszary niewidocznymi dla dowolnego planisty �cie�ki. Rysunek ilustruje dwie pozycje na mapie Raven_DM1, kt�re s� niedost�pne dla narz�dzia planowania �cie�ki.

Te "niewidoczne" obszary s� do�� atwe do wykrycia podczas testowania ma�ej mapy, ale s� znacznie trudniejsze do znalezienia wraz ze wzrostem z�o�ono�ci mapy. Znajduje to odzwierciedlenie w wielu grach, kt�re zosta�y wydane z takimi problemami. Mo�esz zaobserwowa� te problemy z pierwszej r�ki, uruchamiaj�c plik wykonywalny Raven_CoarseGraph. Po uruchomieniu demonstracji bot zbada �rodowisko, tworz�c �cie�ki do losowo wybranych w�z��w graficznych. Kliknij bota prawym przyciskiem myszy, aby go wybra�, a zobaczysz �cie�k�, kt�r� pod��a, pokazan� jako seri� czerwonych kropek. Zwr�� uwag�, jak ruch bota wygl�da dobrze, o ile utrzymuje si� na pozycjach na wykresie nawigacyjnym. Teraz ponownie kliknij prawym przyciskiem myszy bota, aby go "posi��". Po zdobyciu mo�esz klikn�� prawym przyciskiem myszy w dowolnym miejscu w �rodowisku, a bot spr�buje obliczy� �cie�k� do tego punktu (o ile punkt znajduje si� w obszarze �eglownym mapy). Obserwuj, jak bot musi cofa� si�, aby pod��a� pewnymi �cie�kami.

Drobnoziarniste wykresy

Z�e �cie�ki i niedost�pne pozycje mo�na poprawi�, zwi�kszaj�c ziarnisto�� wykresu nawigacyjnego. Rysunek poni�ej to przyk�ad bardzo drobno granulowanego wykresu utworzonego dla mapy Raven_DM1.

R�czne tworzenie takiego wykresu jest niezwykle �mudne, wi�c do wykonania wi�kszo�ci zada� edytor map wykorzystuje algorytm wype�niania zalania. Wi�cej informacji znajduje si� na poni�szym pasku bocznym. Poniewa� drobnoziarniste wykresy s� podobne w topologii do grafik nawigacyjnych opartych na kafelkach - i dlatego stanowi� podobne wyzwania dla programisty AI - wykorzystam je jako podstaw� do zademonstrowania technik opisanych w pozosta�ej cz�ci. W ten spos�b mam nadziej� zabi� kilka ptak�w jednym kamieniem, a pod koniec zrozumiesz, jak stworzy� agenta zdolnego do planowania �cie�ek w dowolnym �rodowisku gry, czy to FPS, RTS, czy RPG.

U�ywanie algorytmu Flood Fill do stworzenia wykresu nawigacyjnego

Aby u�y� algorytmu wype�niania zalania do utworzenia wykresu nawigacyjnego, najpierw gdzie� na mapie umieszczany jest pojedynczy w�ze� "zarodkowy". Patrz rysunek poni�ej, u g�ry w lewo. Algorytm "powi�ksza" wykres, rozszerzaj�c w�z�y i kraw�dzie na zewn�trz z nasion w ka�dym dost�pnym kierunku, a nast�pnie z w�z��w na skraju wykresu, a� do wype�nienia ca�ego obszaru �eglownego. Rysunek pokazuje pierwsze sze�� iteracji takiego procesu.

Jest to podobny rodzaj techniki malowania u�ywanej przez programy do wype�niania nieregularnych kszta�t�w, z wyj�tkiem tego, �e zamiast zalewa� kszta�t kolorem, edytor wykorzystuje algorytm do zalania mapy w�z�ami graficznymi i kraw�dziami. Poszczeg�lne w�z�y mog� by� nast�pnie przenoszone, usuwane lub dodawane przez projektanta w celu uzyskania po��danego rezultatu. Aby zapewni� nieograniczony ruch agenta, podczas procesu algorytm zapewnia, �e wszystkie w�z�y i kraw�dzie s� ustawione w minimalnej odleg�o�ci r�wnej promieniu ograniczaj�cemu agenta od �cian.

Dodawanie przedmiot�w do wykresu nawigacji Raven

Wi�kszo�� gier zawiera przedmioty, kt�re agent mo�e w jaki� spos�b odebra� i wykorzysta�. Te elementy mo�na dodawa� jako w�z�y do wykresu nawigacyjnego, umo�liwiaj�c sztucznej inteligencji planowania �cie�ki �atwe wyszukiwanie element�w i planowanie �cie�ek do nich. Tam, gdzie jest wiele instancji tego samego przedmiotu, sztuczna inteligencja mo�e u�y� nawigatora, aby szybko ustali�, kt�ry jest najmniej kosztowny do osi�gni�cia. Pami�tacie, jak w rozdziale 5 pokaza�em wam przyk�ad klasy w�z��w grafowych zaprojektowanej specjalnie do u�ytku z grafami nawigacyjnymi? Na wypadek gdyby twoja pami�� by�a tak s�aba jak moja, oto znowu lista:

template < class extra_info = void* >
class NavGraphNode : public GraphNode
{
protected:
// pozycja w�z�a
Vector2D m_vPosition;
// cz�sto chcesz, aby w�ze� navgraph zawiera� dodatkowe informacje.
// (na przyk�ad w�ze� mo�e reprezentowa� pozycj� typu elementu
// takie jak zdrowie, umo�liwiaj�c w ten spos�b algorytmowi wyszukiwania przeszukanie wykresu // dla tego typu elementu)
extra_info m_ExtraInfo;
public:
//ctors
NavGraphNode():m_ExtraInfo(extra_info()){}
NavGraphNode(int idx,
Vector2D pos):GraphNode(idx),
m_vPosition(pos),
m_ExtraInfo(extra_info())
{}
virtual ~NavGraphNode(){}
Vector2D Pos()const;
void SetPos(Vector2D NewPosition);
extra_info ExtraInfo()const;
void SetExtraInfo(extra_info info);
/* DODATKOWE SZCZEGӣY POMINI�TE */
};

Jest to klasa w�z��w u�ywana przez wykres nawigacyjny Raven. Jak wspomniano wcze�niej , typy przedmiot�w w Raven pochodz� z klasy Trigger. Po dodaniu wyzwalacza do mapy za pomoc� edytora map dodawany jest r�wnie� w�ze� wykresu. Cz�onek m_ExtraInfo tego w�z�a ma przypisany wska�nik do elementu, z kt�rym jest po��czony, umo�liwiaj�c w ten spos�b zmodyfikowanemu algorytmowi wyszukiwania zapytanie o wykres nawigacji dla okre�lonych typ�w element�w, a tak�e dla okre�lonych indeks�w w�z��w.

WSKAZ�WKA. Projektuj�c mapy niekt�rych gier, dobrze jest umie�ci� cz�sto u�ywane przedmioty, takie jak amunicja i zbroja, bezpo�rednio na najcz�ciej u�ywanych �cie�kach agent�w gry. Pomaga to agentom, poniewa� skupiaj� si� na wa�niejszych celach gry, zamiast biega� w poszukiwaniu broni i amunicji.

Korzystanie z partycjonowania przestrzennego w celu przyspieszenia zapyta� o blisko��

Jedn� z najcz�ciej u�ywanych metod klasy planowania �cie�ki jest funkcja, kt�ra okre�la najbli�szy widoczny w�ze� dla danej pozycji. Je�li to wyszukiwanie zostanie przeprowadzone przez iteracj� przez wszystkie w�z�y w celu znalezienia najbli�szego, wydajno�� nast�pi w czasie O (n2): Za ka�dym razem, gdy liczba w�z��w si� podwoi, czas potrzebny na ich przeszukanie zwi�ksza si� czterokrotnie. Jak widzieli�my w rozdziale 3, skuteczno�� takich wyszukiwa� mo�na poprawi�, stosuj�c technik� podzia�u przestrzennego, tak� jak podzia� na kom�rki, drzewa BSP, drzewa quad lub dowoln� z wielu dost�pnych metod. W przypadku wykres�w nawigacyjnych z kilkuset w�z��w podzia� przestrzenny daje radykalny wzrost pr�dko�ci, poniewa� czas wyszukiwania staje si� funkcj� g�sto�ci w�z��w, O (d), a nie liczb� w�z��w; i od g�sto�ci w�z��w na ca�ym obrazie nawigacyjnym wydaje si� by� do�� sp�jny, czas potrzebny na wykonanie zapytania o blisko�� w�z�a b�dzie sta�y. W zwi�zku z tym klasa Raven_Game dzieli na partycje w�z�y navgraph przy u�yciu metody przestrzeni kom�rkowej po za�adowaniu mapy.

UWAGA. Nie ma napisanego kodu dla tej cz�ci jako takiej. Wszystkie demonstracje zosta�y utworzone przez kompilacj� plik�w projektu Raven z w��czonymi lub wy��czonymi niekt�rymi opcjami, aby zademonstrowa� ka�d� omawian� technik�. Z tego powodu dema u�ywaj� skompilowanych plik�w skryptowych Lua, aby zapobiec manipulowaniu przy opcjach, kt�re mog� spowodowa� awari� demonstracji. Aby uzyska� pe�ne prawa do kr�cenia si�, skompiluj w�a�ciwy projekt Raven!

Tworzenie klasy PathPlanner

Wi�kszo�� pozosta�ej cz�ci tekstu zostanie wydana po opracowaniu klasy planowania �cie�ki zdolnej do wykonywania i zarz�dzania licznymi ��daniami wyszukiwania graf�w wymaganych przez bota Raven. Ta klasa nazywa si� Raven_PathPlanner i ka�dy bot b�dzie mia� jej instancj�. Klasa zacznie si� w prosty spos�b, ale w miar� post�p�w jej mo�liwo�ci b�d� stopniowo rozszerzane, daj�c mo�liwo�� zademonstrowania, jak rozwi�za� wiele typowych problem�w napotkanych podczas opracowywania sztucznej inteligencji planowania �cie�ki. Najpierw rozwa�my minimaln� funkcjonalno��, jak� musi zapewni� obiekt planowania �cie�ki. Bot Raven przynajmniej powinien by� w stanie zaplanowa� �cie�k� z aktualnej pozycji do dowolnej innej lokalizacji, bior�c pod uwag�, �e obie pozycje s� prawid�owe i mo�liwe do nawigacji, a �cie�ka jest mo�liwa. Bot Raven powinien tak�e by� w stanie zaplanowa� �cie�k� o najni�szym koszcie mi�dzy swoj� obecn� pozycj� a okre�lonym typem przedmiotu, takim jak pakiet zdrowia. W rezultacie klasa planowania �cie�ki musi mie� metody przeszukiwania navgraph w poszukiwaniu takich �cie�ek i uzyskiwania dost�pu do wynikowych danych �cie�ki. Maj�c na uwadze te funkcje, spr�bujmy najpierw w klasie planowania �cie�ki.

class Raven_PathPlanner
{
private:
// dla czytelno�ci
enum {no_closest_node_found = -1};
private:
// Wska�nik do w�a�ciciela tej klasy
Raven_Bot* m_pOwner;
// lokalne odniesienie do navgraph
const Raven_Map::NavGraph& m_NavGraph;
//to jest pozycja, kt�r� bot chce zaplanowa� �cie�k� do osi�gni�cia
Vector2D m_vDestinationPos;
// zwraca indeks najbli�szego widocznego i niezak��conego w�z�a graficznego do
// podana pozycja. Je�li nie zostanie znaleziony, zwraca wyliczon� warto��
// "no_closest_node_found"
int GetClosestNodeToPosition(Vector2D pos)const;
public:
Raven_PathPlanner(Raven_Bot* owner);
// znajduje �cie�k� o najni�szym koszcie mi�dzy pozycj� agenta a celem
//pozycja. Wype�nia �cie�k� list� punkt�w, je�li wyszukiwanie zako�czy si� powodzeniem
// i zwraca true. Zwraca false, je�li nie powiedzie si� bool CreatePathToPosition(Vector2D TargetPos, std::list& path);
// znajduje �cie�k� o najni�szym koszcie do wyst�pienia klasy ItemType. Wype�nia �cie�k� znakiem // lista punkt�w, je�li wyszukiwanie zako�czy si� powodzeniem i zwr�ci warto�� true. Zwraca
// false, je�li si� nie powiedzie bool CreatePathToItem(unsigned int ItemType, std::list& path);
};

Ta klasa zapewnia minimaln� funkcjonalno�� wymagan� przez agenta gry. Przyjrzyjmy si� bli�ej metodom tworz�cym �cie�ki.

Planowanie �cie�ki do pozycji

Planowanie �cie�ki z bie��cej lokalizacji bota do miejsca docelowego jest proste. Planista �cie�ki musi:
1. Znajd� najbli�szy widoczny niezak��cony w�ze� grafowy do bie��cej lokalizacji bota.
2. Znajd� najbli�szy widoczny niezak��cony w�ze� wykresu do lokalizacji docelowej.
3. U�yj algorytmu wyszukiwania, aby znale�� cie�k� najmniejszych koszt�w mi�dzy nimi.

Poni�szy kod u�ywa tych krok�w. Komentarze powinny by� odpowiednim wyja�nieniem.

bool Raven_PathPlanner::CreatePathToPosition(Vector2D TargetPos,
std::list& path)
{
// zanotuj pozycj� docelow�
m_vDestinationPos = TargetPos;
// je�li cel nie jest zas�oni�ty od pozycji bota, �cie�ka nie potrzebuje
// do obliczenia, a bot mo�e PRZYBY� bezpo�rednio w miejscu docelowym.
// isPathObstructed to metoda, kt�ra zaczyna si� od pocz�tku // pozycja, pozycja docelowa i promie� encji i okre�la, czy
// agent tego rozmiaru jest w stanie porusza� si� bez przeszk�d mi�dzy dwiema pozycjami.
// S�u�y tutaj do ustalenia, czy bot mo�e przej�� bezpo�rednio do celu
// lokalizacja bez potrzeby planowania �cie�ki.
if (!m_pOwner()->GetWorld()->isPathObstructed(m_pOwner->Pos(),
TargetPos,
m_pOwner->BRadius()))
{
path.push_back(TargetPos);
return true;
}
// znajd� najbli�szy niezak��cony w�ze� w pozycji bota.
// GetClosestNodeToPosition to metoda odpytuj�ca wykres nawigacyjny
// w�z�y (przez partycj� przestrze� kom�rkowa), aby okre�li� najbli�sz� niezak��con�
// w�ze� do podanego wektora pozycji. S�u�y tutaj do znalezienia najbli�szego zdj�cia // niezak��cony w�ze� do bie��cej lokalizacji bota.
int ClosestNodeToBot = GetClosestNodeToPosition(m_pOwner->Pos());
// je�li nie znaleziono widocznego w�z�a, zwr�� b��d. Nast�pi to, je�li
// navgraph jest �le zaprojektowany lub je�li botowi uda�o si� zdoby� // * wewn�trz * geometrii (otoczonej �cianami) lub przeszkody.
if (ClosestNodeToBot == no_closest_node_found)
{
return false;
}
// znajd� najbli�szy widoczny niezak��cony w�ze� do pozycji docelowej
int ClosestNodeToTarget = GetClosestNodeToPosition(TargetPos);
// zwr�cenie b��du, je�li wyst�puje problem ze zlokalizowaniem widocznego w�z�a z poziomu //cel.
// Tego rodzaju rzeczy wyst�puj� znacznie cz�ciej ni� powy�sze. Dla
// przyk�ad, je�li u�ytkownik kliknie wewn�trz obszaru ograniczonego �cianami lub wewn�trz zdj�cia //obiekt.
if (ClosestNodeToTarget == no_closest_node_found)
{
return false;
}
// utw�rz instancj� klasy wyszukiwania A *, aby wyszuka� �cie�k� mi�dzy
// najbli�szy w�ze� do bota i najbli�szy w�ze� do pozycji docelowej. To
// Wyszukiwanie * b�dzie wykorzystywa� heurystyczn� lini� euklidesow�
typedef Graph_SearchAStar< Raven_Map::NavGraph, Heuristic_Euclid> AStar;
AStar search(m_NavGraph,
ClosestNodeToBot,
ClosestNodeToTarget);
// z�ap �cie�k�
std::list PathOfNodeIndices = search.GetPathToTarget();
// je�li wyszukiwanie si� powiedzie, zamie� indeksy w�z��w na wektory pozycji
if (!PathOfNodeIndices.empty())
{
ConvertIndicesToVectors(PathOfNodeIndices, path);
// pami�taj, aby doda� pozycj� docelow� na ko�cu �cie�ki
path.push_back(TargetPos);
return true;
}
else
{
// nie znaleziono �cie�ki podczas wyszukiwania
return false;
}
}

Planowanie �cie�ki do typu elementu

Jest lepszym algorytmem do wyszukiwania �cie�ki o najni�szym koszcie od aktualnej pozycji bota do konkretnej pozycji docelowej, ale co z tym, kiedy wymagana jest �cie�ka o najni�szych kosztach do typu przedmiotu - takiego jak wyrzutnia rakiet - gdzie mo�e by� wiele wyst�pienia w �rodowisku okre�lonego typu? Aby obliczy� koszt heurystyczny podczas wyszukiwania A*, algorytm musi mie� zar�wno pozycj� �r�d�ow�, jak i docelow�. W zwi�zku z tym, u�ywaj�c A* do wyszukiwania najbli�szej instancji typu przedmiotu, wyszukiwanie musi zosta� zako�czone dla ka�dej instancji obecnej w �wiecie gry, zanim ta o najni�szej cenie b�dzie mog�a zosta� wybrana jako najlepsza pozycja do przej�cia. Jest to w porz�dku, je�li twoja mapa zawiera tylko gar�� instancji przedmiotu, ale co, je�li zawiera wiele? W ko�cu �rodowiska gier RTS cz�sto zawieraj� dziesi�tki, a nawet setki instancji zasob�w, takich jak drzewa lub z�oto. Oznacza to, �e konieczne b�dzie przeprowadzenie wielu wyszukiwa� A* w celu zlokalizowania tylko jednego elementu. To nie jest dobre. Gdy wyst�puje wiele podobnych typ�w przedmiot�w, algorytm Dijkstry jest lepszym wyborem. Jak si� dowiedzia�e�, algorytm Dijkstry "wyrasta" najkr�tsz� �cie�k� na zewn�trz od w�z�a g��wnego do momentu osi�gni�cia celu lub zbadania ca�ego wykresu. Gdy tylko szukany element zostanie znaleziony, algorytm zako�czy si�, a SPT b�dzie zawiera� �cie�k� od katalogu g��wnego do najbli�szego elementu po��danego typu. Innymi s�owy, bez wzgl�du na to, ile wyst�pie� typu przedmiotu wyst�puje w �wiecie gry, algorytm Dijkstry musi zosta� uruchomiony tylko raz, aby znale�� cie�k� najmniejszego kosztu do jednego z nich. W obecnej postaci klasa algorytm�w Dijkstry u�ywana do tej pory w ta ksi��ka zako�czy si� dopiero po znalezieniu okre�lonego indeksu w�z��w. W rezultacie kod musi zosta� zmieniony, aby wyszukiwanie zako�czy�o si� po lokalizacji aktywnego typu elementu (wyzwalacza). Mo�na to �atwo osi�gn��, okre�laj�c jako parametr szablonu polityka stanowi warunek zako�czenia. Na przyk�ad:

template < class graph_type, class termination_condition >
class Graph_SearchDijkstra
{
/* POMINI�TE */
};
Polityka warunk�w zako�czenia jest klas� zawieraj�c� pojedyncz� metod� statyczn� isSatisfied, kt�ra zwraca warto�� true, je�li warunki wymagane do zako�czenia s� spe�nione. Podpis isSatisfied wygl�da nast�puj�co:

static bool isSatisfied (const graph_type & G, int target, int CurrentNodeIdx);

Zmodyfikowany algorytm Dijkstry mo�e korzysta� z takich zasad, aby okre�li�, kiedy nale�y zako�czy� wyszukiwanie. Aby to u�atwi�, linia:

// je�li cel zosta� znaleziony, wyjd�
if (NextClosestNode == m_iTarget) return;
found in Graph_SearchDijkstra::Search is replaced with:
// je�li cel zosta� znaleziony, wyjd�
if (termination_condition::isSatisfied(m_Graph,
m_iTarget,
NextClosestNode))
{
// zanotuj indeks w�z�a, kt�ry spe�ni� warunek. To
// jest tak, �e mo�emy pracowa� wstecz od indeksu, aby wyodr�bni� �cie�k� z
// najkr�tsza �cie�ka.
m_iTarget = NextClosestNode;
return;
}

Jednak zanim ten dostosowany algorytm b�dzie m�g� by� u�yty, nale�y stworzy� odpowiedni� polityk� warunk�w zako�czenia. W Raven typy przedmiot�w s� reprezentowane przez wyzwalacze dawc�w. Dlatego podczas wyszukiwania typu elementu wyszukiwanie powinno zako�czy� si�, gdy zostanie zlokalizowany w�ze� wykresu, kt�rego pole m_ExtraInfo wskazuje na aktywny wyzwalacz odpowiedniego typu. Oto klasa zasad warunku zako�czenia, kt�ra ko�czy wyszukiwanie na podstawie tych kryteri�w:

template < class trigger_type >
class FindActiveTrigger
{
public:
template
static bool isSatisfied(const graph_type& G, int target, int CurrentNodeIdx)
{
bool bSatisfied = false;
// uzyska� odwo�anie do w�z�a o podanym indeksie w�z��w
const graph_type::NodeType& node = G.GetNode(CurrentNodeIdx);
// je�li dodatkowe pole informacyjne wskazuje na wyzwalacz dawcy, sprawd�, aby si� upewni�, �e
// jest aktywny i �e jest poprawnego typu.
if ((node.ExtraInfo() != NULL) &&
node.ExtraInfo()->isActive() &&
(node.ExtraInfo()->EntityType() == target) )
{
bSatisfied = true;
}
return bSatisfied;
}
};

Uzbrojeni w ten warunek zako�czenia i dostosowany algorytm wyszukiwania Dijkstra �atwo jest znale�� cie�k� o najni�szym koszcie do aktywnego elementu okre�lonego typu. Powiedzmy, �e chcesz znale�� najbli�sz� paczk� zdrowia dla w�z�a grafu z indeksem 6. Oto jak:

typedef FindActiveTrigger > term_con;
typedef Graph_SearchDijkstra_TS SearchDij;
// utworzy� wyszukiwanie
SearchDij dij(G, //wykres6, //w�ze� �r�d�owy
type_health); // typ przedmiotu, kt�rego szukamy
// z�ap �cie�k�
std::list path = dij.GetPathToTarget();
gdzie type_health jest warto�ci� wyliczon�

UWAGA 3D. Mam nadziej�, �e rozumiesz, �e nie ma r�nicy mi�dzy wyszukiwaniem �cie�ek w 3D a wyszukiwaniem �cie�ek w 2D. Oczywi�cie, aby agent m�g� porusza� si� w wi�kszo�ci �rodowisk 3D, musia�by wykonywa� takie czynno�ci jak skakanie w�wozami i korzystanie z wind, ale te rozwa�ania powinny by� przejrzyste dla planisty �cie�ki. Po prostu manifestuj� si� jako korekty koszt�w brzegowych, dzi�ki czemu algorytm wyszukiwania mo�e uwzgl�dni� koszt wykonania skoku, przej�cia przez p�k�, u�ycia windy lub zrobienia czegokolwiek, gdy szuka �cie�ki o najni�szym koszcie do pozycji docelowej. Je�li nadal nie jest to oczywiste, zdecydowanie zalecamy cofni�cie si� i ponowne przeczytanie cz�ci 5, pami�taj�c, �e wykres mo�e istnie� w dowolnej liczbie wymiar�w.

�cie�ki jako w�z�y czy �cie�ki jako kraw�dzie?

Do tej pory my�leli�my o �cie�kach jako serii wektor�w pozycji lub punkt�w trasy. Cz�sto �cie�ki sk�adaj�ce si� z kraw�dzi wykresu zapewniaj� programistom AI dodatkow� elastyczno��. Jako przyk�ad we�my gr� z postaciami niezale�nymi, w kt�rych ruch mi�dzy punktami w otoczeniu musi by� ograniczony do okre�lonego typu, np. "Palcami tutaj", "czo�ga� si� tutaj" lub "biega� szybko tutaj". Mo�esz pomy�le�, �e odpowiednie w�z�y navgraph gry mog� by� opatrzone adnotacjami z flagami wskazuj�cymi po��dane zachowanie (na przyk�ad, w�ze� mo�e by� oznaczony zachowaniem "palc�w", aby agent zacz�� palcami, jak tylko dotrze do tego w�z�a), ale w �wiczy�, istniej� problemy z tym podej�ciem. Na przyk�ad ryc. 8.10 pokazuje cz�� wykresu nawigacyjnego, w kt�rym jedna z kraw�dzi A - B przecina rzek�.

Projekt gry wymaga, aby agenci zmienili si� na zachowanie "p�ywania" podczas podr�y z A do B (lub odwrotnie), wi�c w�z�y A i B s� opatrzone adnotacjami, aby to odzwierciedli�. Powiedzmy, �e agent pod��a �cie�k� e - A - B - h. Gdy agent dotrze do w�z�a A, jego zachowanie zmieni si� na p�ywanie i mo�e bezpiecznie przekroczy� kraw�d� do B. Jak dot�d tak dobrze, ale niestety w tym momencie ma problemy. Kiedy osi�gnie w�ze� B, kt�ry r�wnie� jest opatrzony adnotacj� o zachowaniu podczas p�ywania, b�dzie kontynuowa� p�ywanie wzd�u� kraw�dzi B - h. Niedobrze. Je�li to nie wystarczy, powiedzmy, �e agent chce pod��a� �cie�k� e - A - c. Jak tylko osi�gnie A, zacznie p�ywa�, mimo �e nie zamierza przekracza� rzeki!

Problem ten mo�na jednak �atwo rozwi�za�, je�li kraw�dzie wykresu s� opatrzone adnotacjami zamiast w�z��w. W ten spos�b agent mo�e �atwo zapyta� o informacje brzegowe, pod��aj�c �cie�k� i odpowiednio zmieni� zachowanie. Bior�c pod uwag� poprzedni przyk�ad, oznacza to, �e kraw�d� A - B jest opatrzona instrukcj� p�ywania, a wszystkie pozosta�e kraw�dzie instrukcj� chodzenia (lub cokolwiek innego, co mo�e by� odpowiednie). Teraz, gdy agent pod��y �cie�k� e - A - B - h, jego ruch b�dzie prawid�owy.
v WSKAZ�WKA. Za pomoc� adnotacji mo�na �atwo okre�li� zachowanie kraw�dzi, kt�re jest modyfikowane podczas gry. Na przyk�ad, mo�esz zaprojektowa� map�, kt�ra ma prowizoryczny most - jak spadaj�cy k��d - przechodz�cy przez strumie�, kt�ry agenci przechodz� normalnie, dop�ki most nie zostanie zniszczony lub przeniesiony. Po zdj�ciu mostu adnotacja na kraw�dzi zmienia si� na "p�ywanie", a jej koszt wzrasta, aby odzwierciedli� dodatkow� ilo�� czasu potrzebn� do poruszania si� wzd�u� niej. W ten spos�b agenci nadal bior� pod uwag� kraw�d� podczas planowania �cie�ek i odpowiednio zmodyfikuj� swoj� animacj�, gdy j� przechodz�. (Mo�na nawet usun�� / wy��czy� kraw�d�, aby przedstawi� warunki uniemo�liwiaj�ce przep�yw strumienia, takie jak pow�d�).

Adnotowany przyk�ad klasy kraw�dzi

Adnotowan� kraw�d� mo�na �atwo utworzy�, wywodz�c z GraphEdge i dodaj�c dodatkowy element danych do reprezentowania flagi (lub flag, w zale�no�ci od tego, jakie informacje chcesz reprezentowa� kraw�d�). Oto przyk�ad:

class NavGraphEdge : public GraphEdge
{
public:
// wyliczy� niekt�re flagi zachowania
enum BehaviorType
{
normal = 1 << 0,
tippy_toe = 1 << 1,
swim = 1 << 2,
crawl = 1 << 3,
creep = 1 << 4
};
protected:
// zachowanie zwi�zane z przechodzeniem przez t� kraw�d�
BehaviorType m_iBehavior;
/* DODATKOWE SZCZEGӣY POMINI�TE */
};

WSKAZ�WKA. Je�li tw�j projekt gry wymaga adnotacji kraw�dzi i / lub w�z�a, cz�sto oka�e si�, �e dodatkowe pola w klasach w�z��w / kraw�dzi s� nieu�ywane (lub ustawione na "normalne") w wi�kszo�ci przypadk�w w grafie nawigacyjnym. Mo�e to by� znaczne marnotrawstwo pami�ci, je�li wykres jest du�y. W takich przypadkach zalecam u�ycie tabeli odno�nik�w typu mapy skr�t�w lub, w przypadku du�ej ilo�ci adnotacji na instancj�, utworzenie specjalnej struktury danych, do kt�rej ka�da kraw�d� lub w�ze� mo�e przechowywa� wska�nik.

Modyfikowanie klasy Planowanie �cie�ki w celu dostosowania kraw�dzi z adnotacjami

Aby uwzgl�dni� adnotacje na kraw�dziach, nale�y zmodyfikowa� klasy planera �cie�ki i algorytmu wyszukiwania, aby zwraca�y �cie�ki zawieraj�ce dodatkowe informacje. Aby to u�atwi�, Raven korzysta z klasy PathEdge - prostej struktury danych, kt�ra przechowuje informacje o po�o�eniu w�z�a i adnotacjach na kraw�dzi. Oto jego listing:

class PathEdge
{
private:
// pozycje w�z��w �r�d�owego i docelowego, kt�re ��czy ta kraw�d�
Vector2D m_vSource;
Vector2D m_vDestination;
// zachowanie zwi�zane z przechodzeniem przez t� kraw�d�
int m_iBehavior;
public:
PathEdge(Vector2D Source,
Vector2D Destination,
int Behavior):m_vSource(Source),
m_vDestination(Destination),
m_iBehavior(Behavior)
{}
Vector2D Destination()const;
void SetDestination(Vector2D NewDest);
Vector2D Source()const;
void SetSource(Vector2D NewSource);
int Behavior()const;
};

Metody Raven_PathPlanner :: CreatePath i odpowiadaj�ce im algorytmy wyszukiwania zosta�y nieznacznie zmienione, aby utworzy� std :: list PathEdges. Oto lista zmodyfikowanej metody CreatePathToPosition

bool Raven_PathPlanner::CreatePathToPosition(Vector2D TargetPos,
std::list& path)
{
// je�li cel nie jest zas�oni�ty od pozycji bota, �cie�ka nie potrzebuje
// do obliczenia, a bot mo�e PRZYBY� bezpo�rednio w miejscu docelowym.
if (!m_pOwner()->GetWorld()->isPathObstructed(m_pOwner->Pos(),
TargetPos,
m_pOwner->BRadius()))
{
// stw�rz kraw�d� ��cz�c� aktualn� pozycj� bota i
// pozycja docelowa i wci�nij j� na list� �cie�ek (oflagowany, aby u�y�
// "normalne" zachowanie)
path.push_back(PathEdge(m_pOwner->Pos(), TargetPos, NavGraphEdge::normal));
return true;
}
// znajd� najbli�szy niezak��cony w�ze� w pozycji bota.
int ClosestNodeToBot = GetClosestNodeToPosition(m_pOwner->Pos());
if (ClosestNodeToBot == no_closest_node_found)
{
// �adna �cie�ka nie jest mo�liwa
return false;
}
// znajd� najbli�szy widoczny niezak��cony w�ze� do pozycji docelowej
int ClosestNodeToTarget = GetClosestNodeToPosition(TargetPos);
if (ClosestNodeToTarget == no_closest_node_found)
{
// �adna �cie�ka nie jest mo�liwa
return false;
}
// utw�rz instancj� klasy wyszukiwania A*.
typedef Graph_SearchAStar AStar;
AStar search(m_NavGraph, ClosestNodeToBot, ClosestNodeToTarget);
// chwy� �cie�k� jako list� PathEdges
path = search.GetPathAsPathEdges();
// je�li wyszukiwanie zako�czy�o si� pomy�lnie, dodaj pierwsz� i ostatni� kraw�d� r�cznie do
// �cie�ka
if (!path.empty())
{
path.push_front(PathEdge(m_pOwner->Pos(),
path.front().GetSource(),
NavGraphEdge::normal));
path.push_back(PathEdge(path.back().GetDestination(),
TargetPos,
NavGraphEdge::normal));
return true;
}
else
{
// nie znaleziono �cie�ki podczas wyszukiwania
return false;
}
}

Bot mo�e teraz �atwo sprawdza� adnotacje na kraw�dziach �cie�ek i wprowadza� odpowiednie zmiany w zachowaniu. W pseudokodzie za ka�dym razem, gdy bot wysuwa now� kraw�d� listy, robi co� takiego:

if (Bot.PathPlanner.CreatePathToPosition(destination, path))
{
PathEdge next = GetNextEdgeFromPath(path)
switch(next.Behavior)
{
case behavior_stealth:
set stealth mode
break
case behavior_swim
set swim mode
break
etc
}
Bot.MoveTo(NavGraph.GetNodePosition(next.To))
}

Od tego momentu mo�esz za�o�y�, �e wszelkie wersje demonstracyjne korzystaj�ce ze struktury Raven b�d� u�ywa� �cie�ek kraw�dzi zamiast �cie�ek punkt�w drogi.

WSKAZ�WKA . Niekt�re �wiaty gry zawieraj� teleportery lub "portale", kt�rych agenci mog� u�ywa� do magicznego i natychmiastowego przemieszczania si� mi�dzy lokalizacjami. Je�li Twoja gra korzysta z takich urz�dze�, nie b�dziesz w stanie u�y� algorytmu wyszukiwania A * do dok�adnego planowania �cie�ek, poniewa� nie jest mo�liwe dostosowanie ich do heurystyki. Zamiast tego musisz u�y� alternatywnego algorytmu wyszukiwania, takiego jak Dijkstra.

Wyg�adzanie �cie�ki

Do�� cz�sto, a zw�aszcza je�li wykres nawigacyjny gry ma kszta�t siatki, �cie�ki utworzone przez planer �cie�ek zawieraj� zwykle niepotrzebne kraw�dzie, powoduj�c za�amania, takie jak te pokazane na rysunku 8.11. Wygl�daj� nienaturalnie dla ludzkiego oka - w ko�cu cz�owiek nie robi�by tak niepotrzebnie takiego zygzaka, wi�c �le wygl�da, gdy robi to agent gry. (Oczywi�cie jest to ca�kowicie do przyj�cia, je�li modelujesz koty domowe, kt�re wydaj� si� mie� sw�j w�asny tajny program podczas przej�cia z A do B.)

Korzystaj�c z A* i nawigatora opartego na siatce, mo�na tworzy� lepiej wygl�daj�ce �cie�ki za pomoc� heurystycznej odleg�o�ci na Manhattanie w po��czeniu z funkcj�, kt�ra karze ka�d� zmian� kierunku. (Pami�taj, �e odleg�o�� na Manhattanie to suma liczby kafelk�w przesuni�tych poziomo i pionowo mi�dzy rozwa�anymi w�z�ami.) Jednak wytworzone �cie�ki wci�� s� dalekie od idea�u ze wzgl�du na topologi� wykresu ograniczaj�c� skr�ty do przyrost�w 45 stopni. Ta metoda r�wnie� nie dzia�a z innym powszechnym problemem. Jak widzieli�my, zanim planista �cie�ki b�dzie m�g� wyszuka� �cie�k�, musi znale�� w�z�y wykresu najbli�sze pozycjom pocz�tkowym i docelowym, i nie zawsze b�d� to te, kt�re daj� naturalnie wygl�daj�c� �cie�k�. Rozwi�zanie dla obu tych problem�w to przetwarzanie �cie�ek ko�cowych w celu "wyg�adzenia" niepo��danych za�ama�. Jest na to kilka metod - jedna zgrubna i jedna precyzyjna.

Wyg�adzanie �cie�ki Szorstkie, ale szybkie

Stosunkowo szybka metoda wyg�adzania �cie�ki polega na sprawdzeniu "przejezdno�ci" mi�dzy s�siednimi kraw�dziami. Je�li jedna z kraw�dzi jest zbyteczna, dwie kraw�dzie s� zast�powane jedn�.

Algorytm dzia�a w nast�puj�cy spos�b: po pierwsze, dwa iteratory, E1 i E2, s� umieszczone odpowiednio na pierwszej i drugiej kraw�dzi �cie�ki. Nast�pnie wykonuje si� nast�puj�ce kroki:

1. Chwy� pozycj� �r�d�ow� E1.
2. Chwy� pozycj� docelow� E2.
3. Je�li agent mo�e porusza� si� mi�dzy tymi dwoma pozycjami bez przeszk�d przez geometri� �wiata, przypisz miejsce docelowe E1 do miejsca docelowego E2 i usu� E2 ze �cie�ki. Ponownie przypisz E2 do nowej kraw�dzi po E1. (Nale�y pami�ta�, �e nie jest to prosty test pola widzenia, poniewa� nale�y wzi�� pod uwag� rozmiar bytu - musi on by� w stanie porusza� si� mi�dzy dwiema pozycjami bez uderzania w �ciany).
4. Je�li agent nie mo�e porusza� si� bez przeszk�d mi�dzy dwiema pozycjami, przypisz E2 do E1 i przejd� do E2.
5. Powtarzaj kroki, a� miejsce docelowe E2 b�dzie r�wne miejscu docelowemu �cie�ki.

Zobaczmy, jak dzia�a ten algorytm i wyg�adzamy �cie�k� pokazan� na rysunku 8.13. Najpierw E1 jest skierowany na pierwsz� kraw�d� �cie�ki, a E2 na drug�.

E1 jest kraw�dzi� S - 1, a E2 kraw�dzi� 1 - 2. Widzimy, �e agent mo�e porusza� si� bez przeszk�d mi�dzy E1-> �r�d�o (S) i E2-> Miejsce docelowe (2), wi�c pozycja indeksu w�z�a 2 wynosi przypisany do E1-> Miejsce docelowe, kraw�d� 1-2 jest usuwana ze �cie�ki, a E2 jest wysuwany, aby wskazywa� na kraw�d� 2-3. (Zwr�� uwag�, �e kraw�d� wskazywana przez E1 ��czy teraz S - 2.)

Po raz kolejny widzimy, �e agent jest w stanie porusza� si� bez przeszk�d mi�dzy E1-> �r�d�o (S) i E2-> Miejsce docelowe (3), wi�c ponownie �cie�ka i iteratory s� aktualizowane, daj�c sytuacj� pokazan� na rysunku

Tym razem jednak pozycje E1-> �r�d�o (S) i E2-> Miejsce docelowe (4) s� zablokowane. Dlatego oba E1 i E2 s� zaawansowane o jedn� kraw�d�.

Ponownie, �cie�ka mi�dzy w�z�ami 3 i 5 jest zablokowana, wi�c E1 i E2 s� zaawansowane. Tym razem, poniewa� �cie�ka mi�dzy 4 a T jest przejezdna, kraw�dzie s� aktualizowane, aby to odzwierciedli�, daj�c ostateczn� wyg�adzon� �cie�k� pokazan� na rysunku.

Kod �r�d�owy do wyg�adzenia �cie�ki przy u�yciu tego algorytmu wygl�da nast�puj�co:

void Raven_PathPlanner::SmoothPathEdgesQuick(std::list< PathEdge >& path)
{
// utw�rz kilka iterator�w i skieruj je na prz�d �cie�ki
std::list::iterator e1(path.begin()), e2(path.begin());
// przyrost e2, tak aby wskazywa� na kraw�d� po e1.
++e2;
// podczas gdy e2 nie jest ostatni� kraw�dzi� na �cie�ce, przejd� przez kraw�dzie, sprawdzaj�c
// aby sprawdzi�, czy agent mo�e porusza� si� bez przeszk�d z w�z�a �r�d�owego
// e1 do w�z�a docelowego e2. Je�li agent mo�e porusza� si� mi�dzy nimi // pozycje, w�wczas dwie kraw�dzie s� zast�powane jedn� kraw�dzi�.
while (e2 != path.end())
{
// sprawd�, czy nie ma przeszk�d, odpowiednio wyreguluj i usu� kraw�dzie
if ( m_pOwner->canWalkBetween(e1->Source(), e2->Destination()) )
{
e1->SetDestination(e2->Destination());
e2 = path.erase(e2);
}
else
{
e1 = e2;
++e2;
}
}
}

Wyg�adzanie �cie�ki Precyzyjne, ale powolne

Niestety, poprzedni algorytm nie jest idealny. Je�li przyjrzysz si� powy�szemu rysunkowi , znowu wida�, �e dwie ostatnie kraw�dzie mo�na �atwo zast�pi� jedn�, jak pokazano na rysunku

Algorytm tego nie zauwa�y�, poniewa� sprawdza� tylko przejezdno�� mi�dzy s�siaduj�cymi kraw�dziami. Bardziej precyzyjny algorytm wyg�adzania musi iterowa� wszystkie kraw�dzie od E1 do kraw�dzi ko�cowej za ka�dym razem, gdy E1 jest przesuwany. Jednak, cho� precyzyjna, metoda ta jest znacznie wolniejsza, poniewa� nale�y wykona� wiele dodatkowych test�w skrzy�owa�. Oczywi�cie, jakiego algorytmu wyg�adzania u�ywasz lub czy w og�le decydujesz si� na wyg�adzanie, zale�y od ilo�ci dost�pnego czasu procesora i wymaga� twojej gry. Kod bardziej precyzyjnie wyg�adzaj�cy �cie�k� wygl�da nast�puj�co:

void Raven_PathPlanner::SmoothPathEdgesPrecise(std::list& path)
{
// utw�rz kilka iterator�w
std::list::iterator e1, e2;
// wska� e1 na pocz�tek �cie�ki
e1 = path.begin();
while (e1 != path.end())
{
// punkt e2 na kraw�dzi bezpo�rednio po e1
e2 = e1;
++e2;
// podczas gdy e2 nie jest ostatni� kraw�dzi� na �cie�ce, przejd� przez kraw�dzie,
// sprawdzanie, czy agent mo�e si� porusza� bez przeszk�d z poziomu
// w�ze� �r�d�owy e1 do w�z�a docelowego e2. Je�li agent mo�e si� przenie�� // mi�dzy tymi pozycjami, w�wczas wszelkie kraw�dzie mi�dzy e1 i e2 s�
// zast�piony jedn� kraw�dzi�.
while (e2 != path.end())
{
// sprawd�, czy nie ma przeszk�d, odpowiednio wyreguluj i usu� kraw�dzie
if ( m_pOwner->canWalkBetween(e1->Source(), e2->Destination()) )
{
e1->SetDestination(e2->Destination());
e2 = path.erase(++e1, ++e2);
e1 = e2;
--e1;
}
else
{
++e2;
}
}
++e1;
}
}

Mo�esz zobaczy� oba te algorytmy w akcji, uruchamiaj�c demo Raven_PathSmoothing.

UWAGA. Je�li mapa korzysta z kraw�dzi wykresu opatrzonych specjalnymi zachowaniami lub je�li agenci maj� inne ograniczenia, takie jak ograniczony promie� skr�tu, algorytmy wyg�adzania nale�y zmodyfikowa�, aby zapobiec usuni�ciu wa�nych kraw�dzi. Zobacz �r�d�o projektu Raven jako przyk�ad.

Metody zmniejszania obci��enia procesora

Skoki obci��enia maj� miejsce, gdy liczba cykli procesora wymaganych przez silnik gry przekracza liczb� dost�pnych cykli. Je�li w grze biegnie mn�stwo agent�w kontrolowanych przez AI, wszyscy s� w stanie ��da� �cie�ek w dowolnym momencie, w�wczas mog� wyst�pi� gwa�towne obci��enia, gdy zbyt wielu z nich jednocze�nie za��da wyszukiwania. Gdy tak si� stanie, przep�yw p�ynu w grze zostanie przerwany, gdy procesor spr�buje nad��y� za stawianymi mu wymaganiami, tworz�c w ten spos�b gwa�towny, j�kaj�cy si� ruch. Oczywi�cie jest to z�a rzecz i nale�y jej unika�, gdy tylko jest to mo�liwe. Kolejne strony po�wi�cone b�d� metodom, kt�re zmniejszaj� prawdopodobie�stwo skok�w obci��enia poprzez zmniejszenie narzutu zwi�zanego z aktualizacj� ��da� planowania �cie�ki.

Wst�pnie obliczone �cie�ki

Je�li twoje �rodowisko gry jest statyczne i masz do dyspozycji pami��, dobr� opcj� dla zmniejszenia obci��enia procesora jest u�ycie wst�pnie obliczonych tabel odno�nik�w, umo�liwiaj�cych bardzo szybkie okre�lenie �cie�ek. Mo�na je obliczy� w dowolnym dogodnym czasie, na przyk�ad gdy mapa jest odczytywana z pliku lub tworzona przez edytor map i przechowywana wraz z danymi mapy. Tabela przegl�dowa musi zawiera� trasy z ka�dego w�z�a na wykresie nawigacyjnym do ka�dego innego w�z�a na wykresie nawigacyjnym. Mo�na to obliczy� za pomoc� algorytmu Dijkstry, aby utworzy� drzewo najkr�tszych �cie�ek (SPT) dla ka�dego w�z�a na wykresie. (Pami�taj, �e SPT jest poddrzewem navgraph zakorzenionym w w�le docelowym, kt�ry zawiera najkr�tsz� �cie�k� do ka�dego innego w�z�a.) Informacje s� nast�pnie wyodr�bniane i przechowywane w dwuwymiarowej tablicy liczb ca�kowitych. Na przyk�ad, bior�c pod uwag� wykres pokazany na rysunku 8.19, odpowiednia tabela odno�nik�w jest taka, jak pokazano na rysunku

Wpisy w tabeli pokazuj� nast�pny w�ze�, do kt�rego agent powinien przej�� na �cie�ce od pocz�tku do miejsca docelowego. Na przyk�ad, aby okre�li� �cie�k� najmniejszego kosztu od C do E, odsy�amy C do E, daj�c w�ze� B. W�ze� B jest nast�pnie odsy�any do miejsca docelowego, aby da� D, i tak dalej, a� pozycja tabeli b�dzie r�wnowa�na w�ze� docelowy. W tym przypadku otrzymujemy �cie�k� C - B - D - E, kt�ra jest najkr�tsz� �cie�k� od C do E. Stworzy tabel� wyszukiwania wszystkich par dla dowolnego typu wykresu z interfejsem podobnym do SparseGraph. To wygl�da tak

template < class graph_type >
std::vector > CreateAllPairsTable(const graph_type& G)
{
enum {no_path = -1};
// utw�rz tabel� 2D element�w ustawionych na wyliczon� warto�� no_path
std::vector row(G.NumNodes(), no_path);
std::vector > shortest_paths(G.NumNodes(), row);
for (int source=0; source {
// obliczy� SPT dla tego w�z�a
Graph_SearchDijkstra search(G, source);
std::vector spt = search.GetSPT();
// teraz, gdy mamy SPT, �atwo jest przeszuka� go wstecz, aby znale��
// najkr�tsze �cie�ki z ka�dego w�z�a do tego w�z�a �r�d�owego
for (int target = 0; target {
if (source == target)
{
shortest_paths[source][target] = target;
}
else
{
int nd = target;
while ((nd != source) && (spt[nd] != 0))
{
shortest_paths[spt[nd]->From][target]= nd;
nd = spt[nd]->From;
}
}
}// nast�pny w�ze� docelowy
}// nast�pny w�ze� �r�d�owy
return shortest_paths;
}

Wst�pnie obliczone koszty

Czasami agent gry musi obliczy� koszt podr�y z jednego miejsca do drugiego. Na przyk�ad, wraz z innymi funkcjami, agent mo�e wzi�� pod uwag� koszt przedmiotu gry, decyduj�c, czy chce odebra� ten przedmiot. Wyszukiwanie w celu ustalenia tych koszt�w dla ka�dego typu elementu na ka�dym etapie aktualizacji AI b�dzie bardzo kosztowne, je�li wykres nawigacyjny jest du�y i / lub istnieje wiele element�w tego samego rodzaju. W takich sytuacjach tabela wst�pnie obliczonych koszt�w mo�e okaza� si� nieoceniona. Jest to skonstruowane w podobny spos�b jak tabela tras dla wszystkich par om�wiona w ostatniej sekcji, z tym wyj�tkiem, �e elementy tabeli reprezentuj� ca�kowity koszt przej�cia najkr�tsz� drog� z jednego w�z�a do drugiego. Zobacz rysunek

Kod do utworzenia takiej tabeli jest nast�puj�cy: r>
template < class graph_type > std::vector > CreateAllPairsCostsTable(const graph_type& G)
{
std::vector row(G.NumNodes(), 0.0);
std::vector > PathCosts(G.NumNodes(), row);
for (int source=0; source {
// przeszukaj
Graph_SearchDijkstra search(G, source);
// iteruj przez ka�dy w�ze� na wykresie i oblicz koszty podr�y do
// ten w�ze�
for (int target = 0; target {
if (source != target)
{
PathCosts[source][target]= search.GetCostToNode(target);
}
}// nast�pny w�ze� docelowy
}// nast�pny w�ze� �r�d�owy
return PathCosts;
}

Planowanie �cie�ki w okre�lonym czasie

Alternatyw� dla wst�pnego obliczania tabel odno�nik�w w celu zmniejszenia obci��enia procesora jest przydzielenie sta�ej ilo�ci zasob�w procesora na krok aktualizacji dla wszystkich ��da� wyszukiwania i r�wnomierne rozdzielenie tych zasob�w pomi�dzy wyszukiwania. Osi�ga si� to poprzez podzielenie wyszukiwania na wiele etap�w czasowych, technik� znan� jako dzielenie czasu. Aby ten pomys� zadzia�a�, wymagana jest dodatkowa praca, ale w przypadku niekt�rych gier warto po�wi�ci� ten wysi�ek, poniewa� obci��enie procesora zwi�zane z wyszukiwaniem wykres�w jest sta�e, bez wzgl�du na to, ilu agent�w wysy�a ��dania.

UWAGA . Chcia�bym wyja�ni�, �e wyszukiwanie �cie�ek czasowych jest przesad� w przypadku gry z garstk� agent�w, takich jak Raven, ale to �wietna technika do rozwa�enia, czy Twoja gra ma dziesi�tki lub setki agent�w, a zw�aszcza je�li tworzysz platform� konsolow�, poniewa� pomaga ci �y� w ograniczeniach sprz�towych.

Przede wszystkim wyszukiwania Dijkstra i A* musz� zosta� zmodyfikowane w taki spos�b, aby mog�y przeszukiwa� wykres na wielu etapach aktualizacji. Nast�pnie, gdy agenci ��daj� wyszukiwania, ich plani�ci �cie�ek tworz� wyst�pienia odpowiednich wyszukiwa� (A * lub Dijkstra) i rejestruj� si� w klasie mened�era �cie�ek. Mened�er �cie�ek prowadzi list� wska�nik�w do wszystkich aktywnych planist�w �cie�ek, kt�re iteruje przez ka�dy krok, r�wnomiernie dziel�c mi�dzy nimi dost�pne zasoby procesora. Gdy wyszukiwanie zako�czy si� pomy�lnie lub �cie�ka nie zostanie znaleziona, planista �cie�ki powiadomi w�a�ciciela, wysy�aj�c mu wiadomo��. Rysunek pokazuje schemat sekwencji typu UML procesu.

Czas przyjrze� si� szczeg�owym modyfikacjom wymaganym do przeprowadzenia tego procesu. Zacznijmy od zbadania, w jaki spos�b adaptowane s� klasy algorytm�w wyszukiwania A* i Dijkstry.

Modyfikowanie algorytm�w wyszukiwania w celu dostosowania do podzia�u czasu

Algorytmy wyszukiwania A* i Dijkstra zawieraj� p�tl�, kt�ra powtarza nast�puj�ce kroki:

1. Z�ap nast�pny w�ze� z kolejki priorytetowej. 2. Dodaj w�ze� do drzewa najkr�tszych �cie�ek.
3. Sprawd�, czy w�ze� jest celem.
4. Je�li w�ze� nie jest celem, sprawd� w�z�y, z kt�rymi jest po��czony, umieszczaj�c je w kolejce priorytetowej, gdy jest to w�a�ciwe. Je�li w�z�em jest cel, zwrot sukcesu.

B�dziemy odnosi� si� do pojedynczej iteracji tych krok�w jako cyklu wyszukiwania. Poniewa� powtarzane iteracje ostatecznie zako�cz� wyszukiwanie, mo�na u�y� cykli wyszukiwania, aby podzieli� wyszukiwanie na wiele etap�w czasowych. W konsekwencji klasy algorytm�w wyszukiwania A * i Dijkstry s� modyfikowane, aby zawiera�y metod� o nazwie CycleOnce, kt�ra zawiera kod wymagany do podj�cia pojedynczego cyklu wyszukiwania. Jest to stosunkowo �atwe, tworz�c instancj� kolejki priorytetowej jako cz�onka klasy i inicjuj�c j� za pomoc� indeksu w�z�a �r�d�owego w konstruktorze. Ponadto algorytm musi zosta� nieznacznie zmodyfikowany, aby CycleOnce zwr�ci� wyliczon� warto�� wskazuj�c� status wyszukiwania. Mo�e to by� jeden z nast�puj�cych stan�w: docelowy_found, docelowy_found lub search_incomplete. Klient mo�e wtedy wywo�ywa� CycleOnce wielokrotnie, dop�ki zwracana warto�� nie wska�e zako�czenia wyszukiwania. Oto lista metody CycleOnce algorytmu A* z ustalonym przedzia�em czasowym.

template < class graph_type, class heuristic >
int Graph_SearchAStar_TS::CycleOnce()
{
// je�li PQ jest pusty, cel nie zosta� znaleziony
if (m_pPQ->empty())
{
return target_not_found;
}
// pobierz w�ze� o najni�szym koszcie z kolejki
int NextClosestNode = m_pPQ->Pop();
// umie�� w�ze� w SPT
m_ShortestPathTree[NextClosestNode] = m_SearchFrontier[NextClosestNode];
// je�li cel zosta� znaleziony, wyjd�
if (NextClosestNode == m_iTarget)
{
return target_found;
}
// teraz, aby przetestowa� wszystkie kraw�dzie do��czone do tego w�z�a
Graph::ConstEdgeIterator EdgeItr(m_Graph, NextClosestNode);
for (const GraphEdge* pE=EdgeItr.beg(); !EdgeItr.end(); pE=EdgeItr.nxt())
{
/* TEN SAM, JAK W POPRZEDNIM ALGORYTMIE */
}
// s� jeszcze w�z�y do zbadania
return search_incomplete;
}

WSKAZ�WKA. Je�li gra wykorzystuje agent�w rozmieszczonych w oddzia�ach lub plutonach, nie musisz planowa� �cie�ki dla ka�dego cz�onka plutonu za ka�dym razem, gdy pluton musi przej�� z punktu A do B; wystarczy zaplanowa� pojedyncz� �cie�k� dla lidera plutonu i sprawi�, aby wszyscy inni cz�onkowie plutonu pod��ali za tym liderem (stosuj�c odpowiednie zachowanie steruj�ce).

Tworzenie wsp�lnego interfejsu dla algorytm�w wyszukiwania

Bior�c pod uwag�, �e planista �cie�ki mo�e wykorzystywa� wyszukiwania A * i Dijkstry (odpowiednio do wyszukiwania pozycji lub pozycji), wygodnie jest im udost�pni� wsp�lny interfejs. W rezultacie zar�wno pokrojona w czasie klasa A *, jak i pokrojona w czasie klasa Dijkstry wywodz� si� z wirtualnej klasy o nazwie Graph_SearchTimeSliced. Oto deklaracja interfejsu:

template < class edge_type >
class Graph_SearchTimeSliced
{
public:
enum SearchType{AStar, Dijkstra};
private:
SearchType m_SearchType;
public:
Graph_SearchTimeSliced(SearchType type):m_SearchType(type){}
virtual ˜Graph_SearchTimeSliced(){}
// Po wywo�aniu ta metoda uruchamia algorytm przez jeden cykl wyszukiwania.
// metoda zwraca wyliczon� warto�� (target_found, target_not_found,
// search_incomplete) wskazuj�cy status wyszukiwania
virtual int CycleOnce()=0;
// zwraca wektor kraw�dzi zbadanych przez algorytm
virtual std::vector GetSPT()const=0;
// zwraca ca�kowity koszt do celu
virtual double GetCostToTarget()const=0;
// zwraca �cie�k� jako list� PathEdges
virtual std::list GetPathAsPathEdges()const=0;
SearchType GetType()const{return m_SearchType;}
};

Klasa planowania �cie�ki mo�e teraz tworzy� instancj� dowolnego rodzaju wyszukiwania i przypisywa� j� do pojedynczego wska�nika. Poni�sza lista jest zaktualizowan� wersj� klasy Raven_PathPlanner i ilustruje dodatkowe dane i metody wymagane do u�atwienia tworzenia ��da� �cie�ki podzielonej na przedzia�y czasowe.

class Raven_PathPlanner
{
private:
// wska�nik do wyst�pienia bie��cego algorytmu wyszukiwania wykres�w.
Graph_SearchTimeSliced* m_pCurrentSearch;
/* DODATKOWE SZCZEGӣY POMINI�TE */
public:
// tworzy instancj� wyszukiwania wed�ug przedzia�u czasu A * i rejestruje j� w
// mened�er �cie�ek
bool RequestPathToItem(unsigned int ItemType);
// tworzy instancj� czasowego wyszukiwania i rejestr�w Dijkstry
// z mened�erem �cie�ki
bool RequestPathToTarget(Vector2D TargetPos);
// mened�er �cie�ek wywo�uje to w celu wykonania iteracji raz przez cykl wyszukiwania
// aktualnie przypisanego algorytmu wyszukiwania. Po zako�czeniu wyszukiwania
// metoda wysy�a w�a�cicielowi wiadomo�� z msg_NoPathAvailable lub
// msg_PathReady wiadomo�ci.
int CycleOnce()const;
// wywo�ywany przez agenta po otrzymaniu powiadomienia o zako�czeniu wyszukiwania
//z powodzeniem. Metoda wyodr�bnia �cie�k� z m_pCurrentSearch, dodaje // dodatkowe kraw�dzie odpowiednie do typu wyszukiwania i zwraca je jako list�
// PathEdges.
Path GetPath();
};

Metoda Raven_PathPlanner :: CycleOnce wywo�uje metod� CycleOnce aktualnie utworzonego wyst�pienia wyszukiwania i sprawdza wynik. Je�li wynik wskazuje na sukces lub niepowodzenie, do w�a�ciciela klasy wysy�any jest komunikat, aby umo�liwi� podj�cie odpowiednich dzia�a�. Aby to wyja�ni�, oto wykaz tej metody:

int Raven_PathPlanner::CycleOnce()const
{
assert (m_pCurrentSearch &&
": No search object instantiated");
int result = m_pCurrentSearch->CycleOnce();
// powiadom bota o niepowodzeniu znalezienia �cie�ki
if (result == target_not_found)
{
Dispatcher->DispatchMsg(SEND_MSG_IMMEDIATELY,
SENDER_ID_IRRELEVANT,
m_pOwner->ID(),
Msg_NoPathAvailable,
NO_ADDITIONAL_INFO);
}
// powiadom bota o znalezieniu �cie�ki
else if (result == target_found)
{
// je�li szukano typu elementu, to ostatni w�ze� na �cie�ce b�dzie
// reprezentuj� wyzwalacza. W zwi�zku z tym warto przekaza� wska�nik
// do wyzwalacza w dodatkowym polu informacyjnym wiadomo�ci. (Wska�nik
// b�dzie po prostu NULL, je�li nie ma wyzwalacza)
void* pTrigger =
m_NavGraph.GetNode(m_pCurrentSearch->GetPathToTarget().back()).ExtraInfo();
Dispatcher->DispatchMsg(SEND_MSG_IMMEDIATELY,
SENDER_ID_IRRELEVANT,
m_pOwner->ID(),
Msg_PathReady,
pTrigger);
}
return result;
}

Przyjrzyjmy si� teraz klasie, kt�ra zarz�dza wszystkimi ��daniami wyszukiwania.

Mened�er �cie�ek

Mened�er �cie�ek to szablon klasy o nazwie, co nie dziwi, PathManager. Kiedy bot wysy�a ��danie trasy za pomoc� swojego narz�dzia do planowania �cie�ki, planista tworzy instancj� odpowiedniego typu wyszukiwania (A * dla pozycji, Dijkstra dla typ�w) i rejestruje si� w mened�erze �cie�ek. Mened�er �cie�ek prowadzi list� wszystkich aktywnych ��da� wyszukiwania, kt�re aktualizuje za ka�dym razem. Oto jego definicja:

template < class path_planner >
class PathManager
{
private:
// kontener wszystkich aktywnych ��da� wyszukiwania
std::list m_SearchRequests;
// to ca�kowita liczba cykli wyszukiwania przydzielonych mened�erowi.
// Ka�dy krok aktualizacji s� r�wno podzielone mi�dzy wszystkie zarejestrowane �cie�ki
// wnioski
unsigned int m_iNumSearchCyclesPerUpdate;
public:
PathManager(unsigned int NumCyclesPerUpdate);
// za ka�dym razem, gdy jest to wywo�ywane, ca�kowita liczba dost�pnych cykli wyszukiwania

// by� r�wno podzielone mi�dzy wszystkie aktywne ��dania �cie�ki. Je�li wyszukiwanie
// zako�czy si� pomy�lnie lub zako�czy si� niepowodzeniem, metoda powiadomi odpowiedniego bota
void UpdateSearches();
// planista �cie�ki powinien wywo�a� t� metod�, aby zarejestrowa� wyszukiwanie w
//mened�er. (Metoda sprawdza, czy planer �cie�ki jest zarejestrowany tylko
// raz)
void Register(path_planner* pPathPlanner);
// agent mo�e u�y� tej metody do usuni�cia ��dania wyszukiwania.
void UnRegister(path_planner* pPathPlanner);
};

Mened�er �cie�ek ma przydzielon� liczb� cykli wyszukiwania, kt�rych mo�e u�y� do aktualizacji wszystkich aktywnych wyszukiwa� na ka�dym etapie aktualizacji. Po wywo�aniu UpdateSearches przydzielone cykle s� r�wno dzielone mi�dzy zarejestrowanymi planistami �cie�ek, a metoda CycleOnce ka�dego aktywnego wyszukiwania jest nazywana odpowiedni� liczb� razy. Gdy wyszukiwanie zako�czy si� powodzeniem lub niepowodzeniem, mened�er �cie�ek usuwa ��danie wyszukiwania z listy. Oto lista metod twojego przeszukiwania.

template < class path_planner >
inline void PathManager::UpdateSearches()
{
int NumCyclesRemaining = m_iNumSearchCyclesPerUpdate;
// iteruj po ��daniach wyszukiwania, dop�ki wszystkie ��dania nie zostan� wykonane // spe�nione lub w tym kroku aktualizacji nie ma �adnych cykli wyszukiwania.
std::list::iterator curPath = m_SearchRequests.begin();
while (NumCyclesRemaining-- && !m_SearchRequests.empty())
{
// wykonaj jeden cykl wyszukiwania dla tego ��dania �cie�ki
int result = (*curPath)->CycleOnce();
// je�li wyszukiwanie zosta�o zako�czone, usu� z listy
if ( (result == target_found) || (result == target_not_found) )
{
// usu� t� �cie�k� z listy �cie�ek
curPath = m_SearchRequests.erase(curPath);
}
//przejd� do nast�pnego
else
{
++curPath;
}
// iterator mo�e teraz wskazywa� na koniec listy. Je�li tak jest,
// nale�y go zresetowa� do pocz�tku.
if (curPath == m_SearchRequests.end())
{
curPath = m_SearchRequests.begin();
}
}//end while
}

UWAGA. Zamiast ogranicza� mened�era �cie�ek do kilku cykli wyszukiwania, mo�esz preferowa� przydzielenie okre�lonej ilo�ci czasu na u�ycie ka�dej aktualizacji do przeszukiwania �cie�ki. Mo�na to �atwo osi�gn��, dodaj�c kod, aby wyj�� z metody PathPlanner :: UpdateSearches po przekroczeniu przydzielonego czasu.

Tworzenie i rejestrowanie wyszukiwania

Jak widzieli�my, ka�dy bot Raven posiada instancj� klasy Raven_Path- Planner. Aby umo�liwi� tworzenie ��da� �cie�ki podzielonej czasowo, klasa ta zosta�a zmodyfikowana tak, aby by�a w�a�cicielem wska�nika do instancji algorytmu wyszukiwania podzielonego czasowo (instancja klasy Graph_SearchDijkstra_TS, gdy bot ��da �cie�ki do typu elementu i instancji klasy Graph_SearchAStar_TS, je�li bot ��da �cie�ki do pozycji docelowej). Te instancje s� tworzone i rejestrowane w mened�erze wyszukiwania w metodach Request-PathToTarget lub RequestPathToItem. Oto, w jaki spos�b wysy�ane jest zapytanie o wyszukiwanie przedmiot�w:

bool Raven_PathPlanner:: RequestPathToItem(unsigned int ItemType)
{
//wyczy�� list� punkt�w i usu� wszelkie aktywne wyszukiwanie
GetReadyForNewSearch();
// znajd� najbli�szy widoczny w�ze� od pozycji bota
int ClosestNodeToBot = GetClosestNodeToPosition(m_pOwner->Pos());
// usu� w�ze� docelowy z listy i zwr�� false, je�li nie jest widoczny
// znaleziono w�ze�. Nast�pi to, je�li nawigator jest �le zaprojektowany lub je�li bot
// uda�o si� dosta� * do * geometrii (otoczonej �cianami)
// lub przeszkoda
if (ClosestNodeToBot == no_closest_node_found)
{
return false;
}
// utw�rz instancj� klasy wyszukiwania Dijkstra
typedef FindActiveTrigger< Trigger > term_con;
typedef Graph_SearchDijkstra_TS< Raven_Map::NavGraph, term_con> DijSearch;
m_pCurrentSearch = new DijSearch(m_pWorld->GetNavigationGraph(),
ClosestNodeToBot,
ItemType);
// i zarejestruj wyszukiwanie w mened�erze �cie�ek
m_pWorld->GetPathManager()->Register(this);
return true;
}

Po zarejestrowaniu mened�er �cie�ki b�dzie wywo�ywa� metod� CycleOnce odpowiedniego algorytmu na ka�dym etapie aktualizacji, a� wyszukiwanie zako�czy si� powodzeniem lub niepowodzeniem. Gdy agent zostanie powiadomiony o znalezieniu �cie�ki, pobiera j� z narz�dzia do planowania �cie�ki, wywo�uj�c metod� Raven_PathPlanner :: GetPath.

Zapobieganie kr�ceniu kciukami

Jedn� z konsekwencji planowania �cie�ki podzielonej na czas jest op�nienie od momentu, gdy agent za��da �cie�ki, do momentu otrzymania powiadomienia o pomy�lnym lub nieudanym wyszukiwaniu. To op�nienie jest proporcjonalne do wielko�ci wykresu nawigacyjnego, liczby cykli wyszukiwania na aktualizacj� przypisanych do mened�era wyszukiwania oraz liczby aktywnych ��da� wyszukiwania. Op�nienie mo�e by� bardzo ma�e, zaledwie kilka krok�w aktualizacji lub mo�e by� du�e, nawet o kilka sekund. W przypadku niekt�rych gier mo�e by� w porz�dku, aby agent siedzia� i kr�ci� kciukami w tym okresie, ale dla wielu wa�ne jest, aby agent zareagowa� natychmiast w jaki� spos�b. W ko�cu, gdy gracz gry kliknie NPC, a nast�pnie kliknie lokalizacj�, do kt�rej ten NPC ma si� przenie��, oczekuje, �e zareaguje on bezzw�ocznie i gra nie b�dzie pod wra�eniem, je�li tak si� nie stanie. Co zatem robi nasz biedny ma�y agent gier w tej sytuacji? Musi zacz�� si� porusza�, zanim zostanie sformu�owana �cie�ka, ale dok�d? Prost� opcj�, kt�rej u�y�em dla Ravena, jest szukanie przez agenta celu, dop�ki nie otrzyma powiadomienia od mened�era wyszukiwania �e �cie�ka jest gotowa, w tym czasie pod��a �cie�k�. Je�li jednak bot poprosi o wyszukiwanie do typu elementu, lokalizacja celu jest nieznana do czasu zako�czenia wyszukiwania (poniewa� mo�e istnie� wiele takich przypadk�w). W tej sytuacji bot po prostu b��ka si�, dop�ki nie otrzyma powiadomienia. Dzia�a to dobrze w wi�kszo�ci przypadk�w, ale stanowi kolejny problem: do czasu sformu�owania �cie�ki agent m�g� przesun�� si� do�� daleko od pozycji, w kt�rej pocz�tkowo ��dano wyszukiwania. W zwi�zku z tym pierwsze kilka w�z��w �cie�ki zwr�conych z planisty zostanie zlokalizowanych w taki spos�b, �e agent b�dzie musia� cofn�� si�, aby je �ledzi�. Przyk�adem tego jest rysunek poni�szy. W A bot poprosi� o �cie�k� od planisty �cie�ki i podczas op�nienia szuka w kierunku celu. Rysunek B pokazuje pozycj� w momencie, gdy bot otrzymuje powiadomienie o sformu�owaniu �cie�ki. Jak wida�, pozostawiony w�asnym urz�dzeniom bot odwr�ci si� i cofnie, aby pod��a� punktami trasy. Z�y bot! Niegrzeczny bot!

Na szcz�cie mamy ju� rozwi�zanie tego problemu. Gdy na �cie�ce zastosowany zostanie algorytm wyg�adzania, wszystkie nadmiarowe punkty trasy s� automatycznie usuwane, co daje bardziej naturalnie wygl�daj�c� �cie�k� pokazan� na rysunku. Dlatego planowanie �cie�ki o okre�lonym czasie powinno by� zawsze stosowane w po��czeniu z pewnego rodzaju wyg�adzaniem �cie�ki.

Mo�esz obserwowa� te efekty z pierwszej r�ki, uruchamiaj�c demo Raven_TimeSlicing i obserwuj�c boty poruszaj�ce si� po �rodowisku z w��czonym lub wy��czonym wyg�adzaniem. (Liczba cykli wyszukiwania dost�pnych dla mened�era wyszukiwania na aktualizacj� jest bardzo ma�a, aby podkre�li� efekt.)

WSKAZ�WKA.Je�li zauwa�ysz, �e twoi agenci cz�sto �ledz� si� nawzajem w jednym pliku, aby dotrze� do lokalizacji lub elementu, i u�ywasz A* do generowania �cie�ek, mo�esz zmienia� �cie�k� wygenerowan� przez algorytm wyszukiwania, dodaj�c troch� szumu do heurystyczny. Spowoduje to nieco inne �cie�ki dla tego samego wyszukiwania.

Hierarchiczne wyszukiwanie �cie�ek

Inna dost�pna technika zmniejszania obci��enia procesora grafem wyszukiwania nosi nazw� hierarchicznego wyszukiwania �cie�ek. Dzia�a w podobny spos�b, jak ludzie poruszaj� si� po swoim otoczeniu. (C�, niezupe�nie, ale to stanowi dobry przyk�ad.) Za��my na przyk�ad, �e budzisz si� w �rodku nocy i decydujesz si� na szklank� mleka. Na jednym poziomie �wiadomo�ci prawdopodobnie b�dziesz pod��a� �cie�k� przechodz�c� przez szereg pokoi (np. Sypialnia do szczytu schod�w na d� schod�w do korytarza do jadalni do kuchni), ale na innym planujesz �cie�ki mi�dzy pokojami jako dotrzesz do nich. Na przyk�ad, gdy dotrzesz do jadalni, tw�j m�zg automatycznie obliczy �cie�k� do kuchni, kt�ra mo�e wymaga� obej�cia sto�u, unikania komody pe�nej talerzy, otwierania drzwi i pr�bowania nie kopni�cia miski z wod� dla psa. Jako taki, tw�j umys� planuje �cie�ki na kilku r�nych poziomach - przy r�nych szczeg�owo�ciach. Innym sposobem spojrzenia na to jest to, �e na jednym poziomie �cie�ka jest planowana przy u�yciu szeregu obszar�w (jadalnia, kuchnia itp.), A na ni�szym poziomie jest planowana przy u�yciu szeregu punkt�w przez te obszary. T� koncepcj� mo�na powt�rzy� w komputerze, projektuj�c planer �cie�ki, kt�ry wykorzystuje dwa na�o�one na siebie wykresy o r�nych ziarnisto�ciach - jeden gruby, drugi drobny. Na przyk�ad wyobra� sobie gr� strategiczn� opart� na wojnie secesyjnej w Ameryce. Hierarchiczny planista �cie�ki dla tej gry mo�e wykorzystywa� gruboziarnisty wykres do reprezentowania informacji o ��czno�ci na poziomie stanu oraz drobno granulowany na poziomie miast i dr�g. Gdy jednostka wojskowa prosi o tras� z Atlanty do Richmond, planista �cie�ki okre�la, w kt�rych stanach le�� te miasta - Georgia i Wirginia - i oblicza drog� mi�dzy nimi za pomoc� stanowego nawigatora: Georgia do Po�udniowej Karoliny, Karolina P�nocna i Wirginia. �cie�k� t� mo�na obliczy� niezwykle szybko, poniewa� wykres zawiera tylko kilkadziesi�t w�z��w, po jednym dla ka�dego stanu reprezentowanego w grze. Nast�pnie planista u�ywa drobnoziarnistego nawigatora do obliczania �cie�ek mi�dzy stanami, gdy i kiedy jednostka ich potrzebuje. W ten spos�b wyszukiwanie drobnoziarnistego wykresu jest utrzymywane na niskim poziomie, a zatem szybkie.

UWAGA. Chocia� u�ycie dw�ch warstw graficznych jest najbardziej typow� implementacj� hierarchicznego wyszukiwania �cie�ek, nic nie stoi na przeszkodzie, aby� u�ywa� wi�kszej liczby warstw, je�li �rodowisko gry jest wystarczaj�co z�o�one, aby to uzasadni�.
Stosuj�c ten sam pomys� do mapy Raven_DM1, planista �cie�ki m�g�by u�y� wykres�w pokazanych na rysunku . Wykres po lewej stronie mo�e s�u�y� do szybkiego okre�lania �cie�ek na poziomie "pokoju", a wykres po prawej stronie do okre�lania �cie�ek mi�dzy pokojami na poziomie "punktu".

Oczywi�cie jest to trywialny przyk�ad; hierarchiczne wyszukiwanie �cie�ek powinno si� rozwa�a� tylko wtedy, gdy gra wymaga planowania �cie�ek w du�ych i / lub z�o�onych �rodowiskach.

Wyj�cie z lepkich sytuacji

Problem, kt�ry gracze w grach komputerowych obserwuj� zbyt cz�sto, to utkni�cie NPC. Mo�e si� to zdarzy� z r�nych powod�w. W szczeg�lno�ci wyst�puje cz�sto, gdy �rodowisko zawiera wiele czynnik�w, a geometria ma w�skie gard�a. W�skim gard�em mo�e by� ma�a przestrze� mi�dzy dwiema przeszkodami, w�skie drzwi lub w�ski korytarz. Je�li zbyt wielu agent�w jednocze�nie pr�buje pokona� w�skie gard�o, to niekt�rzy z nich mog� zosta� zepchni�ci do ty�u i zaklinowa� si� na �cianie lub przeszkodzie. Przyjrzyjmy si� temu z prostym przyk�adem. Rysunek pokazuje bota - nazwiemy go Eric - pod��aj�c �cie�k� od A do B do C. Pokazuje tak�e liczb� innych bot�w podr�uj�cych w przeciwnym kierunku. Eric czeka na paskudn� niespodziank�.

Na rysunku Eric osi�gn�� punkt A, wi�c zosta� usuni�ty z listy i B przypisany jako nast�pny punkt. Niestety, gdy tak si� dzieje, przybywaj� inne boty i zaczynaj� przepycha� Erica przez drzwi.

Na tym rysunku8 Eric zosta� wypchni�ty z powrotem przez drzwi, ale wci�� szuka drogi do punktu B. G�upi stary Eric.

W ko�cu Eric zostaje przyci�ni�ty do �ciany, wci�� walcz�c w�ciekle i beznadziejnie pr�buje dotrze� do nast�pnego punktu, jak pokazano na rysunku

TSK TSK.

Oczywi�cie nie chcemy, aby co� takiego si� wydarzy�o, wi�c ka�da sztuczna inteligencja warta swojej soli powinna regularnie testowa� takie sytuacje i odpowiednio planowa�. Ale jak to zrobi�? Jednym ze sposob�w jest obliczenie przez agenta odleg�o�ci do bie��cego punktu na ka�dym kroku aktualizacji. Je�li ta warto�� pozostaje mniej wi�cej taka sama lub stale ro�nie, oznacza to uczciwy zak�ad, �e agent utkn�� lub zosta� popchni�ty do ty�u przez si�� oddzielaj�c� od s�siednich agent�w. Innym sposobem jest obliczenie oczekiwanego czasu przybycia dla ka�dego punktu trasy i ponowne zaplanowanie, je�li aktualny czas przekroczy oczekiwany czas. Takie jest podej�cie przyj�te w Raven. Jest bardzo prosty do wdro�enia. Za ka�dym razem, gdy nowa kraw�d� jest wyci�gana ze �cie�ki, oczekiwany czas na przej�cie jest obliczany w nast�puj�cy spos�b (w pseudokodzie):

Edge next = GetNextEdgeFromPath (�cie�ka)
// w prostym grafiku kosztem kraw�dzi jest d�ugo�� kraw�dzi
ExpectedTimeToReachPos = next.cost / Bot.MaxSpeed
// uwzgl�dni� margines b��du
MarginOfError = 2.0;
ExpectedTimeToReachPos + = MarginOfError;

Margines b��du s�u�y do uwzgl�dnienia wszelkich reaktywnych zachowa� bota podczas podr�y, takich jak skr�canie w bok w celu unikni�cia kolejnego bota lub przepychanie si� w drzwiach i w�skich przej�ciach. Margines ten powinien by� wystarczaj�co ma�y, aby uniemo�liwi� agentom wygl�danie na g�upie, a jednocze�nie wystarczaj�co du�y, aby uniemo�liwi� agentom cz�ste ��danie nowych �cie�ek od narz�dzia do planowania �cie�ek.

UWAGA Mo�esz zaobserwowa�, �e boty blokuj� si�, je�li uruchomisz demo Raven_BotsGetting- Stuck. W wersji demo kilka bot�w bada map�. Z ich aktualnej pozycji rysowana jest strza�ka do ich bie��cego miejsca docelowego. Kiedy przepychaj� si� przez drzwi, niekt�re z nich utkn�, a niekt�re na sta�e.

Podsumowanie

Przedstawiono wiele metod i technik zwi�zanych z planowaniem �cie�ki. Wi�kszo�� pomys��w zosta�a w��czona do frameworka gry Raven, dzi�ki czemu mo�esz zobaczy�, jak dzia�aj� na miejscu i zbada� kod, aby zobaczy�, jak wszystko dzia�a razem. Pami�taj, �e jest to tylko przyk�ad. Zwykle nie u�ywa�by� wszystkich tych technik jednocze�nie. Po prostu u�ywaj tego, czego wymaga Twoja gra, i nic wi�cej.

Praktyka czyni mistrza

Po przej�ciu do pozycji docelowej boty Raven wype�niaj� luk� utworzon� przez czas potrzebny na przeszukiwanie wykresu, szukaj�c tej pozycji. Jest to tanie i �atwe do wdro�enia, ale w grach z setkami agent�w lub du�ymi nawigatorami op�nienie mo�e by� zbyt d�ugie, aby takie podej�cie by�o skuteczne. Bior�c pod uwag� zbyt d�ugie op�nienie, agenci zaczn� g�upio chodzi� po �cianach i innych przeszkodach. S� te� chwile, w kt�rych najlepsza �cie�ka do pozycji polega na oddaleniu si� od celu lub odchyleniu go od niego przed pochyleniem si�, aby stawi� mu czo�a.

Szukanie w takich sytuacjach przez d�u�szy czas jest zdecydowanie nie-nie. Zamiast tego agenci musz� okre�li� cz�ciow� �cie�k� do pozycji docelowej. Oznacza to, �e algorytm A* musi zosta� zmodyfikowany, aby zwraca� �cie�k� do w�z�a najbli�szego celowi po osi�gni�ciu zdefiniowanej przez u�ytkownika liczby cykli wyszukiwania lub g��boko�ci wyszukiwania. Agent mo�e nast�pnie pod��a� t� �cie�k�, dop�ki nie zostanie utworzona pe�na �cie�ka. Spowoduje to znacznie lepsze zachowanie i zmniejszy szanse, �e agent b�dzie wygl�da� g�upio. Twoim zadaniem, je�li zdecydujesz si� to zaakceptowa�, jest zmodyfikowanie projektu PathPlanner w celu utworzenia cz�ciowych �cie�ek mi�dzy w�z�ami �r�d�owym i docelowym.

Praktyczne planowanie �cie�kiProgramownie A.I. Gier

Praktyczne planowanie �cie�ki