Finite State Machine pada dasarnya adalah melakukan pemecahan behaviour
dari object/agen berdasarkan statenya. Dan nantinya juga harus
didefinisikan aturan2x transisi sehingga state dapat berubah dari yg
satu ke yang lain.
Contoh implementasi FSM di game yaitu di game Pacman, yaitu pada
karakter musuhnya (ghost). 4 hantu yang dikenal dengan nama Pinky,
Clyde, Blinky, dan Inky….
======================================================================
Sekedar warning saja: Source code untuk FSM ini sudah saya revisi
lumayan banyak, udah jauh beda dari yg saya post di sini, jadi bagi yang
mau pake yang terbaru sebaiknya donlot saja di GitHub. Contoh implementasinya juga sudah disertakan
======================================================================
Bentuk diagram state untuk hantu2x tsb kurang lebih seperti ini:
Di mana ada 5 state: Run From Player, Rise, Die, Chase Player, dan Move
Randomly. Dan Antar state terdapat aturan transisi agar dapat melakukan
perubahan state, misal ketika karakter utama memakan ‘pellet’ maka si
musuh ini akan berubah state dari state ‘mengejar’ ke state ‘menjauh’
dari karakter utama, dan seterusnya.
Contoh lain misalnya di game sepakbola: ada state shoot, tackle,
heading, dll. Di game jenis FPS: tembak, cover, reload, get health, dll.
Dan masih banyak lagi contoh implementasi FSM di berbagai macam genre
game.
Finite State Machine di dunia AI Game Programming, merupakan salah satu teknik yang paling sering digunakan. Alasannya yaitu:
1. Implementasinya mudah dan cepat
2. Memudahkan proses debugging. Karena telah dipecah menjadi kepingan
yang lebih kecil, proses debugging kalau terjadi behavoiur yang tidak
semestinya, menjadi lebih mudah
3. Proses komputasi yg minimal, karena sejatinya FSM hanyalah
conditional statement yang dikemas dalam bentuk yang lebih elegan.
4. Fleksibel, dapat dikombinasikan dengan teknik AI lain misalnya fuzzy logic dan neural network
Kekurangannya:
1. Behaviour dari agen mudah diprediksi, karena tidak ada searching dan atau learning di dalam agen tersebut
2. Karena mudah diimplementasi, kadang programmer langsung tembak di
eksekusi tanpa melakukan desain FSM terlbih dahulu. Biasanya akan
terjadi FSM yang terfragmentasi
3. Timbul apa yang dinamakan dengan State Oscillation yaitu ketika batasan antara dua buah state terlalu tipis:
2. Bentuk Implementasi
Ada beberapa bentuk FSM, diantaranya:
1. Naive Approach
Menggunakan conditional statement (if-else atau switch-case) tanpa
memecah object menjadi object2x yang lebih kecil sesuai state nya.
Untuk agen yang cuma punya state yang sedikit, metode ini masih
memungkinkan. Tapi kalau sudah kompleks, penggunaan metode ini jelas
tidak dianjurkan, karena akan membentuk ‘spaghetti code’ dan monolithic
conditional statement. Selain itu juga tidak scalable, tidak fleksibel,
dan proses debugging menjadir lebih rumit.
2. State Transition Table
Bentuk ini sudah mengimplementasikan State Pattern, dengan menempatkan
transition logic di context (untuk lebih jelasnya tentang State Pattern,
baca ini dulu). Bentuk ini juga sering disebut sebagai Classic FSM.
Dengan metode ini dibuat sebuah tabel yang dikenal dengan State Transition Table, bentuknya seperti ini:
Agen akan melakukan query dari tabel tersebut berdasarkan input yang
diterima dari environmentnya. Kemudian ketika salah satu kondisi
terpenuhi, dia akan mengubah current state menjadi state yang baru
sesuai kondisinya.
Dengan begini, maka tentunya akan mempunyai fleksibilitas dan
skalabilitas yang jauh lebih baik daripada jika menggunakan naive
approach. Dengan drawback akan terbentuk monolithic conditional
statements.
3. Embedded Rules
Bentuk ini adalah kebalikan dari bentuk Classical Approach, yang berarti
state transition didefinisikan di state itu sendiri. Dan sama dengan
Classical Approach, bentuk ini juga akan menawarkan fleksibilitas dan
skalabilitas yang baik, namun dengan efek samping agak sulit untuk
di-mantain karena aturan2x transisi diletakkan di state sehingga ketika
terjadi penambahan atau pengurangan state, maka harus dilakukan update
juga terhadap state2x yang terkait.
3. Struktur
Komponen2x nya mirip dengan yang sudah dijelaskan di
State Pattern. Untuk detailnya:
1. State Interface
Ada tiga method di sini:
1. Enter()
Method yang akan dijalankan ketika pertama kali masuk ke state tersebut.
Biasanya digunakan untuk inisiasi data2x atau variabel, atau bisa juga
untuk memainkan animasi ketika masuk state itu
2. Update()
Method yang akan berjalan bersamaan dengan terus berjalannya main game
loop/update. Digunakan untuk menjalankan behaviour agent dan untuk
melakukan checking kondisi apakah harus berpindah state atau tidak
3. Exit()
Method yang dipanggil ketika state tersebut ditinggalkan. biasanya untuk cleanup data2x dan variabel yang sudah tidak digunakan.
2. State Object
Cukup jelas….
3. Finite State Machine
Sebenarnya, ini adalah sebuah context, namun agar reusable, maka dibuat kelas tersendiri.
4. Agent
Context juga, namun di sini agent cukup meng-instatiate object FiniteStateMachine agar mempunyai FSM di dalam dirinya.
Bored with all these bulls**t? 
Well, enough talking and lets dive into the code…..
4. Into the code….
Tapi tunggu sebentar, sebenarnya masih ada beberapa penjelasan lagi sebelum bener2x masuk ke code….
Hehe… Mau bagaimana lagi? untuk mendapatkan hasil yang baik perlu
perencanaan yang baik juga. Maka dari itu, sebelum memulai ke code masri
kita perjelas dulu apa yang akan dibuat di sini:
Contoh ini saya ambil dari buku
Programming Game AI by Example , karya Mark Buckland,
tentunya sudah sy porting ke Flash (Actionscript 3.0). Yang akan dibuat
adalah sebuah agen bernama “Bob” seorang penambang (miner) yang akan
berjalan otonom sesuai dengan kondisi dalam dirinya dan lingkungannya.
Misalnya ketika lelah dia akan tidur, ketika sudah cukup tidur dia akan
berangkant bekerja, dst.
Dan di sini nanti tidak ada aksi konkret yang dilakukan si Bob, tp
memang cuma akan mengeluarkan output berupa text sesuai state yang
sedang berjalan. Kalu cuma sebagai gambaran saja kyknya sekedar text
juga sudah cukup lah.
Untuk lebih jelasnya tentang state dan transisi dari si Bob ini, berikut diagram nya:
Ada empat state: AtHome, Mining, AtBank, dan AtBar…. masing masing punya aturan transisi untuk berpindah ke state lain.
Dan dari sini kita sudah mendapat gambaran bahwa si Bob akan mempunyai
variabel2x seperti: thirsty level, energy, location, jumlah gold
carried, dan bank balance.
Jika behaviour dari Bob sudah cukup jelas, maka selanjutnya adalah
membangun class diagramnya. Strukturnya jelas sama dengan yang sudah
dibahas di atas, cuma untuk kasus ini dibuat lebih simpel dahulu, biar
lebih mudah dimengerti. Dan bentuk implementasi yang digunakan yaitu
Embedded Rule, di mana transisi didefinisikan di masing masing state.
Langsung saja, di bawah ini class diagramnya:
1. State Interface
Sangat simpel, kita cukup membuat 3 method saja di sini, yang nantinya akan diimplement oleh state object:
1: package
2: {
3: public interface IState
4: {
5: function enter():void;
6: function update():void;
7: function exit():void;
8: }
9: }
2. State Machine
Selanjutnya kita buat State Machine nya:
1: package
2: {
3: import states.*;
4:
5: public class StateMachine
6: {
7: private var curState:IState;
8:
9: public function StateMachine()
10: {
11: curState = null;
12: }
13:
14: public function update():void
15: {
16: curState.update();
17: }
18:
19: public function changeState(state:IState):void
20: {
21: if (curState != null)
22: {
23: curState.exit();
24: curState = null;
25: }
26:
27: curState = state;
28: curState.enter();
29: }
30:
31: public function getCurrentState():IState
32: {
33: return curState;
34: }
35: }
36: }
Lets break this sh*t :
7: kita buat object currentState
11: saat object StateMachine ini diinstatiate oleh object lain, set current state dengan null
16: melakukan updating terhadap state yang baru berjalan, dengan cara memanggil method update() yang ada di state object tersebut
19-29: method untuk melakukan pergantian state. Jika current state tidak null, maka jalankan dulu method exit() yang dimiliki state tersebut. Selanjutnya jadikan state yang diinput melalu parameter menjadi current state dan panggil method enter().
3. Base Entity
Base entity ini adalah base class yang nantinya akan diextends oleh
Miner class. Kenapa membuat base clas dulu? ya sapa tau nantinya akan
ditambah agen lain selain si Bob… daripada copy paste code, mending
dipersiapkan dahulu base classnya dari awal….
Okey, ini code di dalam Base Entity:
1: package entities
2: {
3: public class BaseEntity
4: {
5: protected var name:String;
6:
7: protected var curLoc:String;
8:
9: protected var energy:int;
10: protected const maxEnergy:int = 20;
11:
12: protected var thirst:int;
13: protected const maxThirst:int = 10;
14:
15: public function BaseEntity(name:String)
16: {
17: this.name = name;
18:
19: curLoc = Miner.HOME;
20: energy = maxEnergy;
21: thirst = 0;
22: }
23:
24: public function update():void
25: {
26:
27: }
28:
29: public function isTired():Boolean
30: {
31: var temp:Boolean;
32:
33: if (energy <= 0)
34: {
35: temp = true;
36: }
37: else
38: {
39: temp = false;
40: }
41:
42: return temp;
43: }
44:
45: public function isFullyRested():Boolean
46: {
47: var temp:Boolean;
48:
49: if (energy >= maxEnergy)
50: {
51: temp = true;
52: }
53: else
54: {
55: temp = false;
56: }
57:
58: return temp;
59: }
60:
61: public function isThirsty():Boolean
62: {
63: var temp:Boolean;
64:
65: if (thirst >= maxThirst)
66: {
67: temp = true;
68: }
69: else
70: {
71: temp = false;
72: }
73:
74: return temp;
75: }
76:
77: public function isNotThirsty():Boolean
78: {
79: var temp:Boolean;
80:
81: if (thirst <= 0)
82: {
83: temp = true;
84: }
85: else
86: {
87: temp = false;
88: }
89:
90: return temp;
91: }
92:
93: public function increaseEnergy():void
94: {
95: energy += 2;
96: }
97:
98: public function decreaseEnergy():void
99: {
100: energy--;
101: }
102:
103: public function increaseThirst():void
104: {
105: thirst++;
106: }
107:
108: public function decreaseThirst():void
109: {
110: thirst -= 2;
111: }
112:
113: //getter setter
114: public function getEnergy():int
115: {
116: return energy;
117: }
118:
119: public function getThirst():int
120: {
121: return thirst;
122: }
123:
124: public function getLoc():String
125: {
126: return curLoc;
127: }
128:
129: public function setLoc(val:String):void
130: {
131: curLoc = val;
132: }
133:
134: public function getName():String
135: {
136: return name;
137: }
138: }
139: }
5-13: kita buat variabel nama, currentLocation, energy, dan thirstLevel. Serta dua constant untuk menentukan nilai maksimum energy dan thirst level.
17-21: set nama entitas, set current location dengan “home”. Set
energy sesuai energi maksimum, dan set thirst level dengan nilai nol.
Jadi ketika entitias pertama kali diinstatiate mereka akan berada di
rumah, energy nya full, dan thirst level nya nol.
24: method update() kosongkan saja, karena akan nantinya akan di-overriden oleh sub classnya
29-43: method isTired() untuk mendapatkan informasi apakah agen sudah lelah atau belum
45-59: apakah agen sudah benar2x segar atau belum
61-74: memberi informasi apakah agen haus atau tidak
method2x lain sepertinya sudah self-explained, jadi ga perlu dijelaskan lagi….
4. Miner
1: package entities
2: {
3: import states.*;
4:
5: import com.carlcalderon.arthropod.Debug;
6:
7: public class Miner extends BaseEntity
8: {
9: private var myStateMachine:StateMachine;
10:
11: public static const MINE:String = "Mine";
12: public static const BANK:String = "Bank";
13: public static const BAR:String = "Bar";
14: public static const HOME:String = "Home";
15:
16: protected var goldCarried:int;
17: protected const maxGoldCarried:int = 3;
18:
19: protected var goldAtBank:int;
20: protected const wealthy:int = 30;
21:
22: public function Miner(name:String)
23: {
24: super(name);
25:
26: goldCarried = 0;
27: goldAtBank = 0;
28:
29: myStateMachine = new StateMachine();
30: myStateMachine.changeState(new MiningState(this));
31: }
32:
33: override public function update():void
34: {
35: myStateMachine.update();
36: }
37:
38: public function isPocketFull():Boolean
39: {
40: var temp:Boolean;
41:
42: if (goldCarried >= maxGoldCarried)
43: {
44: temp = true;
45: }
46: else
47: {
48: temp = false;
49: }
50:
51: return temp;
52: }
53:
54: public function isWealthy():Boolean
55: {
56: var temp:Boolean;
57:
58: if (goldAtBank >= wealthy)
59: {
60: temp = true;
61: }
62: else
63: {
64: temp = false;
65: }
66:
67: return temp;
68: }
69:
70: public function increaseGoldCarried():void
71: {
72: goldCarried++;
73: }
74:
75: public function depositGold():void
76: {
77: goldAtBank += goldCarried;
78: goldCarried = 0;
79: }
80:
81: //getter setter
82: public function getGoldCarried():int
83: {
84: return goldCarried;
85: }
86:
87: public function getGoldAtBank():int
88: {
89: return goldAtBank;
90: }
91:
92: public function getStateMachine():StateMachine
93: {
94: return myStateMachine;
95: }
96: }
97: }
9: membuat object StateMachine, agar si Miner ini punya kemampuan FSM di dalamnya
16-20: membuat variabel jumlah emas yang dibawa, jumlah emas di
bank, serta konstanta maksimum emas yang bisa dibawa dan jumlah emas di
bank shg bisa disebut kaya (wealthy)
26-27: inisiasi nilai awal goldCarried dan goldAtBank dengan nilai nol
29-30: instatiating object StateMachine dan set state awal dengan state MiningState, berarti dia akan memulai dari kondisi sedang berada di tambang
33: meng-override method update() dari super class. Di sini akan dijalankan method update() di dalam StateMachine
38-52: check apakah kantong miner sudah penuh dengan emas
54-68: check apakah deposit emas di bank sudah memenuhi untuk disebut kaya (wealthy) atau belum
method2x selanjutnya sudah cukup jelas…
5. State Object
1: package states
2: {
3: import com.carlcalderon.arthropod.Debug;
4:
5: import entities.*;
6:
7: public class MiningState implements IState
8: {
9: private var myEntity:Miner;
10:
11: public function MiningState(entity:Miner)
12: {
13: myEntity = entity;
14: }
15:
16: /* INTERFACE IState */
17:
18: public function enter():void
19: {
20: if (myEntity.getLoc() != Miner.MINE)
21: {
22: myEntity.setLoc(Miner.MINE);
23:
24: Debug.log(myEntity.getName() + ": entering mine, lookin' for some gold chunk");
25: }
26: }
27:
28: public function update():void
29: {
30: myEntity.increaseGoldCarried();
31: myEntity.increaseThirst();
32: myEntity.decreaseEnergy();
33:
34: Debug.log(myEntity.getName() + ": wurking at mine, collecting " + myEntity.getGoldCarried() +
35: " chunk of gold. Current energy: " + myEntity.getEnergy() + ". Thirst level: " +
36: myEntity.getThirst());
37:
38:
39: if (myEntity.isTired() == true)
40: {
41: Debug.log(myEntity.getName() + " : I'm tired, heading to home now");
42:
43: myEntity.getStateMachine().changeState(new AtHomeState(myEntity));
44: }
45:
46: if (myEntity.isThirsty() == true)
47: {
48: Debug.log(myEntity.getName() + " : I'm thirsty, lookin' some cold beer at the bar");
49:
50: myEntity.getStateMachine().changeState(new AtBarState(myEntity));
51: }
52:
53: if (myEntity.isPocketFull() == true)
54: {
55: Debug.log(myEntity.getName() + " : Mah pocket is full of gold, I should go to the bank");
56:
57: myEntity.getStateMachine().changeState(new AtBankState(myEntity));
58: }
59: }
60:
61: public function exit():void
62: {
63: Debug.log(myEntity.getName() + ": leavin' this dark gold mine");
64: }
65: }
66: }
9: kita buat object Miner sehingga nantinya state ini punya akses ke method2x milik Miner
18-25: method enter(). Ketika memasuki state ini cek apakah current location benar di tambang (mine), jika tidak ubah dahulu lokasinya mnjd mine.
30-32: karena statenya sekarang sedang bekerja di tambang, maka
tambahkan jumlah emas yang sedang dibawa. Juga tambahkan thrist
levelnya. Untuk energy berarti juga akan terus berkurang.
39-44: cek, jika sudah lelah, maka akan berubah state menjadi AtHomeState
46-47: jika si miner ini haus, dia akan pergi ke bar
53-58: jika kantongnya sudah penuh dengan emas maka dia akan pergi ke bank
61-64: method exit(), sekedar mengeluarkan output text saja…
Begitulah struktur untuk state object MiningState, untuk state2x yang
lain kurang lebih juga seperti itu. Karena kalau di jelaskan satu2x di
sini nanti bakal panjang sekali maka dapat langsung donlot aja source
codenya atau improvisasi sendiri kalau mau…
6. Test
Voila….
Akhir kata, seperti itulah implementasi FSM di actionscript 3.0 versi saya tentunya…
