.png)
ActionScript 3.0: Fuzzy State Machine (FuSM)
Untuk yang kesekian kalinya, saya akan posting tentang state machine. Yap, seperti yang sudah saya utarakan sebelumnya, varian dari state machine sendiri sangat banyak, salah satunya ya yang akan saya bahas kali ini yaitu Fuzzy State Machine atau disingkat FuSM.
Apa itu FuSM? Perbedaan utama dengan FSM/HSM sebenarnya FuSM adalah state machine yang dapat menjalankan lebih dari satu state pada waktu yang sama.
Contoh konkritnya: menembak sambil berlari. Jika pada FSM biasa kita perlu membuat 3 state: menembak, berlari, dan menembak sambil berlari, maka pada FuSM cukup membuat dua state yaitu menembak dan berlari saja, kemudian cukup diaktifkan secara bersamaan.
Dan beberapa poin penting yang harus diperhatikan sebelum masuk lebih dalam ke FuSM ini adalah:
1. FuSM gak ada kaitannya sama sekali dengan Fuzzy Logic. Hanya nama dan beberapa istilah di dalamnya yang sedikit mengambil istilah2x dari Fuzzy Logic, misalnya: istilah Fuzzy itu sendiri & istilah Degree of Membership (DOM) dari fuzzy logic diganti menjadi Degree of Activation (DOA).
2. Tidak ada transisi di FuSM, tidak seperti pada FSM biasanya. Melainkan terdapat Degree of Activation (DOA) yang akan menentukan apakah suatu state dapat diaktifkan atau tidak.
Karena tidak ada transisi maka FuSM punya kelebihan dibanding dengan FSM biasa, yaitu statenya sangat modular, ya, karena kita cukup fokus pada behaviour state tersebut, tidak perlu memikirkan state lain. Selain itu juga tidak akan tercipta state oscillation seperti pada FSM.
Dan kebetulan juga tidak ada definisi yang pasti dari FuSM itu sendiri. Misalnya dari buku AI Game Programming 2nd Ed, Brian Schwab dengan buku Artificial Intelligence for Games, 2nd Ed, Ian Millington, walaupun definisinya sama yaitu state machine yang memungkinkan beberapa state jalan sekaligus, namun dalam implementasinya tidak sama.
Beberapa varian FSM kadang juga disebut sebagai FuSM, walaupun sebenarnya bukan:
1. FSM with Fuzzy Transition, yang udah saya lihat sih hanya sekedar FSM biasa namun mengimplementasikan Fuzzy Logic untuk transisinya.
2. FSM with prioritized transition, kebetulan saya belum pernah lihat seperti apa implementasinya
3. Probabilistic FSM, idem sama yg di atas belum pernah lihat juga.
4. Markov Model, idem juga
5. Fuzzy Logic, yap, Fuzzy Logic biasa, bahkan ga ada kaitannya dengan state machine, biasanya hanya diimplementasikan ke dalam FSM, seperti pada poin no. 1.
Namun, di sini saya akan menggunakan buku pertama karangan Brian Schwab sebagai rujukan utama. Sementara untuk tambahan informasi mengenai FuSM ini bisa dilihat di link ini: rtsairesearch.wordpress.com
Kenapa memakai istilah Fuzzy, sementara hanya menjalankan beberapa state sekaligus jelas tidak mewakili definisi fuzzy itu sendiri? Istilah fuzzy muncul dari DOA yang dimiliki oleh tiap2x state itu sendiri. Di mana dengan DOA ini tercipta behaviour yang bersifat fuzzy/tidak pasti. Tidak seperti pada FSM biasa yang transisinya bersifat crisp, jika A maka B, di FuSM akan dikalkulasi rata2x dari DOA semua state untuk kemudian menjadi batas minimal apakah sebuah state dapat diaktifkan atau tidak. Jadi jelas lebih memberikan kesan abu-abu atw fuzzy. Walaupun pada implementasinya ga DOA juga sering bernilai crisp juga yaitu bernilai 0 dan 1.
Mungkin kurang lebih seperti itu (gw gak terlalu yakin juga sih)
Into The Code
Untuk implementasi codenya sih tidak terlalu panjang, hanya dua class:
1. IFuzzyState, interface yang harus diimplement untuk membuat FuzzyState yang konkret. Kenapa interface? karena tidak ada code di dalam nya jadi saya buat interface saja daripada membuat sebuah Abstract class.
2. FuzzyStateMachine, cukup jelas, machine yang akan menghandle aktivasi state2x yang ada. Sama seperti pada FSM atau HSM biasa.
1. IFuzzyState
package com.pzuh.ai.fuzzystatemachine
{
public interface IFuzzyState
{
function enter():void
function update():void
function exit():void
function getDOA():Number
function removeSelf():void
}
}
Isinya cukup jelas, memuat method enter(), update(), exit(), removeSelf() sama seperti state2x biasa, namun ditambah dengan getDOA(), method untuk mengkalkulasi Degree of Activation dari state tersebut.
2. FuzzyStateMachine
package com.pzuh.ai.fuzzystatemachine
{
import com.pzuh.Basic;
public class FuzzyStateMachine
{
private var activeStates:Array = new Array();
private var stateArray:Array = new Array();
public function FuzzyStateMachine()
{
}
public function addState(state:IFuzzyState):void
{
if (Basic.isElementOfArray(stateArray, state))
{
return;
}
stateArray.push(state);
}
public function isActive(state:IFuzzyState):Boolean
{
if (state.getDOA() > 0)
{
return true;
}
return false;
}
/* calculate the average of Degree of Activation (DOA) for each states
* make sure the value is always between 0.0 and 1.0
* */
private function getAverageDOA():Number
{
var stateCount:int = stateArray.length;
var DOA:Number = 0;
var totalDOA:Number = 0;
for (var i:int = 0; i < stateCount; i++)
{
DOA = stateArray[i].getDOA();
if (DOA < 0)
{
DOA = 0;
}
else if (DOA > 1)
{
DOA = 1;
}
totalDOA += DOA;
}
return totalDOA / stateCount;
}
public function update():void
{
if (stateArray.length <= 0)
{
return;
}
var nonActiveStates:Array = new Array();
/* check each state's DOA
* if it greater than average DOA, add it to active states gtoup
* also check whether it's already in active states group or not,
* so we can call the enter() method for newly added state
* */
var length:int = stateArray.length;
for (var i:int = 0; i < length; i++)
{
if (stateArray[i].getDOA() > getAverageDOA())
{
if (!Basic.isElementOfArray(activeStates, stateArray[i]))
{
activeStates.push(stateArray[i]);
stateArray[i].enter();
}
}
else
{
if (Basic.isElementOfArray(activeStates, stateArray[i]))
{
activeStates.splice(activeStates.indexOf(stateArray[i]), 1);
nonActiveStates.push(stateArray[i]);
}
}
}
var nonActiveLength:int = nonActiveStates.length;
for (var j:int = 0; j < nonActiveLength; j++)
{
nonActiveStates[j].exit();
}
var activeLength:int = activeStates.length;
for (var k:int = 0; k < activeLength; k++)
{
activeStates[k].update();
}
}
public function removeSelf():void
{
activeStates.length = 0;
activeStates = null;
for (var i:int = stateArray.length - 1; i >= 0; i--)
{
stateArray[i].removeSelf();
stateArray.splice(i, 1);
}
stateArray.length = 0;
stateArray = null;
}
}
}
7-8: Dua array, stateArray dan activeStates. Array pertama untuk menyimpan semua state baik yang aktif maupun yang tidak, dan array kedua untuk menyimpan state2x yang aktif saja.
15: Method addState(), cukup jelas, untuk menambahkan state ke machine ini. State baru disimpan di stateArray
25: Method isActive(), untuk memberikan informasi apakah state yang ditentukan sedang aktif atau tidak
38: Method getAverageDOA(), method untuk menghitung nilai rata2x dari DOA untuk semua state. Nilai rata2x inilah yang akan menjadi batas minimal bagi sebuah state untuk dapat diaktifkan atau tidak. Jangan lupa untuk memastikan nilai DOA tiap state adalah antara 0 dan 1.
63: Method update(), method yang akan dipanggil pada main loop sebuah game.
65: Cek apakah ada state di dalam stateArray, jika tidak, maka proses update tidak dapat dilakukan
70: nonActiveStates, array yang digunakan untuk menyimpan state2x yang non-aktif. Karena state2x nonaktif ini nantinya harus di-exit terlebih dahulu.
77: Blok kode yang akan menghitung DOA dari tiap state untuk dibandingkan dengan rata2x DOA semua state. Jika lebih besar maka state itu aktif, masukkan ke dalam activeStates array jika state tersebut belum ada di activeStates array dan panggil method enter(). Jika lebih kecil dan juga berada dalam activeState array, maka keluarkan dari array tersebut dan masukkan ke nonActiveStates array.
98: Memanggil method exit() untuk semua state yang ada di nonActiveState array.
104: Mengupdate semua state yang aktif.
Untuk FuSM kurang lebih seperti itu codenya. Selanjutnya kita bahas untuk contoh implementasinya.
Untuk contoh implementasi FuSM di sini saya akan membuat sebuah bot untuk sebuah pesawat/ship/atau apalah namanya yang punya 4 state:
1. Wander, berjalan random di stage
2. Approach, mendekati target yang ada di areanya
3. Attack, menembak target
4. Evade, menghindari objek jika ada objek yang berada di radius tidak aman.
Dan untuk contoh ini codenya gak akan saya bahas satu persatu, lumayan banyak soalnya. Jadi hanya beberapa bagian yang penting saja.
Inisiasi FuSM:
myFuSM = new FuzzyStateMachine(); myFuSM.addState(new ApproachState(this)); myFuSM.addState(new EvadeState(this)); myFuSM.addState(new WanderState(this)); myFuSM.addState(new AttackState(this));
Insiasi FuSM di class BaseVehicle. Gak ada yang istimewa di sini, hanya menginstatiate object FuSM, dan kemudian menambahkan state2xnya dengan memanggil method addState().
Jangan lupa juga memanggil method update dari FuSM ini di method update class BaseVehicle, agar FuSM dapat terupdate tiap frame juga.
Contoh state:
package vehicle.state
{
import com.pzuh.ai.fuzzystatemachine.IFuzzyState;
import vehicle.BaseVehicle;
public class ApproachState implements IFuzzyState
{
private var myShip:BaseVehicle;
public function ApproachState(ship:BaseVehicle)
{
myShip = ship;
}
/* INTERFACE com.pzuh.ai.fuzzystatemachine.IFuzzyState */
public function enter():void
{
}
public function update():void
{
trace(myShip.getName() + " approaching target");
myShip.approach();
if (!myShip.isInApproachRadius())
{
myShip.removeTarget();
}
}
public function exit():void
{
}
public function getDOA():Number
{
if (myShip.hasTarget())
{
return 1;
}
return 0;
}
public function removeSelf():void
{
}
}
}
Contoh state konkret untuk behaviour Approach. Dapat dilihat pada method updatenya, tidak ada transisi. Hanya ada code untuk mendekati target, dan juga menghapus target jika sudah berada di luar radius.
Dan juga untuk method getDOA() nya, hanya bersifat crisp biasa, tidak fuzzy, jika ada target return 1 dan sebaliknya. Ya karena kita perlu bot yang responsif, tiap ada target terlihat harus dengan segera dikejar.
package vehicle.state
{
import com.pzuh.Basic;
import vehicle.BaseVehicle;
import com.pzuh.ai.fuzzystatemachine.IFuzzyState
public class AttackState implements IFuzzyState
{
private var myShip:BaseVehicle
public function AttackState(ship:BaseVehicle)
{
myShip = ship;
}
/* INTERFACE com.pzuh.ai.fuzzystatemachine.IFuzzyState */
public function enter():void
{
}
public function update():void
{
trace(myShip.getName() + " shooting target");
myShip.shoot();
}
public function exit():void
{
}
public function getDOA():Number
{
if (myShip.hasTarget())
{
return 1 - (Basic.getObjectDistance(myShip, myShip.getTarget()) / BaseVehicle.APPROACH_RADIUS);
}
return 0;
}
public function removeSelf():void
{
}
}
}
State Attack, tidak jauh beda dengan state sebelumnya, hanya saja jika dilihat pada method getDOA(), state ini bersifat fuzzy, karena melakukan perhitungan dulu terhadap jarak dia dengan target. Karena nilai DOA harus antara 0 dan 1, maka harus diubah sedemikian rupa agar kita mendapat angka antara 0 dan 1.
Seperti itulah contoh implementasinya, gak terlalu make sense sih karena memang kasusnya terlalu simple untuk dipaksa menggunakan FuSM.
Running Time
Hasil akhirnya adalah seperti berikut ini:
Kalo gw bilang gak ada bedanya dengan FSM biasa juga. Tp ya sudahlah…
Source Code
Referensi
AI Game Programming 2nd Ed, Brian Schwab
rtsairesearch.wordpress.com
untuk implementasi 3D dikombinasikan dengan algoritma GnT (generate and test) memungkinkan apakah tidak?
ReplyDelete