.png)
ActionScript 3.0: Decision Tree
1. Pendahuluan
Decision Tree (DT) adalah sebuah struktur data pohon (tree) yang mampu mengambil kesimpulan dari permasalahan yang didefinisikan di root node melalui sejumlah decision node yang juga telah didefinisikan sebelumnya.
DT merupakan teknik decision making yang paling sederhana serta merupakan salah satu teknik AI di game programming yang cukup populer.
======================================================================
Sekedar
warning saja: Source code untuk Decision Tree 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 DT yang paling populer yaitu Binary Decision Tree (BDT). Ciri khasnya yaitu hanya mempunyai dua cabang: yes atau no, true atau false, ya atau tidak, dll. Kelebihannya yaitu sangat simple dan mudah dioptimasi.
2. Struktur
Struktur Decision Tree
1. Root Node, sumber dari segala permasalahan…
2. Decision Node, permasalahan2x yang didefinisikan selanjutnya antara root node dengan action node
3. Action Node, akhir dari tree, di mana konklusi sudah didapatkan dan selanjutnya seuatu aksi akan diambil
Class Diagram untuk Decision Tree
Untuk struktur class nya tidak terlalu rumit, hanya ada 3 class dan satu interface.
1. Interface INode
Interface ini hanya punya satu method yaitu makeDecision() yang nantinya akan diimplement oleh ketiga class lainnya.
2. Decision Node
Mendefinisikan percabangan menuju node-node selanjutnya, mendefinisikan query, serta menjalankan method makeDecision() yang akan menentukan ke cabang mana keputusan akan diambil.
3. Action Node
Berisi aksi yang akan dijalankan ketika node ini telah dicapai
4. Decision Tree
Class yang akan digunakan untuk membangun tree dari action node dan decision node, serta mendefinisikan query untuk tiap-tiap decision node.
Class ini juga mengimplement INode, agar bisa dibuat sub-tree dalam tree, Jaga2x kalau tree sudah mulai rumit dan kompleks. Jadi bisa dipecah menjadi bagian yang lebih kecil
3. Into the Code!
Sebelum masuk ke code, sekali lagi kita bahas dulu permasalahannya….
Untuk contoh di sini saya mengambil contoh implementasi BDT dari www.generation5.com, tentunya udah saya buat dalam versi AS3.0. Tree yang akan dibuat adalah seperti ini:
Untuk jalan ceritanya kyknya tidak perlu dijelaskan lagi, dari diagramnya harusnya udah self-explanatory lah…
Intinya ya kayak di game2x gitu, biar AI bisa merespon keadaan di sekitarnya…
Okey, kita mulai dari membuat interface INode nya:
1. Interface INode
1: package com.pzuh.decisiontree
2: {
3: public interface INode
4: {
5: function makeDecision():void;
6: }
7: }
Very simple, hanya ada satu method makeDecision()
2. Decision Node
1: package com.pzuh.decisiontree
2: {
3: public class DecisionNode implements INode
4: {
5: public var falseNode:INode;
6: public var trueNode:INode;
7:
8: public var query:Boolean;
9:
10: public function DecisionNode()
11: {
12:
13: }
14:
15: public function makeDecision():void
16: {
17: if (query == true)
18: {
19: if (trueNode != null)
20: {
21: trueNode.makeDecision();
22: }
23: else
24: {
25: return;
26: }
27: }
28: else
29: {
30: if (falseNode != null)
31: {
32: falseNode.makeDecision();
33: }
34: else
35: {
36: return;
37: }
38: }
39: }
40: }
41: }
5-8: Mendefinisikan variabel falseNode untuk menuju cabang ‘no’, 'false’, ‘tidak’, dll. Variabel trueNode untuk ke cabang sebaliknya. Variabel query menyimpan data boolean hasil pemrosesan pertanyaan di suatu decision node
15: Method makeDecision() akan bekerja secara rekursif, di mana ketika variabel query bernilai true maka trueNode dari decisionNode ini akan menjalankan method makeDecision() juga, begitu seterusnya sampai dicapai sebuah konklusi atau ditemukan node bernilai null. Untuk query yang bernilai false, cara kerjanya juga sama
3. Action Node
Dari diagram yang di atas tadi, berarti ada 3 buah Action Node yaitu: AttackNode, DontAttackNode, dan FleeNode
Berikut ini AttackNode isi dari class AttackNode
1: package tree.node
2: {
3: import com.pzuh.decisiontree.INode;
4:
5: public class AttackNode implements INode
6: {
7: private var myMainClass:Main;
8:
9: public function AttackNode(mainClass:Main)
10: {
11: myMainClass = mainClass;
12: }
13:
14: /* INTERFACE com.pzuh.decisiontree.INode */
15:
16: public function makeDecision():void
17: {
18: myMainClass.getOutputText().text = "Attack!!";
19: }
20: }
21: }
16: method makeDecision() hanya akan mengeluarkan output text “Attack!”. Masih text based, maklum cm buat contoh aja…
Untuk class DontAttackNode dan FleeNode, isinya juga sama, hanya textnya saja yang beda. Jadi ga perlu sy post juga di sini….
4. MainClass
Sebelum masuk ke Tree nya, ada baiknya kalo dibuat dulu MainClassnya, coz ada beberapa data dari mainClass yang harus dipakai di Tree (Sebenernya di ActionNode juga sih)
1: package
2: {
3: import flash.display.*;
4: import flash.events.*;
5: import flash.text.*;
6:
7: import fl.controls.*;
8: import fl.data.*;
9:
10: import tree.Tree;
11:
12: public class Main extends MovieClip
13: {
14: private var query1:Boolean;
15: private var query2:Boolean;
16: private var query3:Boolean;
17:
18: private var myTree:Tree;
19:
20: public function Main():void
21: {
22: myTree = new Tree(this);
23:
24: submitBtn.addEventListener(MouseEvent.CLICK, submitBtnClicked, false, 0, true);
25:
26: comboBox3.visible = false;
27: label3.visible = false;
28: comboBox1.addEventListener(Event.CHANGE, comboBox1Handler, false, 0, true);
29: }
30:
31: private function submitBtnClicked(event:MouseEvent):void
32: {
33: query1 = getComboBoxVal(comboBox1.selectedLabel);
34: query2 = getComboBoxVal(comboBox2.selectedLabel);
35: query3 = getComboBoxVal(comboBox3.selectedLabel);
36:
37: myTree.makeDecision();
38: }
39:
40: private function comboBox1Handler(event:Event):void
41: {
42: var comboBox:Object = event.target;
43:
44: switch(comboBox.selectedLabel)
45: {
46: case "Yes":
47: comboBox2.visible = true;
48: label2.visible = true;
49:
50: comboBox3.visible = false;
51: label3.visible = false;
52: break;
53:
54: case "No":
55: comboBox2.visible = false;
56: label2.visible = false;
57:
58: comboBox3.visible = true;
59: label3.visible = true;
60: break;
61: }
62: }
63:
64: private function getComboBoxVal(val:String):Boolean
65: {
66: switch(val)
67: {
68: case "Yes":
69: return true;
70: break;
71:
72: case "No":
73: return false;
74: break;
75: }
76:
77: return false;
78: }
79:
80: public function getQueryVal(nodeNum:int):Boolean
81: {
82: switch(nodeNum)
83: {
84: case 1:
85: return query1;
86: break;
87:
88: case 2:
89: return query2;
90: break;
91:
92: case 3:
93: return query3;
94: break
95: }
96:
97: return false;
98: }
99:
100: public function getOutputText():TextField
101: {
102: return outputTxt;
103: }
104: }
105: }
Yang akan sy jelaskan di mainClass ini cuma yg penting2x aja, krn selebihnya cm code2x untuk bikin UI nya aja, kalo yg itu males gw ngejelasinnya….
14-16: Mendefinisikan query2x dari tiap decision node, ada 3 query masing2x untuk root node, dan 2 decision node. Berhubung ini cuma contoh, nantinya nilai query ini akan diambil dari combo box.
31: Method submitBtnClicked() dipanggil ketika submit button diklik. DI sini nilai variabel query akan diisi dengan nilai2x yang ada pada combo box. Selanjutnya mehod makeDecision() dari instance myTree dipanggil.
5. Tree
Sebelumnya dibuat sebuah base class untuk tree, Class ini kemudian akan diextends ketika akan membangun sebuah decision tree lain.
1: package com.pzuh.decisiontree
2: {
3: public class DecisionTree implements INode
4: {
5: protected var decisionNodeArray:Array;
6: protected var actionNodeArray:Array;
7:
8: protected var decisionNodeNum:int;
9:
10: public function DecisionTree()
11: {
12: decisionNodeArray = new Array();
13: actionNodeArray = new Array();
14:
15: init();
16: }
17:
18: protected function init():void
19: {
20: for (var i:int = 0; i < decisionNodeNum; i++)
21: {
22: decisionNodeArray.push(new DecisionNode());
23: }
24:
25: constructTree();
26: }
27:
28: protected function constructTree():void
29: {
30: //must be overriden
31: throw new Error("ERROR: Method constructTree() cannot empty and must be overriden");
32: }
33:
34: protected function defineQuery():void
35: {
36: //must be overriden
37: throw new Error("ERROR: Method defineQuery() cannot empty and must be overriden");
38: }
39:
40: public function makeDecision():void
41: {
42: defineQuery();
43:
44: decisionNodeArray[0].makeDecision();
45: }
46: }
47: }
5-6: buat array yang nantinya akan digunakan untuk menyimpan decisionNode dan actionNode
8: variabel decisionNodeNum berisi informasi jumlah decisionNode yang dimiliki oleh sebuah tree
18: method init() akan memasukkan sejumlah decision node ke dalam decisionNodeArray sesuai nilai decisionNodeNum kemudian akan memanggil method costructTree() untuk membangun tree nya
28-38: method constructTree() dan defineQuery() kosong karena akan dioverride dan didefinisikan isinya oleh kelas turunannya. Di sini akan mengeluarkan output error jika ternyata oleh turunannya tidak dioverride
40: method makeDecision() akan memanggil method defineQuery() yang akan menentukan nilai query di tiap decision node, dan kemudian memanggil method makeDecision() dari root node (decisionNodeArray yang berindex 0) yang selanjutnya akan berjalan rekursif sampai sebuah keputusan diambil.
1: package tree
2: {
3: import com.pzuh.decisiontree.DecisionTree;
4: import tree.node.FleeNode;
5:
6: import tree.node.AttackNode;
7: import tree.node.DontAttackNode;
8:
9: public class Tree extends DecisionTree
10: {
11: private var myMainClass:Main;
12:
13: public function Tree(mainClass:Main)
14: {
15: myMainClass = mainClass;
16:
17: super();
18: }
19:
20: override protected function init():void
21: {
22: //tentukan jumlah decision node yang ada dalam tree
23: decisionNodeNum = 3;
24:
25: super.init();
26: }
27:
28: override protected function defineQuery():void
29: {
30: //definisikan kondisi tiap decision node
31: decisionNodeArray[0].query = myMainClass.getQueryVal(1);
32: decisionNodeArray[1].query = myMainClass.getQueryVal(2);
33: decisionNodeArray[2].query = myMainClass.getQueryVal(3);
34: }
35:
36: override protected function constructTree():void
37: {
38: //masukkan action node ke dalam array
39: actionNodeArray[0] = new AttackNode(myMainClass);
40: actionNodeArray[1] = new DontAttackNode(myMainClass);
41: actionNodeArray[2] = new FleeNode(myMainClass);
42:
43: //tentukan percabangan dari tiap2x decision node
44: //decision node #1: "Have you got a weapon?"
45: decisionNodeArray[0].trueNode = decisionNodeArray[1]; //Yes
46: decisionNodeArray[0].falseNode = decisionNodeArray[2]; //No
47:
48: //decision node #2: "Are You close enough to the enemy?"
49: decisionNodeArray[1].trueNode = actionNodeArray[0]; //Yes
50: decisionNodeArray[1].falseNode = actionNodeArray[1]; //No
51:
52: //decision node #3: "Can you tackle the enemy bare-handed?"
53: decisionNodeArray[2].trueNode = actionNodeArray[0]; //Yes
54: decisionNodeArray[2].falseNode = actionNodeArray[2]; //No
55: }
56: }
57: }
20: Meng-override method init() untuk memasukkan jumlah decision node ke variabel decisionNodeNum
28: Meng-override defineQuery(), bisa dilihat sendiri isinya adalah mengisi variabel query milik tiap2x decisionNode dengan query yang didefinisikan di mainClass
38-41: Menginstatiating object AttackNode, DontAttackNode, dan FleeNode, yang kemudian ketiganya dimasukkan ke dalam actionNodeArray
45-54: Mengisi nilai variabel trueNode dan falseNode dari tiap2x decisionNode dengan node2x selanjutnya sesuai dengan struktur di gambar yang udah dibahas sebelumnya
4. Test and Run!
Dan ini adalah sampel implementasi DT yang telah sy buat, silahkan di test:
5. Source Code
Untuk source codenya silakan donlot di link di bawah ini.
6. Referensi
0 comments: