Jednym z potężniejszych wykorzystań std::variant niewątpliwie jest implementacja Maszyny Stanowej. Jakiś czas temu przygotowałem prosty przykład tego wzorca. Dzisiaj jednak mamy coś większego. W dzisiejszym wpisie przygotowanym przez Nikolai Wuttke zobaczycie, jak wykorzystać std::variant przy budowie gry kosmicznej!

Poniższy wpis jest wpisem gościnnym autorstwa Nikolai Wuttke.

Nikolai Wuttke jest dyrektorem technicznym w Ableton - firmie, która zajmuje się oprogramowaniem muzycznym, znajdującej się w Berlinie. W swoim wolnym czassie lubi tworzyć metalowe covery soundtracków gier komputerowych, grać w zespole muzycznym, kolekcjonować komputery z ery DOS-u oraz przeglądać 16-bitowy kod assemblera.

Wstęp

Jednym z nowych dodatków, które do standardowej biblioteki przyniósł C++17 jest std::variant - obiekt, który może przechowywać wartości różnych typów, przy czym tylko jednego typu naraz. W teorii typów zjawisko to jest nazywane sumą typów. Jest to na prawdę przydatna rzecz, która potrafi być wykorzystywana w wielu przypadkach. Jeżeli chcecie dowiedzieć się więcej na temat std::variant oraz tego, co on potrafi - zaglądnijcie pod link Everything You Need to Know About std::variant from C++17. W tym wpisie chciałbym się skupić na jednym konkretnym jego użyciu: modelowaniu maszyny stanowej.

Maszyna stanowa jest wykorzystywana w szerokim spektrum aplikacji, zaczynając od gier komputeorych, a kończąc na programach zarządzających połączeniami HTTP. Kiedykolwiek mielibyście problem ze stanami w aplikacji, rozważcie wykorzystanie maszyny stanowej - wymaga ona od nas bardzo wyraźnego określenia każdego stanu, w którym może być nasz system oraz wszystkich możliwych dróg przejścia pomiędzy tymi stanami. To, zgodnie z moim doświadczeniem, często skutkuje, że nasz kod staje się łatwiejszy w utrzymaniu oraz prostszy do zrozumienia, porównując mniej ustrukturyzowany kod (np. wykorzystując zestaw wartości typu boolean).

Czym więc dokładnie jest maszyna stanowa? Isnieje formalna definicja skończonej maszyny stanów, ale ja wytłumaczę to na przykładzie. Załóżmy, że chcemy zrobić grę, której akcja toczy się w kosmosie.

Specyfikacja gry

Nasz gracz kontroluje statek kosmiczny i musi walczyć z drugim statkiem sterowanym przez komputer. Wrogi statek zachowuje się następująco:

• Kiedy gracz znajduje się na środku pola gry, wroga jednostka krąży wokół niego
• KIedy gracz znajduje się poza punktem centralnym, wrogi statek utrzymuje pozycję na środku planszy
• Jeżeli przeciwnik znajduje się na środku przez pewien okres czasu, powinien na krótko wylecieć ze środka i szybko do niego wrócić, aby trudniej było graczowi w niego trafić

Podczas wykonywania powyższych manewrów wrogi statek ciągie strzela w gracza.
Ponadto chcemy, aby przeciwnik bardzo łagodnie przechodził pomiędzy środkiem a okrążaniem gracza.

Mamy więc cztery odrębne stany, w których może znaleźć się przeciwnik w określonym czasie:

1. Okrążanie gracza
2. Przelot do środka planszy
3. Pozostanie na środku planszy
4. Szybka ucieczka ze środka planszy

Kiedy osiągniemy stan nr 4, po osiągnięciu przez przeciwnika zewnętrznej krawędzi planszy sprawdzamy, czy gracz ciągle znajduje się poza jej środkiem. W zależności od tego, możemy przełączyć się do stanu nr 1 (rozpoczęcie okrążania gracza) lub stanu nr 2 (powrót do środka planszy).

Do wyrażenia tego algorytmu jako maszynę stanów, rysujemy elipsę dla każdego stanu, a następnie rysujemy linie w celu wskazania wszystkich możliwych przejść pomiędzy nimi. W efekcie wyszedł nam następujący diagram:

Teraz obrazki wyglądają ładnie, ale ostatecznie musimy napisać kod naszej gry. W jaki sposób można zamienić tą maszynę stanową ze specyfikacji to działającej implementacji?

Implementacja maszyny stanów zachowań wrogiego statku

Przede wszystkim, potrzebujemy śledzić obecny stan naszego przeciwnika. Możemy do tego celu wykorzystać enum:

    enum class EnemyState {
      Circling,
      FlyToCenter,
      ShootingFromCenter,
      FlyOut
    };

Gdyby to był jedyny stan, który musimy śledzić, to byłoby wspaniale. Ale skoro nie chcemy, aby nasza gra była tekstową przygodówką, to potrzebujemy trochę więcej pracy:

• Chcemy, aby przeciwnik strzelał w stronę gracza z określoną częstotliwością, zatem musimy śledzić czas, który minął od ostatniego strzału
• Chcemy, aby przeciwnik odlatywał ze środka po określonym czasie, zatem musimy śledzić czas, w którym znajduje się on na środku planszy
• Jako okrążenie gracza przyjmijmy lot w kierunku każdego z czterech rogów planszy, jeden po drugim. Zatem potrzebujemy znać narożnik, w kierunku którego statek obecnie się udaje. Przyda się nam ta informacja również do sprawdzenia, czy ten narożnik został osiągnięty.

Wyrażając to w kodzie, potrzebujemy trzy dodatkowe zmienne określające stan:

    double timeSinceLastShot;
    double timeSpentInCenter;

    // Zakładamy, że posiadamy tablicę wszystkich narożników planszy
    int targetCornerIndex;

Teraz moglibyśmy dołączyć te wszystkie zmienne do naszej zmiennej typu enum, którą zadeklarowaliśmy powyżej i mielibyśmy wszystko, czego potrzeba do określenia każdego stanu. Jest jednak jeden problem: wszystkie te zmienne są aktualne jedynie w kontekście określonych stanów, jak zobaczyć możemy w tabelce poniżej:

Moglibyśmy zadać pytanie: “Co za różnica, przecież wiem, kiedy użyć każdej z tych zmiennych. Będę uważał, aby nie używać tych niewłaściwych tam, gdzie nie można ich użyć.”. Całkiem możliwe, że mielibyśmy rację, kiedy pracowalibyśmy nad tak prostym przypadkiem jak ten tutaj. Mogę wyobrazić sobie o wiele bardziej skomplikowane scenariusze, z o wiele większą liczbą stanów, zmiennych i możliwych przejść między nimi. W niektórych przypadkach może być bardzo trudno być pewnym, że wszystkie te zmienne są wykorzystywane tylko w tych stanach, w których mają one znaczenie oraz że resetujemy wartości tych zmiennych poprawnie przy wszystkich przejściach pomiędzy stanami itp. Oczywiście, nie jest niemożliwe dokonanie tego, ale rośnie koszt w postaci godzin spędzonych nad debuggerem. Zatem w końcu, wykorzystujemy nowoczesny C++, więc możemy mieć realny wpływ na to, jak jego funkcjonalności pomagają nam żyć prościej, nie prawda?

To właśnie to miejsce, kiedy wprowadzamy std::variant; przez zakodowanie różnych stanów naszej maszyny stanowej jako osobne typy mamy możliwość korzystania ze zmiennych, których potrzebujemy, przy tych stanach, które ich potrzebują. Jeżeli połączymy wszystkie te typy w jeden std::variant, będziemy mieli zakodowany aktualny stan naszej maszyny stanowej. To dzięki temu właśnie, że std::variant wie, jaką wartość aktualnie przechowuje. Zobaczmy, jak to będzie wyglądało w kodzie:

struct Circling
{
  explicit Circling(const int startIndex)
    : mNextCirclePosIndex(startIndex)
    {
    }

    double mTimeSinceLastShot = 0.0;
    int mNextCirclePosIndex = 0;
};

