A demo of spatial hashing for physics simulations. In this example the algorithm is used to reduce the number of collision checks per frame, by dividing the world into a grid of cells, and then only checking for collisions between objects that are in the same cell.
Turn on the debug grid, to see which cells are being checked for collisions. Cells with lots of checks are colored in red, less expensive cells are green. There's a percentage indicator in the top left corner, showing how many collisions have been saved compared to the brute force "check everything against everything" approach.
The objects are assigned to the cells by rounding their positions to the next multiple of the cell size on x and y axis.
These are then used as keys in a hash table, which is a dictionary with the rounded positions as keys.
A sensible cell size is crucial for this problem. Too small of a cell size means large objects can overlap several cells and actually decrease performance worse, because their collision is checked against objects in each cell they occupy.
On the other hand, a large cell size means that objects that lots of objects may occupy the same cell, leading to a O(n2) collision check within that cell.
The specific hashing function for creating the key from x and y coordinates is called a pairing function,
specifically Szudzik's pairing function.
a >= b ? a * a + a + b : a + b * b; where a, b >= 0 (positive coordinates)
This is a bijecive function, which can easily be reversed to get the original coordinates, e.g. when drawing the occupied debug grid cells.
Every particle is modelled as a spring-mass system, with individual weight and spring stiffness. This model is an example for smoothed particle hydrodynamics, a type of particle based fluid simulation. After some time the lighter circles will float on top of the heavier rectangles, a phase separation occurs.