Coder’s Corner: Spatial Hashes

In our second installment of Coder’s Corner we’ll discuss SpatialHashes. For those of you thinking, “This got intense fast… last month was IDE setup – shouldn’t this be some sort of libgdx ‘hello world’?” Tough. There are many, many tutorials for people (and robots) just starting out in coding and game development. There is less discussion on more intermediate and advanced topics. So that’s where Rho_Bot and I have decided to focus Coder’s Corner. To answer the other half of the initial question, we chose SpatialHashes specifically because I actually made one for Stoned in Space.

Which brings us to the question most of you may be asking: What is a SpatialHash? (Just to be clear we’re going to discuss the data structure used for accelerating collision calculations not the one for compacting loose spatial data.)

According to some eggheads: “Spatial hashing is a process by which a 3D or 2D domain space is projected into a 1D hash table.”

While this is probably true if you delve far enough into how the data is actually stored (It’s exactly how I backed my SpatialHash), I think it misses describing the concept in favor of describing the implementation.

At the most general level a SpatialHash is data structure where an object can be looked up based on its location in space. As a side effect, objects that are physically close together get grouped. Or to describe it in more computer science-y terms, a SpatialHash is a special case of a HashTable where an object can be referenced by its location. That means you can almost say SpatialHash = HashTable<multi-dimensional-point, object>. However, a salient difference between a HashTable and a SpatialHash is that HashTables almost always have unique key-value associations. For a SpatialHash this is not the case. Depending on your situation you might want a relation that links one key to many values or one value to many keys. If the SpatialHash is going to be used for collision detection, having a single key to a single value relationship defeats the point of grouping an object with things it is likely to collide with.

And collision detection was the reason that I created a SpatialHash for Stoned In Space. I originally anticipated there would be a lot more objects and, therefore, many, many potential collisions to check for.

Having a large number of objects means that doing brute force collision detection would take up substantial computational time every frame and make the game unpalatably slow. So we needed a way to make the collision checks faster. I can hear the coders and cyborgs in the audience saying, “You want to partition space. Just use a QuadTree for that.” Maybe… But before we settle on a solution for the problem we should make sure we’ve accurately defined the problem scope. So, let’s round out our initial assumptions:

00. lots of objects (as previously mentioned)
01. uniform object distribution
10. uniform object size
11. Fixed world space (for example we’d always be working with 4 parsecs²; not sometimes 4 and sometimes 9 parsecs²).

Based on these assumptions it turns out that a quad tree would split down into the same number of cells as a SpatialHash. Which eliminates one of the major advantages of the QuadTree – fewer cells to check for collisions. And since the whole point of partitioning the collision space is to reduce the time spent doing collision checks, why not save additional time by sizing the cells in advance instead of splitting them every time collisions are checked?

Adding objects to a SpatialHash can be implemented two general ways. In what we’ll call “Method A”, each object can be consolidated to a point (finally we find an application for that whole center of mass concept from physics). In “Method B” we add an object to all cells intersected by its axis-aligned-bounding-box (aabb).

Method A has fast put and remove methods since it only has to deal with one cell. But since the information on the object’s size isn’t contained in the SpatialHash, all cells that might contain part of the object must scanned when looking for collisions. Assuming the object is placed in the cell that contains its center; the scan radius in cells should be “check radius = object radius / (cell size) + 1”. This method works well for uniformly sized objects with relatively low density. If all objects are approximately the same size it would be easy to size the cells to keep the number of cells scanned per object to nine. This also corresponds to the minimum safe scan number in this style.

Method B has slower put and remove methods since the aabb has to be found and then converted to hash space before the object can be placed in SpatialHash cells, but it results in faster collision detection since you’re only checking cells the object is in (minimum of one). This method is useful if objects vary dramatically in size.

Benchmarking the two styles is left as an exercise for the reader. Mainly because which performs best will depend on the particular application.

How did I implement a SpatialHash? Glad you asked. I used Method B and put together a pretty straightforward 2D SpatialHash (here’s the code). In addition to the SpatialHash object I also used a simple data structure called a HashRectangle. This structure could be replaced with class variables if desired. However I think it adds clarity to the code.

The meat of any hash is its hashing function. So I’m going to constrain my discussion to that section of code and the SpatialHash’s fields. Also I’m going to start referring to “world space” and “hash space”.  In the first drawing world space is the area contained by the large rectangle and is addressable by (float, float); hash space is the subdivision of the world represented by the grid and is addressable by (int, int) or just (int).

Let’s start with fields

List<List<T>> cells;

The inner list is a list of objects in a cell, and the outer list is a list of the cells (you can probably tell from my imaginative name) in space. For reasons that have been lost in the mists of time, I chose a single list to contain all the cells in space rather than some sort of 2D array. Likely this was done for a combination of readability and to reduce memory overhead. The latter of which grows rapidly when adding extra dimensions to data structures in Java. That and you you also only need one loop to iterate over all of space when looking for collisions.

int numRows;
int numColumns;

The numRows and numColumns variables represent the extents of hash space. I’m going to discuss them together. Since I opted for a single list to represent all of the cells, we need to know the dimensions of the area of interest in hash space. The astute among you are already pointing out that I really only need one of these and cells to define the space (numRows = cells.size()/numColumns), and you’re right – one of these variables is a pre-calculated helper variable which is why I wanted to discuss them together.

float cellSize;

This is the size of a cell in world dimensions. In this case I assumed that cells would be square, but rectangular cells could be used if a specific situation called for it. This field is critical since it allows conversion between world space and hash space.

On to methods

private HashRectangle hashFunction(Rectangle worldRect) {
    HashRectangle hashRect = hashFromWorldRect(worldRect)

    if ( isHashRectOutOfBounds(hashRect) ) {
        return null;
    }

    HashRectangle constrainedRect = constrainHashRectToHashSpace(hashRect);
    return constrainedRect;
}

Continuing my trend of imaginative names, the hash method is called ‘hashFunction’. At first this method might appear misnamed since the actual hash conversion is done by the ‘hashFromWorldRect’ method. Which, if you haven’t read the code or guessed, converts the ‘worldRect’ to hash space by dividing  the vertices of the worldRect by cellSize and truncating to form an integer. However, the second half of the method validates and constrains the raw hashRectangle returned by the ‘hashFromWorldRect’ method, and I consider validating and constraining to be part of the overall hashFunction.

At this point those of you who are still conscious and have been able to follow everything so far  are probably thinking, ”ACMU, you used a dynamically resizable data structure (a list) to back the SpatialHash’s data; so you could resize this on the fly, but earlier you mentioned having a fixed world size as being part of the choice to use a SpatialHash over a QuadTree.” This is true. SpatialHashes can be resized on the fly but… one – if not the biggest – advantage of the SpatialHash is that it is pre-partitioned. If your world space is resized then it needs to be repartitioned, and partitioning early and often is where QuadTrees excel. If your world has an occasional resize a SpatialHash might still be more beneficial than a QuadTree, but that’s something you’ll have to benchmark in your particular application.

And that’s everything I know about SpatialHashes. I hope you found this mildly condescending and slightly informative.
If you’d like to read some additional views on SpatialHashing, take a look at these resources:

 

Spatial Hashing, by Tristam MacDonald at Gamedev.net

Spatial Hashing, by Simon Wittber at Entity Crisis

Spatial hashing implementation for fast 2D collisions, Conkerjo at The Mind of Conkerjo