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.