Sztuczna inteligencja jest coraz powszechniej stosowana w grach komputerowych, dostarczając graczom coraz bardziej realistycznych i wciągających doświadczeń. Dzięki zaawansowanym algorytmom i uczeniu maszynowemu, SI pozwala na tworzenie niezwykle złożonych i inteligentnych postaci niezależnych, które mogą reagować na różne sytuacje i działania graczy.

Istnieje wiele różnych metod modelowania sztucznej inteligencji i opisanie ich wszystkich w jednym artykule byłoby niemożliwie. Dlatego zamiast krótkiego i prozaicznego przeglądu wszystkich możliwych metod, w tym artykule skupimy się na bardziej szczegółowym przedstawieniu kilku z nich, wraz z przedstawieniem przykładu ich zastosowania i ich modyfikacji w wybranych grach komputerowych.

Na wstępie warto również zaznaczyć specyfikę sztucznej inteligencji w grach komputerowych. W przeciwieństwie do wielu innych dziedzin, sztuczna inteligencja w grach komputerowych nie koniecznie powinna być jak “najlepsza” – w wielu przypadkach takie gry stałyby się niegrywalne. Możemy wyobrazić sobie sytuację gry FPS, w której komputer zawsze zna położenie gracza i posiada perfekcyjną celność, dzięki czemu jest w stanie natychmiastowo wyeliminować gracza, nie dając mu żadnej szansy na wygraną – w takim przypadku wrażenia z gry byłby zdecydowanie negatywne. Większość gier dąży jednak do tego, aby poziom trudności był odpowiednio zrównoważony – gra stanowiła dla gracza wyzwanie, ale nie udrękę. W niektórych grach możemy dążyć do stworzenia botów, których zachowanie jest jak najbardziej zbliżone do zachowania człowieka – jednak również to nie zawsze jest pożądane. Czasami przeciwnikami w grach są np. kosmici albo zwierzęta, a czasami celowo dążymy do tego, aby przeciwnik nie zachowywał się zbyt inteligentnie. W szczególności, nie dążymy do utworzenia sztucznej inteligencji mającej chociażby pomyślnie przejść test Turinga.

Warto również zaznaczyć, że na odbiór przez gracza przeciwników sterowanych przez komputer zależy również od wielu innych czynników, niezwiązanych bezpośrednio ze sztuczną inteligencją. Należą do nich chociażby: design przeciwników, wydawane przez nich dźwięki, czy system walki zaimplementowany w grze, a w pewnym stopniu również całokształt całego środowiska, z którym gracz wchodzi w interakcje. Artykuł ten skupia się głównie na samych algorytmach i metodach, a o pozostałych czynnikach tylko pobieżnie wspomina.

Drzewa zachowań (Behavior tree)

Jedną z podstawowych technik modelowania sztucznej inteligencji w grach komputerowych są drzewa zachowań (behavior tree). Opierają się one o strukturę informatycznego drzewa (zakładam dalej że czytelnik zna podstawy działania tej struktury). Wyróżniamy 3 rodzaje węzłów: composite, decorator i execution. Wykonanie określonego działania zaczyna się w korzeniu drzewa, który przesyła żądanie wykonania do jednego z dzieci, a ten następnie przesyłają je dalej. Dziecko odsyła do rodzica jeden z trzech stanów: running – gdy zachowanie wciąż jest wykonywane, success jeżeli zakończyło się pomyślnie i failure jeśli zakończyło się porażką.

Zadaniem węzła typu composite jest czuwanie nad poprawnym wykonaniem zadań przez węzły-dzieci. Wyróżniamy dwa podstawowe podtypy:

• Sequence – węzeł ten zleca wykonanie zadania wszystkim swoim dzieciom, w ustalonej kolejności, od lewej do prawej. Węzeł zwróci wartość failure lub running, jeśli chociaż jedno z jego dzieci zwróci taki status, natomiast zwróci wartość success tylko jeśli ostatnie dziecko zwróci taką wartość. Węzeł ten można porównać do logicznego operatora AND, który wymaga, aby wszystkie zadania składowe zakończył się pomyślnie.

• Selector – węzeł typu selector jest natomiast odpowiednikiem logicznego OR – zwróci stan success, jeśli chociaż jedno z dzieci zakończy swoje zadanie pomyślnie, a węzeł selector nie będzie próbował wykonywać innych zadań. Podobnie jak w przypadku sequence, dzieci-akcje są wykonywane w kolejności od lewej do prawej.

Innym typem węzłów są węzły decorator, które mogą mieć tylko jedno dziecko. Ich rola w drzewie różni się w zależności od ich rodzaju. Przykładem węzłów decorator są:

• Inverter – analogicznie do bramki logicznej NOT, odwraca wartość zwróconą przez dzieko.
• Succeeder – zawsze zwróci wartość success
• Repeat Until Fail – wykonuj węzeł-dziecko, dopóki nie zwróci wartości success.

Ostatnim rodzajem węzłów, są węzły execution, będące liśćmi drzewa. Znajdują się w nich konkretne akcje, zaimplementowane i wykonane przez postacie w grze.

Modelowanie sztucznej inteligencji przy pomocy drzew zachowań jest powszechną techniką we współczesnych grach komputerowych, a specjalne moduły ułatwiające pracę nad nimi możemy znaleźć w popularnych silnikach do tworzenia gier, takich jak Unity czy Unreal Engine, czy chociażby Java Behavior Trees dla języka Java.

Case study: Halo 2 (2004)

Jedną z pierwszych gier wykorzystujących behavior trees była gra Halo 2 z 2004 roku. W grze gracz zmierzy się z kilkoma rodzajami przeciwników, każdy z nich różniący się od siebie budową fizyczną, wykorzystywaną bronią i sposobem walki, a co za tym idzie – zachowaniem wobec gracza. Każdy z przeciwników ma więc swoje własne drzewo zachowań, którego gracz musi się nauczyć i do niego dostosować. Przykładowy gameplay z gry: https://www.youtube.com/watch?v=L8tyOFJ55eQ

W celu modelowania zaawansowanych zastosowań, Halo 2 wprowadza kilka modyfikacji do przedstawionych powyżej założeń drzewa zachowań. Drzewa zachowań potrafią być bardzo rozbudowane, jednocześnie każdy z botów musi w czasie rzeczywistym podjąć jak najlepszą decyzję dotyczącą akcji do wykonania. Pierwszym mechanizmem który umożliwia przeciwnikowi podjęcie decyzji jest kontekst. W zależności od tego, w jakiej sytuacji znajduje się przeciwnik – czy np. jedzie pojazdem na miejscu pasażera, czy gracz znajduję się w pobliżu – kontekst w jakim znajduje się bot, może wyłączyć część węzłów (a przez to również “odciąć” niektóre gałęzi drzewa), w celu zmniejszania liczby potencjalnych akcji do wykonania.

Kontekst to jednak nie wszystko. Zadania mają również przypisany swój priorytet. Priorytet zadania jest zależny od aktualnego kontekstu i zmienia się wraz z nim. W niektórych sytuacjach przeciwnik powinien priorytetyzować obronę ponad atak, a w sytuacji w której wrogowie mają przewagę liczebną, a gracz ma mało życia – może warto raczej atakować –  działania ofensywne będą miały przypisany większy priorytet i będą wykonywane pierwsze.

Sam kontekst i priorytety jednak nie wystarczą. W przypadku w którym gracz do nas strzela, priorytetem powinno być odpowiedzenie ogniem, ale kiedy gracz nagle wsiadł do pojazdu, odpowiednią akcją byłoby również skorzystanie z najbliższego pojazdu. Gra wykorzystuje tzw. impulse trigger w celu natychmiastowej zmiany priorytetów i przeniesienia się z jednej gałęzi drzewa na drugą. Przykładem jest sytuacja, w której przy zabiciu przez gracza jednego z oficerów (tzw. elites), pomniejsi, szeregowi przeciwnicy (grunts) przestraszą się i zaczną uciekać w popłochu.

Goal Oriented Action Planning

Goal Oriented Action Planning (GOAT) jest architekturą/systemem projektowania stucznej inteligencji, opartą na solwerze STRIPS (Stanford Research Institute Problem Solver), stworzoną z myślą o projektowaniu zachowań autonomicznych agentów, pozwalającą im na dynamiczne podejmowanie decyzji w złożonych środowiskach.

System działa w oparciu o automat skończony (dalej zakładam ze czytelnik zna podstawy ich działania). W klasycznym modelu GOAT automat ma tylko trzy stany:

• Goto – przemieszczanie się
• Animate – odegranie animacji
• Use Smart Object – interakcja z jednym z obiektów będących częścią świata

Liczba ta może wydać się zaskakująco mała, jednak jeżeli poddamy ten problem głębszej analizie, dojedziemy do wniosku, że tak naprawdę wszystkie działania podejmowane przez wirtualne boty da się sprowadzić do jednego z tych trzech stanów.  Zrezygnowanie z tworzenia skomplikowanych automatów skończonych jest jedną z głównych zalet modelu GOAT.

Agent znajduje się w pewnym środowisku/świecie (world). Pojedyncza informacja na temat środowiska nazywana jest faktem, a zbiór wszystkich faktów na temat środowiska nazywany jest jego stanem (state). W celu zrozumienia działania modelu GOAT, należy wyjaśnić również następujące terminy:

• Goal (Cel) – warunki, do których spełnienia dąży agent.
• Plan – sekwencja akcji, które agent musi wykonać, aby został spełniony cel.
• Action (akcja) – pojedyncze, atomowe działanie, będące częścią składową planu. Do akcji należą np: otwarcie drzwi, odegranie animacji, podniesienie przedmiotu itp. Akcje wykonywane są niezależnie od siebie. Każda akcja posiada również preconditions (warunki wstępne), które są stanami, w jakich musi być środowisko, aby akcja mogła zostać wykonana, oraz effects (efekty), które określają jak zmienią się fakty będące częścią stanu, w którym akcja została wykonana. Wyróżnia się również obiekty (objects), które są przedmiotami, z którymi agent musi wejść w interakcję, aby wykonać daną akcję.

Centralną częścią systemu GOAT jest tzw. planner (planista), będący fragmentem kodu, odpowiedzialnym za konstruowanie planów. Agent dostarcza planiście swój cel, listę dostępnych akcji, oraz aktualny stan środowiska. Planista następnie analizuje warunki wstępne akcji oraz ich efekty (np. przy pomocy algorytmu A*) i w odpowiedzi przesyła agentowi plan, będący kolejką akcji do wykonania, które najlepiej spełnią dany cel. Agent następnie wykonuje dany plan, dopóki nie uda mu się osiągnąć celu, wykonanie planu stanie się niemożliwe, albo znajdzie inny cel, lepiej dostosowany do aktualnej sytuacji – planista tworzy wtedy nowy plan.

Case study: F.E.A.R (2005)

Gra F.E.A.R, stworzona przez studio Monolith i wydana w 2005 roku była pierwszą grą komputerową, wykorzystującą system GOAT. Od dnia premiery gra była wielokrotnie chwalona przez graczy i wciąż, ponad 15 lat po premierze, jest przytaczana jako przykład jednej z najlepszych sztucznych inteligencji w grach typu FPS. Część kodu została udostępniona publicznie, co umożliwia dokładne zapoznanie się z działaniem botów w tej grze.

Większa części gry dzieje się w dosyć ciasnych, zamkniętych pomieszczeniach, posiadającymi nie więcej niż klika możliwych ścieżek do poruszania się dla gracza i przeciwników. Naszymi przeciwnikami są w dużej mierze grupy ludzkich przeciwników, którzy sprawiają wrażenie współpracowania ze sobą, wykonują skomplikowane akcje taktyczne np. zachodzenie gracza z flanki. Dodatkowo wszyscy przeciwnicy żywo werbalizują wykonywane akcję (np. informują o obecności gracza albo o rzuceniu przez gracza granatu). Wszystko to sprawia wrażenie, że mamy styczność z oddziałem przeciwników, którzy kooperują ze sobą i zachowują się w realistyczny, ludzki sposób. Działanie sztucznej inteligencji (i reakcje graczy) można zobaczyć na tym filmiku: https://www.youtube.com/watch?v=KQN3yKYkFmE

Boty w grze posiadają 70 celów. Każdemu z celów nadawany jest priorytet, zależny od aktualnego stanu środowiska. Przykładowo, jeśli żaden z faktów na temat świata nie mówi, że w pobliżu znajduje się gracz, cel KillEnemy będzie miał priorytet 0, a cel Patrol będzie priorytetowy. W grze zaimplementowane jest łącznie 120 akcji, a każdy rodzaj przeciwniki posiada ich odpowiedni ich podzbiór.

Cele i plany muszą być ustalane w czasie rzeczywistym dla każdego z agentów z osobna. Nie stanowiło by to aż takiego problemu, gdyby nie fakt, że stan w jakim znajduje się środowisko również zmienia się dynamicznie (w wyniku gracza lub działania innych agentów), co może spowodować całkowite unieważnienie aktualnego planu. Z tego powodu, gra posiada odpowiedni system walidacji planów. Po pierwsze, każdy plan jest od nowa walidowany zaraz po utworzeniu – planista tworzy kopię aktualnego stanu świata, a następnie wykonuje plan na utworzonej kopii, aby upewnić się że zakładany cel faktycznie zostanie spełniony. Po drugie, specjalna funkcja ReplanRequired cały czas sprawdza, czy aktualny plan powinien zostać porzucony i czy należy zapytać planistę o utworzenie nowego. Po trzecie, przed wykonaniem każdej akcji ponownie sprawdzane jest, czy spełnione są wciąż jej warunki wstępne, a jeśli nie – planista jest proszony o utworzenie nowego planu.

Jeśli akcja może być wykonana automat skończony jest informowany, do jakiego z trzech stanów musi się przenieść, oraz przesyła wszystkie dane potrzebne do wykonania danego stanu. Przykładem jest sytuacja, w której agent musi przeładować broń – w takim przypadku zmienia swój stan na Animate i przekazuje automatowi parametry animacji. Większość planów w grze jest dosyć krótka – zazwyczaj składa się z 1-2 akcji, rzadko przekraczając 4. Umożliwia to dynamiczną zmianę planów, dzięki czemu gracz nieczęsto znajdzie się w sytuacji, w której przeciwnik bezmyślnie stoi w miejscu, zastanawiając się co robić.

Mimo zaawansowanej sztucznej inteligencji, F.E.A.R ucieka się również do kilku “sztuczek”, przez które gracz odbiera sztuczną inteligencję obecną w grze za znacznie lepszą, niż jest w rzeczywistości. Jak zostało wcześniej wspomniane, jedną z pierwszych rzeczy rzucających się w oczy przy obcowaniu z botami w grze, jest ich bogata komunikacja – gracz jest przekonany, że poszczególne komunikaty wymieniane są między członkami oddziału i na ich podstawie zespół dostosowuje swoją taktykę. W rzeczywistości jednak komunikaty są wysyłane “w próżnie” – poszczególni agenci są w pełni autonomiczni i nie wiedzą o istnieniu innych agentów. Iluzja współpracy bierze się stąd, że ich cele mają podobne priorytety dla danej sytuacji (są ustalane przez ten sam algorytm), a więc zazwyczaj po prostu cele większości agentów zbiegają się ze sobą, co z perspektywy gracza sprawia wrażenie współpracy.

Podsumowanie

Przedstawione metody to tylko wierzchołek góry lodowej, jaką jest projektowanie sztucznej inteligencji w grach komputerowych. Przedstawione metody mają swoje liczne udoskonalenia i wariacje, z którymi zainteresowane osoby mogą się zapoznać. Warto również wymienić kilka innych metod projektowania SI w grach, które są powszechnie używane, a które nie zostały szerzej opisane w tym artykule. Należą do nich m.in: rożne rodzaje automatów skończonych, metody heurystyczne, pathfinding, czy Monte-Carlo Tree Search. Czytelników których zainteresowała przedstawiona tematyka, zachęcam do zapoznania się z przedstawionymi poniżej źródłami artykułu.

Bibliografia

• https://www.gamedeveloper.com/programming/behavior-trees-for-ai-how-they-work
• https://www.gamedeveloper.com/programming/gdc-2005-proceeding-handling-complexity-in-the-i-halo-2-i-ai
• Implementation of Behavior Tree in Halo 2 – Fakhri Nail Wibowo
• The Behaviour Tree AI of Halo 2 | AI and Games: https://youtu.be/NU717sd8oUc
• https://alumni.media.mit.edu/~jorkin/goap.html
• https://medium.com/@vedantchaudhari/goal-oriented-action-planning-34035ed40d0b
• https://gamedevelopment.tutsplus.com/tutorials/goal-oriented-action-planning-for-a-smarter-ai–cms-20793
• https://www.bit-tech.net/reviews/gaming/how-ai-in-games-works/3/
• Building the AI of F.E.A.R. with Goal Oriented Action Planning | AI 101: https://www.youtube.com/watch?v=PaOLBOuyswI
• Jeff Orkin – Three States and a Plan: The A.I. of F.E.A.R. 1 – Game Developers Conference 2006