Physics Collision and Spatial Mapping
Physics engines are wildly known and solved spaces as there are plenty of tutorials and frameworks out there to help you write your own version too. To name a few tutorials:
- Game Engine Physics Development by Ian Millington
- How to Create a Custom Physics Engine by Randy Gaul
And some frameworks:
But something that has typically interested me with physics engine is how to potentially detect collisions. Now this is primarily a data structure problem, as we would have to reason about how we would want to structure all of our physics bodies based on their positions. Ultimately, the end goal of this structure is to provide a fast way to check potential collisions without having to brute force and compare every single physics body with each other (this becomes an n² check!).
Spatial Hashmaps
One way to store physics bodies is to divide your play area into a group of cells as a grid. We can then store a bunch of physics bodies into a cell and determine which cells that each physics body is in. By design spatial hash maps are hash maps with chained linked lists as their values. Therefore, potential physics bodies in the same cell will be registered into the same hash.
Key Values
---------
1 -> [A] [B]
2 -> [D]
3 -> [E] [F] [Z]An example with the left column being the key and the right column being multiple values with the same key.
The Hash Function
Each physics body is typically defined with a position represented as Cartesian coordinates (float3) . Ultimately, the hash function will take each axis value and combine the values into a key which we would use to register into the hash map.
A good hash function balances balances the number of potential collision we have per cell. If we have a very accurate hash function, then we may generate new hash map entries for physics bodies which are close together. If we have an inaccurate hash function, then we potentially may add in all physics body positions into a few cells, which may lead us closer to polynomial time to detect collisions.
By dividing the physics body position x and y values by the grid size and adding the components together, we get a decent hash that can contain multiple physics bodies. Here’s the pseudo code of the description above.
int Key(int size, float3 v)
{
return ((int)(floor(v.x / size) + floor(v.y / size)) * size);
}Examples for: (1, 1, 0), (2, 1, 0), and (20, 11, 0) this hash function will produce:Point: (1, 1, 0)
-------
(floor(1 / 10) + floor(1 / 10)) * 10 = hash_value
(0 + 0) * 10 = hash_value
0 = hash_valuePoint: (2, 1, 0)
-------
(floor(2 / 10) + floor (1 / 10)) * 10 = hash_value
(0 + 0) * 10 = hash_value
0 = hash_valuePoint: (20, 11, 0)
-------
(floor(20 / 10) + floor (11 / 10)) * 10 = hash_value
(2 + 1) * 10 = hash_value
30 = hash_value
Physics Shapes
Physics bodies are typically defined with a physics shape. For my needs in Carté Diem, most physics bodies currently are defined as a box. Complex shapes will eventually be included later down the line. For example, our player Ellen can occupy multiple cells:
Now the simplest way to ensure that Ellen occupies multiple cells is likely to brute force and sample some points along each edge of the box. This is obviously not a very nice solution because we can potentially register the same physics body multiple times to the same hash. We can, of course, do a final check to ensure we uniquely add physics bodies to a hash, but we possibly would not know how many times we have to perform this uniqueness check.
But even with brute force, a question like this popped up during development:
- Can we accurately get all the cells that the box physics shape occupy?
Well this problem was similar to an old Graphics problem I learned about which was determining which pixel a line potentially occupied. This is known as Bresenham’s Line Algorithm.
The idea behind the algorithm is to calculate the slope of a line segment and to sample intervals to check which cell the sampled line segment belongs to. Here’s the pseudocode implemented in my physics engine below.
Line(float2 from, float2 to, int cellSize)
{
value = floor(from);
diff = to - from;
step = sign(diff);
offset = float2(
to.x > from.x ?
ceil(from.x) - from.x :
from.x - floor(from.x),
to.y > from.y ?
ceil(from.y) - from.y :
from.y - floor(from.y));
angle = atan2(-diff.y, diff.x);
angles = float2(cos(angle), sin(angle));
tMax = offset / angles;
tDelta = cellSize / angles;
dist = abs(floor(to.x) - floor(from.x)) +
abs(floor(to.y) - floor(from.y)); // v will be associated cell's position. We can add
// this to a collection or process this immediately
v = FloorToNth(value, cellSize);
for (int i = cellSize; i < dist; i+=cellSize)
{
if (abs(tMax.x) < abs(tMax.y))
{
tMax.x += tDelta.x;
value.x += step.x * cellSize;
}
else
{
tMax.y += tDelta.y;
value.y += step.y * cellSize;
}
// Recalcule v again to find a new cell
v = FloorToNth(value, cellSize);
}
}
What makes Brehansem’s line algorithm incredibly useful is visualization. If we collect all cells associated with the line we can provide the cell’s position and draw a heat map which will visualize the density of potential colliders.