struct FlyToCenter
{
};

struct ShootingFromCenter
{
    double mTimeSinceLastShot = 0.0;
    double mTimeSpentInCenter = 0;
};

struct FlyOut
{
    explicit FlyOut(const int cornerIndex)
      : mTargetCornerIndex(cornerIndex)
      {
      }

    int mTargetCornerIndex;
};

using State = std::variant<
    Circling,
    FlyToCenter,
    ShootingFromCenter,
    FlyOut>;

Robiąc to w ten sposób ładnie rozwiązujemy parę problemów z podejściem z wykorzystywaniem typu enumeracyjnego:

• Nie jest możliwy dostęp do zmiennych, z których korzystamy będąc w innym stanie, ponieważ wszystko, czego potrzebujemy zawarte jest wewnątrz jednej struktury
• Przez przypisywanie nowej wartości do wariantu, przełączamy się do nowego stanu, ale również jesteśmy pewni, że wszystkie zmienne mają poprawne wartości, dzięki konstruktorowi naszej struktury. Nie ma potrzeby manualnego resetowania zmiennych przy przechodzeniu ze jednego stanu do drugiego
• Podobnie, jeżeli którykolwiek stan wymaga, aby jego wartości były określone w specyficzny sposób po przejściu w ten stan, możemy to osiągnąć przez niedostarczenie domyślnego konstruktora dla odpowiedniej struktury.

Kluczowym jest to, że wykorzystaliśmy system typowania C++ do zabezpieczenia gry przed wejściem w niepoprawny stan wewnątrz kodu. To znaczy, że mamy mniej rzeczy, o których należy pamiętać, ponieważ to kompilator wyłapie nam wszystkie przez nas popełnione błędy i pozwoli skupić się nam na na prawdę ważnej części: tworzeniu logiki gry. Zostało nam tylko jedno pytanie: w jaki sposób zaimplementować logikę, o której wspomniałem wcześniej, bazując na std::variant?

Do tego celu z pomocą przychodzi nam wzorzec Overload. Pozwala nam on na zapisanie lambdy, która będzie handlerem dla każdego z naszych stanów, podobnie do wzorca Pattern Matching - świetnej opcji pojawiającej się często w językach programowania, takich jak np. Scala czy Rust. W wielu funkcyjnych językach programowania ten wzorzec został wykorzystany jako fundamentalna część języka (np. Haskell). Na dzień dzisiejszy możemy jedynie emulować działanie tego wzorca w języku C++, wykorzystując zewnętrzne biblioteki. Istnieją natomiast proposale będące za dodaniem tego wzorca jako natywnej funkcji języka (P1371, P1260).

Spójrzmy na kod implementujący fukcję aktualizującą stan obiektu przeciwnika:

mState = match(mState,
    [=](Circling& state) -> State
    {
        // Implementacja logiki okrążania

        if (playerInOuterZone()) {
            // Przełączanie do następnego stanu, jeśli potrzebne
            return FlyToCenter();
        }

        return state;
    },

    [=](const FlyToCenter&) -> State
    {
        // Implementacja logiki przelotu do punktu centralnego
    },

    [=](ShootingFromCenter& state) -> State
    {
        // Implementacja logiki strzelania w punkcie centralnym
    },

    [=](const FlyOut& state) -> State
    {
        // Implementacja logiki wylotu z punktu centralnego
    }
);

Funkcja match jest drobnym wrapperem dla wspomnianego wyżej helpera overloaded, który poza oszczędzaniem mi czasu podczas pisania oraz przekazywania argumentu na początek, niewiele tutaj robi spójrzcie na źródło tutaj.

Tutaj implementacja:

    template <typename Variant, typename... Matchers>
    auto match(Variant&& variant, Matchers&&... matchers)
    {
        return std::visit(
             detail::overloaded{std::forward<Matchers>(matchers)...},
             std::forward<Variant>(variant));
    }

