Collision detection

Collision detection

In modulus7, the game is infinite. Enemies spawn based on parametrised criteria near the player. There can be a large number of objects in the game at a time. (hundreds of enemies, thousands of particles)

The game internally uses an Entity Component System to track which objects need to be updated. Enemy objects can look at the player's position and determine if it has collided fairly efficiently.

The same isn't true for bullets. There can be hundreds of bullets, if every enemy had to check every bullet this could impact the game's performance.

Ordinarily a "spatial hash" would solve this problem. Basically, split the game world into a grid like chess board, then each object only needs to check it's grid cell. This approach suffers from 2 main problems:

• the enemies and bullets are usually close to the player 
• the grid is finite size

the problem can be visualised in the grid above. If orange is bullets and blue is enemies, most of the objects share the same grid cell (which means there's no performance gain). Additionally they are near the edge of the grid. If they player moves forward they could run off the edge of the grid.

What instead is done, is that every object's x,y value is combined in a hash and stored in a flat 1d array. For the same x,y this would give the same cells.

This approach allows for a hash function to give an avalanche effect (i.e. small changes in x,y result in large changes in the hash grid). Which gives better performance. It also means that the original x,y can be any value, there's no limit to the size of the game world. 

There are drawbacks, it's bigger objects which might straddle several grid cells are harder to compute. But for a game jam this approach works well