three-spacial-hash-grid is a two-dimensional (!) spatial hash grid for three.js.
Heavily inspired by:
- "Spatial Hash Grids & Tales from Game Development"
- "How I Optimized My JavaScript Project (Complete Walkthrough) | Faster Spatial Hash Grids"
https://andrewisen-tikab.github.io/three-spatial-hash-grid/example/
Setup at scene in three.js and add the grid to the scene.
import from 'three-spatial-hash-grid';
const grid = new (bounds, dimensions);
scene.add(spatialHashGrid.group);Bounds
The min/max the grid will operate on. I.e. if the world goes from -1000, -1000 to 1000, 1000, then this should be [-1000, -1000], [1000, 1000].
dimensions
How many cells along each dimensional axis. I.e. if the world is 100 units wide and we have 5 cells, then each cell will span 100/5=20 units.
Auto-generated docs can be found here:
https://andrewisen-tikab.github.io/three-spatial-hash-grid/docs/
Please note that this is a two-dimensional grid. +Y is up and Z is used for the depth of the grid.
See the example and look at the axesHelper for more information.
This is a work in progress. It is not yet ready for production.
A spatial hash is a 2 or 3 dimensional extension of the hash table. The basic idea of a hash table is that you take a piece of data (the 'key'), run it through some function (the 'hash function') to produce a new value (the 'hash'), and then use the hash as an index into a set of slots ('cells').
Or, in other words: You can define you 2D world into a fixed grid, e.g 4x4.
+---+---+---+---+
| a | b | c | d |
+---+---+---+---+
| e | f | g | h |
+---+---+---+---+
| i | j | k | l |
+---+---+---+---+
| m | n | o | p |
+---+---+---+---+
If you place an object into the world, it would fall into a least one of these cells.
For example, let's put an object X at cell g.
+---+---+---+---+
| a | b | c | d |
+---+---+---+---+
| e | f | X | h |
+---+---+---+---+
| i | j | k | l |
+---+---+---+---+
| m | n | o | p |
+---+---+---+---+
If we want to look for objects nearby, we simply check the nearby cells.
+---+---+---+---+
| | | c | |
+---+---+---+---+
| | f | X | h |
+---+---+---+---+
| | | k | |
+---+---+---+---+
| | | | |
+---+---+---+---+
In this example, we ignore the diagonally neighbors.
In other words: This is just like Minesweeper
+---+---+---+---+
| ? | ? | ? | ? |
+---+---+---+---+
| ? | ? | X | ? |
+---+---+---+---+
| ? | ? | ? | ? |
+---+---+---+---+
| ? | ? | ? | ? |
+---+---+---+---+