Planowanie drogi w grach

Data dodania: 2011-09-18, Autor: Karol Tyl, Dodał: Karol, Wyświetleń: 421

I. Podstawy teoretyczne

Przestrzeń stanów

Większość algorytmów wyszukiwania drogi operuje w przestrzeni stanów i szuka w niej ścieżki od stanu początkowego do końcowego, sprawdzając przyległe stany.

Aby lepiej wyjaśnić, czym jest stan, posłużę się przykładem. W znanej grze w 15 puzzli stan to aktualne ułożenie elementów na planszy o wymiarach 4x4. Stany przyległe do niego to te, które można uzyskać wykonując jeden krok, czyli przesuwając na puste pole klocek z pola bezpośrednio z nim sąsiadującego.

W problemie planowania drogi stan to określone położenie w świecie gry, a stan przyległy to przyległe położenie. Dla ułatwienia generowania trasy, każdy stan (za wyjątkiem początkowego) posiada wskaźnik na stan macierzysty, czyli ten, z którego się do niego dostano. Po znalezieniu przejścia do celu wskaźniki te umożliwiają utworzenie drogi przez “wrócenie się” do stanu początkowego. ­

Reprezentacja świata gry

Istotnym problemem jest dobór odpowiednich położeń na mapie gry jako danych dla algorytmu. Niektóre gry dzielą świat na kostki (np. gry typu RTS dzielą mapę na kwadraty, a gry wojenne na sześciokąty), które można wykorzystać przy planowaniu drogi. Jednak wiele gier nie organizuje świata w ten sposób (zwłaszcza gry 3D). W takich wypadkach odpowiednie położenia należy wygenerować samemu.

Oto kilka sposobów dzielenia przestrzeni:

• siatka prostokątna – polega na podzieleniu przestrzeni na regularną siatkę kwadratów. Położeniami mogą być środki lub narożniki kwadratów.
• drzewa czwórkowe – przestrzeń jest dzielona rekurencyjnie na cztery mniejsze części, następnie każda z nich dzielona jest znów na cztery. Operację tę wykonujemy tak długo, aż otrzymana w ten sposób siatka dopasuje się do terenu. Duże kwadraty przyspieszają szukanie drogi (jest ich mniej) i upraszczają zapamiętywanie położeń, natomiast małe umożliwiają wierniejsze odwzorowanie terenu.
• wielokąty wypukłe – przestrzeń jest dzielona na wielokąty wypukłe. Takie podejście może już występować w reprezentacji mapy (np. gry 3D), więc można je wykorzystać.
• punkty widoczności – ta technika koncentruje się na omijaniu przeszkód. Każde położenie jest umieszczane w niewielkiej odległości od każdego wypukłego wierzchołka każdej przeszkody. Najkrótsza droga wokół przeszkód przeważnie przechodzi obok tych wierzchołków i łączy się z położeniem początkowym i końcowym.
• uogólnione cylindry – przestrzeń między sąsiednimi przeszkodami można traktować jako dwuwymiarowy cylinder. Między parą sąsiednich przeszkód wyznaczamy prostą równoodległą od każdej z nich.

Przecięcia tych linii tworzą położenia wykorzystywane przy szukaniu drogi.

Uzyskiwanie sąsiadów stanu

Sposób uzyskania sąsiednich stanów jest uzależniony od reprezentacji mapy. Niektóre metody używają tylko najbliższych położeń jako stanów (np. kwadratowe siatki), w innych sąsiadami są wszystkie widoczne położenia. Przy dzieleniu mapy metodą inną niż siatka prostokątna, położenia początkowe i końcowe zwykle nie są automatycznie uwzględniane przez algorytm kwantyzujący teren i należy je samodzielnie dodać do listy wszystkich możliwych stanów.

II. Wyszukiwanie drogi

Przeszukiwanie z nawrotami

Mapy w grach są ograniczone (zazwyczaj do prostokąta), dlatego liczba wszelkich możliwych położeń na danej mapie jest skończona. W konsekwencji, dla każdego stanu X istnieje co najwyżej skończona liczba stanów przyległych Y1, Y2, ..., Yn. Algorytm przeszukiwania z nawrotami oznacza aktualny stan jako sprawdzony, wybiera jeden z niesprawdzonych stanów przyległych i wywołuje się rekurencyjnie dla niego. Jeżeli dla danego punktu nie ma żadnego niesprawdzonego, przyległego stanu, to algorytm wraca się do punktu, z którego wszedł na obecną pozycję. Jeśli zdarzy się tak, że powrócił na miejsce, z którego startował i wszystkie stany przyległe są sprawdzone (lub wcale nie ma stanów przyległych) to znaczy, że nie ma drogi łączącej dwa wybrane punkty.

Właściwości:

• jeżeli istnieje droga łącząca punkt początkowy z końcowym, to przeszukiwanie z nawrotami ją znajdzie
• znaleziona w ten sposób droga bardzo rzadko jest optymalna
• algorytm nie korzysta z heurystyki

Wyszukiwanie najkrótszej drogi

Algorytm bazuje na spostrzeżeniu, że jeżeli z punktu początkowego do celu istnieje najkrótsza droga składająca się z k położeń, to do ostatniego z tych położeń wiedzie droga składająca się z (k-1) położeń, do przedostatniego z (k-22) itd. Poza tym, w każdym położeniu pośrednim odległość od początku jak i od celu jest możliwie najmniejsza (bo trasa jest optymalna).

Sugeruje to, że w poszukiwaniu najkrótszej drogi do celu należy sprawdzać położenia możliwie najmniej oddalone od położenia początkowego. Tak więc: w pierwszym kroku sprawdzone zostaną położenia odległe od punktu początkowego o 1, w następnym o 2 itd. Czyli najpierw sprawdzani są sąsiedzi stanu początkowego, później sąsiedzi sąsiadów itd. Algorytm przerywa działanie, kiedy aktualnie sprawdzane pole jest punktem docelowym, lub gdy na mapie nie ma już nieodkrytych pozycji.

Opisany algorytm jest szczególnym przypadkiem tzw. algorytmu Dijkstry.

Właściwości:

• jeżeli istnieje droga łącząca punkt początkowy z końcowym, to algorytm ją znajdzie
• znaleziona droga jest zawsze optymalna (najkrótsza z możliwych)
• wykonywana jest bardzo duża liczba sprawdzeń
• algorytm nie różnicuje kosztów dotarcia do położenia (koszt przejścia z jednego stanu do drugiego jest zawsze równy 1), więc nadaje się jedynie do stosowania dla siatek regularnych
• algorytm nie korzysta z heurystyki

III. Algorytm A*

Ogólne omówienie algorytmu

Algorytm A* (A star) jest jednym ze starszych (używany od 1968 roku), ale jednocześnie jednym z najczęściej wykorzystywanych algorytmów sztucznej inteligencji. Algorytm A* szuka w przestrzeni stanów najmniej kosztownej drogi od stanu początkowego do końcowego, sprawdzając najbardziej obiecujące nieodkryte położenia, które widzi. Jeśli zbadano położenie i jest ono celem, A* kończy działanie. W przeciwnym wypadku zapamiętuje wszystkie przyległe położenia, aby sprawdzić je w przyszłości.

A* śledzi dwie listy stanów – Open i Closed, zawierające odpowiednio niesprawdzone i sprawdzone punkty. Na początku lista Closed jest pusta, a lista Open zawiera tylko położenie początkowe. W każdym kroku algorytm wybiera z listy Open najbardziej obiecujące położenie (wybrane na podstawie heurystycznej1 oceny kosztów dotarcia do celu). Jeżeli nie jest to położenie docelowe, to sprawdza wszystkie sąsiednie stany i jeżeli są nowe (tzn. nie ma ich jeszcze na listach Open ani Closed) dodaje na listę Open. Jeżeli położenie znajduje się już na liście Open, to uaktualnia informację o nim, gdy można dostać się do niego tańszą trasą niż przechowywana dotychczas. W przypadku, gdy nowe położenie znajduje się już na liście Closed, algorytm nie zajmuje się nim. Jeśli algorytm opróżni listę Open zanim dotrze do celu oznacza to, że z punktu wyjścia nie istnieje ani jedna droga do celu.

Każdy stan przechowuje informację o koszcie najtańszej ścieżki prowadzącej do niego z położenia początkowego (CostFromStart(X)), heurystyczną ocenę kosztu drogi pozostałej do celu (CostToGoal(X)) oraz szacowany koszt całkowity (TotalCost(X)=CostFromStart(X)+CostToGoal(X)). Najbardziej obiecujący stan na liście Open to ten, którego całkowity przewidywany koszt dotarcia do celu jest najmniejszy. Każdy stan przechowuje również wskaźnik na stan rodzicielski, czyli stan, który prowadzi do aktualnego najmniejszym kosztem. Po znalezieniu celu wskaźniki te można wykorzystać do utworzenia ścieżki od źródła do celu. W literaturze CostFromStart(X) często oznacza się jako g(X), CostToGoal(X) jako h (X), zaś TotalCost (X) jako f(X).

Ocena kosztu

Kosztem dotarcia do celu jest przeważnie odległość, którą trzeba przebyć, ale może to być czas potrzebny na przejście trasy, liczba pośrednich punktów lub zużycie paliwa. Dodatkowo, można stosować rozmaite kary, np. za przechodzenie przez trudny teren. W wielu grach koszt zależy również od typu agenta, który ma się poruszać w świecie gry, np. drogi zwiększają prędkość pojazdów, ale nie wpływają na piechotę. Czasem koszt może być niesymetryczny, tzn. przejście z A do B ma mniejszy koszt, niż przejście z B do A (np. gdy A jest położony wyżej niż B).

Ocena kosztu polega na uzupełnieniu znanego kosztu dotarcia do danego położenia z punktu początkowego przewidywanym kosztem dotarcia do celu. Przeważnie robi się to mnożąc rzeczywistą odległość do celu przez minimalny koszt terenu na jednostkę odległości. Ponieważ żadna droga nie może być krótsza niż bezpośrednia odległość dwóch punktów, to otrzymana w ten sposób ocena będzie zawsze niedoszacowana. Będzie to gwarantowało znalezienie najtańszej możliwej drogi.

Odległość do celu liczy się zazwyczaj korzystając ze standardowej euklidesowej odległości dwóch punktów w przestrzeni dwu lub trójwymiarowej. W grach o siatce kwadratowej lub sześciokątnej najkrótsza możliwa odległość pomiędzy dwoma punktami będzie zazwyczaj nieco większa niż odległość euklidesowa, np. odległość pól (3,4) i (0,0) w geometrii euklidesowej wynosi 5, jeśli natomiast liczyć ją w siatce kwadratowej, to będzie ona równa 1+3sqrt(2). Zagwarantowanie optymalnej ścieżki nie jest jedynym czynnikiem który należy brać pod uwagę przy wyszukiwaniu drogi. Ważna jest również szybkość przeszukiwania. Na jakość działania A ogromny wpływ ma ocena CostToGoal(X). Jej niedoszacowanie gwarantuje znalezienie ­najkrótszej ścieżki, ale jeżeli będzie ona znacznie zaniżona, to algorytm sprawdzi po drodze dużo stanów (będzie się zachowywał tak, jak algorytm wyszukiwania najkrótszej drogi). Odpowiednia ocena heurystyczna pozwala określić przybliżony kierunek, w którym należy się poruszać. Z kolei przeszacowanie oceny kosztu może przyspieszyć działanie algorytmu, ale znaleziona w ten sposób ścieżka może nie być optymalna.

Zamiast używać minimalnego kosztu na jednostkę terenu w ocenie drogi do celu można wykorzystać typowy koszt danej mapy, który jest stały lub obliczany dynamicznie na podstawie analizy terenu pomiędzy początkiem, a końcem.

Celem poszukiwań jest przeważnie pojedyncze położenie, ale nie zawsze musi tak być. Gdy pojazd z małą ilością paliwa szuka stacji benzynowej, to potencjalnym celem są wszystkie stacje na mapie. W każdym nowym węźle liczone są koszty do każdej z nich, a dopiero najmniejszy z nich jest zapamiętywany jako CostToGoal(X).

Właściwości

• A* znajduje drogę z jednego punktu planszy do drugiego, jeżeli ona istnieje
• znaleziona droga jest optymalna (tzn. najtańsza) jeżeli tylko heurystyczna ocena CostToGoal(X) jest niedoszacowana
• A* najefektywniej wykorzystuje heurystykę. Żadne inne przeszukiwanie, które używa tej samej funkcji heurystycznej CostToGoal(X) nie znajdzie drogi o mniejszym koszcie przy testowaniu mniejszej liczby stanów, nie licząc szczególnych przypadków ze stanami o równym koszcie.
• W grach o rozbudowanych mapach listy Open i Closed mogą zawierać ogromne ilości stanów, a przez to zajmować mnóstwo pamięci.
• A* staje się najmniej efektywny gdy musi sprawdzić, że między punktem początkowym a końcowym nie istnieje droga, gdyż musi wtedy sprawdzić wszystkie stany dostępne ze stanu początkowego.

Optymalizacje estetyczne

Ścieżki wygenerowane za pomocą A* zazwyczaj dochodzą do celu “kołysząc” się, co nie wygląda naturalnie i podważa jakość systemu sztucznej inteligencji w grze. Problem ten można ­rozwiązać na dwa sposoby: poprzez lepsze ocenianie prostych ścieżek w czasie ich wyszukiwania, lub przez prostowanie drogi już po jej znalezieniu.

Pierwszy sposób polega na tym, że podczas wyszukiwania promowane są ścieżki prostsze. Zazwyczaj robi się to przez “ukaranie”, tzn. dołożenie dodatkowego kosztu w przypadku zmiany dotychczasowego kierunku. Rozsądną karą może być połowa kosztu kroku w danym kierunku. Dla regularnej sietki nawet kara rzędu 0.0000001 spowoduje, że algorytm będzie wybierał proste ścieżki.

Z pośród metod prostowania ścieżki już po jej wyznaczeniu warto wymienić metody punktów widoczności oraz wygładzania ścieżek przy pomocy krzywych sklejanych.

Metoda punktów widoczności sprawdza kolejne punkty ścieżki patrząc wprzód w poszukiwaniu najdalszego widocznego położenia (czyli takiego, które można połączyć z aktualnym za pomocą linii prostej), następnie usuwa ze znalezionej trasy wszystkie węzły, które były między tymi dwoma położeniami. Otrzymana w ten sposób droga będzie miała znacznie mniej zakrętów, niż oryginalna.

Mimo stosowania opisanych wyżej metod poprawiania wyglądu wygenerowanej trasy często zdarzają się na niej bardzo ostre zakręty, a postacie poruszające się po tak przygotowanej ścieżce przypominają roboty. Warto więc wygładzić ścieżkę, na przykład za pomocą krzywych sklejanych Catmulla-Roma.

Krzywe te tworzą wygładzoną ścieżkę przechodzącą przez wszystkie punkty kontrolne (w odróżnieniu np. od krzywych Béziera). Jest to ważne, aby wygładzona ścieżka przechodziła przez punkty znalezione przez algorytm wyszukiwania drogi, w przeciwnym razie mogłoby się zdarzyć, że agent wpadnie na przeszkodę.

Wzór Catmulla-Roma wymaga czterech punktów wejściowych i tworzy wygładzoną ścieżkę pomiędzy drugim a trzecim. Aby otrzymać punkt między pierwszym i drugim punktem z trasy należy przekazać punkt pierwszy dwa razy, a następnie punkt drugi i trzeci. Podobnie, aby wyznaczyć punkty pomiędzy przedostatnim a ostatnim punktem ze ścieżki należy przekazać punkt drugi od końca, przedostatni i dwa razy punkt ostatni. Oto wzór Catmulla-Roma:

nowy_punkt = punkt[1] * (­0.5*u*u*u + u*u - 0.5*u) +
­             punkt[2] * (1.5*u*u*u + 2.5*u*u + 1) +
             punkt[3] * (-1.5u*u*u + 2.0*u*u + 0.5*u) +
             punkt[4] * (0.5*u*u*u-0.5*u*u);

Wzór Catmulla-Roma generuje punkt mniej więcej w u% odległości pomiędzy drugim i trzecim punktem wejściowym. Jeżeli u=0, to zwracany jest punkt wejściowy nr 2, a gdy u=1, zwrócony zostanie punkt 3. Ponieważ w grach ważna jest szybkość, można zaoszczędzić trochę mocy obliczeniowej procesora obliczając wstępnie podany wyżej wzór dla kilku wartości u, np. dla u=0.25, u=0,5 i u=0.75. Spowoduje to, że stanie się on liniowy względem punktów wejściowych.

na podstawie:

• "Game programming gems" (HELION)
• "Algorytmy" (WSiP)