December 03, 2020, 08:14:32 PM

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

Offline 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.  
  10. Import brl.linkedlist
  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
  86.                                                 newc[nindex].addlast node
  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
  102.                         Local link:TLink=list._head._succ
  103.                         While link<>content[index]._head
  104.                                 Local node:hash2dnode=hash2dnode(link._value)
  105.                                 If node.x=x And node.y=y Then
  106.                                         link._pred._succ=link._succ
  107.                                         link._succ._pred=link._pred
  108.                                         link._succ=list._head._succ
  109.                                         link._pred=list._head
  110.                                         list._head._succ._pred=link
  111.                                         list._head._succ=link
  112.                                         Return node
  113.                                 EndIf
  114.                                 link=link._succ
  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()
  140.                 content[index].addfirst node
  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
  208.         Field hashindex%,nextindex%,hash:hash2d,link:TLink
  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
  224.                                         link=hash.content[index]._head._succ
  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%()
  235.                 Return nextindex>-1 Or (link And link<>link._value)
  236.         End Method
  237.         Method NextObject:Object()
  238.                 Assert link
  239.                 Local value:Object=link._value
  240.                 link=link._succ
  241.                 If link=link._value And nextindex>-1 Then
  242.                         hashindex=nextindex
  243.                         link=hash.content[hashindex]._head._succ
  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


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal