Zustandsautomaten – Finite State Machine (FSM)

In meinem letzten Artikel über Bézier-Kurven hatte ich ja bereits angekündigt, dass ich einen Artikel über Zustandsautomaten schreiben möchte, da dies eine der Grundlagen für den Editor für die Bézier-Kurven ist. Hier ist nun der versprochene Artikel.

Auch in diesem Artikel möchte ich eher auf die praktische Anwendung, als auf die graue Theorie eingehen. Die hier vorgestellte FiniteStateMachine ist sicherlich nicht der Weisheit letzter Schluss, hat sich aber bei mir bereits häufig bewährt und war bisher für mich sehr gut verwendbar. Wer es genau wissen will, der wird in der theoretischen Informatik fündig. Ein guter Ausgangspunkt dafür ist sicherlich mal wieder Wikipedia.

Was kann man sich nun unter eine FiniteStateMachine (kurz FSM) vorstellen? Eine FSM ist ein Automat, der verschiedene Zustände annehmen kann. Die FSM nimmt Eingaben an und produziert Ausgaben und berücksichtigt dabei den aktuellen Zustand. Gleichzeitig kann eine Eingabe zu einer Zustandsänderung führen.

Ein kleines Beispiel aus dem Bereich der KI (Künstliche Intelligenz) von Spielen:

Gegeben sei ein Strategiespiel in dem man einzelne Einheiten befehligen kann. Mein Automat ist dabei die einzelne Einheit, z.B. ein Panzer. Diese Einheit bzw. besser gesagt dieser Automat kann nun unterschiedliche Zustände annehmen, die sein Verhalten beeinflussen. Dies wären zum Beispiel: Warten, Folgen, Angriff, Patroullieren. Als Eingaben dienen echte Eingaben vom Spieler (z.B. Befehlsschaltfläche wird angeklickt), aber auch Ereignisse in der Umwelt (z.B. Gegner in Sichtweite). Die Ausgabe ist in diesem Fall auch die tatsächliche Ausgabe auf dem Bildschirm.

Der Vorteil ist dabei, dass wir jeden einzelnen Zustand isoliert betrachten und entwickeln können und später auch sehr einfach in der Lage sind, neue Zustände zu entwickeln, einzelne zu ändern oder ganz zu entfernen, ohne die gesamte Logik anpassen zu müssen. Es wird auch vermieden, dass wir riesige Switch- oder If-Statements erzeugen müssen, die jede Eventualität abfangen können.

Das Prinzip ist jedenfalls relativ einfach und sehr universell einsetzbar. In diesem Artikel möchte ich – wie bereits angekündigt – eine FSM für einen Editor vorstellen bzw. diese als konkretes Beispiel verwenden.

Fangen wir mit der abstrakten Basisklasse FiniteStateMachine an, die als Grundlage dient. Gleichzeitig definiere ich noch ein handliches Interface, welche diese Klasse beschreibt.

    public interface IFiniteStateMachine
    {
        void ChangeState(IState newState);
    }

    public abstract class FiniteStateMachine : IFiniteStateMachine
    {
        IState _state;

        public IState State
        {
            get { return _state; }
            private set { _state = value; }
        }

        public void ChangeState(IState newState)
        {
            if (State == newState) return;

            IState oldState = State;
            if (State != null) State.Leave(this, oldState);
            State = newState;
            State.Enter(this, oldState);
        }
    }

Die Basisklasse ist sehr einfach gehalten. Im Grunde genommen wird nur der aktuelle Zustand (IState) in einer Member-Variablen gehalten und mittels einer Eigenschaft nach außen verfügbar gemacht. Zu beachten ist, dass über diese Eigenschaft der Zustand nicht verändert werden kann. Dies ist wichtig, da bei einer Zuständsänderung Eingangs- und Ausgangsbedingungen geprüft werden müssen bzw. der ursprüngliche Zustand eine Meldung bekommt, dass er verlassen wird und der neue Zustand eine Meldung bekommt, dass er jetzt aktuell ist. Dies erfolgt über die Methode ChangeState.

Zur Vervollständigung benötigen wir nun nur noch den eigentlichen Zustand bzw. dessen Interface. Dies ist auch nicht weiter kompliziert:

    public interface IState
    {
        String Name { get; }
        Boolean Enter(FiniteStateMachine fsm, IState oldState);
        Boolean Leave(FiniteStateMachine fsm, IState oldState);
    }

Das sieht jetzt auf den ersten Blick sicherlich alles sonderbar und vor allem umständlich aus. Ist es auch, aber aus einem sehr guten Grund, wie wir im folgenden noch erfahren werden.

Fangen wir mit ein bisschen Planung an, denn wir müssen wissen, was der Editor so alles können soll. Der Editor soll später zwei unterschiedliche Eingabemethoden kennen: Tastatur und Maus. Es soll unterschiedliche Zustände geben:

1. Select-State
2. MoveBasePoint-State
3. MoveControlPointState

Aber was bedeutet dies nun alles? Ganz einfach: Sobald die FSM instantiiert wird, ist der Standard-Zustand der Select-Zustand. Dies prüft ganz einfach, ob beim Klicken der linken Maustaste ein Punkt an der entsprechenden Stelle existiert. Existiert ein Punkt, so wird geprüft ob dies der Start-/End-Punkt oder ein Kontrollpunkt ist. In Abhängigkeit davon wird entweder der Zustand MoveBasePoint oder MoveControlPoint gesetzt.

In Code ausgedrückt ist dies auch nicht viel komplizierter und sogar sehr übersichtlich, wie du im folgenden sehen wirst. Leider ist es eine größere Menge an Code, auf die ich aber detailliert eingehen werde.

Zunächst konkretisieren wir den Zustand, also den State.

    public abstract class EditorState : IState
    {
        public abstract string Name
        {
            get;
        }

        public abstract bool Enter(EditorStateMachine fsm, EditorState oldState);
        public abstract bool Leave(EditorStateMachine fsm, EditorState oldState);

        public bool Enter(FiniteStateMachine fsm, IState oldState)
        {
            return Enter(fsm as EditorStateMachine, oldState as EditorState);
        }

        public bool Leave(FiniteStateMachine fsm, IState oldState)
        {
            return Leave(fsm as EditorStateMachine, oldState as EditorState);
        }

        public virtual void HandleInput(EditorStateMachine fsm)
        {

        }
    }

Dies ist der Sourcecode des abstrakten Basis-Zustand. Die Klasse ist als abstrakt markiert, da wir nur mit spezialisierten Zuständen arbeiten möchten, wie z.B. dem Select-Zustand.

Interessant sind die Zeilen 08 bis 19. Hier definiere ich eine neue Enter- und Leave-Methode, die mit unseren konkretisierten Basis-Klassen arbeitet. Dies ist eine kleine Vereinfachung, damit wir uns im folgenden ein paar Castings sparen können.

Da die Behandlung von Eingaben von unserem jeweiligen und aktuellen Zustand abhängig ist, habe ich direkt noch eine virtuelle HandleInput-Methode angelegt. Diese kann von einem konkreten Zustand überschrieben werden und damit auf Eingaben reagieren, doch dazu später mehr, wenn wir den SelectState besprechen.

Die nächste wichtige Klasse ist unsere eigentliche StateMachine, die EditorStateMachine.

    public class EditorStateMachine : FiniteStateMachine, IFiniteStateMachine
    {
        private MouseState lastMouseState = Mouse.GetState();
        private MouseState mouseState;
        private KeyboardState lastKeyboardState = Keyboard.GetState();
        private KeyboardState keyboardState;
        private Vector2 mousePosition;

        public EditorStateMachine()
        {
            ChangeState(SelectState.Instance);
        }

        public void Update(GameTime gameTime)
        {
            this.mouseState = Mouse.GetState();
            this.keyboardState = Keyboard.GetState();

            this.mousePosition = new Vector2(mouseState.X, mouseState.Y);

            State.HandleInput(this);

            this.lastMouseState = mouseState;
            this.lastKeyboardState = keyboardState;
        }

        public Vector2 MousePosition
        {
            get
            {
                return this.mousePosition;
            }
        }

        public new EditorState State
        {
            get
            {
                return base.State as EditorState;
            }
        }

        public bool LeftMousePressed
        {
            get
            {
                return this.lastMouseState.LeftButton == ButtonState.Released &&
                       this.mouseState.LeftButton == ButtonState.Pressed;
            }
        }
    }

