() translation by (you can also view the original English article)
Mesin finite-state adalah model yang digunakan untuk merepresentasikan dan mengendalikan aliran eksekusi. Ini sangat cocok untuk menerapkan AI (kecerdasan buatan) dalam game, menghasilkan hasil yang bagus tanpa kode yang rumit. Tutorial ini menjelaskan teori, implementasi dan penggunaan mesin finite-state secara sederhana dan berbasis stack.
Semua ikon dibuat oleh Lorc, dan tersedia di http://game-icons.net.
Catatan: Meskipun tutorial ini ditulis menggunakan AS3 dan Flash, Anda harus bisa menggunakan teknik dan konsep yang sama di hampir semua lingkungan pengembangan game.
Apa itu Mesin Finite-State?
Mesin finite-state, atau disingkat FSM, adalah model perhitungan berdasarkan mesin hipotetis yang dibuat dari satu atau lebih kedudukan. Hanya satu kedudukan yang bisa aktif pada saat bersamaan, sehingga mesin harus berpindah dari kedudukan ke kedudukan lain agar bisa melakukan tindakan yang berbeda.
FSM biasanya digunakan untuk mengatur dan merepresentasikan aliran eksekusi, yang berguna untuk menerapkan AI dalam permainan. "Otak" musuh, misalnya, dapat diimplementasikan dengan menggunakan FSM: setiap kedudukan mewakili sebuah tindakan, seperti serangan atau penghindaran:
FSM dapat diwakili oleh grafik, di mana simpulnya adalah suatu kedudukan dan ujungnya adalah transisi. Setiap tepi memiliki label yang menginformasikan kapan transisi harus terjadi, seperti ketika pemain berada di dekat (player is near ) label pada gambar di atas, yang mengindikasikan bahwa mesin akan beralih dari pengembaraan (wander) menjadi menyerang (attack) jika pemainnya berada di dekatnya.
Merencanakan Kedudukan dan Transisi Mereka
Implementasi FSM dimulai dengan kedudukannya dan transisi yang akan dimilikinya. Bayangkan FSM berikut, mewakili otak seekor semut yang membawa pulang daun:
Titik awalnya adalah kedudukan mencari daun (find leaf), yang akan tetap aktif sampai semut menemukan daunnya. Bila itu terjadi, keadaan saat ini dialihkan untuk pulang ke rumah (go home), yang tetap aktif sampai semut pulang. Saat semut akhirnya tiba di rumah, keadaan aktif menjadi mencari daun lagi (find leaf), jadi semut mengulangi perjalanannya.
Jika keadaan aktif mencari daun (find leaf) dan kursor mouse mendekati semut, maka ada transisi menuju keadaan lari (run away). Sementara keadaan itu aktif, semut akan lari dari kursor mouse. Bila kursor bukan ancaman lagi, ada transisi kembali ke kedudukan mencari daun (find leaf).
Karena ada transisi yang menghubungkan mencari daun (find leaf) dan lari (run away), semut akan selalu lari dari kursor mouse saat mendekati selama semut sedang mencari daunnya. Itu tidak akan terjadi jika kedudukan aktif dalah pulang ke rumah (go home) (lihat gambar di bawah). Dalam hal ini semut akan berjalan pulang tanpa rasa takut, hanya bertransisi ke keadaan daun yang ditemukan (find leaf) saat tiba di rumah.
run away) dan pulang ke rumah (go home).Menerapkan FSM
FSM dapat diimplementasikan dan dienkapsulasi dalam satu kelas, diberi nama FSM misalnya. Idenya adalah menerapkan setiap keadaan sebagai fungsi atau metode, menggunakan properti yang disebut activeState di kelas untuk menentukan kedudukan mana yang aktif:
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 |
}
|
Karena setiap kedudukan adalah sebuah fungsi, sementara kedudkan tertentu aktif, fungsi yang mewakili kedudukan tersebut akan dimunculkan pada setiap pembaruan game. Properti ActiveState adalah petunjuk ke sebuah fungsi, jadi akan menunjuk ke fungsi state yang aktif.
Metode update() dari kelas FSM harus dimunculkan setiap frame game, sehingga bisa memanggil fungsi yang ditunjuk oleh properti ActiveState. Panggilan itu akan memperbarui tindakan kedudukan yang sedang aktif.
Metode setState() akan mentransisikan FSM ke keadaan baru dengan mengarahkan properti ActiveState ke fungsi kedudukan yang baru. Fungsi kedudkan tidak harus menjadi anggota FSM; fungsi itu bisa masuk dalam kelas lain, yang membuat kelas FSM lebih umum dan dapat digunakan kembali.
Menggunakan FSM
Menggunakan kelas FSM sudah dijelaskan, saatnya untuk menerapkan "otak" sebuah karakter. Semut yang dijelaskan sebelumnya akan digunakan dan dikendalikan oleh FSM. Berikut ini adalah representasi kedudukan dan transisi, dengan fokus pada kode:
Semut diwakili oleh kelas Ant, yang memiliki properti bernama otak (brain) dan metode untuk setiap kedudukan. Properti otak (brain) adalah contoh kelas FSM:
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 |
}
|
Kelas Ant juga memiliki properti kecepatan (velocity) dan posisi (position), keduanya digunakan untuk menghitung pergerakan menggunakan integrasi Euler (Euler integration). Metode update() dimunculkan setiap frame game, jadi ini akan meng-update FSM.
Untuk menjaga hal-hal agar tetap sederhana, kode yang digunakan untuk menggerakkan semut, seperti moveBasedOnVelocity(), akan dihilangkan. Informasi lebih lanjut tentang hal itu dapat ditemukan dalam seri memahami Steering Behavior (Understanding Steering Behaviors).
Berikut ini adalah implementasi masing-masing kedudukan, dimulai dengan findLeaf(), kedudukan ini bertanggung jawab untuk membimbing semut ke posisi daun:
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 |
}
|
Kedudukan goHome(), digunakan untuk membimbing semut pulang:
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 |
}
|
akhirnya, kedudukan runAway(), digunakan agar semut menajuhi kusor mouse:
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 |
}
|
Hasilnya adalah semut yang dikendalikan oleh otak "FSM":
Meningkatkan Arus: FSM Berbasis Stack
Bayangkan bahwa semut juga perlu lari dari kursor mouse saat sedang pulang. FSM dapat diperbarui sebagai berikut:
Tampaknya ini adalah sebuah modifikasi sepele, penambahan transisi baru, tapi ini menimbulkan masalah: jika keadaan saat ini adalah lari (run away) dan kursor mouse tidak dekat lagi, keadaan apa yang harus mentransisi semut: pulang ke rumah (go home) atau menemukan daun (find leaf)?
Solusi untuk masalah itu adalah FSM berbasis stack (tumpukan). Tidak seperti FSM yang ada, FSM berbasis stack menggunakan tumpukan untuk mengendalikan kedudukan. Bagian atas tumpukan berisi status aktif; transisi ditangani dengan mendorong atau memunculkan kedudukan dari tumpukan:
Kedudukan aktif saat ini dapat menentukan apa yang harus dilakukan selma proses transisi:
Ini bisa muncul dari tumpukan dan mendorong kedudukan lain, yang berarti transisi penuh (seperti yang dilakukan FSM sederhana). Ini bisa muncul dari tumpukan, yang berarti keadaan saat ini komplit dan keadaan selanjutnya di dalam tumpukan harus aktif. Akhirnya, akan bisa mendorong kedudukan baru, yang berarti keadaan saat ini yang aktif akan berubah untuk sementara waktu, namun saat muncul dari tumpukan, keadaan yang sebelumnya aktif akan mengambil alih lagi.
Menerapkan FSM Berbasis Stack
FSM berbasis stack dapat diimplementasikan dengan menggunakan pendekatan yang sama seperti sebelumnya, namun kali ini menggunakan sejumlah petunjuk fungsi untuk mengendalikan tumpukan. Properti ActiveState tidak lagi dibutuhkan, karena bagian atas tumpukan sudah mengarah ke keadaan aktif saat ini:
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 |
}
|
Metode setState() diganti dengan dua metode baru: pushState() dan popState(); pushState() menambahkan kedudukan baru ke bagian atas tumpukan, sementara popState() menghapus kedudukan di bagian atas tumpukan. Kedua metode tersebut secara otomatis mentransmisikan mesin ke keadaan baru, karena keduanya mengubah bagian atas tumpukan.
Menggunakan FSM Berbasis Stack
Saat menggunakan FSM berbasis tumpukan, penting untuk dicatat bahwa setiap kedudukan bertanggung jawab untuk muncul sendiri dari tumpukan. Biasanya sebuah kedudukan menghapus dirinya dari tumpukan saat tidak lagi dibutuhkan, seperti jika attack() aktif namun targetnya telah mati.
Dengan menggunakan contoh semut, hanya sedikit perubahan yang diperlukan untuk menyesuaikan kode menggunakan FSM berbasis stack. Permasalahan tentang tidak mengetahui keadaan untuk transisi ke sekarang diselesaikan dengan mulus berkat sifat pada FSM berbasis stack:
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 |
}
|
Hasilnya adalah semut yang bisa lari dari kursor mouse, beralih kembali ke keadaan yang sebelumnya aktif sebelum ancaman:
Kesimpulan
Finite-state machine berguna untuk mengimplementasikan logika AI dalam game. Mesin ini dapat dengan mudah diwakili menggunakan grafik, yang memungkinkan pengembang melihat gambar besar, mengutak-atik dan mengoptimalkan hasil akhir.
Implementasi FSM menggunakan fungsi atau metode untuk merepresentasikan kedudukan sangatlah sederhana namun kuat. Hasil yang lebih kompleks lagi dapat dicapai dengan menggunakan FSM berbasis tupukan, yang menjamin aliran eksekusi yang dapat dikelola dan ringkas tanpa berdampak negatif terhadap kode tersebut. Sudah waktunya untuk membuat semua musuh game Anda lebih pintar dengan menggunakan FSM!
