Binary search trees allow you to store handles(Doubles for more precision) within a binary tree, then you can search for an exact entry very quickly( 100,000 elements can be searched in around 12-13 cycles in good cases, may vary based on data.). compared to 100,000 brute force/list wise)
whenever you insert something you get a node back.
When you use find it'll find an exact match or return null. FindApprox will find the closest double value to yours(Still using the fast method.) which is nicer for in game stuff.
rem
Strict
ModuleInfo "Version: 1.11"
ModuleInfo "Author:Antony Wells"
ModuleInfo "License:Open Source."
ModuleInfo "Copyright: Open Source."
ModuleInfo "Modserver: "
End Rem
Type BSTree
Function Create:BSTree()
Local Out:BSTree = New BSTree
Return Out
End Function
Method Insert:BNode(Value:Double,Id:Int=0)
If Root = Null
Root = New BNode
Root.Value = Value
Root.Id = Id
Return Root
Else
Return Root.Insert( Value,Id)
EndIf
End Method
Method FindNode:BNode( Value!)
Return Root.FindNode( Value )
End Method
Method FindApprox:BNode( Value!)
BNode.SmallV = 9999999999
' If BNode.SmallV<>99999999999999 Throw "Double precision not accurate enough for BST implentation"
BNode.SmallN = Null
Return Root.FindApprox( Value )
End Method
Field Root:BNode
End Type
Type BNode
Method Insert:BNode( nValue:Double,Id:Int=0 )
If nValue = Value Return
If nValue<Value
If Node[0] = Null
Node[0] = New BNode
Node[0].Top = BNode(Self)
Node[0].Id = Id
Node[0].Value = nValue
Return Node[0]
Else
Node[0].Insert( nValue,Id )
EndIf
Else
If Node[1] = Null
Node[1] = New BNode
Node[1].Id = Id
Node[1].Top = BNode( Self )
Node[1].Value = nValue
Return Node[1]
Else
Node[1].Insert( nValue,Id )
End If
EndIf
End Method
Method FindNode:BNode( nValue:Double )
If Value = nValue Return BNode(Self)
If nValue<Value
If Node[0] = Null Return Null
Return Node[0].FindNode( nValue )
Else
If Node[1] = Null Return Null
Return Node[1].FindNode( nValue )
EndIf
End Method
Method FindApprox:BNode( nValue:Double )
?debug
BNode.Cycle:+1
?
Local dValue! = Abs(nValue-Value)
If dValue<Bnode.SmallV
Bnode.SmallV = dValue
Bnode.SmallN = BNode( Self )
EndIf
If nValue = Value Return Bnode(Self)
If nValue<Value
If Node[0] = Null Return Bnode.SmallN
Return Node[0].FindApprox( nValue )
Else
If Node[1] = Null Return Bnode.SmallN
Return Node[1].FindApprox( nValue )
EndIf
End Method
Field x:Double,y:Double,z:Double
Global Cycle:Int
Field Value!,Obj:Object,Id:Int
Field Node:BNode[2],Top:BNode
Global SmallV!,SmallN:BNode
End Type
Type BSVTree
Method New()
xTree = New BSTree
yTree = New BSTree
zTree = New BStree
End Method
Function Create( Verts:Double[] )
Local Out:BSVTree = New BSVTree
Local VertC:Int = Verts.Length()
Local VertI:Int
While VertI<VertC
Out.xTree.Insert( Verts[ VertI],VertI/3)
Out.yTree.Insert( Verts[ VertI+1],VertI/3)
Out.zTree.Insert( Verts[ VertI+2],VertI/3)
VertI:+3
Wend
Return Out
End Function
Method NearestVertex( X:Double,Y:Double,Z:Double )
Local XNode:BNode = xTree.FindApprox( X )
End Method
Field xTree:BSTree,yTree:BSTree,zTree:BSTree
End Type
Private
Global FoldSpace = 80000
Function FoldPoint!( x!,y!,z!,Tune!=1)
'x:*tune
'y:*tune
'z:*tune
out! = (Foldspace*y+x)+(z*(Foldspace*Foldspace))
Return out
End Function
Function UnfoldPoint( point:Double Var,x:Double Var,Y:Double Var,Z:Double Var,Tune!=1)
y = point / foldSpace Mod foldSpace Mod foldSpace
' x = point Mod FoldSpace Mod foldSpace
z = point/(foldSpace*FoldSpace)
x = point-y*foldSpace
End Function
| 
