Class SpatialHashGrid

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 | ? |
+---+---+---+---+
| ? | ? | ? | ? |
+---+---+---+---+
| ? | ? | ? | ? |
+---+---+---+---+

See: https://www.gamedev.net/tutorials/programming/general-and-gameplay-programming/spatial-hashing-r2697/

Author

André Wisén

Copyright

MIT

Hierarchy

Constructors

constructor

Properties

bounds cells dimensions queryIds

Methods

findNear getCellIndex insert newClient remove updateClient

Constructors

constructor

  • Create a SpatialHashGrid object using a fixed sized grid.

    Parameters

    • bounds: 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: Vector2

      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.

    Returns SpatialHashGrid

Properties

Private bounds

bounds: Bounds

The min and max the grid will operate on.

Private cells

cells: Nodes

A doubly-linked list containing a two-dimensional array of nodes. Each node corresponds to a cell.

See: https://medium.com/front-end-weekly/data-structures-linked-list-implementation-in-js-3beb48ff49cd

Private dimensions

dimensions: Vector2

How many cells along each dimensional axis.

For example: If the world is 100 units wide and we have 5 cells, then each cell will span 100/5=20 units.

Private queryIds

queryIds: number

Used to deduplicate clients in findNear.

Methods

Protected findNear

Private getCellIndex

Private insert

  • Using the position and size of the client, loop over the cells that the client touches.

    If the client touches a cell, then insert the client into it.

    Parameters

    Returns void

Protected newClient

Protected remove

updateClient

Settings

Member Visibility

Theme

On This Page

Generated using TypeDoc