The state machine - is an abstract model containing a finite number of anything. It is used to represent and control the flow of execution of any commands. The state machine is ideally suited for implementationartificial intelligence in games, getting accurate solution without writing a cumbersome and complex code. In this article we consider the theory as well as learn how to use a simple stack-based state machine.
We have already published a series of articles on writing of artificial intelligence with the help of a finite state machine. If you have not read this series, you can do it now:
Author's Note Though the article use ActionScript 3 and Flash, you can easily write in your language.
What is a state machine?
The state machine (or simply FSM - Finite-state machine) is a model of computation based on hypothetical machine states. At one time, only one state can be active. Therefore, to perform any action the machine should change its state.
Finite state machines are typically used to organize and present the flow of doing something.This is especially useful in the implementation of AI in games. For example, to write the "brain" of the enemy: each state is an action (attack, evade, and so on. D.).
Description of states of the automaton
The state machine can be represented as a graph, whose vertices are states and the edges - transitions between them. Each edge has a label that informs about when the transition should occur. For example, the image above shows that the automatic status change «wander» the state «attack» on the condition that the player is next.
Planning states and transitions
The implementation of a finite state machine begins with the identification of its states and transitions between them. Imagine a state machine describing the actions of an ant carrying leaves to the nest:
For descriptions of the intelligence of an ant
The starting point is the state of «find leaf», which remains active as long as an ant finds a sheet. When that happens, the state will change to «go home». The same condition will remain active as long as we do not get to the ant anthill. After that, the state once again changed to «find leaf».
If the state «find leaf» is active, but the cursor is next to the ant, the status changes to «run away». Once the ant is in a fairly safe distance from the mouse cursor will change to the state again «find leaf».
Note that the direction of the home or the house ant is not afraid of the mouse. Why? And because there is no corresponding transition.
For descriptions of the intelligence of an ant. Note the lack of transition between «run away» and «go home»
The implementation of a simple finite state machine
The state machine can be implemented using a single class. We call it the FSM. The idea is to realize the condition as each method or function. We will also use the property activeStateto determine the active state.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public class FSM {
private var activeState :Function; // указатель на активное состояние автомата
public function FSM() {
}
public function setState(state :Function) :void {
activeState = state;
}
public function update() :void {
if (activeState != null) {
activeState();
}
}
}
|
Every state has a function. And so that it will be called for each frame refresh the game. As already mentioned, in activeState will store a pointer to the function of the active state.
The method update () class FSM should be called every frame of the game. And he, in turn, will cause the function of the state, which is currently active.
Method setState () will set a new active state. Furthermore, each function defining a certain state of the automaton, does not have to belong to the class FSM - it makes our class more versatile.
Using the finite state machine
Let's implement AI ant. We have already shown a set of states and transitions between them.We illustrate them again, but this time focus on the code.
For descriptions of the intelligence of an ant, focused on code
Our class is represented by an ant Ant, which is the field of brain. This is just an instance of FSM.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
public class Ant
{
public var position :Vector3D;
public var velocity :Vector3D;
public var brain :FSM;
public function Ant(posX :Number, posY :Number) {
position = new Vector3D(posX, posY);
velocity = new Vector3D( -1, -1);
brain = new FSM();
// Начинаем с поиска листка.
brain.setState(findLeaf);
}
/**
* Состояние "findLeaf".
* Заставляет муравья искать листья.
*/
public function findLeaf() :void {
}
/**
* Состояние "goHome".
* Заставляет муравья идти в муравейник.
*/
public function goHome() :void {
}
/**
* Состояние "runAway".
* Заставляет муравья убегать от курсора мыши.
*/
public function runAway() :void {
}
public function update():void {
// Обновление конечного автомата. Эта функция будет вызывать
// функцию активного состояния: findLeaf(), goHome() или runAway().
brain.update();
// Применение скорости для движения муравья.
moveBasedOnVelocity();
}
(...)
}
|
Class Ant also includes features velocity and position. These variables are used for calculating the motion using the Eulermethod. Function update () is called for each frame refresh the game.
To understand the code, we omit the method implementation moveBasedOnVelocity (). If you want to know more on the subject of motion, read a series of articles Understanding SteeringBehaviors.
The following is the implementation of each of the methods starting with findLeaf () - the state, responsible for the search of the leaves.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public function findLeaf() :void {
// Перемещает муравья к листу.
velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);
if (distance(Game.instance.leaf, this) <= 10) {
// Муравей только что подобрал листок, время
// возвращаться домой!
brain.setState(goHome);
}
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
// Курсор мыши находится рядом. Бежим!
// Меняем состояние автомата на runAway()
brain.setState(runAway);
}
}
|
Status goHome () - used to ant went home.
1
2
3
4
5
6
7
8
9
|
public function goHome() :void {
// Перемещает муравья к дому
velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);
if (distance(Game.instance.home, this) <= 10) {
// Муравей уже дома. Пора искать новый лист.
brain.setState(findLeaf);
}
}
|
And, finally, the state runAway () - used when you roll your mouse cursor on.
1
2
3
4
5
6
7
8
9
10
|
public function runAway() :void {
// Перемещает муравья подальше от курсора
velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);
// Курсор все еще рядом?
if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
// Нет, уже далеко. Пора возвращаться к поискам листочек.
brain.setState(findLeaf);
}
}
|
Improved FSM: automatic, based on the stack
Imagine that an ant on the way home and need to get away from the mouse. So the state will look FSM:
The updated description of the states of intelligence ant
It seems like a trivial change. No such change creates our problem. Imagine what the current status is «run away». If the cursor moves away from the ant, what he should do: go home or find a sheet?
The solution of this problem is a finite state machine, based on the stack. Unlike simple FSM, we have implemented the above, this type of FSM uses a stack for managing states. At the top of the stack is the active state, and transitions occur when adding / removing states from the stack.
The state machine, based on the stack
Here is a graphic demonstration of the finite state machine, based on the stack:
Transitions in the FSM, based on the stack
The implementation of FSM, based on the stack
Such a state machine may be implemented as well as simple. The difference will be the use of an array of pointers to the appropriate state. Property activeState we will not need to becausetop of the stack has to point to an active state.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public class StackFSM {
private var stack :Array;
public function StackFSM() {
this.stack = new Array();
}
public function update() :void {
var currentStateFunction :Function = getCurrentState();
if (currentStateFunction != null) {
currentStateFunction();
}
}
public function popState() :Function {
return stack.pop();
}
public function pushState(state :Function) :void {
if (getCurrentState() != state) {
stack.push(state);
}
}
public function getCurrentState() :Function {
return stack.length > 0 ? stack[stack.length - 1] : null;
}
}
|
Note that the method setState () has been replaced by pushState () (adding a new state to the top of the stack) and popState () (removal state on top of the stack).
Using FSM, based on the stack
Importantly, by using a finite state machine based on the state of each stack is responsible for its removal from the stack without the need for it. For example, the state of attack () itself must remove itself from the stack when the enemy was already destroyed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
public class Ant {
(...)
public var brain :StackFSM;
public function Ant(posX :Number, posY :Number) {
(...)
brain = new StackFSM();
// Начинаем с поиска листка
brain.pushState(findLeaf);
(...)
}
/**
* Состояние "findLeaf".
* Заставляет муравья искать листья.
*/
public function findLeaf() :void {
// Перемещает муравья к листу.
velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);
if (distance(Game.instance.leaf, this) <= 10) {
//Муравей только что подобрал листок, время
// возвращаться домой!
brain.popState(); // removes "findLeaf" from the stack.
brain.pushState(goHome); // push "goHome" state, making it the active state.
}
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
// Курсор мыши рядом. Надо бежать!
// Состояние "runAway" добавляется перед "findLeaf", что означает,
// что состояние "findLeaf" вновь будет активным при завершении состояния "runAway".
brain.pushState(runAway);
}
}
/**
* Состояние "goHome".
* Заставляет муравья идти в муравейник.
*/
public function goHome() :void {
// Перемещает уравья к дому
velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);
if (distance(Game.instance.home, this) <= 10) {
// Муравей уже дома. Пора искать новый лист.
brain.popState(); // removes "goHome" from the stack.
brain.pushState(findLeaf); // push "findLeaf" state, making it the active state
}
if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
// Курсор мыши рядом. Надо бежать!
// Состояние "runAway" добавляется перед "goHome", что означает,
// что состояние "goHome" вновь будет активным при завершении состояния "runAway".
brain.pushState(runAway);
}
}
/**
* Состояние "runAway".
* Заставляет муравья убегать от курсора мыши.
*/
public function runAway() :void {
// Перемещает муравья подальше от курсора
velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);
// Курсор все еще рядом?
if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
// Нет, уже далеко. Пора возвращаться к поискам листочкев.
brain.popState();
}
}
(...)
}
|
Conclusion
Finite state machines are certainly useful for the realization of the logic of artificial intelligence in games. They can easily be represented as a graph, which allows the developer to see all options.
The implementation of a finite state machine states of functions is simple, but at the same time a powerful method. Even more complex weave states can be implemented by FSM.
Комментариев нет:
Отправить комментарий