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.

definition
Figure the first. Graphical representation of a spatial hash

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.

lots-of-objects
You wish there were this many missiles in Stoned In Space

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 

Coder’s Corner: Using Log4j in a LibGdx project in Intellij – Gradle hiccup

Apparently stuxnet managed to hybridize in a way such that it’s taken Josh out for the foreseeable future. Either that or he succumbed to snowcrash. In any event, that means that Rho-Bot and I will be conquering our weekly blog for the foreseeable future. And starting our new and likely recurring segment: Coder’s Corner.

Earlier this week I was setting up our new project (no, we’re not going to squeal on what it is yet), and I wanted to use the Log4j libraries. My primary motivation for doing so is that I like data and, if I’m not the one doing the testing, I usually get incomplete descriptions of bugs back. Since libgdx’s built in logging only outputs to the console we need some way to create actual log files ergo Log4j. I’ve used these libraries in our earlier projects with no problems. But last week I started using Intellij as my IDE. This time, however, after I dropped the libraries and my config file into the same location as the last project and I got this error:

log4j error
ERROR StatusLogger No log4j2 configurationfile found. Using default configuration: logging only errors to the console.

I know what you’re computing ‘ACMU you forgot to add ?*.xml to the resource patterns in your compiler settings. As it happens, 0) I did not forget to do that, and 1) as I found out the next day it’s not strictly necessary to do that for Log4j anyway.
With that most obvious source of my difficulties out of the way I clicked over to the Log4j manual and it says

“If a JSON file cannot be located the XML ConfigurationFactory will try to locate log4j2.xml on the classpath.” 

So you’d think that if my project structure looks like this:

project structure
Whatever the next project is it’s safe to say it’s both bad and angry

the library would find a configuration file acceptable and use it. No dice (Did you processor that pun?). So I spent a few hours on stackexchange making no progress. Then, through some fluke, I read the Log4j configuration page again and realized that a line up at the top says,

“Log4j will inspect the “log4j.configurationFile” system property and, if set, will attempt to load the configuration using the ConfigurationFactory that matches the file extension.”

Alright so we’ll just got to Run->Edit Configurations, set our system property like this:

configuration options

Drop the config file into your working directory and voila, Log4j is configured.

The next morning when I got to work it occurred to me that a work project was using Log4j too. I had just started using Intellij at work too, and I didn’t remember having any configuration issues, so I did a little digging. I went looking for the project’s log4j2.xml file and found it sitting in the /src/ directory and I hadn’t even marked *.xml as a resource file type.

Which leads to the question, “What are the differences between these two projects?”. Well, at home I set up a libgdx project using gradle for dependency management; at work I just write code with no dependency management – because enterprise applications are boring. So, an alternate (and probably better) solution than the one I found is to include the Log4j configuration file as a resource in the gradle.build file. And no I’m not going to tell you how to do that. In the words of many a professor and textbook: it’s left as an exercise for the reader.