Class: Hashspace

LuxModule: luxinialuacore

A hashspace stores data paired with positional information in order to accelerate requests for data within a certain area.

This hashspace is implemented in lua and is restricted to 2D spaces and rectangular areas, which means that only two coordinates can be used to store the data.

The structure is - even though it is implemented in lua only - quite fast. If you have complex environments but don't want to use ODE for collision detection, you can use this class. It is very easy to use and can manage thousands of objects cheaply. You can even remove items from the space and reinsert them somewhere else while the costs for doing that are cheap.

Example

 space = Hashspace.new() -- create hashspace
 space:add("pawn1",5,4,10,10) -- insert pawn at 5,4 with size 10,10
 space:add("pawn2",15,6,10,10) -- insert pawn at 15,6 with size 10,10
 environment = Hashspace.new() -- create a hashspace for the environment
 for i=1,100 do
   -- insert now lots of small boxes scattered around randomly
   environment:add("obstacle "..i,math.random()*100,math.random()*100,4,4)
 end
 space:test(environment, -- test the playerspace against the environment
   function (a,b) -- function is called if two items from each space intersects
     print(a,b) -- print out intersecting items
   end)

Output

The result from the test above (may differ from other results due to different random number generation):
 obstacle 4   pawn2
 obstacle 6   pawn2
 obstacle 23  pawn1
 obstacle 29  pawn1

Methods:

Method overview:


new ([gridsize = 2])
returns: (Hashspace)
Creates a hashspace structure. The gridsize determines the minimum size of the cells in the space - which cannot be smaller than that. If your objects and coordinates are much smaller (i.e. 0.01), you should pass another size which fits the average sizes in your case better. The hashspace works well if the gridsize is somewhere between the minimum and average size of all your objects in your environment.
add (Hashspace, item, centerx,centery,width,height)
returns: ()

inserts item (which can be any type) into the hashspace at the given coordinates. The given rectangle will be used if an intersection case is tested.

Reinserting an element if it is already present in the space will throw an error. Make sure it does not exist in that space before adding it!
get (Hashspace,centerx,centery,width,height,[appendtable = {}])
returns: (table)
rectangular request to the hashspace. It will return a list of all items that are intersecting this area. If the appentable is passed, the items will be appended to that list. This is useful if you have multiple spaces and test them each for an area, creating a single list.
 list = space:get(2,4,10,6) -- request area is at 2,4 with width/height=10,6
 for i,item in ipairs(list) do -- iterate all items
   print(item) -- print out intersecting items
 end
remove (Hashspace, item)
returns: ()
removes a certain item from the hashspace. This can be used if an object has moved over the time and the rectangle has to be updated in the hashspace. If you have lots of objects in a hashspace and only few are changing their position, you shouldn't rebuild the space from scratch (which might be more efficient if lot's of data has changed) but remove the item and reinsert it again. As this is still somewhat expensive, you could also prefer to insert your items with a slightly larger rectangle and make an exact collisiontest for the hitlists yourself and update the rectangle only if the object has moved a larger distance. It improves speed alot if you chose rectangles that are 10% larger if it helps to reduce the number of removes and add calls per frame for about 1:10.
test (Hashspace self, Hashspace otherspace, fncallback)
returns: ()

Tests two hashspaces against each other and call the callback function in case of intersection with both intersecting items (function (a,b)). Testing two hashspaces against each other is much more efficient than doing all the requests by calling the get function. If you have more requests to do, you should batch all requests in another hashspace and test it then with the other space. However, if both structures must be built from scratch, the get function will be a little bit faster. It only pays out if at least one of both structures has been built before anyway.

If two spaces are tested, all items will be only be tested once against each other. However, if both spaces are the same space (for testing intercollisions), you have to ignore selfintersection of an item which will occur then.