[bb] Binary Decision Tree by Techlord [ 1+ years ago ]

[BlitzBot]

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</a> and <a href="http://www.generation5.org/content/2004/data/DecisionTree.zip" target="_blank">C++ Source Code</a>.

Code :

Code (blitzbasic) Select Expand

;//TreeNode

Type TreeNode
Field m_strQuestOrAns$;
Field m_iNodeID%
Field m_pYesBranch.TreeNode
Field m_pNoBranch.TreeNode
End Type

Function TreeNodeNew.TreeNode(nodeID%=0,newQorA$="");
;set the objects pointers To Null in Default constructor
this.TreeNode = New TreeNode
thism_iNodeID = nodeID
thism_strQuestOrAns = newQorA
thism_pYesBranch = Null
thism_pNoBranch= Null
Return this
End Function

Function TreeNodeDelete(this.TreeNode)
Delete this
End Function

;// DecisionTree

Type DecisionTree
Field m_pRootNode.TreeNode;
End Type

Function DecisionTreeRemoveNode(this.DecisionTree,node.TreeNode)
If(node <> Null)
If(nodem_pYesBranch <> Null) DecisionTreeRemoveNode(this,nodem_pYesBranch);
If(nodem_pNoBranch <> Null) DecisionTreeRemoveNode(this,nodem_pNoBranch);
Print("deleting node "+nodem_iNodeID);
Delete node;
EndIf
End Function

Function DecisionTreeOutputBinaryTree(this.DecisionTree,tag$,currentNode.TreeNode)
If(currentNode = Null) Return

Write("[" + tag$ + "] node id = ")
Write(currentNodem_iNodeID)
Write(", question/answer = ")
Print(currentNodem_strQuestOrAns)

; Go down yes branch
DecisionTreeOutputBinaryTree(this,tag$+".1",currentNodem_pYesBranch);
; Go down no branch
DecisionTreeOutputBinaryTree(this,tag$+".2",currentNodem_pNoBranch);
End Function

Function DecisionTreeOutput(this.DecisionTree)
DecisionTreeOutputBinaryTree(this,"1", thism_pRootNode);
End Function

Function DecisionTreeAskQuestion(this.DecisionTree,node.Treenode)
Print(nodem_strQuestOrAns + " (enter yes or no)")
answer$=Input()
If(answer = "yes")
DecisionTreeQueryBinaryTree(this,nodem_pYesBranch)
ElseIf(answer = "no")
DecisionTreeQueryBinaryTree(this,nodem_pNoBranch)
Else
Print("Error please answer yes or no.")
DecisionTreeAskQuestion(this,node)
EndIf
End Function

Function DecisionTreeQuery(this.DecisionTree)
DecisionTreeQueryBinaryTree(this,thism_pRootNode);
End Function

Function DecisionTreeQueryBinaryTree(this.DecisionTree,currentnode.TreeNode)
If(currentNodem_pYesBranch = Null)
;If both the yes And no branch pointers are Null
;the tree is at a decision outcome state so output
;the String
If(currentNodem_pNoBranch = Null)
Print(currentNodem_strQuestOrAns)
Else
Print("Missing yes branch at " + currentNodem_strQuestOrAns + " question")
EndIf
Return
EndIf
If(currentNodem_pNoBranch = Null)
Print("Missing no branch at " + currentNodem_strQuestOrAns + " question")
Return
EndIf
;otherwise Default To asking the question at the currentNode
DecisionTreeAskQuestion(this,currentNode);
End Function

Function DecisionTreeAddYesNode(this.DecisionTree,existingNodeID%,newNodeID%,newQorA$)
;If you dont have a root node you cant add another node
If(thism_pRootNode = Null)
Write("Error - no root node in AddYesNode()")
Return
EndIf
;otherwise query tree And add node
If(DecisionTreeSearchTreeAndAddYesNode(this,thism_pRootNode,existingNodeID%,newNodeID%,newQorA$))
Write("Added 'yes' node")
Write(newNodeID)
Write(" onto 'yes' branch of node ")
Print(existingNodeID)
Else
Write("'yes' Node ")
Write(existingNodeID)
Print(" not found")
EndIf
End Function

Function DecisionTreeAddNoNode(this.DecisionTree,existingNodeID%,newNodeID%,newQorA$)
If(thism_pRootNode = Null)
Print("Error no root node in AddNoNode()")
Return
EndIf
If(DecisionTreeSearchTreeAndAddNoNode(this,thism_pRootNode, existingNodeID, newNodeID, newQorA))
Write("Added 'no' node")
Write(newNodeID)
Write(" onto 'no' branch of node ")
Print(existingNodeID)
Else
Write("'no' Node ")
Write(existingNodeID)
Print(" not found")
EndIf
End Function

Function DecisionTreeSearchTreeAndAddYesNode(this.DecisionTree,currentNode.TreeNode,existingNodeID%,newNodeID%,newQorA$)
If(currentNodem_iNodeID = existingNodeID)
;create node
If(currentNodem_pYesBranch = Null)
currentNodem_pYesBranch = TreeNodeNew(newNodeID%,newQorA$)
Else
currentNodem_pYesBranch = TreeNodeNew(newNodeID%,newQorA$)
EndIf
Return True
Else
;try yes branch If it exists
If(currentNodem_pYesBranch <> Null)
If(DecisionTreeSearchTreeAndAddYesNode(this,currentNodem_pYesBranch,existingNodeID,newNodeID,newQorA))
Return True
Else
;try no branch If it exists
If(currentNodem_pNoBranch <> Null)
Return(DecisionTreeSearchTreeAndAddYesNode(this,currentNodem_pNoBranch,existingNodeID,newNodeID,newQorA))
Else
Return False
EndIf
EndIf
EndIf
Return False
EndIf
End Function

Function DecisionTreeSearchTreeAndAddNoNode%(this.DecisionTree,currentNode.TreeNode,existingNodeID%,newNodeID%,newQorA$)
If(currentNodem_iNodeID = existingNodeID)
If(currentNodem_pNoBranch = Null)
currentNodem_pNoBranch = TreeNodeNew(newNodeID,newQorA$)
Else
currentNodem_pNoBranch = TreeNodeNew(newNodeID,newQorA$)
EndIf
Return True
Else
If(currentNodem_pYesBranch <> Null)
If(DecisionTreeSearchTreeAndAddNoNode(this,currentNodem_pYesBranch,existingNodeID%,newNodeID%,newQorA$))
Return True
Else
If(currentNodem_pNoBranch <> Null)
Return(DecisionTreeSearchTreeAndAddNoNode(this,currentNodem_pNoBranch,existingNodeID%,newNodeID%,newQorA$))
Else
Return False
EndIf
EndIf

Else
Return False
EndIf
EndIf
End Function

Function DecisionTreeCreateRootNode(this.DecisionTree,nodeID%,newQorA$);
thism_pRootNode = TreeNodeNew(nodeID%,newQorA$);
End Function


Function DecisionTreeNew.DecisionTree()
this.DecisionTree = New DecisionTree
thism_pRootNode = Null
Return this
End Function

Function DecisionTreeDelete(this.DecisionTree)
DecisionTreeRemoveNode(this,thism_pRootNode)
End Function

;;main
Graphics(800,600,16,2)

;create he New decision tree Object
newTree.DecisionTree = DecisionTreeNew();

;add the required root node
DecisionTreeCreateRootNode(newTree,1,"Have you got a weapon?");

;add subsequent nodes based on problem definition
DecisionTreeAddYesNode(newTree,1,2,"Are you close enough to attack?");
DecisionTreeAddNoNode(newTree,1,3,"Can you tackle bare-handed?");
DecisionTreeAddYesNode(newTree,2,4,"Attack!!!");
DecisionTreeAddNoNode(newTree,2,5,"Don't attack!!!");
DecisionTreeAddYesNode(newTree,3,6,"Attack!!!");
DecisionTreeAddNoNode(newTree,3,7,"Don't attack!!!");

;output the created tree
DecisionTreeOutput(newTree);

;query the tree
DecisionTreeQuery(newTree);

Print("Press any key to quit...")

;pause
WaitKey()

Delete newTree

Comments :


slenkar(Posted 1+ years ago)

 this is useful thanks!


Rook Zimbabwe(Posted 1+ years ago)

 AI in Blitz... whoa!!!