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

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

Offline 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)
  44.         Write(", question/answer = ")
  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.  
  57. Function DecisionTreeAskQuestion(this.DecisionTree,node.Treenode)
  58.         Print(nodem_strQuestOrAns + " (enter yes or no)")
  59.         answer$=Input()
  60.         If(answer = "yes")
  61.                 DecisionTreeQueryBinaryTree(this,nodem_pYesBranch)
  62.         ElseIf(answer = "no")
  63.                 DecisionTreeQueryBinaryTree(this,nodem_pNoBranch)
  64.         Else
  65.                 Print("Error please answer yes or no.")
  66.                 DecisionTreeAskQuestion(this,node)
  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
  91.         DecisionTreeAskQuestion(this,currentNode);
  92. End Function
  93.  
  94. Function DecisionTreeAddYesNode(this.DecisionTree,existingNodeID%,newNodeID%,newQorA$)
  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
  101.         If(DecisionTreeSearchTreeAndAddYesNode(this,thism_pRootNode,existingNodeID%,newNodeID%,newQorA$))
  102.                 Write("Added 'yes' node")
  103.                 Write(newNodeID)
  104.                 Write(" onto 'yes' branch of node ")
  105.                 Print(existingNodeID)
  106.         Else
  107.                 Write("'yes' Node ")
  108.                 Write(existingNodeID)
  109.                 Print(" not found")
  110.         EndIf
  111. End Function
  112.  
  113. Function DecisionTreeAddNoNode(this.DecisionTree,existingNodeID%,newNodeID%,newQorA$)
  114.         If(thism_pRootNode = Null)
  115.                 Print("Error no root node in AddNoNode()")
  116.                 Return
  117.         EndIf
  118.         If(DecisionTreeSearchTreeAndAddNoNode(this,thism_pRootNode, existingNodeID, newNodeID, newQorA))
  119.                 Write("Added 'no' node")
  120.                 Write(newNodeID)
  121.                 Write(" onto 'no' branch of node ")
  122.                 Print(existingNodeID)
  123.         Else
  124.                 Write("'no' Node ")
  125.                 Write(existingNodeID)
  126.                 Print(" not found")
  127.         EndIf
  128. End Function
  129.  
  130. Function DecisionTreeSearchTreeAndAddYesNode(this.DecisionTree,currentNode.TreeNode,existingNodeID%,newNodeID%,newQorA$)
  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)
  142.                         If(DecisionTreeSearchTreeAndAddYesNode(this,currentNodem_pYesBranch,existingNodeID,newNodeID,newQorA))
  143.                                 Return True
  144.                         Else
  145.                                 ;try no branch If it exists
  146.                                 If(currentNodem_pNoBranch <> Null)
  147.                                         Return(DecisionTreeSearchTreeAndAddYesNode(this,currentNodem_pNoBranch,existingNodeID,newNodeID,newQorA))
  148.                                 Else
  149.                                         Return False
  150.                                 EndIf  
  151.                         EndIf
  152.                 EndIf
  153.                 Return False
  154.         EndIf
  155. End Function
  156.  
  157. Function DecisionTreeSearchTreeAndAddNoNode%(this.DecisionTree,currentNode.TreeNode,existingNodeID%,newNodeID%,newQorA$)
  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)
  167.                         If(DecisionTreeSearchTreeAndAddNoNode(this,currentNodem_pYesBranch,existingNodeID%,newNodeID%,newQorA$))
  168.                                 Return True
  169.                         Else
  170.                                 If(currentNodem_pNoBranch <> Null)
  171.                                         Return(DecisionTreeSearchTreeAndAddNoNode(this,currentNodem_pNoBranch,existingNodeID%,newNodeID%,newQorA$))
  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?");
  209. DecisionTreeAddNoNode(newTree,1,3,"Can you tackle bare-handed?");
  210. DecisionTreeAddYesNode(newTree,2,4,"Attack!!!");
  211. DecisionTreeAddNoNode(newTree,2,5,"Don't attack!!!");
  212. DecisionTreeAddYesNode(newTree,3,6,"Attack!!!");
  213. DecisionTreeAddNoNode(newTree,3,7,"Don't 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


Comments :


slenkar(Posted 1+ years ago)

 this is useful thanks!


Rook Zimbabwe(Posted 1+ years ago)

 AI in Blitz... whoa!!! :)


 

SimplePortal 2.3.6 © 2008-2014, SimplePortal