Da dies weder ein C# noch XNA-Grundlagenartikel werden soll, werde ich in dieser Klasse recht viel Code überspringen und nur die interessanten Stellen näher erläutern. Member-Variablen, Eigenschaften und einfaches Input-Handling setze ich einfach als bekannt voraus.

Fangen wir mit dem Konstruktor und Zeile 11 an. Unser Standard-Zustand ist der SelectState, welchen wir mit der Methode ChangeState setzen. Die Eigenschaft .Instance gibt uns eine fertige Instanz dieses Zustands zurück und erspart uns, diese mit new jedesmal neu erzeugen zu müssen. Was genau dahintersteckt sehen wir gleich, wenn wir den SelectState genauer durchleuchten.

Die Update-Methode ab Zeile 14 ist Standard, hervorzuheben ist hier nur die Zeile 21. Hier wird die HandleInput-Methode des aktuellen Zustand aufgerufen. Damit übergeben wir die Kontrolle an den aktuellen Zustand und definieren damit indirekt das Verhalten des Editors.

Ab Zeile 35 habe ich die State-Eigenschaft neu definiert, um uns jedesmal ein Casting zum Typ EditorState zu ersparen.

Ab Zeile 43 kommen Hilfsmethoden und -eigenschaften. Momentan ist dies lediglich eine Einzige, aber daran erkennt man schon, worauf dies hinauslaufen wird. Der aktuelle Zustand enthält später nicht den Code, der von jedem Zustand gebraucht werden könnte, sondern bemüht dafür die zentrale StateMachine, die solch wichtige Informationen vorhält und bereitstellt.

Das ist sie bereits, die komplette EditorStateMachine. Schlicht und einfach, auch wenn dies ein wenig mehr Code ist, als eine ähnliche Funktionalität mit verschachtelten If’s direkt in der Update-Methode hätte. Dies ist selbstverständlich noch nicht die komplette Klasse, aber für das Verständnis sollte es ausreichen und es wird ja auch noch einen Folgeartikel geben, in dem ich den Editor noch genauer beschreiben werde.

Kommen wir nun zum letzten Puzzlestück unseres Zustandsautomaten, dem konkreten Zustand SelectState.

    public class SelectState : EditorState
    {
        private static EditorState instance;
        public static EditorState Instance
        {
            get
            {
                if (instance == null)
                {
                    instance = new SelectState();
                }

                return instance;
            }
        }

        public override string Name
        {
            get 
            { 
                return "Select"; 
            }
        }

        public override bool Enter(EditorStateMachine fsm, EditorState oldState)
        {
            // nothing to do
            return true;
        }

        public override bool Leave(EditorStateMachine fsm, EditorState oldState)
        {
            // nothing to do
            return true;
        }

        public override void HandleInput(EditorStateMachine fsm)
        {
            if (fsm.LeftMousePressed)
            {
                // test for Start/Endpoint
                fsm.ChangeState(MoveBasePoint.Instance);

                // test for Controlpoint
                fsm.ChangeState(MoveControlPoint.Instance);
            }
        }
    }

Dieser implementiert im Grunde genommen nur die abstrakte Basisklasse EditorState. Dabei gibt es aber ein paar kleine, aber feine Besonderheiten.

Zuerst eine kleine Abwandlung des Singleton-Patterns. Um auf die konkrete Instanz eines Zustandes zuzugreifen und diese einfach mit z.B. SelectState.Instance aufrufen zu können, erzeugen wir ganz einfach eine statische Member-Variable des jeweiligen EditorState um die Instanz zu speichern. In der zugehörigen statischen Eigenschaft Instance prüfen wir nun zunächst, ob bereits eine Instanz erzeugt wurde und machen dies, wenn dies noch nicht geschehen ist. Erst dann geben wir die konkrete Instanz als Ergebnis zurück. Damit können wir einfach auf automatisch erzeugte Instanzen eines Zustands zugreifen.

Ansonsten ist in diesem Fall eigentlich nur die HandleInput-Methode interessant, die automatisch von unserer EditorStateMachine aufgerufen wird. Die Prüfung dort ist sehr, sehr einfach und übersichtlich und das ist auch der entscheidende Vorteil. Wir prüfen schlicht und einfach ob die linke Maustaste gedrückt wurde. Ist sie gedrückt, dann prüfen wir, ob sich ein Start-/End-Punkt unter dem Mauscursor befindet und setzen den neuen Zustand MoveBasePoint (Zeile 42, der eigentliche Hit-Test mit Rectangle.Intersects ist nicht aufgeführt). Danach prüfen wir noch, ob eine Kontrollpunkt geklickt wurde und verzweigen ggfls. in den entsprechenden Status.

Die Magie dabei ist nun, dass wir eine sehr einfache Regel im jeweiligen Zustand haben. Im SelectState ist dies lediglich:

  • Start-/Endpunkt geklickt? -> MoveBasePoint-Zustand setzen
  • Kontrollpunkt geklickt? -> MoveControlPoint-Zustand setzen

Was im Falle eines Klicks passiert, ist für den SelectState vollkommen uninteressant, da dieser schlicht und einfach die Kontrolle an einen der anderen Zustände abgibt. Dieser hat dann wieder einfache Regeln, was nun zu tun ist.

Ich zeige für den nächsten Zustand keinen konkreten Code mehr, aber möchte noch auf ein paar interessante Aspekte eingehen. Code gibt es erst im Folgeartikel, aber trotzdem sind diese Hinweise gut geeignet um das bisher gelernte ein wenig zu vertiefen und den fleissigen Entwickler in die Lage zu versetzen, weiter zu entwickeln und vielleicht dem nächsten Artikel so schon vorgreifen kann.

Im Zustand MoveBasePoint können wir sehr gut die Methoden Enter verwenden, die automatisch aufgerufen wird, sobald dieser Zustand aufgerufen wird. In Enter speichern wir die Position des geklickten Punktes in einer Member-Variablen. Wir sichern also den aktuellen Stand bei Eintritt in den Zustand. In HandleInput prüfen wir dann, ob die Escape-Taste gedrückt wurde, welche zu einem Abbruch führen soll (so wie in Blender). In diesem Fall soll einfach die vorherige Position des Punktes angenommen werden, die wir ja in Enter gesichert haben und wieder in den SelectState gewechselt werden.

In HandleInput holen wir nun einfach die aktuelle Mausposition von unserer EditorStateMachine und setzen die Position des aktuellen Punkts auf exakt diese Position.

Zuletzt prüfen wir noch, ob die Maustaste losgelassen wurde. Dies führt dazu, dass wir wieder in den SelectState springen, um den nächsten Punkt bewegen zu können.

Man sieht also, auch MoveBasePoint ist sehr einfach und übersichtlich gestaltet:

  • aktuellen Punkt auf aktuelle Mausposition setzen
  • Escape gedrückt? -> Ursprüngliche Position wiederherstellen und Wechsel in SelectState
  • Maustaste losgelassen? -> Wechsel in SelectState

Dies war es auch schon wieder mit diesem Artikel, in dem ich versucht habe, das Konzept des Zustandsautomaten zu vermitteln. Komplexe Regelwerke für AI, Editoren oder viele andere Anwendungsfälle können so schnell und einfach in Code gegossen werden. Zu jedem Zeitpunkt ist dabei ein einfache Erweiterbarkeit garantiert und ein Debugging ist auch relativ einfach, da immer nur die Teilregeln eines Zustandes berücksichtigt werden müssen.

Im Folgeartikel werde ich noch etwas genauer auf die eigentliche Implementierung des Editors für Bézier-Kurven eingehen. Dieser Artikel ist dafür aber bereits eine wichtige Grundlage, so dass ich im nächsten Artikel nur noch die Besonderheiten und die eigentliche Funktionalität beschreibe und nicht mehr erklären muss, wie und warum eine FSM funktioniert.

Vielen Dank für die Aufmerksamkeit und bis zum nächsten Artikel…

Veröffentlicht am 11.05.2011 in Algorithmen, C#, XNA und mit , , , getaggt. Setze ein Lesezeichen auf den Permalink. 13 Kommentare.

  1. Ein sehr guter Artikel (mal wieder), ich bin noch gar nicht auf die Idee gekommmen eine FSM in einem Editor einzusetzen.
    Wo ich sie aber benutzt habe ist im AI Contest, und da hatte meine einen Stack. Ich bin mir jetzt nicht sicher, ob der zur „normalen“ FSM gehört, aber er ist für AI extrem praktisch, da man den Basis Zustand nicht speichern muss, in den eine Einheit zurückfällt, wenn sie z.B. einen Feind getötet hat.

    • Danke sehr🙂

      Ein Stack von Zuständen kann sehr hilfreich sein, hängt aber auch stark vom Anwendungsgebiet ab und auch ein wenig von den Vorlieben. Bei einer AI, gerade wenn man auch noch Fuzzy-Logiken verwendet ist ein Stack wichtiger, als bei einem Editor, wo es klar abgegrenzte und definierte Statusübergänge gibt.

      State-Machines sind jedenfalls extrem hilfreich in vielen „Lebenslagen“. Weitere Beispiele sind z.B. Parser, Tokenizer bzw. Interpreter aller Art (z.B. XML als einfachstes Beispiel) oder aber ein weiteres Beispiel, wenn man es etwas abstrakter sieht, die Bewaffnung in einem RPG. Diese „Basistechnologie“ kann man ja beliebig ausweiten und vor allem weiterentwickeln.

  2. Netter Artikel!

    Eine Kleinigkeit in dem IState-Interface:
    Boolean Enter(FiniteStateMachine fsm, IState oldState);
    macht mehr Sinn den Parameter newState zu nennen😉

    • Danke sehr… Trotzdem muss ich dir wiedersprechen😉 Es wird ja die Enter-Methode des neuen States aufgerufen und dieser bekommt – um evtl. noch Daten zu holen bzw. zu wissen, woher die Statusänderung kommt – den alten, d.h. vorherigen State übergeben. Der „newState“ ist ja bereits bekannt, da dieser ja ganz einfach über „this“ zu erreichen ist.

  3. Netter Blog, sehr informativ und schoen gemacht.

  4. binary101010

    Sehr schöner Artikel.
    Vielen Dank dafür!

    Gruß Binary

  5. Hi Glatzemann,

    guter Artikel wie immer. Das kommt in etwa da hin, worüber wir in „verweise und referenzen oder wie greife ich auf die game klasse zu“ geredet haben. Hast du vielleicht eine List mit solchen Konstrukten, müsste nicht mal eine Beschreibung dabei sein.
    Gibt es Design Patterns die speziell in der Spieleentwicklung eingesetzt werden oder dort Sinn machen?

  6. Sehr interessanter Artikel, hab einiges draus gelernt. Danke dafür.🙂

    Eine Frage hätte ich aber: Wozu haben die Enter- und die Leave-methode Bool als Rückgabetyp? Das wird ja in der ChangeState-methode gar nicht verwendet.

    • Ich verwende diese in der Regel dazu, daß der State selbst entscheiden kann, ob er die Kontrolle übernehmen kann oder abgeben möchte. Wird false zurückgegeben, so ist/war der State-Change nicht erfolgreich.

  1. Pingback: Bézier, oder: Wie bringe ich jemanden locker um die Ecke « "Mit ohne Haare"

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

Folgen

Erhalte jeden neuen Beitrag in deinen Posteingang.

Schließe dich 140 Followern an

%d Bloggern gefällt das: