Tworzenie gry w C# z użyciem silnika Ogre - cz.6

12.05.2011 - Mateusz Osowski
TrudnośćTrudność

Drzewa działań

Pierwszym pomysłem, jaki nasuwa się zwykle w związku z zarządzaniem stanami jest automat skończony (ang. FSM, finite state machine). Koncepcja jest bardzo prosta i nawet działa, lecz niestety, wraz ze wzrostem liczby różnych stanów liczba przejść między nimi rośnie coraz szybciej (stanowi kwadrat liczby stanów). Jesteśmy zmuszeni do określania tych przejść explicite, przez co niewiele trzeba, by nasza maszyna stanów zamieniła się w poplątane spaghetti (FSM - flying spaghetti monster ;) ). Niewielkim ulepszeniem takich automatów jest hierarchiczna maszyna stanów - wówczas przejścia możemy określać między większymi grupami stanów. Natura rozwiązania pozostaje jednak taka sama - kłopotliwa. W grach implementujących SI stanów zwykle jest dużo, a każdy z nich musi obsługiwać zewnętrzne zdarzenia. My w domowym zaciszu tworząc gry dla zabawy nie mamy możliwości zatrudnienia programistów, którzy zajmowaliby się żmudnym tworzeniem takiej wydumanej maszyny stanów. Musimy więc wymyślić coś innego, rozwiązanie, które będzie miało inną naturę i będzie pozwalało na dynamiczne zachowania.

Wybiegnijmy trochę do przodu, spójrzmy na sytuację z perspektywy implementacji zachowań przeciwników. Rozważmy postać zabójcy gnomów. Zabójca stacjonuje w lesie. Celem jego egzystencji jest zabijanie gnomów. Posiada łuk, strzały i miecz. Kiedy widzi gnoma, odczuwa nieodpartą chęć natychmiastowego posłania go na tamten świat. Gnomy zauważone z daleka zabija strzałem z łuku, pod warunkiem, że ma strzały. Gnomy są jednak podstępne i czasami zachodzą naszego zabójcę od pleców, wtedy preferowanym rozwiązaniem staje się miecz. Kiedy gnomów nie ma w pobliżu, wojownik przechadza się po lesie zatrzymując się raz na jakiś czas i wypatrując wrednych karzełków.

Zauważmy, że realizacja głównego celu - zabijania gnomów - sprowadza się do zrealizowania grupy mniejszych pod-celów, różnej w zależności od sytuacji. Strukturą dobrze nadającą się do reprezentacji tego problemu jest drzewo. Wynikiem przejścia po nim powinien być liść, który określać będzie niskopoziomową, już niepodzielną czynność, którą ma wykonać postać - liść-zadanie. Do podejmowania jakichkolwiek decyzji potrzebny będzie liść sprawdzający, pozwalający zajrzeć do stanu gry - asercja. Złożone czynności można rozbić na mniejsze, które wykonywać będziemy po kolei. Pojawia się więc potrzeba wprowadzenia węzła, którego przejście polegać będzie na wykonaniu wszystkich dzieci w kolejności od lewej do prawej. Przejście po asercji spowoduje sprawdzenie jej predykatu, czyli warunku. Jeżeli on zawiedzie, zrezygnujemy z odwiedzania dalszych dzieci tego węzła. Co dalej? Asercja może się powieść lub nie - uogólnijmy to na wszystkie węzły. Niepowodzenie asercji w pewnej liście czynności spowoduje niepowodzenie całej grupy. Wtedy też wyniesiemy niepowodzenie do węzła-rodzica. Naturalną konsekwencją wprowadzenia stanów sukcesu i porażki na całym drzewie w kontekście podejmowania decyzji jest wprowadzenie alternatywy. Jak się okazuje, te cztery konstrukcje wystarczają do określenia całkiem złożonych zachowań. Podsumujmy, co mamy:

  • Asercja - liść z predykatem. Zwraca to, co zwróci predykat. Odpytuje środowisko gry.
  • Zadanie - liść z zadaniem. Wykonuje kod, wywiera wpływ na świat gry.
  • Węzeł ogólny - Odwiedza swoje dzieci w kolejności od lewej do prawej. Jeżeli któreś z nich odniesie porażkę, przestaje wykonywać dalsze i zwraca porażkę. Jeżeli wszystkie się powiodą - zwraca sukces.
  • Alternatywa (węzeł szczególny) - Odwiedza swoje dzieci w kolejności od lewej do prawej. Jeżeli któreś z nich odniesie sukces, przestaje wykonywać dalsze i zwraca sukces. Jeżeli wszystkie się nie powiodą - zwraca porażkę.

Wróćmy do zabijania gnomów. Zobaczmy, jak będzie wyglądać drzewo działań (kliknij, by powiększyć):


Całe skomplikowane zachowanie zostało uproszczone do przejrzystego drzewa. Dobrze zaprojektowane drzewo powinno kończyć się powodzeniem - w naszym przypadku gwarancją powodzenia jest prawe dziecko alternatywy w korzeniu - spacerowanie. W przypadku węzłów ogólnych (niebieskich) asercje (pomarańczowe) na początku warunkują nam podejmowanie działań położonych za nimi. Natomiast w przypadku alternatyw (węzłów szczególnych, zielonych) asercja pozwala nam nie wykonywać czynności, których nie trzeba wykonywać, co widać na przykładzie wyciągania łuku, czy też miecza. Konstrukcje są podobne do drzewa programu, zatem można stwierdzić, że pozwalają na bardzo wiele. Są przy tym nieskomplikowane i proste w utrzymaniu. Dodatkowym ich atutem jest możliwość wielokrotnego użycia elementów (wówczas z drzewa zrobi się skierowany graf acykliczny, co wcale nam nie przeszkadza).

Niedokończone zadania

Zanim pożegnamy się z automatami skończonymi, zwróćmy uwagę na pewien ważny problem. Chcemy, by drzewa pozwalały na dynamiczną reakcję postaci na zmieniający się stan gry. Zmienia się on praktycznie w każdej klatce, zatem będziemy przechodzić po drzewie dość często. Wiele niepodzielnych czynności, takich jak np. uderzanie, czy strzelanie z łuku trwa przez pewien czas. Nie możemy wówczas w trakcie jednego przeglądnięcia drzewa określić, czy lista czynności zakończyła się sukcesem bądź porażką. Jeżeli niedokończona czynność zwróci sukces - odwiedzone zostanie następne dziecko i zostanie rozpoczęta następna czynność. Można próbować temu zaradzić wprowadzając odpowiednią asercję, jednak musiałaby się ona odnosić do poprzedniej czynności. Stracilibyśmy modularność i prostotę rozwiązania. Zwrócenie przez wykonywaną czynność niepowodzenia spowoduje przekazanie fałszu wyżej, w konsekwencji przejście do innej gałęzi alternatywy. Tego nie chcemy. Co zrobić?

Lekarstwo

Dobrym wyjściem będzie wprowadzenie trzeciego stanu - pół-sukcesu. Każda czynność powinna wiedzieć, czy skończyła się wykonywać. Niedokończona czynność zwróci pół-sukces. Jego semantyka będzie prosta - dla alternatyw oznaczać będzie znaczyć tyle co sukces, a dla węzłów ogólnych - porażkę. Zapobiegnie to odwiedzaniu wszystkich dzieci w przypadku ogólnym i jednocześnie nie spowoduje wejścia do innej gałęzi alternatywy.

Implementacja

Utwórzmy folder DecTree w projekcie i zacznijmy od utworzenia w nim ogólnej, abstrakcyjnej klasy węzła:
1
2
3
4
5
6
7
8
9
10
11
12
13
public abstract class Node
{
  public enum Status
  {
    Fail,
    HalfSuccess,
    Success
  }
 
  public List<Node> Children = new List<Node>();
 
  public abstract Status Visit(Character ch);
}
DecTree/Node.cs


Chcemy, by drzewa nadawały się do używania przez wiele postaci, więc sama postać będzie przekazywana jako argument.

Klasa liścia-zadania:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Job : Node
{
  public Func<Character,bool> Func;
 
  public Job(Func<Character, bool> func)
  : base()
  {
    Func = func;
  }
 
  public override Status Visit(Character ch)
  {            
    if (Func(ch))
      return Status.Success;
    else
      return Status.HalfSuccess;
  }
}
DecTree/Job.cs


Funkcja podpinana jako zadanie będzie określana już w konstruktorze. Przyjmujemy, że funkcja zadania zwraca true, jeżeli zadanie się zakończyło, false, jeśli jeszcze trwa. Zakładamy, że pole Func będzie przechowywać tylko jedną funkcję.

Klasa asercji:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Assert : Node
{
  Func<Character,bool> Predicate;
 
  public Assert(Func<Character, bool> predicate)
  : base()
  {
    Predicate = predicate;
  }
 
  public override Status Visit(Character ch)
  {
    if (Predicate(ch))
      return Status.Success;
    else
      return Status.Fail;
  }        
}
DecTree/Assert.cs


W klasie tej korzystamy z typu Func<> zamiast Predicate<> do określenia predykatu, by zachować spójność typów z Job.

Klasa węzła ogólnego:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FirstFail : Node
{
  public FirstFail(params Node[] children) 
    : base()
  {
    Children = children.ToList();
  }
 
  public override Status Visit(Character ch)
  {
    foreach (Node node in Children)
    {
      Status status = node.Visit(ch);
      if (status != Status.Success)
        return status;
    }            
    return Status.Success;
  }    
}
DecTree/FirstFail.cs


Jak nazwa klasy wskazuje, węzeł będzie odwiedzać swoje dzieci do pierwszej porażki. W konstruktorze podawać będziemy listę dzieci. Sukces wszystkich dzieci oznacza sukces węzła. Przerywające działanie wyniki dzieci, w szczególności pół-sukces przekazywane będą do rodzica.

Klasa alternatywy (węzła szczególnego):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FirstSucc : Node
{
  public FirstSucc(params Node[] children) 
    : base()
  {
    Children = children.ToList();
  }
 
  public override Status Visit(Character ch)
  {
    foreach (Node node in Children)
    {
      Status status = node.Visit(ch);
      if (status != Status.Fail)
        return status;
    }
    return Status.Fail;            
  }
}
DecTree/FirstSucc.cs


Tym razem pierwszy sukces (lub pół-sukces) kończy odwiedzanie dzieci. Gdy żadne z dzieci nie odniesie sukcesu, odwiedzenie węzła zwraca porażkę.

Implementacja jest gotowa do użycia! Zaprojektujmy drzewo dla naszej obecnej postaci:


Na niebiesko podświetlone zostało poddrzewo podnoszenia przedmiotu. Będzie ono mogło zostać użyte jako pod-akcja przyszłych, bardziej rozbudowanych zachowań. Dzięki strukturze drzewa nie musimy przejmować się wewnętrzną budową poszczególnych poddrzew projektując postępowania wyższego poziomu.

Wraz z wprowadzeniem drzewa działań zmieni się zarządzanie postacią. Nie będziemy dłużej wywoływać metod przełączających stan. Zamiast tego, ustawimy odpowiednią flagę, a drzewo samo pokieruje postacią w odpowiedni sposób.

Aby nie wypływać na zbyt głęboką wodę zbyt szybko, stan rozmowy z wcześniejszej wersji zastępujemy flagą zezwalającą na rozmowę ustawianą w ostatniej gałęzi alternatywy odpowiadającej stanowi bezczynności (Idle). W przyszłości, kiedy stan rozmowy będzie posiadał własną animację i będzie wyróżniać się odmiennym zachowaniem, wystarczy, że dodamy odpowiednie poddrzewo.

Zwróćmy uwagę na zadania PickItemOrder = false. Mają za zadanie wyczyścić informacje o poleceniu podniesienia przedmiotu. Wykonują się zarówno w przypadku sukcesu samego podniesienia, jak i jego porażki, ponieważ zakładamy, że ta gałąź jako jedyna obsługuję flagę PickItemOrder.

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com