Unity3d QuickTip – czyli szybkie porady, rozwiązania częstych problemów i sztuczki w Unity3d!

Dzisiejszy odcinek: Drzewa Decyzyjne

Uwaga! Jest to poradnik typu QuickTip. Zatem skupia się on na osiągnięciu założonego celu. Zatem zakładamy że użytkownik zna na tyle program Unity3d, aby samodzielnie wykonać najprostsze czynności, jak np. dodanie modelu kostki do sceny czy dodanie modelowi jakiegoś komponentu. Jeżeli brakuje Ci tej podstawowej wiedzy, zapraszam do tutoriala:
Unity Tutorial – Podstawy

Teoria

Sztuczna inteligencja w grach odpowiada za sterowanie postaciami komputerowymi. Jedną z popularniejszych metod jest wykorzystanie drzew decyzyjnych. Obecnie do głosu dochodzą bardziej zaawansowane algorytmy i techniki, takie jak logika rozmyta, wybór przez wartościowanie czy nawet całe sieci neuronowe. Jednak w dalszym ciągu, drzewa decyzyjne, obok maszyn stanów skończonych, są najpopularniejszą metodą tworzenia sztucznej inteligencji.

Zanim przystąpimy do tworzenia kodu, należy omówić teorię i szczerze ostrzegam, w tym temacie teorii jest sporo.

Zacznijmy od tego czym są drzewa decyzyjne? W informatyce i matematyce mamy często do czynienia z drzewami. Jest to specyficzny rodzaj grafu. Grafy, zbudowane są z węzłów powiązanych ze sobą. Drzewo ma jeden główny węzeł (korzeń) i z niego wychodzą pomniejsze węzły, z nich kolejne, a z nich następne, aż do węzłów nie posiadających dzieci (childów), które nazywamy liśćmi.

Drzewo. Źródło: Wikipedia
Drzewo.
Źródło: Wikipedia

Na powyższym rysunku liśćmi będą wierzchołki: E, F, C, I, J, K, L. Ponieważ nie posiadają dzieci (childów).

W informatyce drzewa stosowane są bardzo często. Na nich opierają się algorytmy optymalizacyjne. Sztandarowe wykorzystanie drzewa to wyszukiwanie. Gdy obiekty mają pewną hierarchę i są pośrutowane w drzewie, wyszukanie jakiegoś elementu jest dużo łatwiejsze.

Węzły w drzewie decyzyjnym

W typowym zastosowaniu drzew, węzły mają pewne wartości. W przypadku drzew decyzyjnych węzły wykonują operację i zwracają wartość. Mamy kilka typowych rodzajów węzłów, które dla kogoś obytego z matematyką dyskretną czy logiką mogą być bardzo proste.

Dla ułatwienia zrozumienia, będę odwoływał się do wcześniejszego obrazka.

  • Selector (Wybieracz) – Ten rodzaj węzła przeszukuje wszystkie swoje dzieci (childy) – tylko o 1 poziom niżej! – i sprawdza je, aż do napotkania węzła, który zwróci true. Co ważne, selector sprawdza je od lewej strony. Czyli w przypadku gry, priorytetowe zachowanie powinno znaleźć się po lewej stronie.
    W naszym przykładzie, gdyby selectorem był wierzchołek A (co pewnie by miało miejsce, bo z reguły korzeń jest właśnie selectorem), nasz kod najpierw sprawdzi wartość wierzchołka B, jeśli ten zwróci false, przejdzie do C, jeśli też zwróci false do D. Jeśli wierzchołek C zwróciłby true, selector nie sprawdzałby wartości dla D.
  • Sequence (Sekwencja) – Również sprawdza swoje childy, również o 1 poziom. Jednak sekwencja oczekuje, że wszystkie zwrócą true, wtedy sam zwraca true.
    W naszym przykładzie, jeśli sekwencją byłby wierzchołek B, to zwróci on true, tylko gdy wierzchołek E oraz wierzchołek F zwrócą true. Gdyby zrobił to tylko jeden z nich, cała sekwencja zwraca false.
  • Invert (Odwróć) – Jego można kojarzyć z negacją, bo dokładnie to robi, czyli zmienia stan na przeciwny.
    W naszym przykładzie, gdyby wierzchołek G był invertem, to zwróci on true, gdy wierzchołek I zwróci false i odwrotnie.
  • Action (Akcja) – Ten przypisany będzie najczęściej do liści. Jego zadanie, to wykonać jakieś operację i wyprowadzić jeden z wyników: true/false. Akcję mogą być dowolne, czy to przestawiamy postać i sprawdzamy czy jej odległość od rywala jest mniejsza od 10, czy też sprawdzamy czy mamy amunicję aby oddać strzał.

Są to najbardziej podstawowe wierzchołki. Oczywiście można tworzyć własne, jeśli tylko istnieje taka potrzeba. Zasadniczo, drzewa mogą zwracać inne wartości niż true/false. Zależy to tylko od nas, jednak trzeba pamiętać o konsekwencji.

Prosty przykład matematyczny

Mam nadzieję, że teoria dała dostateczną wiedzę, żeby pozwolić zrozumieć przykład. Zaczniemy od bardzo prostego kalkulatora.

Przykład może będzie prosty, ale kodu stworzymy sporo. Zaczynamy!

Zaczniemy prosto. Nasz pierwszy skrypt to: NodeStates.cs:

Tak, to cały skrypt, nie potrzebujemy nic więcej! Tak jak mówiłem, stany nie muszą być tylko true i false u nas będą to: Sukces, Porażka i Trawający.

Drugi skrypt będzie matrycą dla wszystkich wierzchołków, nazwiemy go: BTNode.cs:

Dodatkowa Wiedza
BT = Behaviour Tree

Komentarze z grubsza tłumaczą co mamy w skrypcie, więc skupię się na tych trudniejszych rzeczach.

Przede wszystkim klasa jest abstrakcyjna. Nie będziemy tworzyć na jej podstawie wierzchołków, ale będzie bazą dla selektora, sekwencji etc. Klasa abstrakcyjna, sprawia, że będziemy dysponować funkcją, która określa wartość danego wierzchołka. Dzięki temu, nie będzie się dało stworzyć typu wierzchołka, który nie zwraca wartości.

Mamy już podstawy. Czas przygotować specjalne rodzaje wierzchołków, które często nazywa się dekoratorami (bo nie wykonują same akcji, tylko proste operację):

Selector.cs:

Najważniejsza jest tu funkcja ewaluująca: Evaluate. Sprawdza ona nam wszystkie potomne węzły. (Tablicę przelatujemy od początku, więc pierwszy dodany węzeł zostanie sprawdzony pierwszy – sprawdzamy drzewo od lewej strony i teraz to jest widoczne).

Jeśli napotkamy fałsz, lecimy dalej, jeśli sukces lub trwanie, zwracamy ten stan. Wniosek? Do póki jakiś child nie będzie zwracał true, to sprawdzamy dalej.

Sequence.cs

Ponownie omówię tylko funkcję ewaluacji. Jeśli wszystkie childy zwrócą sukces, cały węzeł zwraca sukces, jeśli przynajmniej jeden zwróci porażkę, przerywamy sprawdzanie i zwracamy porażkę. Dodatkowo sprawdzamy czy przypadkiem jakiś z węzłów nie jest jeszcze obliczany.

Inverter.cs

Tutaj jest bardzo prosto. Jeśli potomny wierzchołek (może być tylko jeden!) zwraca sukces, inverter zwraca porażkę. Jeśli potomny wierzchołek zwróci porażkę, to inverter zwróci sukces.

Na koniec został nienależący do dekoratorów wierzchołek akcji.

ActionNode.cs

Tutaj jest nieco inaczej, bo wartość węzła nie zależy od węzłów potomnych, tylko od funkcji wierzchołka. Tworzymy delegata, który określa jak taka funkcja ma wyglądać, a samą funkcję podajemy jako parametr konstruktora.

Jak widać w Switch nie pojawia się tak jak uprzednio wartość węzła, tylko m_action, które jest naszą funkcją podaną w konstruktorze. W zależności od tego co zwróci funkcja, taką wartość zwróci cały węzeł.

Środowisko testowe

Czas to wszystko przetestować, dlatego tworzymy ostatni skrypt: MathTree.cs Jest on nieco bardziej rozbudowany, więc podam go i omówię w kawałkach.

Ale zanim zaczniemy, w przypadku drzew, bardzo ważna jest planowanie. Tworzenie drzewa na żywo szybko skończy się takim poplątaniem, że nie będziemy go w stanie zakodować. Najlepsze do wizualizacji będzie stworzenie takiego drzewa na kartce czy w jakimś programie.

Nasze drzewo testowe
Nasze drzewo testowe

Nie ma ono zasadniczo większego sensu, ale chodzi o to, żeby pokazać jak działa selector, inverter i action node. Więc zostawiam to tak. Czas na kod.

MathTree.cs

Najpierw zmienne pomocnicze. Nie ma się tutaj czego bać. Większość z nich, to zmienne, które nam pomogą stworzyć wizualizację wyniku działania.

Pierwsze trzy to kolory dla naszych stanów. Później mamy korzeń, oraz kolejne węzły z przydzielonymi odpowiednio typami (jeden Inverter i 3 akcje). Później pięć obiektów, które będą zwykłymi boxami – kolorami pokażemy sobie stan konkretnych węzłów. Późniejsze dwie zmienne liczbowe, posłużą do wyliczeń. Jest to docelowa wartość, którą chcemy osiągnąć, oraz obecna wartość. Na koniec pole tekstowe, do wyświetlania aktualnego wyniku.

Kolejne części kodu będą dodawane w miejscu komentarza!

Najważniejsze, to fakt, że drzewo budujemy od dołu. Nie dałoby się dodać węzła 3 jako potomka 2B kiedy zaczęlibyśmy budowanie od góry.

Parametry dla węzłów akcji, to nazwy funkcji, które napiszemy za chwilę. Trzeba pamiętać, że funkcję muszą spełniać założenia delegata. Gdy mamy do czynienia z dekoratorem, jako parametr podajemy inny węzeł lub listę węzłów.

Gdy przygotujemy już całą strukturę drzewa, to przekazujemy sobie wartość do przygotowanego obiektu tekstowego, następnie wyliczamy wartość dla korzenia. Możemy liczyć tylko dla korzenia, ponieważ korzeń, będzie sprawdzał każde z dzieci, a każde z dzieci, żeby określić swój stan, sprawdzi stan swoich dzieci i w ten rekurencyjny sposób sprawdzimy całe drzewo.

Dodatkowa Wiedza
Rekurencja – odwołanie się funkcji do samej siebie. Funkcja rekurencyjna, zwraca wynik na podstawie swojego własnego wyniku dla mniejszej wartości.

Funkcja UpdateBoxes, pomaga w wizualizacji i nie jest skomplikowana, więc nie poświęcimy jej dużo czasu:

Sprawdzamy sobie stan każdego węzła i w zależności od wartości ustalamy sobie kolor boxa do wizualizacji, za pomocą funkcji SetSucceeded i SetFailed, które wyglądają tak:

Czyli bierzemy renderer danego boxa i ustawiamy mu kolor na jeden z narzuconych przez nas na początku.

Zostały nam dwie funkcję dla węzłów akcji:

Funkcja AddTen, co może zaskakiwać, dodaje 10 do wartości. Od razu w naszym polu tekstowym podaje nową wartość, oraz co musi robić każda funkcja zwraca wartość stanu węzła. Tutaj, jeśli obecna wartość zgadza się z docelową, to dostaniemy sukces, gdy nie, to porażkę.

Druga funkcja zwraca sukces, kiedy wynik oczekiwany różni się od obecnego.

Tyle kodu.

Scena testowa

Na koniec musimy sobie przygotować scenę testową. Będzie bardzo prosta, bo składać się będzie z 5 ułożonych w plusa standardowych boxów. Nazywamy sobie je zgodnie z naszymi węzłami i ustawiamy tak, żeby je reprezentowały.

Dodatkowo tworzymy sobie pusty GameObject i nazywamy go Tree. Do niego przypisujemy nasz skrypt MathTree.

Potem dodajemy sobie Canvas [GameObject -> UI -> Canvas], a do niego dodajemy komponent tekstowy: [Component -> UI -> Text].

Teraz zostaje tylko poprzypisywać wszystkie zmienne publiczne do skryptu MathTree:

Wygląd sceny testowej
Wygląd sceny testowej

Czerwone opisy na rysunku są dołożone ode mnie, żeby było widać, który box odpowiada za który węzeł.

Target Value ustalone u mnie jest na 10, ale to jest parametr, który służy do zabawy. Zmieniając go, można zaobserwować różne zachowania drzewa decyzyjnego.

Przykładowo tak prezentuje się wynik dla wartości 20:

Wynik dla wartości 20
Wynik dla wartości 20

Co tutaj się podziało?

  • Nasz korzeń zaczyna sprawdzania i odwołuje się do 2A,
  • A2 dodaje 10 (mamy 10, oczekujemy 20), więc wartość się nie zgadza, i zwraca porażkę,
  • Korzeń nie trafił na sukces, to odpytuje 2B,
  • 2B ustala wartość na podstawie 3, więc go odpytuje,
  • 3 sprawdza i widzi, że obecna wartość jest inna niż oczekiwana, więc zwraca sukces,
  • 2B odbiera sukces, ale jest iverterem, więc sam zwraca porażkę,
  • Korzeń nie trafił na sukces, więc odpytuje 3C
  • 3C dodaje 10 (mamy 20, oczekujemy 20), więc wartość się zgadza i zwraca sukces,
  • Korzeń zwraca sukces.

Zaawansowany przykład

No dobra, ale po co wam kalkulator? Chcielibyście pewnie prawdziwą sztuczną inteligencję. Dlatego zaprezentuję prosty przykład. Oczywiście najpierw schemat:

Drzewo dla żołnierza
Drzewo dla żołnierza

Wygląda na nieco bardziej skomplikowane, ale pokazuje też fajną rzecz. Z niektórych węzłów można korzystać kilka razy. Nie do końca jest to poprawne, ale można tak zrobić.

Znów ważna jest kolejność. Ucieczka jest pierwsza z lewej. Gdybyśmy dali ją na koniec, dostalibyśmy żołnierza kamikaze.

W naszej kwestii jest to, co damy w akcjach. Np. dla ucieczki może to być ilość życia. Całość można też rozbudować, np. o sprawdzanie stanu amuniacji i dodanie węzła „przeładowanie”.

Ale jak takie coś wygląda w kodzie? Już spieszę z pomocą:

Funkcja Start:

Oczywiście odpowiednie zmienne trzeba wcześniej zadeklarować.

Teraz załóżmy, że mamy funkcję która każe wykonać ruch przeciwnikowi:

Wyliczamy sobie nowe wartości (żeby podjąć decyzję na świeżych danych), a następnie wykonujemy ruch. Ta funkcja może być wywołana eventem, albo np. co parę sekund, ewentualnie w każdej klatce. W zależności od gry.

Tutaj sprawdzamy, która opcja została wybrana i to ją wykonujemy. Kod zostawiam do waszej dyspozycji, bo będzie zależny od gry i tego co chcecie osiągnąć.

Nie podaje funkcji playerIsVisible czy checkHP, bo łatwo można się domyślić ich wyglądu, a też będą zależne od gry.

PlayerIsVisible, naturalnie można połączyć z poprzednim kursem, o zmysłach.

  • Pingback: Recenzja: Unity AI Game Programming | mWin()

  • MrT

    Tłumaczysz dobrze, jednak twój kod nie jest najlepszej jakości, dużo elementów często się powtarza co sprawia że kod nie wygląda najlepiej, do tego mógłbyś użyć LINQ.

    • W moim odczuciu kod prawie zawsze może być lepszy i fajniejszy. W moim przypadku pewnie czasem zdarza się, że coś zrobię gorzej niż by można było – ale to pewnie przypadłość każdego programisty, natomiast czasami celowo niektóre fragmenty (niedotyczące tematu poradnika) robię po najmniejszej linii oporu, żeby nie komplikować dodatkowo całości i nie odrywać czytelnika od głównego problemu. Może to nie do końca pedagogiczne, ale czasami wydaje mi się lepszym rozwiązaniem niż rozciąganie poradnika 2-3 krotnie dla pięknego kodu w każdym miejscu. Tutaj wiem, że wiele osób się ze mną nie zgodzi, przy czym piszę to wszystko w wolnym czasie, więc staram się nieco czasu oszczędzić.

      Mimo wszystko, wiem że może być lepiej i dzięki za uwagę :)