Jak powstaje sztuczna inteligencja w grach komputerowych

Sztuczna inteligencja brzmi bardzo skomplikowanie i zawile, kiedy tak naprawdę prawie wszyscy realizują ją tymi samymi metodami. Ten artykuł je omawia.

Dość dawno omawialiśmy sobie historię powstawania sztucznej inteligencji. Zaprezentowałem wszystkie kroki milowe i intrygujące rozwiązania począwszy od testu Turinga z 1951 roku, kończąc na AlphaGo z Listopada 2015. Wymieniłem najciekawsze gry, które były na swój sposób przełomowe. W tych wszystkich opisach pojawiły się takie pojęcia jak: Maszyny stanów skończonych, drzewa decyzyjne, sieci neuronowe i kilka innych. Czas sobie wyjaśnić czym one są i jak działają.

Techniki podejmowania decyzji

Najbardziej oczywistym zagadnieniem dotyczącym sztucznej inteligencji w grach komputerowych jest system podejmowania decyzji. To ten moment, kiedy agent reaguje na zachowanie gracza. Docierają do niego pewne bodźce, które może przeanalizować i zachować się w adekwatny do sytuacji sposób. Przykładowo, bodźcem może być zobaczenie gracza, reakcją na to będzie otworzenie ognia. Przy czym to bardzo banalny przykład, bo często komputerowi rywale analizują dużo więcej danych, zanim podejmą decyzję. W przypadku strzelanki, zanim padnie decyzja o otworzeniu ognia, agent musi sprawdzić, czy ma załadowany magazynek, czy ma dość życia żeby stanąć do walki, czy nie lepiej będzie najpierw przedostać się za osłonę itd.
[stextbox id=”info” defcaption=”true”]Agent – Tak w żargonie sztucznej inteligencji nazywamy komputerowego przeciwnika, a raczej każdą istotę zdolną do odczuwania i podejmowania własnych decyzji. Tak więc, handlarz, przechadzający się po ulicy anonimowy obywatel, czy biegająca po lesie wiewiórka, będą agentami.[/stextbox]
Mimo, że wydaje się iż w każdej grze schematy podejmowania decyzji mogą być kompletnie różne, to prawda jest taka, że większość gier korzysta z tych samych algorytmów, a różną się tylko dane wejściowe i wyjściowe.

Maszyny Stanów Skończonych

Najpowszechniej i najszerzej stosowana metoda realizacji sztucznej inteligencji w grach komputerowych to Maszyny Stanów Skończony (ang. Finite-State Machine – FSM). W polskim tłumaczeniu pojawia się też nazwa: automat o skończonej liczbie stanów lub w skrócie automat skończony.

Zasada działania jest bardzo prosta. A dokładniej mamy 3 zasady:

• Automat musi mieć skończoną liczbę stanów, w których może się znajdować,
• Pomiędzy stanami istnieją przejścia, realizowane po spełnieniu pewnych warunków,
• Automat może znajdować się na raz tylko w jednym stanie.

Do naszego automatu dostarczamy dane wejściowe. Na ich podstawie obliczany jest stan wyjściowy, co może być nieco mylące, bo automat nie zwraca żadnej wartości, a jedynie przechodzi z jednego stanu do drugiego. Tym stanem wyjściowym jest właśnie stan, w którym znajduje się automat po przetworzeniu danych wejściowych.

Brzmi skomplikowanie, więc przykład objaśniający. Programowanie najczęściej stara się odzwierciedlić rzeczywistość, dlatego rzeczy widoczne dookoła nas, będą miały bardzo dobre zastosowanie jako przykłady. Żarówka np. ma dwa stany: Włączona i Wyłączona. Albo woda i jej 3 stany skupienia: ciekły, gazowy i stały. Do przejść między stanami doprowadza zmiana temperatury. Kolejny przykład drzwi. Jakie mogą mieć stany drzwi?

• Otwarte
• Zamknięte
• Zamknięte na klucz

Do tego musimy mieć jakieś dane wejściowe. Oczywiście zawsze możemy podać cokolwiek, ale w tym wypadku sensowne są dwa sygnały wejściowe:

• Użyj ręki (naciśnij klamkę)
• Użyj klucza (włóż i przekręć klucz w zamku)

Jeżeli wykorzystamy sygnał ręki na drzwiach otwartych to stanem wyjściowym, będą drzwi zamknięte. Jeśli znów wykorzystamy sygnał ręki na drzwiach zamkniętych, to stanem wyjściowym będą drzwi otwarte. Analogicznie będzie przy drzwiach zamkniętych i zamkniętych na klucz i sygnałem klucza. Jednak bardziej rozbudowana kombinacja pojawia się, gdy chcemy przejść z drzwi zamkniętych na klucz do drzwi otwartych. Nie mamy tutaj bezpośredniego połączenia. Więc najpierw trzeba użyć klucza, a następnie ręki.

Wszystko fajnie, ale jak to zastosować w grze? Najczęściej stany będą pewną akcją wykonywaną przez agenta. Patrolowanie, atakowanie, ucieczka, leczenie się etc. Przejścia między stanami dalej będą przejściami między stanami, jednak zaczną oczekiwać spełnienia warunków. Np. żeby agent przeładował, musi mieć zapasową amunicję i miejsce w magazynku (po co przeładowywać naładowany karabin?), żeby atakował gracza, musi mieć amunicję w magazynku i musi widzieć gracza.

Na powyższym rysunku przedstawiłem przykładową maszynę stanów skończonych. Jest to chyba najbardziej podstawowy rodzaj jaki możemy sobie zrobić.

Tak naprawdę jedyne co teraz można robić to dokładać kolejne stany i budować bardziej skomplikowane warunki. Przykładowo między podejściem, a atakiem mamy warunek czy gracz jest w zasięgu ataku. Bodźcem jest tutaj zmiana odległości między graczem, a agentem. Ale po za zasięgiem, możemy sobie jeszcze sprawdzić czy mamy amunicję. Im bardziej złożone będą warunki i im więcej będzie stanów, tym bardziej złożona i (być może) lepsza będzie nasza sztuczna inteligencja. Warto pamiętać o odpowiednim doborze połączeń i nie wstawiać za wszelką cenę jak najwięcej opcji, bo wtedy sami możemy się pogubić, albo agent będzie lekko opóźniony, bo przejście całego drzewa zajmie mu kilkanaście sekund.

Jeśli chodzi o same warunki, mogą być one banalnie proste: dostaje bodziec w postaci zauważenia gracza, to atakuje, a mogą być realizowane przez jakieś funkcję, które sprawdzą szereg warunków. Dodatkowa ważna informacja, to fakt, że jeden agent może być sterowany nawet kilkoma maszynami stanów. Jeśli będą dobrze zaprojektowane, nic nie stanie na przeszkodzie. Również dany stan może być opisany kolejną maszyną stanów. Np. w stanie “Patroluj”, moglibyśmy mieć 2 stany: idź do punktu patrolowego i znajdź kolejny punkt patrolowy. Jeden wykonywałby akcję przemieszczania, a drugi ustalał, gdzie szukać kolejnego punktu.

W zasadzie tak prezentują się maszyny stanów skończonych. Najprostsza metoda kreowania sztucznej inteligencji.

Drzewa Decyzyjne

Ten system stał się bardzo popularny u dużych developerów w ciągu ostatnich 20 lat. Sprzęt stał się na tyle mocny, że było możliwe wykorzystanie tej techniki. Przodownikami były tutaj ekipy pracujące nad grami Halo i Gears Of War.

Drzewa decyzyjne opierają się na zasadach tworzenia drzew w informatyce. Czyli dostajemy zorganizowaną, hierarchiczną strukturę danych, która zaczyna się od korzenia (root) i kończy na liściach (leaf).

W tym wypadku agent, żeby określić jak powinien się zachować wykonuje obliczenia na drzewie. Czyli sprawdza wszystkie kolejne gałęzie, aż dojdzie do liścia. Każdy z węzłów, może zwrócić: ture, false albo running – czyli określa, że jeszcze się nie policzył. Ostatni stan jest wbrew pozorom ważny. Mając na scenie kilku agentów, ze skomplikowanymi drzewami, nie byłoby opcji policzyć całego drzewa w ciągu jednej klatki, więc decyzje byłby głupie, albo gra by się zawieszała. Dlatego proces liczenia takiego drzewa, może trwać nawet kilka klatek gry.

W drzewie decyzyjnym rozróżniamy kilka szczególnych rodzajów węzłów:

• Węzły złożone – Mają pod sobą kilka dzieci i określają w jaki sposób realizować sprawdzanie:
  • Sekwencja (Sequence) – Zwraca true, kiedy wszystkie węzły potomne zwróciły true (takie logiczne AND),
  • Selektor (Selector) – Zwraca true, gdy trafi na pierwsze możliwe true.
• Węzły dekoracyjne – W przeciwieństwie do złożonych, te mogą mieć tylko jednego potomka i wykonują pewną operację:
  • Negacja (Inverter) – Jest to klasyczne, logiczne NOT. Jeśli jego potomek zwraca true, to on zwraca false,
  • Powtarzacz (Repeater) – Oblicza swoją wartość określoną (bądź nieskończoną) liczbę razy, do póki nie osiągnie założonej wartości. Można go wykorzystać, np. do oczekiwania na odpowiednią ilość energii.
  • Ogranicznik (Limiter ) – Ograniczę liczbę obliczeń danego węzła. Swojego rodzaju ogranicznik dla powtarzacza.

Same liście mogą zwracać nam wyniki działań funkcji, czy sprawdzanych atrybutów. Np. sprawdzać, czy odległość między graczem, a agentem jest mniejsza od 10.

Ważne jest również to, że obliczanie zaczyna się od lewej strony i idzie w prawo (patrz rysunek powyżej). Czyli, jeśli jako pierwszy child dla roota będzie “Atakować?”, to właśnie takie rozwiązanie wybierze agent jeśli tylko spełni warunki. Np. w drzewie powyżej, korzeń zacznie badanie od węzła “Uciekaj”. Który sprawdza, czy życie jest mniejsze od 20. Powiedzmy, że zwróci false, przez co cały węzeł “Uciekaj” zwraca false. Przechodzimy do węzła “Atakuj”. Powiedzmy że oba jego warunki zostały spełnione i zwraca true. W tym momencie, ponieważ korzeń jest selektorem zwraca true. Tym samym przeciwnik podjął decyzje i atakuje.

Pytanie, które tutaj się samo nasuwa: To jaka jest różnica między drzewami decyzyjnymi i maszyną stanów skończonych? Główna przewaga drzew to skalowalność, oraz fakt, że są lepszym rozwiązaniem modułowym. Co to oznacza? Łatwiej i przejrzyściej powiększyć nam tak zbudowane drzewo, niż diagram stanów, który czasami może się bardzo rozrosnąć – możemy mieć nawet setki stanów. Tutaj hierarchia zapewnia, że wszystko będzie dalej czytelne. Jeśli chodzi o moduły, to tak opakowana sztuczna inteligencja może być z powodzeniem wykorzystana wielokrotnie w różnych projektach. Kiedy maszyna stanów często jest dedykowana konkretnemu przypadkowi. Jak wspominał Damian Isla na konferencji GDC (Game Developers Conference) w 2005 roku, tak rozbudowane maszyny stanów są zbyt trudne do debugowanie, dlatego jego ekipa, pracująca nad grą Halo 2, wykorzystała drzewa decyzyjne.

W ogólnym rozrachunku, nic nie stoi na przeszkodzie, żeby wykorzystywać jednoczenie oba rozwiązania.

Skala Użyteczności (Utility AI)

Ten koncept jest raczej nowy i nie opisany zbyt dokładnie w różnych źródłach. Jednak pojawiają się firmy, które ten schemat chcą mocno promować, takie jak Apex Game Tools.

Idea powstała dlatego, że twórcy chcący budować coraz to bardziej skomplikowane i rozbudowane systemy sztucznej inteligencji, napotkali ponownie problem rozrostu w drzewach decyzyjnych. Drzewa rosły do takich rozmiarów, że mimo układu hierarchicznego i tak stawały się trudne do ogarnięcia i debugowania. Dodatkowo ogromne drzewo obliczało swój ruch bardzo długo. Próbowano rozwiązać problem tworząc pod-drzewa, które miały być w stanie obliczać swoją wartość, bez udziału reszty drzewa, jednak to potęgowało tylko problemy z debugowaniem.

Biorąc pod uwagę najnowsze trendy w grach, gdzie dominują otwarte, wypełnione zawartością światy, takie jak Far Cry, czy Wiedźmin, mamy tam ogromne zapotrzebowanie na wielu agentów na raz, którzy będą zachowywali się naturalnie. Przy skomplikowanym systemie, zmarnujemy na to wiele zasobów komputera, przez co może na tym ucierpieć płynność rozgrywki, albo przeciwnicy będą bardzo głupi.

Pierwszym studiem, które wykorzystało Utility AI było Guerilla Games. System pojawił się w grze Killzone 2. Podobne systemy, ale nie do końca to, wykorzystano w F.E.A.R czy w Cywilizacji. Ale na czym to w zasadzie polega? Nasz agent może zawsze wykonać pewne akcję. Jednak aby zdecydować, jaką akcję podjąć ocenia sytuację. Gdzie ocenia jest słowem kluczem. Każdej sytuacji dotyczą pewne okoliczności, które tutaj są danymi wejściowymi. Dla różnych działań, każda okoliczność ma jakąś wartość punktową. System zlicza punkty i wybiera akcję najlepiej punktowaną.

Korzyści z tego rozwiązania jest kilka. Po pierwsze, taki system jest prosty do zaprojektowania. Znika bariera słowna między projektantem, a programistą. Można powiedzieć: “Jeśli żołnierz jest pod ostrzałem, to najważniejsze dla niego, jest znaleźć osłonę”. Łatwo całość rozszerzyć. Jeśli będziemy chcieli dodać nową zasadę, np. dla żołnierza ma się teraz dodatkowo liczyć czy ma kompana czy nie, to taką zasadę możemy od ręki dopisać wszędzie. W przypadku drzewa, czy maszyny stanów, możemy sobie coś zepsuć. Po trzecie, mając do dyspozycji prosty w obsłudze system, generujemy mniej błędów, przez co mamy więcej czasu na tworzenie sztucznej inteligencji, zamiast marnować go na debugowanie.

Dodatkowym plusem jest to, że praktycznie automatycznie wprowadzamy sobie elementy logiki rozmytej.

Logika Rozmyta

Zdefiniowanie logiki rozmytej jest najprostsze, kiedy skonfrontujemy ją z logiką klasyczną. W naszej klasycznej logice mamy dwa stany: Prawda albo Fałsz. Logika rozmyta daje nam stany pośrednie i pozwala pracować z koncepcjami, które nie są rzeczowe – czyli wymagają określenie “w jakim stopniu” lub “ile”. Np. bardzo mały, dość duży, średni etc.

Taki stan rzeczy pozwala na budowanie bardziej skomplikowanych i rzeczywistych systemów sztucznej inteligencji. Pozwala np. wprowadzić emocje. Nasz przeciwnik już nie jest zły albo spokojny, tylko może być spokojny, poirytowany, wkurzony, bardzo zły, rozgniewany etc. Zyskujemy na tym dwie rzeczy. Po pierwsze możemy operować na tych stanach pośrednich, a po drugie w rozmowie programisty z projektantem, określenie “Przeciwnik ma atakować, kiedy będzie bardzo zły, nabiera sensu”.

Ważne jest, że wartości logiki rozmytej zapisujemy w formie znormalizowanej. Tzn. przyjmujemy wartości od 0 do 1, gdzie można rozumieć to jak procenty: 0 = 0%, 0.23 = 23%, 0.76 = 76%, 1 = 100%.

Żeby wykorzystać logikę rozmytą, musimy sobie najpierw określić co chcemy symulować za jej pomocą. Załóżmy, że chcemy sprawdzać, czy agent powinien rzucić zaklęcie leczenia. Będzie to zależało od dwóch czynników: Jego stopnia bezpieczeństwa (dla uproszczenia przyjmiemy, że będzie to odległość od gracza), oraz od aktualnego stanu zdrowia.

Teraz musimy sobie wymodelować zasady, które możemy uważać za rozsądne. W moim odczuciu wygląda to tak:

• Jeżeli jestem bardzo ranny to rzucam zaklęcie dużego leczenia, jeżeli jest bezpiecznie
• Jeżeli jestem trochę ranny to rzucam zaklęcie małego leczenia, gdy jest bezpiecznie lub niebezpiecznie,
• Jeżeli nie jestem ranny to się nie leczę,
• Nie leczę się, jeśli jest niebezpiecznie.

Teraz na tej podstawie musimy określić zbiory rozmyte, które będą definiować nasze rozmiary przedstawione w języku naturalnym. Czyli w jakiś sposób trzeba przedstawić, kiedy bardzo ranny, zmienia się w ranny, a kiedy bezpiecznie zmienia się w niebezpiecznie. Najczęściej służą do tego wykresy:

Załóżmy, że agent ma 80% życia. Będzie to wtedy gdzieś w tym miejscu:

Co z tego możemy odczytać? Że nasz bohater jest w 0.5 lekko ranny oraz w 0.25 zdrowy. Teraz podobne badanie robimy na naszej zmiennej odległości. Najpierw wykres:

A następnie zaznaczamy aktualną wartość. Powiedzmy, że gracz jest 350m od agenta:

Wynika z tego, że pozycja agenta jest w 25% bezpieczna i w ok 65% niebezpieczna.

Teraz zobaczmy, jakie zasady mogą być spełnione? Nasz gracz jest trochę zdrowy i trochę lekko ranny, więc pojawiają się trzy pierwsze zasady, mogące mieć zastosowanie:

• Nie leczę się, gdy jestem zdrowy,
• Rzucam zaklęcie małego leczenia, kiedy jestem lekko ranny i jest niebezpiecznie,
• Rzucam zaklęcie małego leczenia, kiedy jestem lekko ranny i jest bezpiecznie.

W oparciu o bezpieczeństwo, możemy określić że jest bezpiecznie i niebezpiecznie, co dokłada nam możliwość wystąpienia kolejnych 3 zasad:

• Rzucam zaklęcie małego leczenia, gdy jestem lekko ranny i jest niebezpiecznie (tutaj mamy duplikat),
• Rzucam zaklęcie małego leczenia, gdy jestem lekko rany i jest bezpiecznie (znów duplikat),
• Rzucam zaklęcie dużego leczenia gdy jestem bardzo ranny i jest bezpiecznie.

Teraz należy wykonać oceny prawdziwości każdego ze scenariuszy. Prawdziwość, to najmniejszy możliwy procent ze wszystkich warunków. Przykładowo: Rzucam zaklęcie małego leczenia, gdy jestem lekko ranny i jest bezpiecznie. Jestem lekko ranny w 50%, a jest bezpiecznie w  25%. Zatem, w najwyższym możliwym procencie, zdanie jest prawdziwe w 25%. Takiej ewaluacji dokonujemy dla każdego zdania, otrzymując:

• Nie leczę się, gdy jestem zdrowy – 25% (Jestem zdrowy w 25%, odległość tutaj nie miała znaczenia),
• Rzucam zaklęcie małego leczenia, kiedy jestem lekko ranny i jest bezpiecznie – 25% (To omawialiśmy w przykładzie),
• Rzucam zaklęcie małego leczenia, kiedy jestem lekko ranny i jest niebezpiecznie – 50% (50% jestem ranny i 65% jest niebezpiecznie),
• Rzucam zaklęcie dużego leczenia, gdy jestem bardzo ranny i jest bezpiecznie – 0% (w 0% jestem bardzo ranny).

I teraz wybieramy najwyżej ocenione zdanie, czyli tutaj rzucam zaklęcie małego leczenia, bo jestem lekko ranny i jest niebezpiecznie. W ten sposób decyzję możemy podejmować na każdy możliwy temat.

W przypadku Utility AI wspomniałem, że praktycznie z automatu dodaje nam logikę rozmytą. Teraz widać dlaczego. Jeśli każde zadanie, zależy od kilku czynników, które oceniamy w różnych skalach to tak naprawdę dodajemy elementy logiki rozmytej. Jeżeli np. przeładowanie broni zależy od odległości w jakiej jest przeciwnik i tego ile pocisków zostało nam w karabinie, to możemy przyznać np. 20pkt za odległość i 100pkt za ostatnie 2 pociski. Wtedy, jeśli żadna czynność nie dostanie więcej punktów, wygrywa przeładowanie.

Tyle, jeśli chodzi o dokonywanie decyzji.

Wyszukiwanie ścieżki (Pathfinding)

Przechodzimy teraz do algorytmów szukania ścieżki. Jest to jedna z ważniejszych rzeczy w grach. Co z tego, że przeciwnik podejmie decyzję, jeśli potem nie będzie potrafił nigdzie się dostać, czy przemieszczać się po planszy?

Kiedyś plansze gier były dużo prostsze, przykładowo w klasycznym Space Invaders przeciwnicy tylko opadali w dół i ruszali się na boki. W Pacmanie, rywale jako jedyne ograniczenie mieli ściany labiryntu. Dzisiaj, gdy to bardzo rozbudowane światy z krzywiznami terenu i masą różnych dekoracyjnych elementów, oraz dziesiątkami innych agentów. Dlatego poruszanie się agenta, musi być przemyślane.

W wypadku wyszukiwania ścieżek, najczęściej do głosu dochodzą algorytmu wyszukiwania ścieżki w grafie. Nie zawsze są one rozwiązaniami najlepszymi, dlatego mówimy tu o algorytmach heurystycznych, czyli optymalizacyjnych.

Algorytm A* (A-Star)

Najpopularniejszym algorytmem wyszukującym ścieżkę pomiędzy punktami A i B, jest algorytm A* (A-star). Mimo, że istnieje wiele innych algorytmów, robiących to samo, jak algorytm Dijkstry (nie mylić z grubasem z Wiedźmina), czy algorytm Monte-Carlo wykorzystany np. w AlphaGo od Google.  Dzieje się tak, ponieważ ze wszystkich algorytmów A* jest prosty w implementacji i efektywny w działaniu.

A* zawsze znajduje ścieżkę między dwoma punktami, jeśli tylko ona istnieje, dodatkowo będzie to zawsze optymalna ścieżka. Kolejnym powodem opowiadającym się za tym algorytmem, jest fakt że dobrze wykorzystuje heurystykę, tzn. żaden innych algorytm (korzystający z tej samej heurystyki), nie znajdzie bardziej optymalnej drogi, przy testowaniu mniejszej liczby węzłów.

Już wiemy, czemu algorytm jest fajny, ale w zasadzie na czym polega? Musimy tutaj rozważyć naszą planszę jako graf z pewnymi wierzchołkami. Wierzchołki połączone są krawędziami, które mogą mieć pewien koszt. Algorytm zawsze wybiera najtańsze w danym momencie przejście, czyli przechodzi do wierzchołka, do którego koszt przejścia był najniższy. Wykonuje to, dopóki nie trafi na punkt docelowy. Bardzo ładnie obrazuje to gif z Wikipedii:

Jak widać, algorytm na początku ma do wyboru dwie krawędzie o wartościach: 1,5 oraz 2. Ale do całości dolicza heurystykę – h(a) dla każdego wierzchołka. Czyli faktyczny pierwszy wybór to: 5,5 i 6,5 – ruszamy więc do wierzchołka A. Kolejny wybór to: 1,5 + 2 + 2 (bo dwie krawędzie + heurystyka), oraz 2 + 4,5, czyli ogólnie: 5,5 vs 6,5. Wybieramy wierzchołek B. Kolejna para to znów wierzchołek D o ciągle tym samym koszcie 6,5, oraz wierzchołek C o koszcie: 6,5 (za karawędzie) + 4, czyli 11,5. Tym razem wygrywa wierzchołek D. No i kolejny test: Wierzchołek C z: 11,5 oraz wierzchołek E z: 7. Wybieramy E. Następny krok to wierzchołek docelowy, więc go bierzemy i jesteśmy u celu.

Wszystko fajnie. Tylko gdzie wierzchołki i krawędzie w grach? W turówkach to jeszcze, ale w strzelance?

Uproszczanie świata gry

Mimo, że czasami tego nie widać, większość gier dzieli sobie świat na właśnie takie proste przestrzenie. Metod podziałów jest kilka i wybranie sobie odpowiedniego zależy głównie od stylu gry jaką wybierzemy. Przykładami mogą być kwadraty czy sześciany. Ale mamy też bardziej skomplikowane metody podziału, takie jak czworoboki wypukłe, czy punkty widoczności.

Tutaj mamy odpowiednio:

• A – Niepodzielony świat
• B – Siatka prostokątna – najprostsza możliwa metoda. Środkami (czyli naszymi wierzchołkami grafu) mogą być tutaj środki czy wierzchołki kwadratów.
• C – Drzewa czwórkowe – Podobne do prostokątnej siatki, tyle, że dzielimy sobie kwadraty na coraz mniejsze, aż do momentu kiedy pełny kwadrat zmieści się w świecie gry nieprzysłonięty. Środki to znów centrum lub wierzchołek kwadratu. Na plus zasługuje tutaj fakt, że duże kwadraty przyspieszają wyszukiwanie drogi.
• D – Wielokąty wypukłe – Bardziej skomplikowana metoda, gdzie fragmenty wyznacza się w oparciu o wierzchołki przeszkód, z których ciągnie się linię przecięcia, aż do napotkają inne przecięcie, bądź przeszkodę. Można też tworzyć tutaj siatki nawigacyjne. Środkami mogą być środki wielokątów, lub ich obwody.
• E – Punkty widoczności – Ta metoda podziału skupia się głównie na omijaniu przeszkód. Wierzchołki określają gdzie znajduje się przeszkoda i każemy agentowi poruszać się w pewnej odległości od wierzchołków.
• F – Uogólnione cylindry – Przestrzeń między sąsiadującymi przeszkodami traktujemy jak dwuwymiarowy cylinder. Obliczamy sobie oś środkową w przestrzeni pomiędzy dwoma sąsiadującymi przeszkodami, wliczając w to granicę mapy. Tak wyznaczone punkty, określają nam, gdzie postać może się przemieszczać.

To pewnie nie wszystkie metody w jakie da się podzielić siatkę. Wszystko zależy od zapotrzebowania i stylu gry jaką tworzymy. Każda z tych metod ma swoje wady i zalety. Np. przy podziale siatki na wielokąty, musimy dodać algorytm, który rozwiąże problem poruszania się, wewnątrz wielokąta. W punktach widoczności nie uwzględnimy dynamicznych postaci. Siatka prostokątna, da nam opcję omijania przeszkód i postaci, ale za to wymaga najwięcej obliczeń. Wybór powinien zależeć od gry jaką tworzymy.

Algorytm A* ma jedną zasadniczą wadę. Potrafi obliczać się długo i czasami się zawiesić, jeśli szukana ścieżka nie istnieje. Dlatego, zanim przystąpimy do wyszukiwania ścieżki, warto wcześniej sprawdzić, czy droga do wybranego punktu w ogóle istnieje. Przy okazji możemy też sprawdzić, czy droga którą szukamy nie jest linią prostą – wtedy nie potrzeba liczyć całej drogi i można w ten sposób zoptymalizować działanie algorytmu. Istnieją jeszcze inne techniki optymalizacji tego algorytmu, ale nie będziemy tego tutaj omawiać.

Są również inne algorytmy i sposoby obliczania ścieżki, jednak to ten stosowany jest szeroko i niemal we wszystkich grach od 1968 roku i nic nie zapowiada, żeby miało się to zmienić. Dlatego nie omawiam innych, bardziej niszowych algorytmów. Nawet w Unity NavMesh to bardzo zoptymalizowany i rozbudowany A*.

Algorytmy stadne

Kolejnym zagadnieniem nad którym się pochylimy są algorytmy stadne. Zasadniczo są to algorytmy, które mają symulować zachowanie roju pszczuł, gromady ptaków lub ławicy ryb. Algorytm został zaproponowany przez Craiga Raynoldsa w 1987 roku. Jego postulat zakładał, że są 3 proste zasady, które połączone razem dają nam realistyczne zachowanie. Te zasady to:

• Rozdzielność – Oznacza, że dany boid (bo tak nazywamy agentów w grupie), stara się utrzymać odległość od będących w jego pobliżu pozostałych boidów,
• Wyrównywanie – Oznacza, że dany boid porusza się w tym samym kierunku, w którym porusza się całe stado z tą samą prędkością,
• Spójność – Oznacza, że boid stara się utrzymać minimalny dystans od środka całej grupy.

Po pewnym czasie Raynolds dołożył kolejną zasadę:

• Omijanie – Oznacza, że boidy mogą patrzeć przed siebie, sprawdzając czy nie trzeba dokonać korekcji trasy, aby ominąć przeszkodę.

Ponieważ ten algorytm jest bezstanowy, czyli między uaktualnieniami, nie są przechowywane żadne dane. Każdy agent oblicza sobie co pewien czas jak wygląda sytuacja. Dzięki takiemu zachowaniu, nie tylko oszczędzamy pamięć, ale też pozwalamy boidom reagować w czasie rzeczywistym.

Jak to wykorzystać w grach? Można zoptymalizować ruch wielu jednostek na raz, np. w grach RTS. Dodatkowo, możemy pozwolić w realistyczny sposób włóczyć się zombie po lochu czy innym podziemiu. Do takich zastosowań wykorzystano tą technologię w grach takich jak Half-Life, Unreal czy Enemy Nations (RTS).

W zasadzie tyle. Nie ma tutaj czego za bardzo optymalizować.

Wykrywanie przeciwnika – Sensory

Sensory to jeden z często pomijanych elementów sztucznej inteligencji, który ma na nią ogromny wpływ. Co z tego, że postać umie podjąć decyzję, jeśli nie docierają do niej żadne bodźce? Pierwszą grą, która poważniej podeszła do tego tematu był Thief, gdzie jako złodziej skrywaliśmy się w cieniu i staraliśmy się zachować cicho, tylko dlatego, że przeciwnik nie mógł nas dostrzec w ciemności, a gdy byliśmy głośno, to mógł nas usłyszeć.

Do dziś, głównie w grach skradankowych, ten koncept mocno się rozwinął. Nie ma tutaj tak naprawdę bardzo wyrafinowanych rzeczy, modelujemy rzeczywistość w czystej postaci. Stożek naszego wzroku, czy sfera słyszalności to bardzo naturalne pojęcia, które rozumiemy odruchowo. Wykorzystując logikę rozmytą, możemy urzeczywistnić efekt. Tzn. przeciwnik zauważa nas słabiej i potrzebuje chwili, żeby nas zauważyć kiedy jesteśmy na skraju jego stożka widoczności, a zauważy nas od razu, kiedy jesteśmy w centrum.

Ważne jest, że nie tylko ludzkie zmysły zaliczają się do sensorów. Kiedy kreujemy robota, to może on wykorzystać kamerę podczerwieni, albo radar. To też będą sensory i tylko od nas zależy jak je zaprogramujemy. Nic nie stoi na przeszkodzie stworzenia kosmity, który ma zasięg wzroku 360 stopni.

Druga istotna rzecz w tym temacie, to fakt, że czasami możemy oszukiwać. Myśląc o realistycznym podejściu, oczekujemy że przeciwnik wie tyle, ile widzi. Ale! Czasami danie mu dostępu do wiedzy, do której nie powinien mieć dostępu, czyli np. dokładna odległość od gracza, albo stanu życia gracza, pozwala podjąć bardziej skomplikowane i realistyczne decyzje. Jeżeli przeciwnik zna stan życia gracza, może zadecydować, że skoro jest bardzo ranny to trzeba go szukać i dobić. Ma to faktyczne uzasadnienie. Widząc ranną osobę, widzimy cieknącą po niej krew, albo że kuleje. Dając agentom dostęp do wiedzy o punktowym stanie życia gracza, możemy symulować właśnie fakt, że ranę dało się zauważyć.

Samo uczący się przeciwnik

Tym samym przebyliśmy wszystkie podstawowe techniki tworzenia sztucznej inteligencji. Jednak człowiek zawsze poszukuje czegoś lepszego. Wymyślono, że fajnie by było, gdyby agenci potrafili uczyć się w czasie gry, czy to od gracza, aby dynamicznie podnosić swój poziom. Takie coś, głównie stosują boty w grach sieciowych, które podkradają sposób przemieszczania się graczom. Pierwsze takie systemy pojawiły się w grach Unreal, czy Colin McRae Rally 2.

Sieci Neuronowe

Sieci neuronowe to system oparty o budowę ludzkich komórek mózgowych, czyli właśnie neuronów. Z biologicznego punktu widzenia (w uproszczeniu) działa to tak, że ciało neuronu otrzymuje pewną informację od dendrytu. W ciele wykonywane są obliczenia i następnie informacja jest przesyłana dalej przez aksony, które łączą się z dendrytami kolejnego neuronu. Tutaj mamy elektroniczny model tego zjawiska.

Od razu trzeba zaznaczyć, że sieci neuronowe to dużo wyższa szkoła jazdy. Połączone z logiką rozmytą i innymi technikami, potrafią dać nam naprawdę potężną, sztuczną inteligencję. Jednak ich implementacja nie jest ani prosta, ani przyjemna. Co możemy sobie wymodelować w ten sposób? W zasadzie wszystko. Narzędzie jest naprawdę potężne i pozwala na generowanie różnych rozwiązań, zależnych od potrzeb i umiejętności.

Cytując Andre LaMonte kilka przykładowych rozwiązań to:

• Skanowanie i klasyfikacja środowiska – Możemy sieć neuronową karmić wiedzą, którą potem wykorzystamy do wybierania odpowiedzi lub uczenia sieci. Sieć może się uczyć w czasie rzeczywistym, a tym samym ciągle optymalizować sieć,
• Pamięć – Sieć można wykorzystać jako swojego rodzaju pamięć. Uczyć ją nowych rzeczy, a wtedy gdy pojawi się nieprzewidziana sytuacja, sieć zareaguje inteligentnie,
• Sterowanie zachowaniem – Jako wejście możemy podać różne dane, a wtedy dane wyjściowe posłużą do sterowania zachowaniem postaci,

Wdawanie się w szczegóły implementacji może tutaj być bezcelowe, jednak posłużę się wiedzą Jeffa Hannana z Codemasters, który pracował nad sztuczną inteligencją w Colinie.

W ich przypadku sieć opierała się o dwie dane “Racing Line” i “Driving Model”. Czyli linia jazdy i model jazdy. Linia reprezentowała wiedzę na temat trasy. Szerokość trasy, zakręty do ścięcia, zakręty których nie należy ścinać etc. Model jazdy składał się na informację na temat samochodu: jego pozycja, prędkość. Wtedy pojawia się problem przed jakim często stają ludzie, którzy chcą samo uczących się systemów. Dane treningowe.

Sieci neuronowe mogą się uczyć i podejmować decyzję, ale muszą mieć podstawową bazę wiedzy, na której się oprą. Dlatego w przypadku Colina, również przygotowano takie dane, czyli wejściowe informację o trasie i pojeździe. Aby wygenerować te dane, autor musiał po prostu wyjeździć po torze odpowiednią liczbę razy. Jaka to liczba? Dla różnych sieci neuronowych, będzie ona inna. W przypadku Colina było to kilka tysięcy rajdów.

Późniejszy rozwój sieci neuronowej to próby, sukcesy i błędy. Dodawanie kolejnych danych wejściowych, różne rodzaje obliczeń, aż dostajemy efekt wyjściowy. W przypadku gry od Codemasters, wyjściem były flagi włączony/wyłączony reprezentujące różne klawisze na klawiaturze. Więc dostawaliśmy np. flagę włączony dla przycisku hamowania, przez co symulowaliśmy sytuację, gdzie kierowca naciska hamulec.

Jakie dane należy uwzględnić w sieci neuronowej? Wg. Hanana należy pilnować aby było ich jak najmniej i nie dodawać redundantnych informacji. Warto eksperymentować z wprowadzaniem kolejnych informacji, aż otrzymamy najlepszy wynik.

Dysponująca sporą wiedzą sieć neuronowa, nie potrzebowała nauki dla każdej nowej trasy. Mając zebraną wiedzę, potrzebowała otrzymać tylko nowy “driving line” dla trasy i komputer był w stanie ją sam pokonać – i właśnie o to chodzi w sieciach neuronowych.

Sieć neuronowa to tylko jeden z przykładów szerszej dziedziny jaką jest uczenie maszynowe, jednak nie słyszałem, aby w grach wykorzystywano inne techniki, dlatego omawianie tego zagadnienia skończę na tym jednym przykładzie.

Sztuczna Inteligencja vs Unity3d

Jak już wiemy, sztuczna inteligencja to skomplikowany temat, a czasami wręcz bardzo trudny. Dlatego czasami warto wykorzystać gotowe rozwiązania, aby pracę sobie ułatwić, bądź nie wynajdywać koła na nowo. Dlatego przygotowałem krótkie zestawienie tego, co daje nam Unity, aby pracę ze sztuczną inteligencją przyspieszyć.

Mecanim

Nie do końca jest to narzędzie do sztucznej inteligencji, a bardziej kreowany był z myślą o zarządzaniu animacjami. Tak się jednak składa, że genialnie nadaje się do tworzenia maszyn stanów skończonych. Mamy tam konkretne stany, które mają między sobą przejścia oparte o różne zasady.

NavMesh

Genialne narzędzie do znajdowania ścieżki. Dzieli automatycznie teren na trójkątne obszary, oblicza za nas ścieżkę, potrafi omijać przeszkody i innych agentów, wyznacza koszt trasy, przez co można uwzględnić bagna, wodę czy drogę i zachęcać postać do korzystania z drogi. Dodatkowo mamy mechanizmy, które pozwolą przeskakiwać obszary, przy braku 100% spójności.

Collider i Rigidbody

To połączenie może wydawać się typowe i nic nie znaczące, jednak dodając oba komponenty do obiektu i pisząc odrobinę skryptu, możemy stworzyć sobie algorytm standy bez zbędnego rozpisywania się.

RAIN AI

RAIN AI to jeden z najpopularniejszych pluginów do tworzenia sztucznej inteligencji w grach, który wykorzystuje drzewa decyzyjne. Jest w 100% darmowy i również wykorzystuje Mecanima do wizualizacji tego jak wygląda nasze drzewo.

Apex Utility AI

Gdy wspomniałem o Utility AI padła nazwa firmy Apex, która również dostarcza darmowy plugin do Unity, pozwalający wprowadzić ich technologię. Wersja free ma pewne ograniczenia względem pełnej wersji, ale i tak warto sprawdzić to rozwiązanie.

Reaction AI

Kolejny darmowy plugin, tym razem realizujący sieć neuronową. Też darmowy. Można się nim pobawić, jeśli ktoś chce zgłębić tą tematykę. Problemem może być brak dokumentacji.

Dodatek A

Jako ciekawostkę dodam, że Unral Engine dysponuje narzędziem tworzenia drzew decyzyjnym domyślnie.

Jako ostatnie słowo dodam jedną ciekawostkę. Do dziś za najbardziej rozbudowane AI w grach komputerowych uznaje się to wykorzystane w F.E.A.R 3. Programiści wykazali się sporą kreatywnością i sprytem łącząc kilka technik tworzenia sztucznej inteligencji, nie omówiłem tego tutaj, ale zrobię to przy kolejnej okazji.