W zeszłym tygodniu wpadłem na pytanie: jak się w praktyce implementuje maszyny stanu? Szczególnie interesowało mnie podejście w tworzeniu gier. Ku mojemu zdziwieniu i udręce, kod który zobaczyłem w tutorialach na YouTubie był słaby, bo był bardzo mocno powiązany z innymi częściami systemu piszącego. Dlatego postanowiłem chwilę poeksperymentować i teraz zaprezentować moje podejście.
Tydzień temu opisałem typy algebraiczne w C#. Można mieć maszyny stanu,
z prostymi stanami - reprezentowane przez enum, albo nasze stany mogą być parametryzowane,
do czego typy algebraiczne nadają się świetnie.
Maszyna stanów
Zacznę bardzo prosto i abstrakcyjnie. Maszyna stanów, to koncept bardzo bliski do automatów rozpoznających wyrażenia regularne. Mamy kilka stanów oraz podpisane strzałki między nimi. Strzałka reprezentuje przejście ze stanu A do stanu B jeśli zaszło wydarzenie E, którym podpisana jest ta strzałka (więcej znajdziesz na Wikipedii).
Wobec tego możemy stworzyć prostą abstrakcyjną klasę dla naszych maszyn:
public abstract class StateMachine<TState, TEvent>
{
public TState State { get; protected set; }
public abstract void ProcessEvent(TEvent @event);
public StateMachine(TState initialState)
=> State = initialState;
}
Nasza maszyna ma jakiś stan i zdolność do zmiany tego stanu pod wpływem jakiegoś zdarzenia.
Przykład implementacji
Powiedzmy, że chcemy modelować naszą maszyną stanu pogodę. Utworzyłem więc algebraiczny typ danych, zgodnie z poprzednim blogpostem, który odpowiada tej pseudo definicji:
type WeatherState =
| Sun(int ConsecutiveDays)
| Rain(int ConsecutiveDays)
| Storm(int ConsecutiveRainDays)
Do tego potrzebujemy jeszcze zdarzenia
type WeatherEvent =
| NoChange
| StartRain
| StopRain
| BringStorm
Teraz mając już określone dane będziemy chcieli zaimplementować maszynę stanu, która opisze przejścia między nimi. Można to zrobić na kilka różnych sposobów, ale ja poszedłem najprostszą ścieżką.
public override void ProcessEvent(WeatherEvent @event)
{
var state = State;
switch(state.Tag)
{
case WeatherState.Enum.Sun:
State = HandleEventAtSun(state.As<WeatherState.Sun>(), @event);
break;
case WeatherState.Enum.Rain:
State = HandleEventAtRain(state.As<WeatherState.Rain>(), @event);
break;
case WeatherState.Enum.Storm:
State = HandleEventAtStorm(state.As<WeatherState.Storm>(), @event);
break;
default: throw new PatternMatchException<WeatherState.Enum>(state.Tag);
}
}
Co jest dla mnie istotne, to żebym był w stanie napisać testy do tej maszyny. Powyższa metoda jest bardzo prosta, a testowalna logika przejść między stanami została wyprowadzona do poszczególnych funkcji.
internal WeatherState HandleEventAtRain(WeatherState.Rain state, WeatherEvent @event)
{
switch(@event)
{
case WeatherEvent.NoChange:
return new WeatherState.Rain(state.ConsecutiveDays + 1);
case WeatherEvent.StopRain:
return new WeatherState.Sun();
case WeatherEvent.BringStorm:
return new WeatherState.Storm(state.ConsecutiveDays + 1);
case WeatherEvent.StartRain:
throw new ApplicationException($"Invalid event '{@event.Tag}' in state '{state.Tag}'.");
default: throw new PatternMatchException<WeatherEvent.Enum>(@event.Tag);
}
}
Szybka maszyna dla enumów
Kiedy nasze stany i zdarzenia nie mają dodatkowych parametrów to można je reprezentować jako zwykły enum i przejścia zaimplementować w postaci macierzy:
public unsafe sealed class EnumStateMachine<TState, TEvent>
: StateMachine<TState,TEvent>
where TState : System.Enum
where TEvent : System.Enum
{
public EnumStateMachine(TState initialState,
delegate*<ref TState[,], void> fillMatrix)
: base(initialState)
{
var states = Enum.GetValues(typeof(TState)).Length;
var events = Enum.GetValues(typeof(TEvent)).Length;
TransitionMatrix = new TState[states, events];
fillMatrix(ref TransitionMatrix);
}
public TState[,] TransitionMatrix;
public override void ProcessEvent(TEvent @event)
{
var state = State;
State = TransitionMatrix[
Unsafe.As<TState,int>(ref state),
Unsafe.As<TEvent,int>(ref @event)
];
}
}
Tutaj istotne jest aby enum był zadeklarowany z domyślnymi wartościami 0-N. Ponadto trzeba do stanów dołożyć stan błędu (najlepiej o wartości 0), bo nie ma jak rzucić wyjątku w przypadku gdy pewien stan nie ma przejścia po pewnym zdarzeniu.
Funkcja fillMatrix jest przekazana jako delegat funkcyjny, bo Action nie wspierał parametru ref.
Łańcuchy Markova
Łańcuchy Markova opisują maszyny stanów, gdzie zajście zdarzenia E w stanie A ma prawdopodobieństwo P. Możemy napisać funkcję, która dostając losową liczbę rzeczywistą z zakresu 0-1 oraz stan, zwraca nam zdarzenie zgodne z pewnym prawdopodobieństwem.
public static WeatherEvent WeatherMarkov(WeatherState state, double chance)
{
switch(state.Tag)
{
case WeatherState.Enum.Sun:
if (chance < 0.8)
return WeatherEvent.NoChange;
else
return WeatherEvent.StartRain;
case WeatherState.Enum.Rain:
if (chance < 0.75)
return WeatherEvent.NoChange;
else if (chance < 0.95)
return WeatherEvent.StopRain;
else return WeatherEvent.BringStorm;
case WeatherState.Enum.Storm:
if (chance < 0.6)
return WeatherEvent.NoChange;
// continue to rain
else
return WeatherEvent.StopRain;
default:
throw new PatternMatchException<WeatherState.Enum>(state.Tag);
}
}
Potem możemy jej użyć z naszą maszyną stanów:
var @event = MarkovWeather(stateMachine.State, random.NextDouble());
stateMachine.ProcessEvent(@event);
Podsumowanie
Praca z maszynami stanów opartymi na algebraicznych typach danych, które są niezależne od reszty systemu pozwala nam na pisanie łatwo testowalnego, przenośnego kodu. Kiedy potrzebujemy maksimum wydajności to użycie prostych typów enumeratorów da nam najlepsze wyniki, ale ograniczy nam nieco pole manewru. Wszystko zależy od tego jaki problem się próbuje rozwiązać.
Bardzo możliwe, że w przyszłości zastosuję powyższe rozwiązania w praktyce i postaram się wtedy podlinkować tutaj taki praktyczny przykład.