[bmx] Sparse array Tree by Otus [ 1+ years ago ]

Started by BlitzBot, June 29, 2017, 00:28:43

Previous topic - Next topic

BlitzBot

Title : Sparse array Tree
Author : Otus
Posted : 1+ years ago

Description : A tree-like data structure, which stores the values of a sparse two-dimensional array of objects more efficiently. Test included shows that a 16MB array, where only 1/100 of cells are used stores in a 3MB tree. If the data is clustered, it is even more efficient.

Made this to store collision data for game areas, and I think it's quite good for the task. If someone can optimize it further (especially speed wise), I'd be interested to see the changes, so please email me the changes (see profile).


Code :
Code (blitzmax) Select
'The T4Tree stores a sparse two dimensional
' array in a tree-like structure, where the
' leaves store the array values.
'By Otus,
' released to public domain.

SuperStrict

'Rem 'Comment this line to test
Framework BRL.Basic
Import BRL.Random
Rem
End Rem


'Private

Function POW:Int(a:Int, b:Int)
'This is needed, because ^-operator
' doesn't work well with integers.
'Replace with a faster alternative,
' if you can find one.
Local a2:Int = a
b:-1
While b
a2:*a
b:-1
Wend
Return a2
End Function

Type TNode
'A node points to 4 objects below it,
' which are either other nodes, or
' values, depending on the depth.
'Nodes which don't point to anything
' don't (shouldn't) exist.

Field ul:Object, ur:Object
Field bl:Object, br:Object

Method Get:Object(x:Int, y:Int, d:Int=1)
If d=1
If x
If y Return br Else Return bl
Else
If y Return ur Else Return ul
End If
End If
If x<d
If y<d
If ul=Null
Return Null
Else
Return TNode(ul).Get(x, y, d/2)
End If
Else
If bl=Null
Return Null
Else
Return TNode(bl).Get(x, y - d, d/2)
End If
End If
Else
If y<d
If ur=Null
Return Null
Else
Return TNode(ur).Get(x - d, y, d/2)
End If
Else
If br=Null
Return Null
Else
Return TNode(br).Get(x - d, y - d, d/2)
End If
End If
End If
End Method

Method Set(o:Object, x:Int, y:Int, d:Int=1)
If d=1
If x
If y br=o Else bl=o
Return
Else
If y ur=o Else ul=o
Return
End If
End If
If x<d
If y<d
If ul=Null Then ul = New TNode
TNode(ul).Set(o,x, y, d/2)
Else
If bl=Null Then bl = New TNode
TNode(bl).Set(o,x, y - d, d/2)
End If
Else
If y<d
If ur=Null Then ur = New TNode
TNode(ur).Set(o,x - d, y, d/2)
Else
If br=Null Then br = New TNode
TNode(br).Set(o,x - d, y - d, d/2)
End If
End If
End Method

Method Remove:Byte(x:Int, y:Int, d:Int=1)
If d=1
If x
If y br=Null Else bl=Null
Else
If y ur=Null Else ul=Null
End If
If ul=Null And ur=Null And bl=Null And br=Null Return 1 Else Return 0
End If

If x<d
If y<d
If ul=Null Then ul = New TNode
If TNode(ul).Remove(x, y, d/2)
ul=Null
If ur=Null And bl=Null And br=Null Return 1 Else Return 0
End If
Else
If bl=Null Then bl = New TNode
If TNode(bl).Remove(x, y - d, d/2)
bl=Null
If ur=Null And ul=Null And br=Null Return 1 Else Return 0
End If
End If
Else
If y<d
If ur=Null Then ur = New TNode
If TNode(ur).Remove(x - d, y, d/2)
ur=Null
If ul=Null And bl=Null And br=Null Return 1 Else Return 0
End If
Else
If br=Null Then br = New TNode
If TNode(br).Remove(x - d, y - d, d/2)
br=Null
If ur=Null And bl=Null And ul=Null Return 1 Else Return 0
End If
End If
End If
End Method

End Type

'Public

Type T4Tree Extends TNode

Field depth:Short

Method Get:Object(x:Int, y:Int, d:Int=0)
'Get value at indices. d parameter
' is legacy of the base type method.
Return Super.Get(x,y,POW(2,depth-1))
End Method

Method Set(o:Object, x:Int, y:Int, d:Int=0)
'Get value at indices to o. d parameter
' is again legacy of the base type method.
If o=Null
Super.Remove(x,y,POW(2,depth-1))
Else
Super.Set o, x, y, POW(2,depth-1)
End If
End Method

Method Remove:Byte(x:Int, y:Int, d:Int=1)
Super.Remove(x,y,POW(2,depth-1))
End Method

Function Create:T4Tree(width:Int, height:Int=0)
Local t:T4Tree = New T4Tree
width=Max(width, height)
t.depth=Max(Ceil(Log(width)/Log(2)),1)
Return t
End Function

Function FromArray:T4Tree(array:Object[,])
Local dim:Int[] = array.Dimensions()
Local size:Int = Max(dim[0],dim[1])

Local t:T4Tree = New T4Tree
t.depth=Max(Ceil(Log(size)/Log(2)),1)

For Local i:Int = 0 Until dim[0]
For Local j:Int = 0 Until dim[1]
If Not array[i,j]=Null t.Set(array[i,j],i,j)
Next
Next

Return t
End Function

End Type

'Rem 'Comment this line to test
SeedRnd MilliSecs()

Local s:String="1"

Const tsize:Int = 2000

Local mem:Int = GCMemAlloced()
Local array:Object[tsize,tsize]
Local mem0:Int = GCMemAlloced() - mem

For Local i:Int = 0 Until tsize
For Local j:Int = 0 Until tsize
If Rand(100) = 1 Then array[i,j]=s 'Store a '1' in approx. 1/100 cells
Next
Next

GCCollect()
mem = GCMemAlloced()
Local t:T4Tree = T4Tree.FromArray(array)
GCCollect()
Local mem1:Int = GCMemAlloced() - mem

Print "Array took: "+mem0+"B, T4Tree took: "+mem1+"B"

For Local i:Int = 1 To 10
Local x:Int = Rand(0,tsize-1), y:Int = Rand(0,tsize-1)
Print String(array[x,y])+" - "+String(t.Get(x,y))
Next

For Local i:Int = 1 To 1000
t.Remove(Rand(0,tsize-1),Rand(0,tsize-1))
Next
GCCollect()
mem1=GCMemAlloced()-mem

Print "After some removal takes: "+mem1+"B"

Rem
End Rem


Comments : none...