4
\$\begingroup\$

I feel kind of silly for asking this question, but are there examples or tutorials on how to implement a spatial hash (grid/cell-based partitioning), preferably in C++?

I'm stuck and I have no idea how to tackle this problem. I've searched all over but all I get are people saying "gosh that's easy to do", which I'm sure is true if you've seen another implementation or have done so yourself.

Instead of quadtrees I'd like to have a spatial hash to query areas of my game which has a very large world.

Thinking it probably wouldn't even have to account for sizes, merely points, as the type of game mine is that isn't that big of an issue. And if it is, I could always add that.

\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

To do a basic spatial hash (slightly more complicated forms exist), you need to generate a broad discrete grid location for any game location. This might be as easy as converting float positions to ints or taking int positions and dividing them all by 64 or some other constant.

The idea there is to create a single discrete location most nearby objects will map to. For instance, if dividing by 64, then both objects at (137,76) and (142, 65) will be mapped to the cell (2, 1).

You can use this cell id as the index to a hash table or other fast lookup structure. You should be able to use std::pair<int,int> as a key to std::unordered_map, I think. Add both objects to the cell they belong to. Now you can easily query all objects that share the same cell.

To find all objects near a particular object, you could query every cell bordering the target object's cell. So to find all objects that might be colliding with an object in cell (3, 7), you'd check that cell plus (2, 6), (3, 6), (4, 6), (2, 7), etc. Just to find all neighbors of a particular game object will you do 9 spatial hash lookups.

Alternatively, insert every object into the cell its own and all neighboring cells. Whenever an object moves, calculate the new 3x3 grid it occupies. Take the disjunction between the old grid and the new one. These sets might be both empty if the object only moved a little (that is, it's new 3x3 grid is identical to the old 3x3 grid). Remove the object from the cells it no longer neighbors and add it to the new ones. In the worst case, if an object moves more than 1 tile in a second update cycle, you'll have to do 9 removals and 9 insertions, but that should be rare.

Which approach is better will depend on your game, but in general, the second approach will likely have a minor performance benefit.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .