14 October 2011


1. Pendahuluan
Yap, sesuai dengan judulnya, di sini saya akan mencoba menjelaskan mengenai kombinasi antara Finite State Machine (FSM) yang dikombinasikan dengan Decision Tree (DT). Manfaat penggunaan kombinasi antara FSM dan DT ini dapat terlihat ketika kondisi untuk melakukan transisi dari suate state ke state lain sudah mulai kompleks. Biasanya sudah melakukan checking dengan lebih dari satu kondisi.
combo


Berikut ini adalah contoh illustrasinya:

image

Dapat dilihat, terdapat 3 kondisi yang akan dicek: player in sight, player far away, dan player is close by. Dan terdapat dua action. Sehingga kondisi2x tersebut akan digabungkan dengan melakukan konjungsi. Dengan melakukan konjungsi maka berarti kondisi2x tersebut harus dicek semua untuk memastikan apakah sebuah transisi dapat dilakukan. Cukup jelas yang harus dicek adalah kondisi apakah player dalam jarak pandang, cek apakah jarak antara agent dengan player masuk dalam kategori jauh, dan cek apakah jarak agent dengan player masuk kategori dekat.

Jika kompleksitas algoritma untuk melakukan cek thd kondisi2x tsb tidak terlalu rumit dan jumlah kondisi yang dilakukan untuk transisi masih sedikit, mungkin tanpa DT pun tidak masalah. Namun ketika kompleksitas algo nya sudah rumit, tentu akan sangat memakan waktu, apalagi semua kondisi akan selalu di cek.

Maka dari itu untuk DT merupakan solusi yang tepat untuk mengatasi masalah ini, karena DT adalah solusi paling efisien untuk melakukan pencocokan serangkaian kondisi. Untuk lebih jelasnya dapat melihat gambar di bawah ini:

image

Dengan menggunakan DT, tiap2x kondisi tidak perlu dilakukan checking secara bersamaan. Dari gambar, cukup jelas bahwa pada kondisi awal agent hanya akan melakukan checking apakah player dalam jarak pandang agent. Jika tidak, maka akan kembali ke state awal dan kondisi2x lain/selanjutnya dalam tree jelas tidak akan dilakukan checking. Jika ya, baru kemudian akan dilakukan checking jarak. Checking jarak ini juga bisa disimpelkan jika menggunakan DT, cukup cek satu kondisi apakah player ada di dekat agent, jika terpenuhi maka agent akan bertahan, dan jika tidak maka agent akan membunyikan alarm.

2. Implementasi
Sebelum masuk ke implementasi, bagi yang belum tau mengenai FSM dan DT ada baiknya membaca dulu post saya sebelmunya ttg DT dan FSM, karena implementasi nya di sini nanti hanya akan menunjukkan perubahan yang diperlukan untuk mengkombinasikan FSM dan DT.

Okeh, kalau sudah, mari dilanjut…
Untuk melakukan kombinasi antara DT dengan FSM ini hanya perlu menmodifikasi action node dalam tree agar actionnya akan menuju ke suatu state di FSM. Caranya? ya cukup bikin variabel targetState yang nantinya akan dipanggil pada method makeDecision di action node. Bingung? kalo gitu tinggal liat code nya sajah…

FSMActionNode:
   1: package com.pzuh.decisiontree
   2: {
   3:     import com.pzuh.statemachine.IState;
   4:     
   5:     public class FSMActionNode implements INode
   6:     {
   7:         protected var myAgent:Object;
   8:         protected var targetState:IState;
   9:         
  10:         public function FSMActionNode(agent:Object, targetState:IState)
  11:         {
  12:             myAgent = agent;
  13:             this.targetState = targetState;
  14:         }
  15:         
  16:         public function makeDecision():void
  17:         {
  18:             myAgent.getStateMachine().changeState(targetState);
  19:         }
  20:     }
  21: }


8: Mendeklarasikan targetState, state tujuan ketika proses tree sudah sampai pada node ini.

13: Variabel ini selanjutnya akan dimasukkan valuenya via constructor parameter

18: Pada method makeDecision(), method yang akan dieksekusi pada node ini, terdapat aksi di mana agent akan merubah statenya ke targetState



Tree:

Untuk inisiasi actionNode di method constructTree dalam sebuah Tree kurang lebih contohnya seperti ini:


   1: override protected function constructTree():void
   2:         {
   3:             actionNodeArray[0] = new FSMActionNode(myShip, myShip.getState(ShipAI.ATTACK_STATE));
   4:             actionNodeArray[1] = new EvadeNode(myShip, myShip.getState(ShipAI.EVADE_STATE));
   5:             actionNodeArray[2] = new FSMActionNode(myShip, myShip.getState(ShipAI.SHIELDED_STATE));

Bisa diliat kita menginstantiating FSMActionNode baru dan mengisi parametenya dengan sebuah target state.

Trus apa itu kok ada yang namanya EvadeNode?

Well, terkadang untuk berpindah ke state baru, ada proses2x laen yang harus dilakukan. Dan tentunya tidak bisa langsung dilakukan via FSMActionNode (entah emang tdk bisa dilakukan atw saya nya yg cupu). Jadi mau ga mau harus bikin kelas baru yang mengextends kelas FSMActionNode dan meng-override method makeDecision() nya.


Contoh isi dari EvadeNode tadi seperti ini:
   1: package src.decisiontree.node 
   2: {
   3:     import com.pzuh.decisiontree.*;
   4:     import com.pzuh.statemachine.*;
   5:     
   6:     import src.gameObject.ships.ShipAI;
   7:     
   8:     public class EvadeNode extends FSMActionNode
   9:     {
  10:         
  11:         public function EvadeNode(agent:Object, targetState:IState) 
  12:         {            
  13:             super(agent, targetState);
  14:         }    
  15:         
  16:         override public function makeDecision():void
  17:         {
  18:             myAgent.removeTarget();
  19:             
  20:             super.makeDecision();
  21:         }
  22:     }
  23: }

18: Proses tambahannya yaitu memanggil method removeTarget() dulu sebelum pindah ke state baru.

Cm satu baris aja harus bikin kelas baru?

Yah, untuk sementara emang itu solusinya, ntar kalo sy sudah tambah jago, baru deh dipikirkan solusi laennya yg lebih baik…



Terakhir tinggal pake aja tree nya di state awal:

   1: public function update():void 
   2: {    
   3:     myEvadeTree.makeDecision();

Cukup panggil method makeDecision() milik tree nya, dan biarkan da magik happnd….



3. Sekian

Yap, sekian dulu dari saya.

Demo & source code? emang sengaja ga saya buat dan sertakan… males om….

Bikin sendiri aja yah, ga susah2x amad kok….


4. Referensi

0 comments:

Post a Comment