Ooops
January 15, 2021, 06:25:06 PM

### Author Topic: [bb] Binary Decision Tree by Techlord [ 1+ years ago ]  (Read 525 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bb] Binary Decision Tree by Techlord [ 1+ years ago ]
« on: June 29, 2017, 12:28:42 AM »
Title : Binary Decision Tree
Author : Techlord
Posted : 1+ years ago

Description : Blitz3D Version of Binary Decision Tree AI Algorithm found in <a href="http://www.generation5.org/content/2004/bdt-implementation.asp" target="_blank">Article[/url] and <a href="http://www.generation5.org/content/2004/data/DecisionTree.zip" target="_blank">C++ Source Code[/url].

Code :
Code: BlitzBasic
1. ;//TreeNode
2.
3. Type TreeNode
4.         Field m_strQuestOrAns\$;
5.         Field m_iNodeID%
6.         Field m_pYesBranch.TreeNode
7.         Field m_pNoBranch.TreeNode
8. End Type
9.
10. Function TreeNodeNew.TreeNode(nodeID%=0,newQorA\$="");
11.         ;set the objects pointers To Null in Default constructor
12.         this.TreeNode = New TreeNode
13.         thism_iNodeID = nodeID
14.         thism_strQuestOrAns = newQorA
15.         thism_pYesBranch = Null
16.         thism_pNoBranch= Null
17.         Return this
18. End Function
19.
20. Function TreeNodeDelete(this.TreeNode)
21.         Delete this
22. End Function
23.
24. ;// DecisionTree
25.
26. Type DecisionTree
27.         Field m_pRootNode.TreeNode;
28. End Type
29.
30. Function DecisionTreeRemoveNode(this.DecisionTree,node.TreeNode)
31.         If(node <> Null)
32.                 If(nodem_pYesBranch <> Null) DecisionTreeRemoveNode(this,nodem_pYesBranch);
33.                 If(nodem_pNoBranch <> Null) DecisionTreeRemoveNode(this,nodem_pNoBranch);
34.                 Print("deleting node "+nodem_iNodeID);
35.                 Delete node;
36.         EndIf
37. End Function
38.
39. Function DecisionTreeOutputBinaryTree(this.DecisionTree,tag\$,currentNode.TreeNode)
40.         If(currentNode = Null) Return
41.
42.         Write("[" + tag\$ + "] node id = ")
43.         Write(currentNodem_iNodeID)
45.         Print(currentNodem_strQuestOrAns)
46.
47.         ; Go down yes branch
48.         DecisionTreeOutputBinaryTree(this,tag\$+".1",currentNodem_pYesBranch);
49.         ; Go down no branch
50.         DecisionTreeOutputBinaryTree(this,tag\$+".2",currentNodem_pNoBranch);
51. End Function
52.
53. Function DecisionTreeOutput(this.DecisionTree)
54.         DecisionTreeOutputBinaryTree(this,"1", thism_pRootNode);
55. End Function
56.
58.         Print(nodem_strQuestOrAns + " (enter yes or no)")
61.                 DecisionTreeQueryBinaryTree(this,nodem_pYesBranch)
63.                 DecisionTreeQueryBinaryTree(this,nodem_pNoBranch)
64.         Else
67.         EndIf
68. End Function
69.
70. Function DecisionTreeQuery(this.DecisionTree)
71.         DecisionTreeQueryBinaryTree(this,thism_pRootNode);
72. End Function
73.
74. Function DecisionTreeQueryBinaryTree(this.DecisionTree,currentnode.TreeNode)
75.         If(currentNodem_pYesBranch = Null)
76.                 ;If both the yes And no branch pointers are Null
77.                 ;the tree is at a decision outcome state so output
78.                 ;the String
79.                 If(currentNodem_pNoBranch = Null)
80.                         Print(currentNodem_strQuestOrAns)
81.                 Else
82.                         Print("Missing yes branch at " + currentNodem_strQuestOrAns + " question")
83.                 EndIf
84.                 Return
85.         EndIf
86.         If(currentNodem_pNoBranch = Null)
87.                 Print("Missing no branch at " + currentNodem_strQuestOrAns + " question")
88.                 Return
89.         EndIf
90.         ;otherwise Default To asking the question at the currentNode
92. End Function
93.
95.         ;If you dont have a root node you cant add another node
96.         If(thism_pRootNode = Null)
97.                 Write("Error - no root node in AddYesNode()")
98.                 Return
99.         EndIf
100.         ;otherwise query tree And add node
103.                 Write(newNodeID)
104.                 Write(" onto 'yes' branch of node ")
105.                 Print(existingNodeID)
106.         Else
107.                 Write("'yes' Node ")
108.                 Write(existingNodeID)
110.         EndIf
111. End Function
112.
114.         If(thism_pRootNode = Null)
115.                 Print("Error no root node in AddNoNode()")
116.                 Return
117.         EndIf
120.                 Write(newNodeID)
121.                 Write(" onto 'no' branch of node ")
122.                 Print(existingNodeID)
123.         Else
124.                 Write("'no' Node ")
125.                 Write(existingNodeID)
127.         EndIf
128. End Function
129.
131.         If(currentNodem_iNodeID = existingNodeID)
132.                 ;create node
133.                 If(currentNodem_pYesBranch = Null)
134.                         currentNodem_pYesBranch = TreeNodeNew(newNodeID%,newQorA\$)
135.                 Else
136.                         currentNodem_pYesBranch = TreeNodeNew(newNodeID%,newQorA\$)
137.                 EndIf
138.                 Return True
139.         Else
140.                 ;try yes branch If it exists
141.                 If(currentNodem_pYesBranch <> Null)
143.                                 Return True
144.                         Else
145.                                 ;try no branch If it exists
146.                                 If(currentNodem_pNoBranch <> Null)
148.                                 Else
149.                                         Return False
150.                                 EndIf
151.                         EndIf
152.                 EndIf
153.                 Return False
154.         EndIf
155. End Function
156.
158.         If(currentNodem_iNodeID = existingNodeID)
159.                 If(currentNodem_pNoBranch = Null)
160.                         currentNodem_pNoBranch = TreeNodeNew(newNodeID,newQorA\$)
161.                 Else
162.                         currentNodem_pNoBranch = TreeNodeNew(newNodeID,newQorA\$)
163.                 EndIf
164.                 Return True
165.         Else
166.                 If(currentNodem_pYesBranch <> Null)
168.                                 Return True
169.                         Else
170.                                 If(currentNodem_pNoBranch <> Null)
172.                                 Else
173.                                         Return False
174.                                 EndIf
175.                         EndIf
176.
177.                 Else
178.                         Return False
179.                 EndIf
180.         EndIf
181. End Function
182.
183. Function DecisionTreeCreateRootNode(this.DecisionTree,nodeID%,newQorA\$);
184.         thism_pRootNode = TreeNodeNew(nodeID%,newQorA\$);
185. End Function
186.
187.
188. Function DecisionTreeNew.DecisionTree()
189.         this.DecisionTree = New DecisionTree
190.         thism_pRootNode = Null
191.         Return this
192. End Function
193.
194. Function DecisionTreeDelete(this.DecisionTree)
195.          DecisionTreeRemoveNode(this,thism_pRootNode)
196. End Function
197.
198. ;;main
199. Graphics(800,600,16,2)
200.
201. ;create he New decision tree Object
202. newTree.DecisionTree = DecisionTreeNew();
203.
204. ;add the required root node
205. DecisionTreeCreateRootNode(newTree,1,"Have you got a weapon?");
206.
207. ;add subsequent nodes based on problem definition
208. DecisionTreeAddYesNode(newTree,1,2,"Are you close enough to attack?");
214.
215. ;output the created tree
216. DecisionTreeOutput(newTree);
217.
218. ;query the tree
219. DecisionTreeQuery(newTree);
220.
221. Print("Press any key to quit...")
222.
223. ;pause
224. WaitKey()
225.
226. Delete newTree

slenkar(Posted 1+ years ago)

this is useful thanks!

Rook Zimbabwe(Posted 1+ years ago)

AI in Blitz... whoa!!!