Transcript
„Sztuczna inteligencja w grach z oponentem” Autor: Michał Jaworski Data opracowania: 13-04-2017 Wstęp: W moim referacie chciałbym skupić się na grach video, które są najbardziej popularne w dzisiejszych czasach, a mianowicie na grach z grafiką trójwymiarową. Gry tego typu tworzone są głównie z myślą o rozrywce gracza. Składają się z kilku elementów: grafiki, dźwięku, scenariusza, czyli opowiadanej historii oraz sztucznej inteligencji. Chciałbym dzisiaj skupić się na ostatnim z wymienionych wyżej elementów. Na wstępie chciałbym zwrócić uwagę na pewnego rodzaju nieścisłość, z którą się spotkałem, tworząc ten referat: istnieje znaczna różnica między powszechnie znaną dziedziną sztucznej inteligencji, a tym, czym twórcy gier nią nazywają. Co prawda czasami wykorzystuje się techniki sztucznej inteligencji, ze względu jednak na prędkość działania i prostotę programowania częściej stosuje się proste algorytmy, wciąż mylnie nazywane sztuczną inteligencją. Sztuczna inteligencja w grach komputerowych z oponentem to z reguły nic innego, jak techniki sterujące zachowaniem pewnych jednostek. Głównym ich założeniem jest, aby gracz czerpał przyjemność z rywalizowania z zaprogramowanym przeciwnikiem, więc algorytmy kierujące oponentem powinny symulować do pewnego stopnia zachowania ludzkie, łącznie z popełnianiem błędów podobnych do tych, które popełnia przeciętny gracz. Ja jednak chciałbym powiedzieć o algorytmie, który odchodzi od tej reguły, a jest wykorzystywany w większości dzisiejszych gier komputerowych. A*: A* jest algorytmem wywodzącym się ze sztucznej inteligencji, służącym do wyznaczenia najtańszej drogi między dwoma wierzchołkami grafu ważonego. Jest to algorytm zupełny, czyli znajdujący najlepsze rozwiązanie, a nie przybliżone. W grach komputerowych używany jest dość często, gdy mamy do czynienia z przeciwnikiem poruszającym się w przestrzeni dwuwymiarowej lub trójwymiarowej. Po wyznaczeniu najlepszej pod względem kosztu drogi od punktu położenia postaci przeciwnika do bieżącej pozycji gracza, bądź innego elementu przedstawionego świata, należy przydzielić ją algorytmowi odpowiedzialnemu za poruszanie się oponenta. Dzięki temu przeciwnicy są w stanie wybrać najkrótszą drogę, omijając tym samym napotkane przeszkody. Graf ważony to struktura danych składająca się ze zbioru wierzchołków i zbioru krawędzi, która dodatkowo posiada informacje na temat wagi każdego elementu tych zbiorów. W przestrzeni trójwymiarowej, podobnie jak w rzeczywistości, pokonanie pewnej drogi wiąże się z jakimś kosztem. Wierzchołki posiadają wagi zależne od odległości dzielącej je od celu końcowego, krawędzie zaś koszt związany z przejściem między wierzchołkami. Celem algorytmu jest dobór kolejnych wierzchołków grafu w taki sposób, żeby każda kolejna funkcja h(x) była niewiększa od poprzednio wybranej, gdzie x to dany wierzchołek. Dla każdego grafu liczymy sumę wyrażoną wzorem: f(x) = g(x) + h(x) gdzie: g(x) – to suma kosztów związanych z przejściem z wierzchołka początkowego do wierzchołka bieżącego. h(x) – to prognozowana odległość od danego wierzchołka do wierzchołka końcowego. Funkcja ta wykorzystuje heurezę, która ustala bezwzględnie najkrótszą drogę.
Ze względu na nieskończoną ilość punktów w układzie kartezjańskim, implementując algorytm do gry, należy stworzyć graf o stałej długości krawędzi i ilości wierzchołków. Wartość funkcji h(x) prawie zawsze liczy się ze wzoru na odległość między dwoma punktami w układzie współrzędnych:
Powyższe grafiki przedstawiają prosty przykład zobrazowany za pomocą dwuwymiarowej siatki. Na niebiesko zaznaczyłem przewidywane odległości wierzchołków od punktu końcowego o współrzędnych x = 8, y = -4 i z = 0. Obraz po lewej pokazuje źle dobraną drogę. Czerwonym kolorem wypisane są kolejno f(x) wybranych wierzchołków. Z wierzchołka o współrzędnych (0, -4, 0) nie da wybrać się punktu x+1, którego funkcja h(x+1) będzie niewiększa od tej samej funkcji tego wierzchołka. W tym momencie algorytm powinien cofnąć się do poprzedniego wierzchołka i wybrać drugi najbliższy wierzchołek. I tak, aż do znalezienia najlepszej drogi. Obraz po prawej pokazuje najtańszą drogę znalezioną przez algorytm. Jak widać odległość od punktu końcowego nie rośnie, co daje gwarancję poprawnego rozwiązania. Ostateczna wartość funkcji f(x) jest mniejsza od wartości obliczonej w pierwszym przykładzie. Ilość koniecznych operacji uzależniona jest od ukształtowania terenu, rodzaju i mnogości przeszkód, które trzeba ominąć i ilości badanych wierzchołków. Znając najkrótszą drogę możemy wykorzystać ją do zmiany położenia oponenta. W podobny sposób można wykorzystać ten algorytm do szacowania korzystności podejmowanych przez przeciwnika decyzji. Jest to szczególnie przydatne w automatach skończonych sterujących zachowaniem oponenta. Wtedy nie brany tylko i wyłącznie koszt związany z przebyciem jakiejś odległości, lecz także zysk. Dzięki implementacji algorytmu A* do takiego automatu, przeciwnik wybiera najkorzystniejszą dla niego drogę zachowań. Podsumowanie: Chociaż twórcy gier komputerowych często mylnie nazywają algorytmy sterujące zachowaniem przeciwnika sztuczną inteligencją, to pewne techniki sztucznej inteligencji są stosowane w tej dziedzinie. Ciężko dowieść skąd wzięła się ta nieścisłość. Najprawdopodobniej wywodzi się to z potocznego nazewnictwa algorytmów zarządzających zachowaniem postaci z gier, które mają w pewien sposób symulować reakcje i decyzje, które podejmuje człowiek.
