Natknąłem się na ciekawy materiał na temat sztucznej inteligencji w grach. Z wyjaśnieniem podstawowych rzeczy na temat sztucznej inteligencji na prostych przykładach, a wewnątrz znajduje się wiele przydatnych narzędzi i metod umożliwiających jej wygodny rozwój i projektowanie. Tam również opisano, jak, gdzie i kiedy z nich korzystać.
Większość przykładów napisana jest w pseudokodzie, więc nie jest wymagana zaawansowana wiedza programistyczna. Pod wycięciem znajduje się 35 arkuszy tekstu ze zdjęciami i gifami, więc przygotujcie się.
UPD. Przepraszam, ale zrobiłem już własne tłumaczenie tego artykułu na temat Habré . Możesz przeczytać jego wersję , ale z jakiegoś powodu artykuł mnie ominął (użyłem wyszukiwania, ale coś poszło nie tak). A ponieważ piszę na blogu poświęconym tworzeniu gier, zdecydowałem się zostawić moją wersję tłumaczenia dla subskrybentów (niektóre punkty są inaczej sformatowane, inne zostały celowo pominięte za radą twórców).
Co to jest sztuczna inteligencja?
Sztuczna inteligencja gry skupia się na tym, jakie działania powinien wykonać obiekt w zależności od warunków, w jakich się znajduje. Nazywa się to powszechnie zarządzaniem „inteligentnym agentem”, w którym agentem jest postać gracza, pojazd, bot lub czasami coś bardziej abstrakcyjnego: cała grupa bytów lub nawet cywilizacja. W każdym przypadku jest to rzecz, która musi widzieć swoje otoczenie, na jego podstawie podejmować decyzje i postępować zgodnie z nimi. Nazywa się to cyklem Poczuj/Myśl/Działaj:
- Zmysł: Agent wyszukuje lub otrzymuje informacje o rzeczach w swoim otoczeniu, które mogą mieć wpływ na jego zachowanie (zagrożenia w pobliżu, przedmioty do zebrania, ciekawe miejsca do zwiedzania).
- Pomyśl: Agent decyduje, jak zareagować (rozważa, czy zebranie przedmiotów jest wystarczająco bezpieczne, czy też powinien najpierw walczyć/ukryć się).
- Działaj: agent wykonuje czynności mające na celu wykonanie poprzedniej decyzji (zaczyna zbliżać się do wroga lub obiektu).
- ...teraz sytuacja uległa zmianie w wyniku działań bohaterów, więc cykl się powtarza z nowymi danymi.
Sztuczna inteligencja ma tendencję do skupiania się na części pętli związanej ze zmysłami. Na przykład samochody autonomiczne wykonują zdjęcia drogi, łączą je z danymi radarowymi i lidarowymi oraz je interpretują. Zwykle odbywa się to poprzez uczenie maszynowe, które przetwarza przychodzące dane i nadaje im znaczenie, wydobywając informacje semantyczne, takie jak „20 metrów przed tobą jest inny samochód”. Są to tak zwane problemy klasyfikacyjne.
Gry nie potrzebują skomplikowanego systemu do wydobywania informacji, ponieważ większość danych stanowi już ich integralną część. Nie ma potrzeby uruchamiania algorytmów rozpoznawania obrazu, aby określić, czy przed nami znajduje się wróg – gra już o tym wie i przekazuje informacje bezpośrednio do procesu decyzyjnego. Dlatego część cyklu „Poczuj” jest często znacznie prostsza niż część „Myśl i działaj”.
Ograniczenia sztucznej inteligencji w grach
Sztuczna inteligencja ma szereg ograniczeń, których należy przestrzegać:
- Sztucznej inteligencji nie trzeba wcześniej szkolić, jak gdyby była to algorytm uczenia maszynowego. Nie ma sensu pisać sieci neuronowej w trakcie programowania, aby monitorować dziesiątki tysięcy graczy i uczyć się najlepszego sposobu gry przeciwko nim. Dlaczego? Ponieważ gra nie została wydana i nie ma graczy.
- Gra powinna być zabawna i wymagająca, więc agenci nie powinni szukać najlepszego podejścia przeciwko ludziom.
- Agenci muszą wyglądać realistycznie, aby gracze czuli się, jakby grali przeciwko prawdziwym ludziom. Program AlphaGo osiągnął lepsze wyniki niż ludzie, ale wybrane kroki były bardzo dalekie od tradycyjnego rozumienia gry. Jeśli gra symuluje ludzkiego przeciwnika, to uczucie nie powinno istnieć. Algorytm należy zmienić, aby podejmował decyzje wiarygodne, a nie idealne.
- Sztuczna inteligencja musi działać w czasie rzeczywistym. Oznacza to, że algorytm nie może monopolizować wykorzystania procesora przez dłuższy czas przy podejmowaniu decyzji. Nawet 10 milisekund to za długo, ponieważ większość gier potrzebuje tylko 16 do 33 milisekund na wykonanie całego przetwarzania i przejście do następnej klatki graficznej.
- W idealnym przypadku przynajmniej część systemu powinna opierać się na danych, tak aby osoby niebędące programistami mogły szybciej wprowadzać zmiany i dostosowania.
Przyjrzyjmy się podejściu do sztucznej inteligencji, które obejmuje cały cykl Poczuj/Myśl/Działaj.
Podejmowanie podstawowych decyzji
Zacznijmy od najprostszej gry – Ponga. Cel: przesuń paletkę tak, aby piłka odbiła się od niej, a nie przeleciała obok niej. To jak tenis, gdzie przegrywasz, jeśli nie trafisz piłki. Tutaj sztuczna inteligencja ma stosunkowo łatwe zadanie – zdecydować, w którym kierunku przesunąć platformę.
Instrukcje warunkowe
Dla AI w Pongu najbardziej oczywistym rozwiązaniem jest zawsze próba umieszczenia platformy pod piłką.
Prosty algorytm napisany w pseudokodzie:
każda klatka/aktualizacja podczas działania gry:
jeśli piłka znajduje się na lewo od wiosła:
przesuń wiosło w lewo
w przeciwnym razie, jeśli piłka jest na prawo od wiosła:
przesuń wiosło w prawo
Jeśli platforma porusza się z prędkością piłki, jest to idealny algorytm dla AI w Pongu. Nie ma potrzeby niczego komplikować, jeśli nie ma zbyt wielu danych i możliwych działań dla agenta.
To podejście jest tak proste, że cały cykl Poczuj/Myśl/Działaj jest ledwo zauważalny. Ale jest tam:
- Część Sense składa się z dwóch instrukcji if. Gra wie, gdzie jest piłka i gdzie znajduje się platforma, więc sztuczna inteligencja szuka w niej tych informacji.
- Część Think jest również zawarta w dwóch instrukcjach if. Uosabiają one dwa rozwiązania, które w tym przypadku wzajemnie się wykluczają. W rezultacie wybierana jest jedna z trzech akcji - przesuń platformę w lewo, przesuń ją w prawo lub nie rób nic, jeśli jest już poprawnie ustawiona.
- Część Akt znajduje się w instrukcjach Move Paddle Left i Move Paddle Right. W zależności od projektu gry mogą poruszać platformą natychmiast lub z określoną prędkością.
Takie podejście nazywa się reaktywnym - istnieje prosty zestaw reguł (w tym przypadku instrukcji w kodzie), które reagują na aktualny stan świata i podejmują działania.
Drzewo decyzyjne
Przykład Ponga jest w rzeczywistości odpowiednikiem formalnej koncepcji sztucznej inteligencji zwanej drzewem decyzyjnym. Algorytm przechodzi przez to, aby dotrzeć do „liścia” – decyzji o tym, jakie działanie podjąć.
Zróbmy schemat blokowy drzewa decyzyjnego dla algorytmu naszej platformy:
Każda część drzewa nazywana jest węzłem – sztuczna inteligencja wykorzystuje teorię grafów do opisu takich struktur. Istnieją dwa typy węzłów:
- Węzły decyzyjne: wybór pomiędzy dwiema alternatywami w oparciu o testowanie pewnego warunku, gdzie każda alternatywa jest reprezentowana jako oddzielny węzeł.
- Węzły końcowe: Akcja do wykonania, która reprezentuje ostateczną decyzję.
Algorytm rozpoczyna się od pierwszego węzła („korzenia” drzewa). Podejmuje decyzję o tym, do którego węzła podrzędnego się udać, lub wykonuje akcję zapisaną w węźle i kończy działanie.
Jaka jest korzyść z posiadania drzewa decyzyjnego wykonującego tę samą pracę, co instrukcje if z poprzedniej sekcji? Istnieje ogólny system, w którym każda decyzja ma tylko jeden warunek i dwa możliwe wyniki. Umożliwia to programiście tworzenie sztucznej inteligencji na podstawie danych reprezentujących decyzje w drzewie bez konieczności ich kodowania. Przedstawmy to w formie tabeli:
Po stronie kodu otrzymasz system odczytu ciągów znaków. Dla każdego z nich utwórz węzeł, połącz logikę decyzyjną w oparciu o drugą kolumnę, a węzły podrzędne w oparciu o trzecią i czwartą kolumnę. Nadal musisz zaprogramować warunki i działania, ale teraz struktura gry będzie bardziej złożona. Tutaj dodajesz dodatkowe decyzje i działania, a następnie dostosowujesz całą sztuczną inteligencję, po prostu edytując plik tekstowy definicji drzewa. Następnie przesyłasz plik do projektanta gry, który może zmienić zachowanie bez konieczności ponownej kompilacji gry lub zmiany kodu.
Drzewa decyzyjne są bardzo przydatne, gdy są budowane automatycznie na podstawie dużego zestawu przykładów (na przykład przy użyciu algorytmu ID3). Dzięki temu są skutecznym i wydajnym narzędziem do klasyfikacji sytuacji na podstawie uzyskanych danych. Wychodzimy jednak poza prosty system wyboru działań przez agentów.
Scenariusze
Przeanalizowaliśmy system drzewa decyzyjnego, który wykorzystywał wcześniej utworzone warunki i działania. Osoba projektująca sztuczną inteligencję może zorganizować drzewo jak chce, ale nadal musi polegać na koderze, który to wszystko zaprogramował. A gdybyśmy mogli dać projektantowi narzędzia do tworzenia własnych warunków lub działań?
Aby programista nie musiał pisać kodu dla warunków Czy piłka jest na lewo od wiosła i Czy piłka jest na prawo od wiosła, może stworzyć system, w którym projektant napisze warunki w celu sprawdzenia tych wartości. Wtedy dane drzewa decyzyjnego będą wyglądać następująco:
Zasadniczo jest to to samo, co w pierwszej tabeli, ale rozwiązania same w sobie mają swój własny kod, trochę jak część warunkowa instrukcji if. Po stronie kodu oznaczałoby to drugą kolumnę dotyczącą węzłów decyzyjnych, ale zamiast szukać konkretnego warunku do wykonania (Is Ball Left Of Paddle), ocenia wyrażenie warunkowe i odpowiednio zwraca wartość true lub false. Odbywa się to za pomocą języka skryptowego Lua lub Angelscript. Za ich pomocą programista może pobierać obiekty ze swojej gry (piłkę i wiosło) i tworzyć zmienne, które będą dostępne w skrypcie (ball.position). Ponadto język skryptowy jest prostszy niż C++. Nie wymaga etapu pełnej kompilacji, dlatego idealnie nadaje się do szybkiego dostosowania logiki gry i pozwala „niekodującym” samodzielnie stworzyć potrzebne funkcje.
W powyższym przykładzie język skryptowy służy jedynie do oceny wyrażenia warunkowego, ale można go również wykorzystać do wykonywania akcji. Na przykład dane Move Paddle Right mogą stać się instrukcją skryptu (ball.position.x += 10). Dzięki temu akcja jest również zdefiniowana w skrypcie, bez konieczności programowania Move Paddle Right.
Można pójść jeszcze dalej i napisać całe drzewo decyzyjne w języku skryptowym. Będzie to kod w postaci zakodowanych na stałe instrukcji warunkowych, ale będą one zlokalizowane w zewnętrznych plikach skryptów, czyli będzie można je zmieniać bez konieczności ponownej kompilacji całego programu. Często możesz edytować plik skryptu podczas rozgrywki, aby szybko przetestować różne reakcje AI.
Odpowiedź na wydarzenie
Powyższe przykłady są idealne dla Ponga. W sposób ciągły realizują cykl Poczuj/Myśl/Działaj i działają w oparciu o najnowszy stan świata. Ale w bardziej złożonych grach trzeba reagować na indywidualne wydarzenia, a nie oceniać wszystko na raz. Pong w tym przypadku jest już złym przykładem. Wybierzmy inny.
Wyobraźcie sobie strzelankę, w której wrogowie stoją w bezruchu, dopóki nie wykryją gracza, po czym postępują w zależności od swojej „specjalizacji”: ktoś pobiegnie, by „nabiec”, ktoś zaatakuje z daleka. To wciąż podstawowy system reaktywny – „jeśli gracz zostanie wykryty, zrób coś” – ale można go logicznie podzielić na zdarzenie „Widzenie gracza” i reakcję (wybierz odpowiedź i wykonaj ją).
To prowadzi nas z powrotem do cyklu Poczuj/Myśl/Działaj. Możemy zakodować część Sense, która będzie sprawdzała każdą klatkę, czy sztuczna inteligencja widzi gracza. Jeśli nie, nic się nie dzieje, ale jeśli zobaczy, tworzone jest zdarzenie Player Seen. Kod będzie zawierał oddzielną sekcję z informacją „gdy wystąpi zdarzenie Player Seen, wykonaj”, w której znajduje się odpowiedź, której potrzebujesz, aby zająć się częściami „Myśl i działaj”. W ten sposób ustawisz reakcje na zdarzenie Player Seen: dla „pędzącej” postaci – ChargeAndAttack, a dla snajpera – HideAndSnipe. Relacje te można utworzyć w pliku danych w celu szybkiej edycji bez konieczności ponownej kompilacji. Tutaj również można zastosować język skryptowy.
Podejmowanie trudnych decyzji
Chociaż proste systemy reakcji mają ogromne możliwości, istnieje wiele sytuacji, w których nie wystarczą. Czasami trzeba podjąć inne decyzje w zależności od tego, co agent aktualnie robi, ale trudno wyobrazić sobie to jako warunek. Czasami jest zbyt wiele warunków, aby skutecznie przedstawić je w drzewie decyzyjnym lub skrypcie. Czasami trzeba z wyprzedzeniem ocenić, jak zmieni się sytuacja, zanim podejmie się decyzję o kolejnym kroku. Aby rozwiązać te problemy, potrzebne są bardziej wyrafinowane podejścia.
Maszyna skończonych stanów
Maszyna skończona lub FSM (maszyna skończona) to sposób na powiedzenie, że nasz agent znajduje się obecnie w jednym z kilku możliwych stanów i może przejść z jednego stanu do drugiego. Istnieje pewna liczba takich stanów – stąd nazwa. Najlepszym przykładem z życia jest sygnalizacja świetlna. W różnych miejscach znajdują się różne sekwencje świateł, ale zasada jest ta sama – każdy stan coś reprezentuje (stop, spacer itp.). Sygnalizacja świetlna znajduje się w danym momencie tylko w jednym stanie i przemieszcza się z jednego do drugiego w oparciu o proste zasady.
Podobnie jest z NPC-ami w grach. Weźmy na przykład strażnika z następującymi stanami:
- Patrolowanie.
- Napadający.
- Uciekając.
I te warunki zmiany jego stanu:
- Jeśli strażnik zobaczy wroga, atakuje.
- Jeśli strażnik zaatakuje, ale nie widzi już wroga, wraca na patrol.
- Jeśli strażnik zaatakuje, ale zostanie ciężko ranny, ucieka.
Możesz także pisać instrukcje if ze zmienną stanu strażnika i różnymi sprawdzeniami: czy w pobliżu jest wróg, jaki jest poziom zdrowia NPC itp. Dodajmy jeszcze kilka stanów:
- Bezczynność - pomiędzy patrolami.
- Przeszukiwanie - gdy zauważony wróg zniknął.
- Znalezienie pomocy - gdy zostanie wykryty wróg, ale jest zbyt silny, aby walczyć samotnie.
Wybór dla każdego z nich jest ograniczony - np. strażnik nie będzie szukał ukrytego wroga, jeśli ma niski poziom zdrowia.
W końcu istnieje ogromna lista „jeśli” , To " może stać się zbyt kłopotliwe, dlatego musimy sformalizować metodę, która pozwoli nam pamiętać o stanach i przejściach między stanami. Aby to zrobić, bierzemy pod uwagę wszystkie stany i pod każdym stanem zapisujemy na liście wszystkie przejścia do innych stanów wraz z niezbędnymi dla nich warunkami.
To jest tabela przejść stanów - kompleksowy sposób reprezentowania FSM. Narysujmy diagram i uzyskajmy pełny przegląd zmian zachowania NPC.
Diagram oddaje istotę podejmowania decyzji przez tego agenta w oparciu o aktualną sytuację. Ponadto każda strzałka pokazuje przejście między stanami, jeśli warunek obok niej jest prawdziwy.
Przy każdej aktualizacji sprawdzamy aktualny stan agenta, przeglądamy listę przejść i jeśli warunki przejścia są spełnione, akceptuje on nowy stan. Na przykład każda ramka sprawdza, czy upłynął 10-sekundowy licznik czasu i jeśli tak, strażnik przechodzi ze stanu Bezczynności do Patrolowania. W ten sam sposób stan Ataku sprawdza zdrowie agenta - jeśli jest niskie, przechodzi w stan Ucieczki.
Jest to obsługa przejść między stanami, ale co z zachowaniem związanym z samymi stanami? Jeśli chodzi o implementację rzeczywistego zachowania dla konkretnego stanu, istnieją zazwyczaj dwa rodzaje „haczyków”, w których przypisujemy działania do FSM:
- Czynności, które okresowo wykonujemy dla bieżącego stanu.
- Działania, jakie podejmujemy podczas przejścia z jednego stanu do drugiego.
Przykłady dla pierwszego typu. Stan Patrolowanie będzie przesuwał agenta wzdłuż trasy patrolu w każdej klatce. Stan Atakowanie będzie próbował zainicjować atak w każdej klatce lub przejdzie do stanu, w którym jest to możliwe.
W przypadku drugiego typu rozważ przejście „jeśli wróg jest widoczny, a wróg jest zbyt silny, przejdź do stanu Szukanie pomocy. Agent musi wybrać, gdzie udać się po pomoc i przechowywać te informacje, aby stan Znajdowanie pomocy wiedział, dokąd się udać. Po znalezieniu pomocy agent powraca do stanu Atakowanie. W tym momencie będzie chciał poinformować sojusznika o zagrożeniu, dlatego może nastąpić akcja NotifyFriendOfThreat.
Po raz kolejny możemy spojrzeć na ten system przez pryzmat cyklu Poczuj/Myśl/Działaj. Sens jest zawarty w danych wykorzystywanych przez logikę przejścia. Pomyśl - przejścia dostępne w każdym stanie. A działanie realizowane jest poprzez czynności wykonywane okresowo w obrębie państwa lub w przejściach między stanami.
Czasami warunki przejścia w trybie ciągłego odpytywania mogą być kosztowne. Na przykład, jeśli każdy agent wykonuje złożone obliczenia w każdej klatce, aby określić, czy widzi wrogów i sprawdzić, czy może przejść ze stanu Patrolowanie do Ataku, zajmie to dużo czasu procesora.
Ważne zmiany w stanie świata można traktować jako zdarzenia, które będą przetwarzane w miarę ich pojawiania się. Zamiast sprawdzania przez FSM warunku przejścia „czy mój agent widzi gracza?” w każdej klatce, można skonfigurować osobny system tak, aby sprawdzał rzadziej (np. 5 razy na sekundę). W rezultacie po przejściu kontroli zostanie wyświetlony komunikat Player Seen.
Jest to przekazywane do FSM, który powinien teraz przejść do warunku odebrania zdarzenia Player Seen i odpowiednio zareagować. Wynikowe zachowanie jest takie samo, z wyjątkiem prawie niezauważalnego opóźnienia przed odpowiedzią. Jednak wydajność uległa poprawie w wyniku oddzielenia części Sense na oddzielną część programu.
Hierarchiczna maszyna skończona
Jednak praca z dużymi FSM nie zawsze jest wygodna. Jeśli chcemy rozszerzyć stan ataku, aby oddzielić atak wręcz i atak dystansowy, będziemy musieli zmienić przejścia ze wszystkich innych stanów prowadzących do stanu ataku (obecnego i przyszłego).
Prawdopodobnie zauważyłeś, że w naszym przykładzie jest dużo zduplikowanych przejść. Większość przejść w stanie bezczynności jest identyczna z przejściami w stanie patrolowania. Byłoby miło się nie powtarzać, zwłaszcza jeśli dodamy więcej podobnych stanów. Sensowne jest pogrupowanie biegu jałowego i patrolowania pod ogólną etykietą „bez walki”, gdzie istnieje tylko jeden wspólny zestaw przejść do stanów bojowych. Jeśli pomyślimy o tej etykiecie jako o stanie, wówczas Praca na biegu jałowym i Patrolowanie staną się podstanami. Przykład użycia osobnej tabeli przejść dla nowego podstanu niebojowego:
Główne stany:
Stan poza walką:
Oraz w formie diagramu:
To ten sam system, ale z nowym stanem niezwiązanym z walką, obejmującym bezczynność i patrolowanie. Z każdym stanem zawierającym FSM z podstanami (a te podstany z kolei zawierają własne FSM – i tak dalej tak długo, jak potrzeba), otrzymujemy Hierarchiczną Maszynę Skończoną Stanową, czyli HFSM (hierarchiczna maszyna skończona). Grupując stan niezwiązany z walką, wycięliśmy kilka zbędnych przejść. Możemy zrobić to samo dla dowolnych nowych stanów ze wspólnymi przejściami. Na przykład, jeśli w przyszłości rozszerzymy stan Ataku na stany Ataku Wręcz i Ataku Rakietowego, będą to podstany przechodzące między sobą w zależności od odległości od wroga i dostępności amunicji. W rezultacie złożone zachowania i podzachowania mogą być reprezentowane przy minimalnej liczbie podwójnych przejść.
Drzewo zachowań
Dzięki HFSM w prosty sposób tworzone są złożone kombinacje zachowań. Istnieje jednak niewielka trudność polegająca na tym, że podejmowanie decyzji w formie przepisów przejściowych jest ściśle powiązane ze stanem obecnym. W wielu grach właśnie to jest potrzebne. Ostrożne korzystanie z hierarchii stanów może zmniejszyć liczbę powtórzeń przejść. Ale czasami potrzebujesz reguł, które działają niezależnie od stanu, w którym się znajdujesz, lub które mają zastosowanie w prawie każdym stanie. Na przykład, jeśli zdrowie agenta spadnie do 25%, będziesz chciał, aby uciekł niezależnie od tego, czy walczył, był bezczynny, czy rozmawiał - będziesz musiał dodać ten warunek do każdego stanu. A jeśli Twój projektant będzie chciał później zmienić dolny próg zdrowia z 25% na 10%, trzeba będzie to zrobić ponownie.
Idealnie, sytuacja ta wymaga systemu, w którym decyzje o tym, „w jakim stanie się znaleźć”, podejmowane są poza samymi państwami, aby zmiany można było wprowadzać tylko w jednym miejscu i nie dotykać warunków przejściowych. Tutaj pojawiają się drzewa zachowań.
Istnieje kilka sposobów ich wdrożenia, ale istota jest mniej więcej taka sama dla wszystkich i przypomina drzewo decyzyjne: algorytm zaczyna się od węzła „głównego”, a drzewo zawiera węzły reprezentujące decyzje lub działania. Istnieje jednak kilka kluczowych różnic:
- Węzły zwracają teraz jedną z trzech wartości: powiodło się (jeśli zadanie zostało ukończone), nie powiodło się (jeśli nie można go uruchomić) lub działa (jeśli nadal działa i nie ma końcowego wyniku).
- Nie ma już węzłów decyzyjnych do wyboru pomiędzy dwiema alternatywami. Zamiast tego są to węzły dekoratora, które mają jeden węzeł podrzędny. Jeśli im się to uda, wykonują swój jedyny węzeł podrzędny.
- Węzły wykonujące akcje zwracają wartość Running, która reprezentuje wykonywane akcje.
Ten mały zestaw węzłów można połączyć, aby utworzyć dużą liczbę złożonych zachowań. Wyobraźmy sobie strażnika HFSM z poprzedniego przykładu jako drzewo zachowań:
Przy tej strukturze nie powinno być oczywistego przejścia ze stanów bezczynności/patrolowania do stanu ataku lub jakichkolwiek innych stanów. Jeśli wróg jest widoczny, a zdrowie postaci jest niskie, wykonanie zatrzyma się w węźle Ucieczki, niezależnie od tego, który węzeł był poprzednio wykonywany – Patrolowanie, Bezczynność, Atak czy jakikolwiek inny.
Drzewa zachowań są złożone — istnieje wiele sposobów ich tworzenia, a znalezienie właściwej kombinacji dekoratorów i węzłów złożonych może być wyzwaniem. Pojawiają się też pytania o to, jak często sprawdzać drzewo – czy chcemy przejść przez każdą jego część, czy tylko wtedy, gdy zmienił się któryś z warunków? Jak przechowujemy stan odnoszący się do węzłów – skąd wiemy, że byliśmy w stanie bezczynności przez 10 sekund lub skąd wiemy, które węzły wykonywały się ostatnim razem, abyśmy mogli poprawnie przetworzyć sekwencję?
Dlatego istnieje wiele wdrożeń. Na przykład w niektórych systemach węzły dekoratorów zastąpiono dekoratorami wbudowanymi. Dokonują ponownej oceny drzewa, gdy zmieniają się warunki dekoratora, pomagają łączyć węzły i zapewniają okresowe aktualizacje.
System oparty na użyteczności
Niektóre gry mają wiele różnych mechanik. Pożądane jest, aby otrzymały wszystkie korzyści wynikające z prostych i ogólnych zasad przejściowych, ale niekoniecznie w postaci pełnego drzewa zachowań. Zamiast mieć jasny zestaw wyborów lub drzewo możliwych działań, łatwiej jest przeanalizować wszystkie działania i wybrać najwłaściwsze w danym momencie.
Pomoże w tym właśnie system oparty na Utility. Jest to system, w którym agent ma wiele działań i wybiera, które z nich wykonać, na podstawie względnej użyteczności każdego z nich. Gdzie użyteczność jest arbitralną miarą tego, jak ważne lub pożądane jest, aby agent wykonał tę czynność.
Obliczona użyteczność akcji na podstawie aktualnego stanu i środowiska, agent może w każdej chwili sprawdzić i wybrać najbardziej odpowiedni inny stan. Jest to podobne do FSM, z wyjątkiem sytuacji, gdy przejścia są określane na podstawie oszacowania dla każdego potencjalnego stanu, w tym bieżącego. Pamiętaj, że wybieramy najbardziej przydatną akcję, aby przejść dalej (lub zostać, jeśli ją już wykonaliśmy). Aby zapewnić większą różnorodność, może to być wyważony, ale losowy wybór z małej listy.
System przypisuje dowolny zakres wartości użyteczności – na przykład od 0 (całkowicie niepożądane) do 100 (całkowicie pożądane). Każda akcja ma szereg parametrów, które wpływają na obliczenie tej wartości. Wracając do przykładu naszego opiekuna:
Przejścia pomiędzy akcjami są niejednoznaczne – każdy stan może następować po każdym innym. Priorytety akcji znajdują się w zwróconych wartościach użyteczności. Jeśli wróg jest widoczny i jest on silny, a zdrowie postaci jest niskie, wówczas zarówno Ucieczka, jak i FindingHelp zwrócą wysokie, niezerowe wartości. W takim przypadku FindingHelp będzie zawsze wyższa. Podobnie działania niezwiązane z walką nigdy nie zwracają więcej niż 50, więc zawsze będą niższe niż działania bojowe. Trzeba to wziąć pod uwagę przy tworzeniu akcji i obliczaniu ich użyteczności.
W naszym przykładzie akcje zwracają stałą wartość lub jedną z dwóch stałych wartości. Bardziej realistyczny system zwróciłby oszacowanie na podstawie ciągłego zakresu wartości. Na przykład akcja Ucieczki zwraca wyższe wartości użyteczności, jeśli zdrowie agenta jest niskie, a akcja Ataku zwraca niższe wartości użyteczności, jeśli wróg jest zbyt silny. Z tego powodu akcja Ucieczki ma pierwszeństwo przed Atakiem w każdej sytuacji, w której agent czuje, że nie ma wystarczającego zdrowia, aby pokonać wroga. Pozwala to na priorytetyzację działań w oparciu o dowolną liczbę kryteriów, dzięki czemu podejście to jest bardziej elastyczne i zmienne niż drzewo zachowań lub FSM.
Każda akcja ma wiele warunków do obliczenia programu. Można je zapisać w języku skryptowym lub jako serię wzorów matematycznych. The Sims, które symuluje codzienność postaci, dodaje dodatkową warstwę kalkulacji – agent otrzymuje szereg „motywacji”, które wpływają na oceny użyteczności. Jeśli postać jest głodna, z czasem stanie się jeszcze bardziej głodna, a wartość użyteczna akcji Zjedz Jedzenie będzie rosła, dopóki postać jej nie wykona, zmniejszając poziom głodu i przywracając wartość Zjedz Jedzenie do zera.
Idea wybierania działań w oparciu o system ocen jest dość prosta, dlatego system oparty na Utility może być stosowany jako część procesów decyzyjnych AI, a nie jako ich całkowity zamiennik. Drzewo decyzyjne może poprosić o ocenę użyteczności dwóch węzłów podrzędnych i wybrać wyższy. Podobnie drzewo zachowań może zawierać złożony węzeł Utility służący do oceny użyteczności działań w celu podjęcia decyzji, które dziecko ma zostać wykonane.
Ruch i nawigacja
W poprzednich przykładach mieliśmy platformę, którą przesuwaliśmy w lewo lub w prawo, oraz strażnika, który patrolował lub atakował. Ale jak dokładnie radzimy sobie z przemieszczaniem agentów w pewnym okresie czasu? Jak ustalamy prędkość, jak omijamy przeszkody i jak planujemy trasę, gdy dotarcie do celu jest trudniejsze niż samo poruszanie się po linii prostej? Spójrzmy na to.
Управление
Na początkowym etapie założymy, że każdy agent ma wartość prędkości, która zawiera informację o tym, jak szybko się porusza i w jakim kierunku. Można ją mierzyć w metrach na sekundę, kilometrach na godzinę, pikselach na sekundę itp. Przywołując pętlę Poczuj/Myśl/Działaj, możemy sobie wyobrazić, że część Myśl wybiera prędkość, a część Działaj stosuje tę prędkość do agenta. Zazwyczaj gry posiadają system fizyki, który wykonuje to zadanie za Ciebie, poznając wartość prędkości każdego obiektu i dostosowując ją. Dlatego możesz zostawić AI z jednym zadaniem – zdecydować, jaką prędkość powinien mieć agent. Jeśli wiesz, gdzie powinien znajdować się agent, to musisz przesunąć go we właściwym kierunku z zadaną prędkością. Bardzo trywialne równanie:
pożądana_travel = pozycja_docelowa – pozycja_agenta
Wyobraź sobie świat 2D. Agent znajduje się w punkcie (-2,-2), miejsce docelowe znajduje się gdzieś na północnym wschodzie w punkcie (30, 20), a wymagana droga, aby agent się tam dostał, to (32, 22). Załóżmy, że te pozycje są mierzone w metrach – jeśli przyjmiemy, że prędkość agenta wynosi 5 metrów na sekundę, wówczas przeskalujemy nasz wektor przemieszczenia i otrzymamy prędkość w przybliżeniu (4.12, 2.83). Przy tych parametrach agent dotrze do celu w niemal 8 sekund.
Wartości możesz przeliczyć w dowolnym momencie. Jeżeli agent był w połowie drogi do celu, ruch byłby o połowę krótszy, ale ponieważ maksymalna prędkość agenta wynosi 5 m/s (zdecydowaliśmy o tym powyżej), prędkość będzie taka sama. Działa to również w przypadku ruchomych celów, umożliwiając agentowi wprowadzanie niewielkich zmian w miarę ich ruchu.
Chcemy jednak większej różnorodności – na przykład powolnego zwiększania prędkości, aby symulować zmianę postaci ze stojącej do biegnącej. To samo można zrobić na końcu, przed zatrzymaniem. Cechy te nazywane są zachowaniami sterującymi, a każde z nich ma specyficzne nazwy: szukanie, uciekanie, przybycie itp. Pomysł jest taki, że siły przyspieszenia można zastosować do prędkości agenta w oparciu o porównanie pozycji agenta i aktualnej prędkości z celem w aby zastosować różne metody dochodzenia do celu.
Każde zachowanie ma nieco inny cel. Seek and Arrival to sposoby na przeniesienie agenta do miejsca docelowego. Unikanie przeszkód i separacja dostosowują ruch agenta tak, aby omijał przeszkody na drodze do celu. Dopasowanie i spójność sprawiają, że agenci poruszają się razem. Można zsumować dowolną liczbę różnych zachowań układu kierowniczego, aby utworzyć pojedynczy wektor ścieżki, uwzględniający wszystkie czynniki. Agent korzystający z zachowań Przybycie, Oddzielenie i Unikanie przeszkód, aby trzymać się z daleka od ścian i innych agentów. Takie podejście sprawdza się w otwartych lokalizacjach bez zbędnych szczegółów.
W trudniejszych warunkach gorzej sprawdza się dodanie różnych zachowań – np. agent może utknąć w ścianie w wyniku konfliktu pomiędzy Przybyciem a Unikaniem przeszkód. Dlatego należy rozważyć opcje bardziej złożone niż zwykłe dodanie wszystkich wartości. Sposób jest następujący: zamiast sumować skutki każdego zachowania, możesz rozważyć ruch w różnych kierunkach i wybrać najlepszą opcję.
Jednakże w złożonym środowisku pełnym ślepych zaułków i możliwości wyboru drogi, będziemy potrzebować czegoś jeszcze bardziej zaawansowanego.
Znalezienie ścieżki
Zachowania związane z kierowaniem świetnie sprawdzają się w przypadku prostego poruszania się na otwartej przestrzeni (boisko piłkarskie lub arena), gdzie dotarcie z punktu A do punktu B to prosta ścieżka z jedynie niewielkimi objazdami wokół przeszkód. W przypadku skomplikowanych tras potrzebujemy pathfindingu, czyli sposobu poznawania świata i decydowania o trasie przez niego.
Najprościej jest przyłożyć siatkę do każdego pola obok agenta i ocenić, który z nich może się poruszyć. Jeśli jeden z nich jest celem podróży, podążaj trasą od każdego kwadratu do poprzedniego, aż dotrzesz do początku. To jest trasa. W przeciwnym razie powtarzaj proces z innymi pobliskimi kwadratami, aż znajdziesz cel podróży lub skończą Ci się pola (co oznacza, że nie ma możliwej trasy). Jest to formalnie znane jako wyszukiwanie wszerz lub BFS (algorytm wyszukiwania wszerz). Na każdym kroku rozgląda się we wszystkich kierunkach (stąd szerokość, „szerokość”). Przestrzeń poszukiwań jest jak czoło fali, które porusza się, aż dotrze do żądanego miejsca – przestrzeń poszukiwań rozszerza się z każdym krokiem, aż do uwzględnienia punktu końcowego, po czym można ją prześledzić z powrotem do początku.
W rezultacie otrzymasz listę kwadratów, wzdłuż których zostanie utworzona żądana trasa. To jest ścieżka (stąd pathfinding) – lista miejsc, które odwiedzi agent, podążając do celu.
Biorąc pod uwagę, że znamy położenie każdego kwadratu na świecie, możemy używać zachowań sterujących do poruszania się po ścieżce - od węzła 1 do węzła 2, następnie od węzła 2 do węzła 3 i tak dalej. Najprostszą opcją jest skierowanie się w stronę środka kolejnego pola, ale jeszcze lepszą opcją jest zatrzymanie się w połowie krawędzi pomiędzy obecnym kwadratem a następnym. Dzięki temu agent będzie mógł pokonywać zakręty na ostrych zakrętach.
Algorytm BFS ma również wady - bada tyle samo kwadratów w „złym” kierunku, co we „właściwym” kierunku. W tym miejscu do gry wchodzi bardziej złożony algorytm o nazwie A* (gwiazda A). Działa to w ten sam sposób, ale zamiast na ślepo sprawdzać sąsiednie kwadraty (następnie sąsiadów sąsiadów, potem sąsiadów sąsiadów itd.), zbiera węzły na listę i sortuje je tak, że następnym sprawdzanym węzłem jest zawsze ten taki, który prowadzi najkrótszą trasą. Węzły są sortowane w oparciu o heurystykę, która uwzględnia dwie rzeczy — „koszt” hipotetycznej trasy do żądanego kwadratu (w tym wszelkie koszty podróży) oraz szacunkową odległość tego kwadratu od miejsca docelowego (co wpływa na wyszukiwanie w dobry kierunek).
Ten przykład pokazuje, że agent eksploruje jedno pole na raz, za każdym razem wybierając sąsiednie, które jest najbardziej obiecujące. Wynikowa ścieżka jest taka sama jak w BFS, ale w procesie uwzględniono mniejszą liczbę kwadratów – co ma duży wpływ na wydajność gry.
Ruch bez siatki
Jednak większość gier nie jest ułożona na siatce i często nie da się tego zrobić bez utraty realizmu. Potrzebne są kompromisy. Jakiej wielkości powinny być kwadraty? Za duże i nie będą w stanie poprawnie przedstawić małych korytarzy czy zakrętów, za małe i będzie za dużo kwadratów do przeszukania, co ostatecznie zajmie dużo czasu.
Pierwszą rzeczą, którą należy zrozumieć, jest to, że siatka daje nam wykres połączonych węzłów. Algorytmy A* i BFS faktycznie działają na wykresach i w ogóle nie przejmują się naszą siatką. Węzły moglibyśmy umieścić w dowolnym miejscu świata gry: dopóki istnieje połączenie pomiędzy dowolnymi dwoma połączonymi węzłami, a także pomiędzy punktem początkowym i końcowym oraz co najmniej jednym z węzłów, algorytm będzie działał tak samo dobrze jak wcześniej. Nazywa się to często systemem punktów orientacyjnych, ponieważ każdy węzeł reprezentuje znaczącą pozycję na świecie, która może być częścią dowolnej liczby hipotetycznych ścieżek.
Przykład 1: węzeł w każdym kwadracie. Wyszukiwanie rozpoczyna się od węzła, w którym znajduje się agent, a kończy w węźle żądanego kwadratu.
Przykład 2: Mniejszy zestaw węzłów (punktów trasy). Wyszukiwanie rozpoczyna się od kwadratu agenta, przechodzi przez wymaganą liczbę węzłów, a następnie kontynuuje się do miejsca docelowego.
Jest to całkowicie elastyczny i wydajny system. Należy jednak zachować ostrożność przy podejmowaniu decyzji, gdzie i jak umieścić punkt orientacyjny, w przeciwnym razie agenci mogą po prostu nie widzieć najbliższego punktu i nie będą mogli rozpocząć wyznaczania trasy. Byłoby łatwiej, gdybyśmy mogli automatycznie umieszczać punkty orientacyjne na podstawie geometrii świata.
W tym miejscu pojawia się siatka nawigacyjna lub navmesh (siatka nawigacyjna). Zwykle jest to dwuwymiarowa siatka trójkątów nałożona na geometrię świata – wszędzie tam, gdzie agent może chodzić. Każdy z trójkątów siatki staje się węzłem na wykresie i ma maksymalnie trzy sąsiadujące ze sobą trójkąty, które stają się sąsiadującymi węzłami na wykresie.
Ten obrazek jest przykładem z silnika Unity - przeanalizował on geometrię świata i stworzył navmesh (na zrzucie ekranu w kolorze jasnoniebieskim). Każdy wielokąt w siatce nawigacyjnej to obszar, na którym agent może stać lub przemieszczać się z jednego wielokąta do drugiego. W tym przykładzie wielokąty są mniejsze niż piętra, na których się znajdują - robi się to w celu uwzględnienia wielkości środka, który będzie wystawał poza jego nominalne położenie.
Możemy wyszukać trasę przez tę siatkę, ponownie używając algorytmu A*. Da nam to niemal idealną trasę na świecie, która uwzględnia całą geometrię i nie wymaga zbędnych węzłów i tworzenia waypointów.
Pathfinding to zbyt szeroki temat, dla którego jedna sekcja artykułu nie wystarczy. Jeśli chcesz przestudiować to bardziej szczegółowo, to pomoże .
planowanie
Dzięki funkcji znajdowania ścieżki nauczyliśmy się, że czasami nie wystarczy po prostu wybrać kierunek i ruszyć – musimy wybrać trasę i wykonać kilka zakrętów, aby dotrzeć do upragnionego celu. Możemy uogólnić tę myśl: osiągnięcie celu to nie tylko kolejny krok, ale cała sekwencja, w której czasami trzeba spojrzeć w przód na kilka kroków, aby dowiedzieć się, jaki powinien być pierwszy. Nazywa się to planowaniem. Znalezienie ścieżki można uznać za jedno z kilku rozszerzeń planowania. Jeśli chodzi o cykl Poczuj/Myśl/Działaj, w tym miejscu część Myśl planuje wiele części Działaj na przyszłość.
Spójrzmy na przykład gry planszowej Magic: The Gathering. Na początek ruszamy z następującym zestawem kart w rękach:
- Bagno - Daje 1 czarną manę (karta lądu).
- Las - daje 1 zieloną manę (karta lądu).
- Zbiegły Czarodziej – do przywołania wymaga 1 niebieskiej many.
- Elficki mistyk – do przyzwania wymaga 1 zielonej many.
Dla ułatwienia ignorujemy pozostałe trzy karty. Zgodnie z zasadami gracz może zagrać 1 kartę lądu na turę, może „tapować” tę kartę, aby wydobyć z niej manę, a następnie rzucać zaklęcia (w tym przywoływać stworzenie) w zależności od ilości many. W tej sytuacji gracz prowadzący ludzi wie, że musi zagrać w Las, wybrać 1 zieloną manę, a następnie przywołać Elfickiego Mistyka. Ale jak sztuczna inteligencja gry może to rozgryźć?
Łatwe planowanie
Trywialne podejście polega na wypróbowywaniu każdej akcji po kolei, aż nie pozostaną już żadne odpowiednie. Patrząc na karty, sztuczna inteligencja widzi, w co może zagrać Swamp. I on to gra. Czy pozostały jeszcze jakieś akcje w tej turze? Nie może przywołać ani Elfickiego Mistyka, ani Zbiegłego Czarodzieja, ponieważ do ich przywołania wymagają odpowiednio zielonej i niebieskiej many, podczas gdy Bagno zapewnia tylko czarną manę. I nie będzie już mógł grać w Forest, ponieważ grał już w Swamp. Zatem sztuczna inteligencja gry postępowała zgodnie z zasadami, ale zrobiła to słabo. Można ulepszyć.
W planowaniu można znaleźć listę działań, które doprowadzą grę do pożądanego stanu. Tak jak każde pole na ścieżce miało sąsiadów (przy znajdowaniu ścieżki), tak każda akcja w planie również ma sąsiadów lub następców. Możemy szukać tych działań i kolejnych działań, aż osiągniemy pożądany stan.
W naszym przykładzie pożądanym rezultatem jest „przywołanie stworzenia, jeśli to możliwe”. Na początku tury widzimy tylko dwie możliwe akcje, na które pozwalają zasady gry:
1. Zagraj w Swamp (rezultat: Swamp w grze)
2. Zagraj w Las (rezultat: Las w grze)
Każda podjęta akcja może prowadzić do dalszych działań i zamykania kolejnych, ponownie w zależności od zasad gry. Wyobraź sobie, że graliśmy w Bagno - w następnym kroku usuniemy Bagno (już w to graliśmy), a to także usunie Las (ponieważ zgodnie z zasadami możesz zagrać jedną kartę lądu na turę). Następnie AI dodaje zdobycie 1 czarnej many jako kolejny krok, ponieważ nie ma innych opcji. Jeśli pójdzie dalej i wybierze Tap the Swamp, otrzyma 1 jednostkę czarnej many i nie będzie mógł nic z nią zrobić.
1. Zagraj w Swamp (rezultat: Swamp w grze)
1.1 Bagno „Tap” (rezultat: „Tap” bagna, +1 jednostka czarnej many)
Brak dostępnych działań - KONIEC
2. Zagraj w Las (rezultat: Las w grze)
Lista działań była krótka, znaleźliśmy się w ślepym zaułku. Powtarzamy proces w następnym kroku. Gramy w Las, otwieramy akcję „zdobądź 1 zieloną manę”, co z kolei otworzy trzecią akcję - przywołanie Elfickiego Mistyka.
1. Zagraj w Swamp (rezultat: Swamp w grze)
1.1 Bagno „Tap” (rezultat: „Tap” bagna, +1 jednostka czarnej many)
Brak dostępnych działań - KONIEC
2. Zagraj w Las (rezultat: Las w grze)
2.1 Las „Tap” (rezultat: Las jest „tapowany”, +1 jednostka zielonej many)
2.1.1 Przywołanie Elfickiego Mistyka (rezultat: Elficki Mistyk w grze, -1 zielonej many)
Brak dostępnych działań - KONIEC
W końcu zbadaliśmy wszystkie możliwe działania i znaleźliśmy plan przywołania stworzenia.
To bardzo uproszczony przykład. Wskazane jest, aby wybrać najlepszy możliwy plan, a nie byle jaki plan spełniający jakieś kryteria. Ogólnie rzecz biorąc, możliwa jest ocena potencjalnych planów w oparciu o wynik lub ogólne korzyści z ich wdrożenia. Możesz zdobyć 1 punkt za zagranie karty lądu i 3 punkty za przywołanie stworzenia. Gra na Bagnie będzie planem za 1 punkt. A grając w Las → Dotknij lasu → przywołaj Elfickiego Mistyka, natychmiast otrzymasz 4 punkty.
Tak właśnie działa planowanie w Magic: The Gathering, ale ta sama logika ma zastosowanie w innych sytuacjach. Na przykład przesuwanie pionka, aby zrobić miejsce dla gońca w szachach. Możesz też schować się za ścianą i bezpiecznie strzelać w XCOM w ten sposób. Ogólnie rzecz biorąc, masz pomysł.
Ulepszone planowanie
Czasami jest zbyt wiele potencjalnych działań, aby rozważyć każdą możliwą opcję. Wracając do przykładu z Magic: The Gathering: załóżmy, że w grze i na twojej ręce znajduje się kilka kart lądów i stworzeń – liczba możliwych kombinacji ruchów może sięgać dziesiątek. Istnieje kilka rozwiązań tego problemu.
Pierwszą metodą jest łączenie wsteczne. Zamiast próbować wszystkich kombinacji, lepiej zacząć od wyniku końcowego i spróbować znaleźć bezpośrednią drogę. Zamiast przechodzić od korzenia drzewa do konkretnego liścia, poruszamy się w przeciwnym kierunku – od liścia do korzenia. Ta metoda jest łatwiejsza i szybsza.
Jeśli wróg ma 1 punkt zdrowia, możesz znaleźć plan „Zadaj 1 lub więcej obrażeń”. Aby to osiągnąć należy spełnić szereg warunków:
1. Zaklęcie może spowodować obrażenia - musi być w ręku.
2. Aby rzucić zaklęcie, potrzebujesz many.
3. Aby zdobyć manę, musisz zagrać kartę lądu.
4. Aby zagrać kartę lądu, musisz ją mieć na ręce.
Innym sposobem jest wyszukiwanie najpierw najlepszego. Zamiast wypróbowywać wszystkie ścieżki, wybieramy tę najodpowiedniejszą. Najczęściej ta metoda daje optymalny plan bez zbędnych kosztów poszukiwań. A* to forma najlepszego pierwszego wyszukiwania - badając od początku najbardziej obiecujące trasy, może już znaleźć najlepszą ścieżkę bez konieczności sprawdzania innych opcji.
Ciekawą i coraz popularniejszą opcją wyszukiwania metodą „najpierw jest pierwsze” jest wyszukiwanie drzew Monte Carlo. Zamiast zgadywać, które plany są lepsze od innych przy każdym kolejnym działaniu, algorytm wybiera losowo następców na każdym kroku, aż do samego końca (kiedy plan zakończył się zwycięstwem lub porażką). Wynik końcowy służy następnie do zwiększania lub zmniejszania wagi poprzednich opcji. Powtarzając ten proces kilka razy z rzędu, algorytm dobrze szacuje, jaki będzie najlepszy następny ruch, nawet jeśli sytuacja się zmieni (jeśli wróg podejmie działania, które będą przeszkadzać graczowi).
Żadna opowieść o planowaniu w grach nie byłaby kompletna bez planowania działań zorientowanych na cel, czyli GOAP (planowanie działań zorientowanych na cel). Jest to szeroko stosowana i omawiana metoda, ale poza kilkoma wyróżniającymi szczegółami jest to w zasadzie metoda łączenia wstecznego, o której mówiliśmy wcześniej. Jeśli celem było „zniszczenie gracza”, a gracz znajduje się za osłoną, plan mógłby być następujący: zniszczyć granatem → zdobyć go → rzucić.
Zwykle jest kilka celów, każdy z własnym priorytetem. Jeśli cel o najwyższym priorytecie nie może zostać zrealizowany (żadna kombinacja akcji nie tworzy planu „zabić gracza”, ponieważ gracz nie jest widoczny), sztuczna inteligencja powróci do celów o niższym priorytecie.
Szkolenie i adaptacja
Powiedzieliśmy już, że sztuczna inteligencja w grach zazwyczaj nie korzysta z uczenia maszynowego, ponieważ nie nadaje się do zarządzania agentami w czasie rzeczywistym. Nie oznacza to jednak, że nie można pożyczyć czegoś z tego obszaru. Chcemy przeciwnika w strzelance, od którego możemy się czegoś nauczyć. Na przykład dowiedz się o najlepszych pozycjach na mapie. Lub przeciwnik w bijatyce, który blokowałby często używane przez gracza ruchy kombinowane, motywując go do użycia innych. Dlatego uczenie maszynowe może być bardzo przydatne w takich sytuacjach.
Statystyki i prawdopodobieństwa
Zanim przejdziemy do skomplikowanych przykładów, zobaczmy, jak daleko możemy się posunąć, wykonując kilka prostych pomiarów i wykorzystując je do podejmowania decyzji. Np. strategia czasu rzeczywistego – jak ustalić, czy gracz może przeprowadzić atak już w pierwszych minutach gry i jaką obronę przed tym przygotować? Możemy przestudiować przeszłe doświadczenia gracza, aby zrozumieć, jakie mogą być przyszłe reakcje. Na początek nie mamy takich surowych danych, ale możemy je zebrać – za każdym razem, gdy AI gra przeciwko człowiekowi, potrafi zarejestrować czas pierwszego ataku. Po kilku sesjach otrzymamy średni czas potrzebny graczowi na atak w przyszłości.
Jest też problem ze średnimi wartościami: jeśli gracz 20 razy śpieszył się i 20 razy grał wolno, to wymagane wartości będą gdzieś pośrodku, a to nie da nam nic przydatnego. Jednym z rozwiązań jest ograniczenie danych wejściowych – można uwzględnić ostatnie 20 sztuk.
Podobne podejście stosuje się przy szacowaniu prawdopodobieństwa określonych działań, zakładając, że przeszłe preferencje gracza będą takie same w przyszłości. Jeśli gracz zaatakuje nas pięciokrotnie kulą ognia, dwa razy błyskawicą i raz wręcz, to oczywiste jest, że woli kulę ognia. Ekstrapolujmy i zobaczmy prawdopodobieństwo użycia różnych broni: kula ognia=62,5%, błyskawica=25% i walka wręcz=12,5%. Nasza sztuczna inteligencja w grze musi przygotować się na ochronę przed ogniem.
Inną ciekawą metodą jest wykorzystanie Naiwnego Klasyfikatora Bayesa do badania dużych ilości danych wejściowych i klasyfikowania sytuacji tak, aby sztuczna inteligencja zareagowała w pożądany sposób. Klasyfikatory Bayesa są najbardziej znane ze swojego zastosowania w filtrach spamu e-mailowego. Tam sprawdzają słowa, porównują je z miejscami, w których te słowa pojawiały się wcześniej (w spamie lub nie) i wyciągają wnioski na temat przychodzących e-maili. Możemy zrobić to samo, nawet przy mniejszej liczbie wejść. W oparciu o wszystkie przydatne informacje, które widzi sztuczna inteligencja (takie jak tworzone jednostki wroga, jakich używa zaklęć lub jakie technologie badają) oraz wynik końcowy (wojna lub pokój, pośpiech lub obrona itp.) - wybierzemy pożądane zachowanie AI.
Wszystkie te metody szkoleniowe są wystarczające, jednak zaleca się ich stosowanie w oparciu o dane testowe. Sztuczna inteligencja nauczy się dostosowywać do różnych strategii, z których korzystali Twoi testerzy. Sztuczna inteligencja, która dopasowuje się do gracza po premierze, może stać się zbyt przewidywalna lub zbyt trudna do pokonania.
Adaptacja oparta na wartościach
Biorąc pod uwagę zawartość naszego świata gry i zasady, możemy zmienić zestaw wartości wpływających na podejmowanie decyzji, zamiast po prostu korzystać z danych wejściowych. My to robimy:
- Pozwól AI zbierać dane o stanie świata i kluczowych wydarzeniach podczas rozgrywki (jak wyżej).
- Zmieńmy kilka ważnych wartości w oparciu o te dane.
- Nasze decyzje realizujemy w oparciu o przetwarzanie lub ocenę tych wartości.
Na przykład agent ma do wyboru kilka pokoi na mapie strzelanki pierwszoosobowej. Każdy pokój ma swoją wartość, która określa, jak pożądane jest jego odwiedzenie. Sztuczna inteligencja losowo wybiera pokój, do którego się uda, na podstawie wartości. Agent zapamiętuje wówczas, w którym pokoju został zabity i zmniejsza jego wartość (prawdopodobieństwo, że tam wróci). Podobnie jest w sytuacji odwrotnej – jeśli agent zniszczy wielu przeciwników, wówczas wartość pomieszczenia wzrasta.
Model Markowa
A gdybyśmy wykorzystali zebrane dane do przewidywania? Jeśli przez określony czas będziemy pamiętać każdy pokój, w którym widzimy gracza, będziemy w stanie przewidzieć, do którego pokoju gracz może się udać. Śledząc i rejestrując ruchy gracza po pokojach (wartości), możemy je przewidzieć.
Weźmy trzy pokoje: czerwony, zielony i niebieski. A także obserwacje, które zanotowaliśmy podczas oglądania sesji gry:
Liczba obserwacji w każdym pomieszczeniu jest prawie równa - nadal nie wiemy, gdzie zrobić dobre miejsce na zasadzkę. Zbieranie statystyk komplikuje także odradzanie się graczy, którzy pojawiają się równomiernie na całej mapie. Ale dane o kolejnym pomieszczeniu, do którego wejdą po pojawieniu się na mapie, są już przydatne.
Widać, że zielony pokój odpowiada graczom – większość osób przenosi się do niego z czerwonego pokoju, z czego 50% pozostaje tam dalej. Pokój niebieski natomiast nie jest popularny, prawie nikt do niego nie chodzi, a jeśli już, to nie zostaje tam długo.
Dane mówią nam jednak coś ważniejszego – kiedy gracz znajdzie się w niebieskim pokoju, następne pomieszczenie, w którym go zobaczymy, będzie czerwone, a nie zielone. Mimo że zielony pokój jest bardziej popularny niż czerwony, sytuacja zmienia się, jeśli gracz znajdzie się w niebieskim pokoju. Następny stan (czyli pokój, do którego trafi gracz) zależy od stanu poprzedniego (czyli pokoju, w którym aktualnie znajduje się gracz). Ponieważ badamy zależności, dokonamy dokładniejszych przewidywań, niż gdybyśmy po prostu liczyli obserwacje niezależnie.
Przewidywanie przyszłego stanu na podstawie danych ze stanu przeszłego nazywa się modelem Markowa, a takie przykłady (z pokojami) nazywane są łańcuchami Markowa. Ponieważ wzorce reprezentują prawdopodobieństwo zmian pomiędzy kolejnymi stanami, są one wizualnie wyświetlane jako FSM z prawdopodobieństwem wokół każdego przejścia. Wcześniej używaliśmy FSM do przedstawienia stanu behawioralnego, w jakim znajdował się agent, ale koncepcja ta rozciąga się na każdy stan, niezależnie od tego, czy jest on powiązany z agentem, czy nie. W tym przypadku stany reprezentują pokój, w którym przebywa agent:
Jest to prosty sposób przedstawienia względnego prawdopodobieństwa zmian stanu, dający AI pewną zdolność przewidywania następnego stanu. Możesz przewidzieć kilka kroków do przodu.
Jeśli gracz znajduje się w zielonym pomieszczeniu, istnieje 50% szans, że pozostanie tam następnym razem, gdy zostanie zaobserwowany. Ale jakie są szanse, że nadal tam będzie, nawet później? Nie tylko istnieje szansa, że gracz po dwóch obserwacjach pozostał w green roomie, ale jest też szansa, że wyszedł i wrócił. Oto nowa tabela uwzględniająca nowe dane:
Pokazuje, że szansa zobaczenia gracza w zielonym pokoju po dwóch obserwacjach będzie równa 51% - 21%, że będzie on z czerwonego pokoju, 5% z nich, że gracz odwiedzi niebieskie pomieszczenie pomiędzy nimi, oraz 25%, których gracz nie opuści zielonego pokoju.
Tabela jest po prostu narzędziem wizualnym – procedura wymaga jedynie pomnożenia prawdopodobieństw na każdym kroku. Oznacza to, że możesz patrzeć daleko w przyszłość z jednym zastrzeżeniem: zakładamy, że szansa na wejście do pokoju zależy wyłącznie od tego, w którym pokoju się aktualnie znajdujesz. Nazywa się to własnością Markowa – przyszły stan zależy tylko od teraźniejszości. Ale to nie jest w stu procentach dokładne. Gracze mogą zmieniać decyzje w zależności od innych czynników: poziomu zdrowia czy ilości amunicji. Ponieważ nie rejestrujemy tych wartości, nasze prognozy będą mniej dokładne.
N-gramów
A co powiesz na przykład bijatyki i przewidywania kombinacji ruchów gracza? Ten sam! Ale zamiast jednego stanu lub zdarzenia przeanalizujemy całe sekwencje składające się na kombinację ciosów.
Jednym ze sposobów osiągnięcia tego jest przechowywanie każdego wejścia (takiego jak kopnięcie, uderzenie lub blok) w buforze i zapisanie całego bufora jako zdarzenia. Tak więc gracz wielokrotnie naciska Kick, Kick, Punch, aby użyć ataku SuperDeathFist, system AI przechowuje wszystkie dane wejściowe w buforze i zapamiętuje trzy ostatnie użyte w każdym kroku.
(Linie pogrubione oznaczają moment, w którym gracz uruchamia atak SuperDeathFist.)
Sztuczna inteligencja zobaczy wszystkie opcje, gdy gracz wybierze Kopnięcie, a następnie kolejne Kopnięcie, a następnie zauważy, że następnym wejściem jest zawsze Uderzenie. Umożliwi to agentowi przewidzenie kombinacji ruchu SuperDeathFist i zablokowanie jej, jeśli to możliwe.
Te sekwencje zdarzeń nazywane są N-gramami, gdzie N jest liczbą przechowywanych elementów. W poprzednim przykładzie był to 3 gram (trygram), co oznacza: pierwsze dwa wpisy służą do przewidzenia trzeciego. Odpowiednio w przypadku 5 gramów pierwsze cztery wpisy przewidują piąty i tak dalej.
Projektant musi ostrożnie wybierać wielkość N-gramów. Mniejsze N wymaga mniej pamięci, ale przechowuje także mniej historii. Na przykład 2-gramowy (bigram) zarejestruje Kick, Kick lub Kick, Punch, ale nie będzie mógł zapisać Kick, Kick, Punch, więc sztuczna inteligencja nie zareaguje na kombinację SuperDeathFist.
Z drugiej strony większe liczby wymagają więcej pamięci, a sztuczna inteligencja będzie trudniejsza do wytrenowania, ponieważ możliwych opcji będzie znacznie więcej. Gdybyś miał trzy możliwe wejścia: kopnięcie, uderzenie lub blok, a my użylibyśmy 10 gramów, byłoby to około 60 tysięcy różnych opcji.
Model bigramu to prosty łańcuch Markowa - każda para stan przeszły/stan bieżący jest bigramem i na podstawie pierwszego można przewidzieć drugi stan. 3-gramowe i większe N-gramy można również traktować jako łańcuchy Markowa, w których wszystkie elementy (z wyjątkiem ostatniego w N-gramie) razem tworzą pierwszy stan, a ostatni element drugi. Przykład gry walki pokazuje szansę przejścia ze stanu kopnięcia i kopnięcia do stanu kopnięcia i uderzenia. Traktując wiele wpisów historii wprowadzania jako pojedynczą jednostkę, zasadniczo przekształcamy sekwencję wejściową w część całego stanu. Daje nam to właściwość Markowa, która pozwala nam używać łańcuchów Markowa do przewidywania następnego sygnału wejściowego i odgadnięcia, jaki będzie następny ruch combo.
wniosek
Rozmawialiśmy o najpopularniejszych narzędziach i podejściach w rozwoju sztucznej inteligencji. Przyjrzeliśmy się także sytuacjom, w których należy ich użyć i gdzie są szczególnie przydatne.
To powinno wystarczyć, aby zrozumieć podstawy sztucznej inteligencji w grach. Ale oczywiście to nie wszystkie metody. Do mniej popularnych, ale nie mniej skutecznych zaliczają się:
- algorytmy optymalizacyjne, w tym wspinaczka górska, zjazdy gradientowe i algorytmy genetyczne
- algorytmy wyszukiwania/harmonogramu kontradyktoryjnego (przycinanie minimax i alfa-beta)
- metody klasyfikacji (perceptrony, sieci neuronowe i maszyny wektorów nośnych)
- systemy przetwarzania percepcji i pamięci agentów
- architektoniczne podejście do AI (systemy hybrydowe, architektury podzbiorów i inne sposoby nakładania się systemów AI)
- narzędzia animacyjne (planowanie i koordynacja ruchu)
- czynniki wydajności (poziom szczegółowości, czas i algorytmy podziału czasu)
Zasoby internetowe na ten temat:
1. GameDev.net ma a także .
2. zawiera wiele prezentacji i artykułów na różnorodne tematy związane z rozwojem sztucznej inteligencji w grach.
3. zawiera tematy ze szczytu GDC AI, z których wiele jest dostępnych bezpłatnie.
4. Przydatne materiały można znaleźć także na stronie .
5. Tommy Thompson, badacz sztucznej inteligencji i twórca gier, nagrywa filmy na YouTube z wyjaśnieniem i badaniem sztucznej inteligencji w grach komercyjnych.
Książki na ten temat:
1. Seria książek Game AI Pro to zbiór krótkich artykułów wyjaśniających, jak wdrożyć określone funkcje lub jak rozwiązać określone problemy.
2. Seria AI Game Programming Wisdom jest poprzedniczką serii Game AI Pro. Zawiera starsze metody, ale prawie wszystkie są aktualne nawet dzisiaj.
3. to jeden z podstawowych tekstów dla każdego, kto chce zrozumieć ogólną dziedzinę sztucznej inteligencji. To nie jest książka o tworzeniu gier – uczy podstaw sztucznej inteligencji.
Źródło: www.habr.com