Seeing the hash-based code written out, it’s essentially a fixed grid based approach but with all of the clarity removed. (and some strange method names)
You can replace 90% of this code with two classes: SimMath’s Grid class and Guava’s Multimap class. You would also be able to handle a world of huge sizes with essentially no additional cost.
SimMath can be found here and in jcenter: GitHub - Simsilica/SimMath: A double-based math package similar to JME's float-based math classes.
Google’s Guava can be found here: GitHub - google/guava: Google core libraries for Java
The basic idea for the code you have or the Grid-based code is essentially the same. But the Grid-based code to me makes it a little clearer what’s going on.
Basic idea: turn a location into a grid cell ‘key’ and use that to store the objects in the cells. You can easily look up the objects in some cell later, etc…
The version of code you have does all of the “hashing” directly and preloads a bunch of stuff (possibly unnecessarily). It also manually manages a map of ArrayLists which Guava’s Multimap class would do for you.
SimMath Grid:
If you want the “cell ID” for some position then you just ask the grid for it. If you want the world position of some “cell ID” then you can go that direction also.
Grid.worldToId()
Grid.cellToWorld(Grid.idToCell())
Or instead of raw long-int cell IDs you can opt to use GridCell as your key. This would allow for some more convenient debugging.
As mentioned, Multimap does all of the ‘map’ management for you as it’s a Map implementation where you can have more than one value per key.
Putting it together, the setup looks something like:
Grid grid = new Grid(cellSize);
Multimap<GridCell, GameObject> index = MultimapBuilder.hashKeys().hashSetValues();
So adding an object looks like:
GridCell cell = grid.getContainingCell(gameObj.getLocation());
index.put(cell, gameObj);
Looking up all object’s in a particular cell is easy:
index.get(cell)
Philosophically there are now two approaches one could take:
- put the object into all of the cells that it can affect.
- put the object into only the cell of its location and look for neighbors only when needed.
In the first approach, when adding the object you loop through all of the cells that it intersects and add to all of those cells.
Rough pseudo code:
Vec3i min = grid.worldToCell(lowest location);
Vec3i max = grid.worldToCell(highest location);
for( int x = min.x; x <= max.x; x++ ) {
for( int y = min.x; y <= max.x; y++ ) {
for( int z = min.x; z <= max.x; z++ ) {
GridCell cell = grid.getCell(x, y, z);
index.put(cell, gameObject);
}
}
}
Then you know for any cell you look in, it will contain any object that potentially intersects that cell.
The down side is that when objects move then you have a lot more maintenance to do with respect to removing objects from the old cells and adding them to the new ones.
In the second approach, you put the “search neighbor cells” burden on the code that is doing the collision checks or whatever other queries it needs. So if you want to know what objects collides with “gameObject” you would do a similar min/max loop to the above to find the cells to look in… then do collisions with any of the objects in those cells.
The bonus is that when moving an object, you only have to take it out of the cell it used to be in and put it into the cell it’s in now. It is never “in” more than one cell.
The down side is that every time you do a collision check you will do those neighbor searches. BUT: it is quite often that you don’t know how big of an area that you want to search until you go to do it. For example, if an object is moving very fast then you might want to search a larger area… or an area biased ahead of the object, etc… These are things you won’t know until after the object is already in the index.
Furthermore, it’s quite common to want to do general “give me all of the objects in this bounding rectangle” for other reasons… and if you already have to write that routine then you might as well use it for object collisions.
Either way, it’s still way better than than the n-squared check you do without a spatial indexing scheme. The tradeoffs to each approach just depend on what you need for your game.