W celu implementacji naszej maszyny stanowej, będziemy korzystali z funkcji match na naszym wariancie, a następnie dorzucimy odrobinę logiki dla każdego ze stanów. Ta logika obejmuje strzelanie, ruszanie się itp, tak jak również warunki sprawdzające, czy potrzebujemy dostać się do nowego stanu. Jeżeli do tego dojdzie, zwrócimy obiekt stanu, który będzie reprezentował stan, do którego chcemy się przełączyć. W przeciwnym wypadku zwrócimy aktualny stan. Wszystko, co zwrócimy z wybranej lambdy, zostaje zwrócone przez match i przypisane do mState.

Dlaczego aktualizujemy mState przez wartość zwracaną, kiedy moglibyśmy przechwycić wskaźnik this i zmodyfikować mState bezpośrednio w lambdach? Jest to zabezpieczenie przez zachowaniem niezdefiniowanym (undefined behavior). Problemem jest tutaj fakt, że lambdy korzystają z referencji do aktualnego stanu, który jest przechowywany w wariancie. Jeżeli zmienilibyśmy wariant z wnętrza lambdy, moglibyśmy zwrócić argument lambdy do nieistniejącej referencji (dandling reference), czyli referencji wskazującejna obiekt, który został w tej chwili zniszczony. Ponieważ kompilator nie zabiera nam dostępu do argumentu po przypisaniu go do wariantu, całkiem łatwym staje się włączenie do programu zachowania niezdefiniowanego (jeżli nie będziemy wystarczająco ostrożni). Ponieważ głównym punktem korzystania z warianu w celu reprezenacji naszej maszyny stanowej jest zmniejszenie podatności na błędy, powinniśmy zablokować możliwość wystąpienia również tego problemu.

Jak uniknąć dodatkowych kopii?

Powyższy mechanizm ma jedną wadę: dodatkowe przypisanie obiektu stanu, kiedy ten nie został zmieniony. Prawdopodobnie nie będzie to problemem, kiedy nasz obiekt stanu będzie względnie mały. Jeśli natomiast chcemy za wszelką cenę ominąć ten koszt, możemy wykorzystać do tego celu std::optional:

using MaybeNextState = std::optional<State>;
auto maybeNextState = match(mState,
    [=](Circling& state) -> MaybeNextState 
    {
    // Implementacja logiki okrążania

        if (playerInOuterZone()) {
          // Przełączanie do następnego stanu, jeśli potrzebne
          return FlyToCenter();
        }

        return std::nullopt;
    },...

if (maybeNextState)
{
    mState = *maybeNextState;
}

W powyższym kodzie zmieniamy wartość mState tylko, jeżeli maybeNextState jest dostępny. Unikniemy dzięki temu dodatkowych kopii.

Uwaga od Bartłomieja Filipka: ta technika została oryginalnie zaimplementowana przez Nikolai, ale z uwagi na długość kodu zaproponowałem pominąć std::optional. Więcej szczegółów znajdziecie pod tym linkiem.

Kod źródłowy

Jeżeli chcecie zobaczyć grę, o której pisałem w tym artykule, znajdziecie ją na GitHub’ie. Pełny kod źródłowy maszyny stanowej znajdziecie tutaj. Logika przeciwnika omówiona powyżej znajduje się w pliku enemy.cpp.

Wnioski

Zobaczyliśmy, w jaki sposób można zaimplementować prostą maszynę stanową w solidny sposób, wykorzystując przy tym standardową bibliotekę C++17 oraz kilka linijek kodu pomocniczego. Implementacja jest całkowicie ekspresywna i bezpieczna dla typu. Dodatkowo całość jest w dużej mierze odporna na pomyłki, będąc przy tym dość zwięzłym. Lubię wykorzystywać to podejście za każdym razem, kiedy problem nadaje się do korzystania z maszyny stanowej. Warto wspomnieć, że to podejście ma swoje ograniczenia. Kiedy liczba stanów i przejść pomiędzy tymi stanami osiągnie pewien rozmiar, możemy poczuć potrzebę sformalizowania kilku rzeczy, bądź skorzystać z bibliotek specjalizujących się w maszynie stanów.

Zachęcam Was również do obejrzenia mojej prezentacji na Meeting C++ 2018.