Birthday Sale! Up to 40% off unlimited courses & creative assets Birthday Sale! Save up to 40%!
Advertisement
  1. Game Development
  2. Artificial Intelligence
Gamedevelopment

Finite-State-Maschinen: Theorie und Implementierung

by
Difficulty:IntermediateLength:LongLanguages:

German (Deutsch) translation by Valentina (you can also view the original English article)

Eine Finite-State-Maschine ist ein Modell zur Darstellung und Steuerung des Ausführungsflusses. Es ist perfekt für die Implementierung von KI in Spielen geeignet und liefert großartige Ergebnisse ohne komplexen Code. Dieses Tutorial beschreibt die Theorie, Implementierung und Verwendung einfacher und stapelbasierter Finite-State-Maschinen.

Alle von Lorc erstellten und auf http://game-icons.net verfügbaren Symbole.

Hinweis: Obwohl dieses Tutorial mit AS3 und Flash geschrieben wurde, sollten Sie in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte verwenden können.


Was ist eine Finite-State-Maschine?

Eine Finite-State-Maschine, kurz FSM, ist ein Berechnungsmodell, das auf einer hypothetischen Maschine basiert, die aus einem oder mehreren Zuständen besteht. Es kann immer nur ein Status aktiv sein, daher muss die Maschine von einem Status in einen anderen wechseln, um verschiedene Aktionen ausführen zu können.

FSMs werden üblicherweise verwendet, um einen Ausführungsfluss zu organisieren und darzustellen, was nützlich ist, um KI in Spielen zu implementieren. Das "Gehirn" eines Feindes kann zum Beispiel mit einem FSM implementiert werden: Jeder Zustand repräsentiert eine Aktion wie attack oder evade:

FSM repräsentiert das Gehirn eines Feindes.

Ein FSM kann durch einen Graphen dargestellt werden, wobei die Knoten die Zustände und die Kanten die Übergänge sind. Jede Kante hat ein Etikett, das angibt, wann der Übergang stattfinden soll, so wie sich player is near der Beschriftung in der obigen Abbildung befindet. Dies zeigt an, dass die Maschine vom wander zum attack übergeht, wenn sich der Spieler in der Nähe befindet.


Planungsstaaten und ihre Übergänge

Die Implementierung eines FSM beginnt mit den Zuständen und Übergängen, die es haben wird. Stellen Sie sich das folgende FSM vor, das das Gehirn einer Ameise darstellt, die Blätter nach Hause trägt:

FSM repräsentiert das Gehirn einer Ameise.

Ausgangspunkt ist der Zustand find leaf, der aktiv bleibt, bis die Ameise das Blatt findet. In diesem Fall wird der aktuelle Status auf go home umgestellt, der aktiv bleibt, bis die Ameise nach Hause kommt. Wenn die Ameise endlich nach Hause kommt, wird der aktive Zustand wieder find leaf, sodass die Ameise ihre Reise wiederholt.

Wenn der aktive Zustand find leaf ist und sich der Mauszeiger der Ameise nähert, erfolgt ein Übergang in den run away-Zustand. Während dieser Zustand aktiv ist, rennt die Ameise vom Mauszeiger weg. Wenn der Cursor keine Bedrohung mehr darstellt, erfolgt ein Übergang zurück in den Zustand find leaf.

Da es Übergänge gibt, die find leaf verbinden und run away, rennt die Ameise immer vom Mauszeiger weg, wenn sie sich nähert, solange die Ameise das Blatt findet. Dies ist nicht der Fall, wenn der aktive Status go home (siehe Abbildung unten). In diesem Fall geht die Ameise furchtlos nach Hause und wechselt erst dann in den Zustand find leaf, wenn sie nach Hause kommt.

FSM repräsentiert das Gehirn einer Ameise. Beachten Sie das Fehlen eines Übergangs zwischen run away und go home.

Implementierung eines FSM

Ein FSM kann in einer einzelnen Klasse implementiert und gekapselt werden, beispielsweise FSM. Die Idee ist, jeden Status als Funktion oder Methode zu implementieren, indem eine Eigenschaft namens activeState in der Klasse verwendet wird, um zu bestimmen, welcher Status aktiv ist:

Da jeder Status eine Funktion ist, während ein bestimmter Status aktiv ist, wird die Funktion, die diesen Status darstellt, bei jeder Spielaktualisierung aufgerufen. Die Eigenschaft activeState ist ein Zeiger auf eine Funktion, sodass sie auf die Funktion des aktiven Status verweist.

Die update() -Methode der FSM-Klasse muss in jedem Spielrahmen aufgerufen werden, damit sie die Funktion aufrufen kann, auf die die activeState-Eigenschaft zeigt. Dieser Aufruf aktualisiert die Aktionen des aktuell aktiven Status.

Die setState()-Methode versetzt den FSM in einen neuen Status, indem die activeState-Eigenschaft auf eine neue Statusfunktion verweist. Die Statusfunktion muss kein Mitglied von FSM sein. Es kann zu einer anderen Klasse gehören, wodurch die FSM-Klasse allgemeiner und wiederverwendbarer wird.


Verwenden eines FSM

Mit der bereits beschriebenen FSM-Klasse ist es Zeit, das "Gehirn" eines Charakters zu implementieren. Die zuvor erläuterte Ameise wird von einem FSM verwendet und gesteuert. Das Folgende ist eine Darstellung von Zuständen und Übergängen, wobei der Code im Mittelpunkt steht:

FSM des Ameisenhirns mit Fokus auf den Code.

Die Ameise wird durch die Ant-Klasse dargestellt, die eine Eigenschaft namens brain und eine Methode für jeden Zustand hat. Die brain-Eigenschaft ist eine Instanz der FSM-Klasse:

Die Ant-Klasse hat auch eine velocity- und eine position-Eigenschaft, die beide zur Berechnung der Bewegung mithilfe der Euler-Integration verwendet werden. Die update()-Methode wird in jedem Spielrahmen aufgerufen, sodass der FSM aktualisiert wird.

Um die Dinge einfach zu halten, wird der Code, der zum Verschieben der Ameise verwendet wird, wie z. B. moveBasedOnVelocity(), weggelassen. Weitere Informationen hierzu finden Sie in der Reihe Lenkverhalten verstehen.

Nachfolgend finden Sie die Implementierung jedes Zustands, beginnend mit findLeaf(), dem Zustand, der dafür verantwortlich ist, die Ameise zur Blattposition zu führen:

Der Zustand goHome(), mit dem die Ameise nach Hause geführt wird:

Schließlich der Zustand runAway(), mit dem die Ameise vor dem Mauszeiger flieht:

Das Ergebnis ist eine Ameise, die von einem FSM- "Gehirn" kontrolliert wird:

Ameise von einem FSM gesteuert. Bewegen Sie den Mauszeiger, um die Ameise zu bedrohen.

Verbesserung des Flusses: Stapelbasiertes FSM

Stellen Sie sich vor, die Ameise muss auch vor dem Mauszeiger weglaufen, wenn sie nach Hause geht. Der FSM kann auf Folgendes aktualisiert werden:

Ant FSM mit neuen Übergängen aktualisiert.

Es scheint eine triviale Modifikation zu sein, das Hinzufügen eines neuen Übergangs, aber es entsteht ein Problem: Wenn der aktuelle Status run away ist und der Mauszeiger nicht mehr in der Nähe ist, in welchen Status sollte die Ameise übergehen: go home oder find leaf?

Die Lösung für dieses Problem ist ein stapelbasierter FSM. Im Gegensatz zu unserem vorhandenen FSM verwendet ein stapelbasierter FSM einen Stapel, um Zustände zu steuern. Die Oberseite des Stapels enthält den aktiven Status. Übergänge werden durch Verschieben oder Löschen von Zuständen vom Stapel behandelt:

Stapelbasiertes FSM

Der aktuell aktive Status kann entscheiden, was während eines Übergangs zu tun ist:

Übergänge in einem stapelbasierten FSM: Pop selbst + Push New; Pop selbst; neu drücken.

Es kann sich vom Stapel lösen und einen anderen Status verschieben, was einen vollständigen Übergang bedeutet (genau wie es das einfache FSM getan hat). Es kann sich vom Stapel lösen, was bedeutet, dass der aktuelle Status vollständig ist und der nächste Status im Stapel aktiv werden sollte. Schließlich kann einfach ein neuer Status verschoben werden, was bedeutet, dass sich der aktuell aktive Status für eine Weile ändert. Wenn er sich jedoch vom Stapel löst, übernimmt der zuvor aktive Status wieder.


Implementierung eines stapelbasierten FSM

Ein stapelbasierter FSM kann mit demselben Ansatz wie zuvor implementiert werden, diesmal jedoch mit einem Array von Funktionszeigern zur Steuerung des Stapels. Die Eigenschaft activeState wird nicht mehr benötigt, da der obere Rand des Stapels bereits auf den aktuell aktiven Status zeigt:

Die setState()-Methode wurde durch zwei neue Methoden ersetzt: pushState() und popState(); pushState() fügt oben im Stapel einen neuen Status hinzu, während popState() den Status oben im Stapel entfernt. Beide Methoden versetzen die Maschine automatisch in einen neuen Zustand, da sie die Oberseite des Stapels ändern.


Verwenden eines stapelbasierten FSM

Bei Verwendung eines stapelbasierten FSM ist zu beachten, dass jeder Status dafür verantwortlich ist, sich vom Stapel zu lösen. Normalerweise entfernt sich ein Status vom Stapel, wenn er nicht mehr benötigt wird, z. B. wenn attack() aktiv ist, das Ziel aber gerade gestorben ist.

Am Beispiel von ant sind nur wenige Änderungen erforderlich, um den Code für die Verwendung eines stapelbasierten FSM anzupassen. Das Problem, den Zustand, in den übergegangen werden soll, nicht zu kennen, ist jetzt dank der Natur des stapelbasierten FSM nahtlos gelöst:

Das Ergebnis ist eine Ameise, die vor dem Mauszeiger davonlaufen und vor der Bedrohung in den zuvor aktiven Zustand zurückkehren kann:

Ameise gesteuert von einem stapelbasierten FSM. Bewegen Sie den Mauszeiger, um die Ameise zu bedrohen.

Abschluss

Finite-State-Maschinen sind nützlich, um KI-Logik in Spielen zu implementieren. Sie können einfach mithilfe eines Diagramms dargestellt werden, mit dem ein Entwickler das Gesamtbild sehen, das Endergebnis optimieren und optimieren kann.

Die Implementierung eines FSM unter Verwendung von Funktionen oder Methoden zur Darstellung von Zuständen ist einfach, aber leistungsstark. Noch komplexere Ergebnisse können mit einem stapelbasierten FSM erzielt werden, der einen überschaubaren und präzisen Ausführungsfluss gewährleistet, ohne den Code negativ zu beeinflussen. Es ist Zeit, alle Ihre Spielfeinde mit einem FSM schlauer zu machen!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.