() translation by (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:
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:
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.
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:
1 |
public class FSM { |
2 |
private var activeState :Function; // points to the currently active state function |
3 |
|
4 |
public function FSM() { |
5 |
}
|
6 |
|
7 |
public function setState(state :Function) :void { |
8 |
activeState = state; |
9 |
}
|
10 |
|
11 |
public function update() :void { |
12 |
if (activeState != null) { |
13 |
activeState(); |
14 |
}
|
15 |
}
|
16 |
}
|
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:
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:
1 |
public class Ant |
2 |
{
|
3 |
public var position :Vector3D; |
4 |
public var velocity :Vector3D; |
5 |
public var brain :FSM; |
6 |
|
7 |
public function Ant(posX :Number, posY :Number) { |
8 |
position = new Vector3D(posX, posY); |
9 |
velocity = new Vector3D( -1, -1); |
10 |
brain = new FSM(); |
11 |
|
12 |
// Tell the brain to start looking for the leaf.
|
13 |
brain.setState(findLeaf); |
14 |
}
|
15 |
|
16 |
/**
|
17 |
* The "findLeaf" state.
|
18 |
* It makes the ant move towards the leaf.
|
19 |
*/
|
20 |
public function findLeaf() :void { |
21 |
}
|
22 |
|
23 |
/**
|
24 |
* The "goHome" state.
|
25 |
* It makes the ant move towards its home.
|
26 |
*/
|
27 |
public function goHome() :void { |
28 |
}
|
29 |
|
30 |
/**
|
31 |
* The "runAway" state.
|
32 |
* It makes the ant run away from the mouse cursor.
|
33 |
*/
|
34 |
public function runAway() :void { |
35 |
}
|
36 |
|
37 |
public function update():void { |
38 |
// Update the FSM controlling the "brain". It will invoke the currently
|
39 |
// active state function: findLeaf(), goHome() or runAway().
|
40 |
brain.update(); |
41 |
|
42 |
// Apply the velocity vector to the position, making the ant move.
|
43 |
moveBasedOnVelocity(); |
44 |
}
|
45 |
|
46 |
(...)
|
47 |
}
|
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:
1 |
public function findLeaf() :void { |
2 |
// Move the ant towards the leaf.
|
3 |
velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); |
4 |
|
5 |
if (distance(Game.instance.leaf, this) <= 10) { |
6 |
// The ant is extremelly close to the leaf, it's time
|
7 |
// to go home.
|
8 |
brain.setState(goHome); |
9 |
}
|
10 |
|
11 |
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { |
12 |
// Mouse cursor is threatening us. Let's run away!
|
13 |
// It will make the brain start calling runAway() from
|
14 |
// now on.
|
15 |
brain.setState(runAway); |
16 |
}
|
17 |
}
|
Der Zustand goHome(), mit dem die Ameise nach Hause geführt wird:
1 |
public function goHome() :void { |
2 |
// Move the ant towards home
|
3 |
velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); |
4 |
|
5 |
if (distance(Game.instance.home, this) <= 10) { |
6 |
// The ant is home, let's find the leaf again.
|
7 |
brain.setState(findLeaf); |
8 |
}
|
9 |
}
|
Schließlich der Zustand runAway(), mit dem die Ameise vor dem Mauszeiger flieht:
1 |
public function runAway() :void { |
2 |
// Move the ant away from the mouse cursor
|
3 |
velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); |
4 |
|
5 |
// Is the mouse cursor still close?
|
6 |
if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { |
7 |
// No, the mouse cursor has gone away. Let's go back looking for the leaf.
|
8 |
brain.setState(findLeaf); |
9 |
}
|
10 |
}
|
Das Ergebnis ist eine Ameise, die von einem FSM- "Gehirn" kontrolliert wird:
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:
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:
Der aktuell aktive Status kann entscheiden, was während eines Übergangs zu tun ist:
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:
1 |
public class StackFSM { |
2 |
private var stack :Array; |
3 |
|
4 |
public function StackFSM() { |
5 |
this.stack = new Array(); |
6 |
}
|
7 |
|
8 |
public function update() :void { |
9 |
var currentStateFunction :Function = getCurrentState(); |
10 |
|
11 |
if (currentStateFunction != null) { |
12 |
currentStateFunction(); |
13 |
}
|
14 |
}
|
15 |
|
16 |
public function popState() :Function { |
17 |
return stack.pop(); |
18 |
}
|
19 |
|
20 |
public function pushState(state :Function) :void { |
21 |
if (getCurrentState() != state) { |
22 |
stack.push(state); |
23 |
}
|
24 |
}
|
25 |
|
26 |
public function getCurrentState() :Function { |
27 |
return stack.length > 0 ? stack[stack.length - 1] : null; |
28 |
}
|
29 |
}
|
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:
1 |
public class Ant { |
2 |
(...)
|
3 |
public var brain :StackFSM; |
4 |
|
5 |
public function Ant(posX :Number, posY :Number) { |
6 |
(...)
|
7 |
brain = new StackFSM(); |
8 |
|
9 |
// Tell the brain to start looking for the leaf.
|
10 |
brain.pushState(findLeaf); |
11 |
|
12 |
(...)
|
13 |
}
|
14 |
|
15 |
/**
|
16 |
* The "findLeaf" state.
|
17 |
* It makes the ant move towards the leaf.
|
18 |
*/
|
19 |
public function findLeaf() :void { |
20 |
// Move the ant towards the leaf.
|
21 |
velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); |
22 |
|
23 |
if (distance(Game.instance.leaf, this) <= 10) { |
24 |
// The ant is extremelly close to the leaf, it's time
|
25 |
// to go home.
|
26 |
brain.popState(); // removes "findLeaf" from the stack. |
27 |
brain.pushState(goHome); // push "goHome" state, making it the active state. |
28 |
}
|
29 |
|
30 |
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { |
31 |
// Mouse cursor is threatening us. Let's run away!
|
32 |
// The "runAway" state is pushed on top of "findLeaf", which means
|
33 |
// the "findLeaf" state will be active again when "runAway" ends.
|
34 |
brain.pushState(runAway); |
35 |
}
|
36 |
}
|
37 |
|
38 |
/**
|
39 |
* The "goHome" state.
|
40 |
* It makes the ant move towards its home.
|
41 |
*/
|
42 |
public function goHome() :void { |
43 |
// Move the ant towards home
|
44 |
velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); |
45 |
|
46 |
if (distance(Game.instance.home, this) <= 10) { |
47 |
// The ant is home, let's find the leaf again.
|
48 |
brain.popState(); // removes "goHome" from the stack. |
49 |
brain.pushState(findLeaf); // push "findLeaf" state, making it the active state |
50 |
}
|
51 |
|
52 |
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { |
53 |
// Mouse cursor is threatening us. Let's run away!
|
54 |
// The "runAway" state is pushed on top of "goHome", which means
|
55 |
// the "goHome" state will be active again when "runAway" ends.
|
56 |
brain.pushState(runAway); |
57 |
}
|
58 |
}
|
59 |
|
60 |
/**
|
61 |
* The "runAway" state.
|
62 |
* It makes the ant run away from the mouse cursor.
|
63 |
*/
|
64 |
public function runAway() :void { |
65 |
// Move the ant away from the mouse cursor
|
66 |
velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); |
67 |
|
68 |
// Is the mouse cursor still close?
|
69 |
if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) { |
70 |
// No, the mouse cursor has gone away. Let's go back to the previously
|
71 |
// active state.
|
72 |
brain.popState(); |
73 |
}
|
74 |
}
|
75 |
(...)
|
76 |
}
|
Das Ergebnis ist eine Ameise, die vor dem Mauszeiger davonlaufen und vor der Bedrohung in den zuvor aktiven Zustand zurückkehren kann:
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!
