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

[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

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...