[bmx] 2D spatial hash by Pineapple [ 1+ years ago ]

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

Previous topic - Next topic

BlitzBot

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</a>

Code :
Code (blitzmax) Select
' --+-----------------------------------------------------------------------------------------+--
'  |   This code was originally written by Sophie Kirschner (sophiek@pineapplemachine.com)   |  
'  | It is released as public domain. Please don't interpret that as liberty to claim credit |  
'  |   that isn't yours, or to sell this code when it could otherwise be obtained for free   |  
'  |                because that would be a really shitty thing of you to do.                |
' --+-----------------------------------------------------------------------------------------+--

SuperStrict

Import brl.linkedlist


' Example code
Rem

' Create a new spatial hash
Local hash:hash2d=hash2d.Create(256,32)

' Add a bunch of numbers as strings to a rectangle of coordinates.
Local n%=0
For Local i%=2 Until 4
For Local j%=0 Until 8
hash.insert i,j,String(n)
n:+1
Next
Next

' Resize it, just for fun.
hash.resize(48,8)

' Iterate through the hash and print the values.
For Local t$=EachIn hash
Print t
Next

EndRem


Rem
bbdoc: Spatial hash type.
End Rem
Type hash2d
' number of buckets in the hash
Field size%
' used in placing coordinates in the hash
Field pitch%
' number of objects in the hash
Field count%
' the buckets
Field content:TList[]

Rem
bbdoc: Creates a new hash2d object.
returns: A new hash2d object.
End Rem
Function Create:hash2d(size%,pitch%=128)
Local n:hash2d=New hash2d
n.setsize(size)
n.pitch=pitch
Return n
End Function
Rem
bbdoc: Sets the size of the hash2d object. Deletes all existing values.
End Rem
Method setsize(nsize%)
size=nsize
content=New TList[size]
count=0
End Method
Rem
bbdoc: Sets the size of the hash2d object. Retains all existing values.
End Rem
Method resize(nsize%,npitch%=-1)
If count=0
setsize(nsize)
pitch=npitch
Else
Local newc:TList[]=New TList[nsize]
size=nsize
pitch=npitch
For Local i%=0 Until content.length
If content[i] Then
For Local node:hash2dnode=EachIn content[i]
Local nindex%=contentindex(node.x,node.y)
If Not newc[nindex] Then newc[nindex]=New TList
newc[nindex].addlast node
Next
EndIf
Next
content=newc
EndIf
End Method
Rem
bbdoc: Find a node.
returns: The node at the specified coordinates; null if none exists.
End Rem
Method findnode:hash2dnode(x%,y%)
Assert content
Local index%=contentindex(x,y)
Local list:TList=content[index]
If list Then
Local link:TLink=list._head._succ
While link<>content[index]._head
Local node:hash2dnode=hash2dnode(link._value)
If node.x=x And node.y=y Then
link._pred._succ=link._succ
link._succ._pred=link._pred
link._succ=list._head._succ
link._pred=list._head
list._head._succ._pred=link
list._head._succ=link
Return node
EndIf
link=link._succ
Wend
EndIf
Return Null
End Method
Rem
bbdoc: Find a value.
returns: The value at the specified coordinates; null if none exists.
End Rem
Method find:Object(x%,y%)
Local node:hash2dnode=findnode(x,y)
If node Then
Return node.value
Else
Return Null
EndIf
End Method
Rem
bbdoc: Insert a value.
returns: The node created to contain the value.
End Rem
Method insert:hash2dnode(x%,y%,value:Object)
Assert content
Local index%=contentindex(x,y)
Local node:hash2dnode=hash2dnode.Create(x,y,value)
If Not content[index] Then content[index]=CreateList()
content[index].addfirst node
count:+1
Return node
End Method
Rem
bbdoc: Remove a node.
returns: True if the node was successfully removed, false otherwise.
End Rem
Method removenode%(node:hash2dnode)
Assert content And node
Local index%=contentindex(node.x,node.y)
Local list:TList=content[index]
If list.remove(node)
count:-1
If list.isempty() content[index]=Null
Return True
Else
Return False
EndIf
End Method
Rem
bbdoc: Remove the value at a coordinate.
returns: The node that was removed; null if no such node existed.
End Rem
Method remove:hash2dnode(x%,y%)
Local node:hash2dnode=findnode(x,y)
If node Then
If Not removenode(node) Then node=Null
EndIf
Return node
End Method
' Returns the bucket index for a given coordinate.
Method contentindex%(x%,y%)
Return (((x+y*pitch) Mod size)+size) Mod size
End Method
Rem
bbdoc: Implements EachIn support for values.
returns: An iterator object.
End Rem
Method ObjectEnumerator:hash2denum()
Return hash2denum.Create(Self,0)
End Method
Rem
bbdoc: Implements EachIn support for nodes.
returns: An iterator object.
End Rem
Method NodeEnumerator:hash2denum()
Return hash2denum.Create(Self,1)
End Method
End Type

Rem
bbdoc: Hash2d node type.
End Rem
Type hash2dnode
Field x%,y%
Field value:Object
Function Create:hash2dnode(x%,y%,value:Object)
Local n:hash2dnode=New hash2dnode
n.x=x;n.y=y;n.value=value
Return n
End Function
End Type

Rem
bbdoc: Enumerator type for EachIn support.
End Rem
Type hash2denum
Field hashindex%,nextindex%,hash:hash2d,link:TLink
Field nodeenum%=0
Function Create:hash2denum(hash:hash2d,nodeenum%)
Local n:hash2denum=New hash2denum
n.hash=hash
n.nodeenum=nodeenum
n.init
Return n
End Function
Method init()
hashindex=-1;nextindex=-1
Local index%=0
Repeat
If hash.content[index] And (Not hash.content[index].isempty())
If hashindex=-1 Then
hashindex=index
link=hash.content[index]._head._succ
Else
nextindex=index
Exit
EndIf
EndIf
index:+1
If index>=hash.size Then Exit
Forever
End Method
Method HasNext%()
Return nextindex>-1 Or (link And link<>link._value)
End Method
Method NextObject:Object()
Assert link
Local value:Object=link._value
link=link._succ
If link=link._value And nextindex>-1 Then
hashindex=nextindex
link=hash.content[hashindex]._head._succ
Repeat
nextindex:+1
If nextindex>=hash.size Then nextindex=-1;Exit
If hash.content[nextindex] And (Not hash.content[nextindex].isempty()) Then Exit
Forever
EndIf
If nodeenum
Return value
Else
Return hash2dnode(value).value
EndIf
End Method
Method ObjectEnumerator:hash2denum()
Return Self
End Method
End Type


Comments : none...