December 03, 2020, 08:14:32 PM

### Author Topic: [bmx] 2D spatial hash by Pineapple [ 1+ years ago ]  (Read 501 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bmx] 2D spatial hash by Pineapple [ 1+ years ago ]
« on: June 29, 2017, 12:28:41 AM »
Title : 2D spatial hash
Author : Pineapple
Posted : 1+ years ago

Description : What's a spatial hash good for, you ask? Here's a good article on the workings and uses of the data structure: <a href="http://www.gamedev.net/page/resources/_/technical/game-programming/spatial-hashing-r2697" target="_blank">http://www.gamedev.net/page/resources/_/technical/game-programming/spatial-hashing-r2697[/url]

Code :
Code: BlitzMax
1. '       --+-----------------------------------------------------------------------------------------+--
2. '         |   This code was originally written by Sophie Kirschner (sophiek@pineapplemachine.com)   |
3. '         | It is released as public domain. Please don't interpret that as liberty to claim credit |
4. '         |   that isn't yours, or to sell this code when it could otherwise be obtained for free   |
5. '         |                because that would be a really shitty thing of you to do.                |
6. '       --+-----------------------------------------------------------------------------------------+--
7.
8. SuperStrict
9.
11.
12.
13. ' Example code
14. Rem
15.
16. ' Create a new spatial hash
17. Local hash:hash2d=hash2d.Create(256,32)
18.
19. ' Add a bunch of numbers as strings to a rectangle of coordinates.
20. Local n%=0
21. For Local i%=2 Until 4
22. For Local j%=0 Until 8
23.         hash.insert i,j,String(n)
24.         n:+1
25. Next
26. Next
27.
28. ' Resize it, just for fun.
29. hash.resize(48,8)
30.
31. ' Iterate through the hash and print the values.
32. For Local t\$=EachIn hash
33.         Print t
34. Next
35.
36. EndRem
37.
38.
39.         Rem
40.         bbdoc: Spatial hash type.
41.         End Rem
42. Type hash2d
43.         ' number of buckets in the hash
44.         Field size%
45.         ' used in placing coordinates in the hash
46.         Field pitch%
47.         ' number of objects in the hash
48.         Field count%
49.         ' the buckets
50.         Field content:TList[]
51.
52.         Rem
53.         bbdoc: Creates a new hash2d object.
54.         returns: A new hash2d object.
55.         End Rem
56.         Function Create:hash2d(size%,pitch%=128)
57.                 Local n:hash2d=New hash2d
58.                 n.setsize(size)
59.                 n.pitch=pitch
60.                 Return n
61.         End Function
62.         Rem
63.         bbdoc: Sets the size of the hash2d object. Deletes all existing values.
64.         End Rem
65.         Method setsize(nsize%)
66.                 size=nsize
67.                 content=New TList[size]
68.                 count=0
69.         End Method
70.         Rem
71.         bbdoc: Sets the size of the hash2d object. Retains all existing values.
72.         End Rem
73.         Method resize(nsize%,npitch%=-1)
74.                 If count=0
75.                         setsize(nsize)
76.                         pitch=npitch
77.                 Else
78.                         Local newc:TList[]=New TList[nsize]
79.                         size=nsize
80.                         pitch=npitch
81.                         For Local i%=0 Until content.length
82.                                 If content[i] Then
83.                                         For Local node:hash2dnode=EachIn content[i]
84.                                                 Local nindex%=contentindex(node.x,node.y)
85.                                                 If Not newc[nindex] Then newc[nindex]=New TList
87.                                         Next
88.                                 EndIf
89.                         Next
90.                         content=newc
91.                 EndIf
92.         End Method
93.         Rem
94.         bbdoc: Find a node.
95.         returns: The node at the specified coordinates; null if none exists.
96.         End Rem
97.         Method findnode:hash2dnode(x%,y%)
98.                 Assert content
99.                 Local index%=contentindex(x,y)
100.                 Local list:TList=content[index]
101.                 If list Then
105.                                 If node.x=x And node.y=y Then
112.                                         Return node
113.                                 EndIf
115.                         Wend
116.                 EndIf
117.                 Return Null
118.         End Method
119.         Rem
120.         bbdoc: Find a value.
121.         returns: The value at the specified coordinates; null if none exists.
122.         End Rem
123.         Method find:Object(x%,y%)
124.                 Local node:hash2dnode=findnode(x,y)
125.                 If node Then
126.                         Return node.value
127.                 Else
128.                         Return Null
129.                 EndIf
130.         End Method
131.         Rem
132.         bbdoc: Insert a value.
133.         returns: The node created to contain the value.
134.         End Rem
135.         Method insert:hash2dnode(x%,y%,value:Object)
136.                 Assert content
137.                 Local index%=contentindex(x,y)
138.                 Local node:hash2dnode=hash2dnode.Create(x,y,value)
139.                 If Not content[index] Then content[index]=CreateList()
141.                 count:+1
142.                 Return node
143.         End Method
144.         Rem
145.         bbdoc: Remove a node.
146.         returns: True if the node was successfully removed, false otherwise.
147.         End Rem
148.         Method removenode%(node:hash2dnode)
149.                 Assert content And node
150.                 Local index%=contentindex(node.x,node.y)
151.                 Local list:TList=content[index]
152.                 If list.remove(node)
153.                         count:-1
154.                         If list.isempty() content[index]=Null
155.                         Return True
156.                 Else
157.                         Return False
158.                 EndIf
159.         End Method
160.         Rem
161.         bbdoc: Remove the value at a coordinate.
162.         returns: The node that was removed; null if no such node existed.
163.         End Rem
164.         Method remove:hash2dnode(x%,y%)
165.                 Local node:hash2dnode=findnode(x,y)
166.                 If node Then
167.                         If Not removenode(node) Then node=Null
168.                 EndIf
169.                 Return node
170.         End Method
171.         ' Returns the bucket index for a given coordinate.
172.         Method contentindex%(x%,y%)
173.                 Return (((x+y*pitch) Mod size)+size) Mod size
174.         End Method
175.         Rem
176.         bbdoc: Implements EachIn support for values.
177.         returns: An iterator object.
178.         End Rem
179.         Method ObjectEnumerator:hash2denum()
180.                 Return hash2denum.Create(Self,0)
181.         End Method
182.         Rem
183.         bbdoc: Implements EachIn support for nodes.
184.         returns: An iterator object.
185.         End Rem
186.         Method NodeEnumerator:hash2denum()
187.                 Return hash2denum.Create(Self,1)
188.         End Method
189. End Type
190.
191.         Rem
192.         bbdoc: Hash2d node type.
193.         End Rem
194. Type hash2dnode
195.         Field x%,y%
196.         Field value:Object
197.         Function Create:hash2dnode(x%,y%,value:Object)
198.                 Local n:hash2dnode=New hash2dnode
199.                 n.x=x;n.y=y;n.value=value
200.                 Return n
201.         End Function
202. End Type
203.
204.         Rem
205.         bbdoc: Enumerator type for EachIn support.
206.         End Rem
207. Type hash2denum
209.         Field nodeenum%=0
210.         Function Create:hash2denum(hash:hash2d,nodeenum%)
211.                 Local n:hash2denum=New hash2denum
212.                 n.hash=hash
213.                 n.nodeenum=nodeenum
214.                 n.init
215.                 Return n
216.         End Function
217.         Method init()
218.                 hashindex=-1;nextindex=-1
219.                 Local index%=0
220.                 Repeat
221.                         If hash.content[index] And (Not hash.content[index].isempty())
222.                                 If hashindex=-1 Then
223.                                         hashindex=index
225.                                 Else
226.                                         nextindex=index
227.                                         Exit
228.                                 EndIf
229.                         EndIf
230.                         index:+1
231.                         If index>=hash.size Then Exit
232.                 Forever
233.         End Method
234.         Method HasNext%()
236.         End Method
237.         Method NextObject:Object()
242.                         hashindex=nextindex
244.                         Repeat
245.                                 nextindex:+1
246.                                 If nextindex>=hash.size Then nextindex=-1;Exit
247.                                 If hash.content[nextindex] And (Not hash.content[nextindex].isempty()) Then Exit
248.                         Forever
249.                 EndIf
250.                 If nodeenum
251.                         Return value
252.                 Else
253.                         Return hash2dnode(value).value
254.                 EndIf
255.         End Method
256.         Method ObjectEnumerator:hash2denum()
257.                 Return Self
258.         End Method
259. End Type