ActionScript 3.0: Finite State Machine
6:43 PM Actionscript 3.0 , Artificial Intelligence , Flash , Programming , tutorial 2 Comments

siapin kopi dulu, this is gonna be long article…..

1. Pendahuluan

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….

bila kurang jelas, bisa baca ini dulu…

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:

package  
{
    public interface IState 
    {
        function enter():void;
        function update():void;
        function exit():void;
    }    
}

2. State Machine

Selanjutnya kita buat State Machine nya:

package  
{
    import states.*;
    
    public class StateMachine
    {
        private var curState:IState;
        
        public function StateMachine() 
        {
            curState = null;
        }    
        
        public function update():void
        {
            curState.update();
        }
        
        public function changeState(state:IState):void
        {
            if (curState != null)
            {
                curState.exit();
                curState = null;
            }
            
            curState = state;
            curState.enter();
        }
        
        public function getCurrentState():IState
        {
            return curState;
        }
    }
}

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:

package entities 
{
    public class BaseEntity
    {
        protected var name:String;
        
        protected var curLoc:String;        
        
        protected var energy:int;
        protected const maxEnergy:int = 20;
        
        protected var thirst:int;
        protected const maxThirst:int = 10;
        
        public function BaseEntity(name:String) 
        {
            this.name = name;
            
            curLoc = Miner.HOME;
            energy = maxEnergy;
            thirst = 0;
        }    
        
        public function update():void
        {
            
        }
        
        public function isTired():Boolean
        {
            var temp:Boolean;
            
            if (energy <= 0)
            {
                temp = true;
            }
            else
            {
                temp = false;
            }
            
            return temp;
        }
        
        public function isFullyRested():Boolean
        {
            var temp:Boolean;
            
            if (energy >= maxEnergy)
            {
                temp = true;
            }
            else
            {
                temp = false;
            }
            
            return temp;
        }
        
        public function isThirsty():Boolean
        {
            var temp:Boolean;
            
            if (thirst >= maxThirst)
            {
                temp = true;
            }
            else
            {
                temp = false;
            }
            
            return temp;
        }
        
        public function isNotThirsty():Boolean
        {
            var temp:Boolean;
            
            if (thirst <= 0)
            {
                temp = true;
            }
            else
            {
                temp = false;
            }
            
            return temp;
        }
        
        public function increaseEnergy():void
        {
            energy += 2;
        }
        
        public function decreaseEnergy():void
        {
            energy--;
        }
        
        public function increaseThirst():void
        {
            thirst++;
        }
        
        public function decreaseThirst():void
        {
            thirst -= 2;
        }
        
        //getter setter
        public function getEnergy():int
        {
            return energy;
        }
        
        public function getThirst():int
        {
            return thirst;
        }
        
        public function getLoc():String
        {
            return curLoc;
        }
        
        public function setLoc(val:String):void
        {
            curLoc = val;
        }
        
        public function getName():String
        {
            return name;
        }
    }
}

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

package entities 
{    
    import states.*;
    
    import com.carlcalderon.arthropod.Debug;
    
    public class Miner extends BaseEntity
    {
        private var myStateMachine:StateMachine;
        
        public static const MINE:String = "Mine";
        public static const BANK:String = "Bank";
        public static const BAR:String = "Bar";
        public static const HOME:String = "Home";
        
        protected var goldCarried:int;
        protected const maxGoldCarried:int = 3;
        
        protected var goldAtBank:int;
        protected const wealthy:int = 30;
        
        public function Miner(name:String) 
        {
            super(name);
            
            goldCarried = 0;
            goldAtBank = 0;
            
            myStateMachine = new StateMachine();
            myStateMachine.changeState(new MiningState(this));
        }
        
        override public function update():void
        {
            myStateMachine.update();
        }
        
        public function isPocketFull():Boolean
        {
            var temp:Boolean;
            
            if (goldCarried >= maxGoldCarried)
            {
                temp = true;
            }
            else
            {
                temp = false;
            }
            
            return temp;
        }
        
        public function isWealthy():Boolean
        {
            var temp:Boolean;
            
            if (goldAtBank >= wealthy)
            {
                temp = true;
            }
            else
            {
                temp = false;
            }
            
            return temp;
        }
        
        public function increaseGoldCarried():void
        {
            goldCarried++;
        }
        
        public function depositGold():void
        {
            goldAtBank += goldCarried;
            goldCarried = 0;
        }
        
        //getter setter
        public function getGoldCarried():int
        {
            return goldCarried;
        }
        
        public function getGoldAtBank():int
        {
            return goldAtBank;
        }
        
        public function getStateMachine():StateMachine
        {
            return myStateMachine;
        }
    }
}

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

package states 
{
    import com.carlcalderon.arthropod.Debug;
    
    import entities.*;
    
    public class MiningState implements IState
    {
        private var myEntity:Miner;
        
        public function MiningState(entity:Miner) 
        {
            myEntity = entity;
        }
        
        /* INTERFACE IState */
        
        public function enter():void 
        {
            if (myEntity.getLoc() != Miner.MINE)
            {
                myEntity.setLoc(Miner.MINE);
                
                Debug.log(myEntity.getName() + ": entering mine, lookin' for some gold chunk");
            }
        }
        
        public function update():void 
        {
            myEntity.increaseGoldCarried();
            myEntity.increaseThirst();
            myEntity.decreaseEnergy();
            
            Debug.log(myEntity.getName() + ": wurking at mine, collecting " + myEntity.getGoldCarried() + 
            " chunk of gold. Current energy: " + myEntity.getEnergy() + ". Thirst level: " +
            myEntity.getThirst());
            
            
            if (myEntity.isTired() == true)
            {
                Debug.log(myEntity.getName() + " : I'm tired, heading to home now");
                
                myEntity.getStateMachine().changeState(new AtHomeState(myEntity));
            }
            
            if (myEntity.isThirsty() == true)
            {
                Debug.log(myEntity.getName() + " : I'm thirsty, lookin' some cold beer at the bar");
                
                myEntity.getStateMachine().changeState(new AtBarState(myEntity));
            }
            
            if (myEntity.isPocketFull() == true)
            {
                Debug.log(myEntity.getName() + " : Mah pocket is full of gold, I should go to the bank");
                
                myEntity.getStateMachine().changeState(new AtBankState(myEntity));
            }
        }
        
        public function exit():void 
        {
            Debug.log(myEntity.getName() + ": leavin' this dark gold mine");
        }        
    }
}

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….