Ooops
November 28, 2020, 01:56:14 PM

Author Topic: [bmx] Sparse array Tree by Otus [ 1+ years ago ]  (Read 1012 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bmx] Sparse array Tree by Otus [ 1+ years ago ]
« on: June 29, 2017, 12:28:43 AM »
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
  1. 'The T4Tree stores a sparse two dimensional
  2. ' array in a tree-like structure, where the
  3. ' leaves store the array values.
  4. 'By Otus,
  5. ' released to public domain.
  6.  
  7. SuperStrict
  8.  
  9. 'Rem    'Comment this line to test
  10. Framework BRL.Basic
  11. Import BRL.Random
  12. Rem
  13. End Rem
  14.  
  15.  
  16. 'Private
  17.  
  18. Function POW:Int(a:Int, b:Int)
  19.         'This is needed, because ^-operator
  20.         ' doesn't work well with integers.
  21.         'Replace with a faster alternative,
  22.         ' if you can find one.
  23.         Local a2:Int = a
  24.         b:-1
  25.         While b
  26.                 a2:*a
  27.                 b:-1
  28.         Wend
  29.         Return a2
  30. End Function
  31.  
  32. Type TNode
  33.         'A node points to 4 objects below it,
  34.         ' which are either other nodes, or
  35.         ' values, depending on the depth.
  36.         'Nodes which don't point to anything
  37.         ' don't (shouldn't) exist.
  38.        
  39.         Field ul:Object, ur:Object
  40.         Field bl:Object, br:Object
  41.        
  42.         Method Get:Object(x:Int, y:Int, d:Int=1)
  43.                 If d=1
  44.                         If x
  45.                                 If y Return br Else Return bl
  46.                         Else
  47.                                 If y Return ur Else Return ul
  48.                         End If
  49.                 End If
  50.                 If x<d
  51.                         If y<d
  52.                                 If ul=Null
  53.                                         Return Null
  54.                                 Else
  55.                                         Return TNode(ul).Get(x, y, d/2)
  56.                                 End If
  57.                         Else
  58.                                 If bl=Null
  59.                                         Return Null
  60.                                 Else
  61.                                         Return TNode(bl).Get(x, y - d, d/2)
  62.                                 End If
  63.                         End If
  64.                 Else
  65.                         If y<d
  66.                                 If ur=Null
  67.                                         Return Null
  68.                                 Else
  69.                                         Return TNode(ur).Get(x - d, y, d/2)
  70.                                 End If
  71.                         Else
  72.                                 If br=Null
  73.                                         Return Null
  74.                                 Else
  75.                                         Return TNode(br).Get(x - d, y - d, d/2)
  76.                                 End If
  77.                         End If
  78.                 End If
  79.         End Method
  80.        
  81.         Method Set(o:Object, x:Int, y:Int, d:Int=1)
  82.                 If d=1
  83.                         If x
  84.                                 If y br=o Else bl=o
  85.                                 Return
  86.                         Else
  87.                                 If y ur=o Else ul=o
  88.                                 Return
  89.                         End If
  90.                 End If
  91.                 If x<d
  92.                         If y<d
  93.                                 If ul=Null Then ul = New TNode
  94.                                 TNode(ul).Set(o,x, y, d/2)
  95.                         Else
  96.                                 If bl=Null Then bl = New TNode
  97.                                 TNode(bl).Set(o,x, y - d, d/2)
  98.                         End If
  99.                 Else
  100.                         If y<d
  101.                                 If ur=Null Then ur = New TNode
  102.                                 TNode(ur).Set(o,x - d, y, d/2)
  103.                         Else
  104.                                 If br=Null Then br = New TNode
  105.                                 TNode(br).Set(o,x - d, y - d, d/2)
  106.                         End If
  107.                 End If
  108.         End Method
  109.        
  110.         Method Remove:Byte(x:Int, y:Int, d:Int=1)
  111.                 If d=1
  112.                         If x
  113.                                 If y br=Null Else bl=Null
  114.                         Else
  115.                                 If y ur=Null Else ul=Null
  116.                         End If
  117.                         If ul=Null And ur=Null And bl=Null And br=Null Return 1 Else Return 0
  118.                 End If
  119.                
  120.                 If x<d
  121.                         If y<d
  122.                                 If ul=Null Then ul = New TNode
  123.                                 If TNode(ul).Remove(x, y, d/2)
  124.                                         ul=Null
  125.                                         If ur=Null And bl=Null And br=Null Return 1 Else Return 0
  126.                                 End If
  127.                         Else
  128.                                 If bl=Null Then bl = New TNode
  129.                                 If TNode(bl).Remove(x, y - d, d/2)
  130.                                         bl=Null
  131.                                         If ur=Null And ul=Null And br=Null Return 1 Else Return 0
  132.                                 End If
  133.                         End If
  134.                 Else
  135.                         If y<d
  136.                                 If ur=Null Then ur = New TNode
  137.                                 If TNode(ur).Remove(x - d, y, d/2)
  138.                                         ur=Null
  139.                                         If ul=Null And bl=Null And br=Null Return 1 Else Return 0
  140.                                 End If
  141.                         Else
  142.                                 If br=Null Then br = New TNode
  143.                                 If TNode(br).Remove(x - d, y - d, d/2)
  144.                                         br=Null
  145.                                         If ur=Null And bl=Null And ul=Null Return 1 Else Return 0
  146.                                 End If
  147.                         End If
  148.                 End If
  149.         End Method
  150.  
  151. End Type
  152.  
  153. 'Public
  154.  
  155. Type T4Tree Extends TNode
  156.        
  157.         Field depth:Short
  158.        
  159.         Method Get:Object(x:Int, y:Int, d:Int=0)
  160.                 'Get value at indices. d parameter
  161.                 ' is legacy of the base type method.
  162.                 Return Super.Get(x,y,POW(2,depth-1))
  163.         End Method
  164.        
  165.         Method Set(o:Object, x:Int, y:Int, d:Int=0)
  166.                 'Get value at indices to o. d parameter
  167.                 ' is again legacy of the base type method.
  168.                 If o=Null
  169.                         Super.Remove(x,y,POW(2,depth-1))
  170.                 Else
  171.                         Super.Set o, x, y, POW(2,depth-1)
  172.                 End If
  173.         End Method
  174.        
  175.         Method Remove:Byte(x:Int, y:Int, d:Int=1)
  176.                 Super.Remove(x,y,POW(2,depth-1))
  177.         End Method
  178.        
  179.         Function Create:T4Tree(width:Int, height:Int=0)
  180.                 Local t:T4Tree = New T4Tree
  181.                 width=Max(width, height)
  182.                 t.depth=Max(Ceil(Log(width)/Log(2)),1)
  183.                 Return t
  184.         End Function
  185.        
  186.         Function FromArray:T4Tree(array:Object[,])
  187.                 Local dim:Int[] = array.Dimensions()
  188.                 Local size:Int = Max(dim[0],dim[1])
  189.                
  190.                 Local t:T4Tree = New T4Tree
  191.                 t.depth=Max(Ceil(Log(size)/Log(2)),1)
  192.                
  193.                 For Local i:Int = 0 Until dim[0]
  194.                         For Local j:Int = 0 Until dim[1]
  195.                                 If Not array[i,j]=Null t.Set(array[i,j],i,j)
  196.                         Next
  197.                 Next
  198.                
  199.                 Return t
  200.         End Function
  201.        
  202. End Type
  203.  
  204. 'Rem    'Comment this line to test
  205. SeedRnd MilliSecs()
  206.  
  207. Local s:String="1"
  208.  
  209. Const tsize:Int = 2000
  210.  
  211. Local mem:Int = GCMemAlloced()
  212. Local array:Object[tsize,tsize]
  213. Local mem0:Int = GCMemAlloced() - mem
  214.  
  215. For Local i:Int = 0 Until tsize
  216.         For Local j:Int = 0 Until tsize
  217.                 If Rand(100) = 1 Then array[i,j]=s      'Store a '1' in approx. 1/100 cells
  218.         Next
  219. Next
  220.  
  221. GCCollect()
  222. mem = GCMemAlloced()
  223. Local t:T4Tree = T4Tree.FromArray(array)
  224. GCCollect()
  225. Local mem1:Int = GCMemAlloced() - mem
  226.  
  227. Print "Array took: "+mem0+"B, T4Tree took: "+mem1+"B"
  228.  
  229. For Local i:Int = 1 To 10
  230.         Local x:Int = Rand(0,tsize-1), y:Int = Rand(0,tsize-1)
  231.         Print String(array[x,y])+" - "+String(t.Get(x,y))
  232. Next
  233.  
  234. For Local i:Int = 1 To 1000
  235.         t.Remove(Rand(0,tsize-1),Rand(0,tsize-1))
  236. Next
  237. GCCollect()
  238. mem1=GCMemAlloced()-mem
  239.  
  240. Print "After some removal takes: "+mem1+"B"
  241.  
  242. Rem
  243. End Rem


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal