Optimizing Collision Detection
In the previous chapter, we created a simple collision detection system that can detect and take action whenever two bodies collide. However, the implementation is slow because it has to check every pair of bodies in the system. In this article, we will optimize the collision detection system by using a spatial partitioning system. This spatial partitioning system will divide the world into a grid of cells, and then only check for collisions between bodies in the same cell. In practice, this will speed up the collision detection system by a factor of about 10 to 100.
The key insight behind this optimization is that collisions are not possible between bodies that are "far" away. For this reason, if we can determine that two bodies are not close enough to each other to possibly collide, we can skip the collision detection step. This is called the broad phase of the collision detection system.
In comparison, the narrow phase is what actually checks for collisions between two bodies. In the previous article, we used the narrow phase exclusively on all pairs of bodies. However, in this article we'll show how we can use the broad phase to eliminate most of the pairs of bodies that we need to check. Therefore the final collision detection system will work by first running the broad phase and placing the bodies in different spatial cells. Then, the narrow phase will be run on each cell in the grid.
There are many ways to implement the broad phase. We'll be implementing a uniform grid, which is not the most efficient method, but it's still fast enough for most games and it's the simplest method. If we get to a point where the uniform grid is still not fast enough, there are algorithms such as QuadTree, KDtree, and others which we can use. Until then, the uniform grid will serve us well.
The first thing we have to decide is the size of the grid. If we make the grid small, we will have to check less pairs of bodies, but at the same time we will have to spend more and more memory to hold the grid. The reverse is also true, the larger the grid the more comparisons between bodies, but less memory used. Because modern computers have an abundance of memory, it's best to stay on the safe side and make the grid relatively small, a good rule of thumb is to make it roughly two or three times the size of the player character.
A grid cell is defined by its top-left corner and size. For example, if we have a cell with a top-left corner of (0, 0) and a size of 150, we can simply call this cell 0|0, the next cell to the right would be 150|0, and the next cell to the bottom would be 150|150.
The next step is to create a function that will calculate which cells does a body fit into. Given a BodyComponent, we can calculate the cell (or cells) that the body fits into. The body can fit into multiple cells in the case where it is larger than the size of a cell, or if it sits between multiple cells.
function calculateCells(bodyComponent) {
const cellSize = 150;
const xCells = [];
const yCells = [];
const calculatedCells = [];
let maxX = Math.ceil((bodyComponent.position.x + bodyComponent.width)/cellSize)*cellSize;
let maxY = Math.ceil((bodyComponent.position.y + bodyComponent.height)/cellSize)*cellSize;
for(let x = bodyComponent.position.x; x <= maxX; x+=cellSize) {
xCells.push(Math.floor(x/cellSize)*cellSize);
}
for(let y = bodyComponent.position.y; y <= maxY; y+=cellSize) {
yCells.push(Math.floor(y/cellSize)*cellSize);
}
for(let i = 0;i<xCells.length;i++) {
for(let j = 0;j<yCells.length;j++) {
calculatedCells.push(`${xCells[i]}|${yCells[j]}`);
}
}
return calculatedCells;
}Using the calculateCells function, we can place each CollisionComponent in the appropriate cells. This must be done during each call of CollisionSystem.update().
Once all the CollisionComponents are placed in the appropriate cells, we iterate through each cell and check for collisions between bodies within each cell. Since the expected number of bodies inside a cell is relatively small, this is much faster than naively iterating through all bodies in the system. Also important to note is that the behavior and signature of the CollisionSystem is the same as what we had before, so we can simply replace the old class with the new and it will work as expected.
Well, there is one bug we have introduced that we have to fix before it's a true replacement. If a body is placed in two cells, it will be checked against all bodies in both cells. This is expected, but if yet another body is placed in the same two cells, then the same pair of bodies will be checked twice, the collision will be detected twice, and the collision callback will called twice. This is not what we want, and the way to fix it is to keep a list of pairs that we've already checked and only check pairs that are not in this list.
The code for the complete system is as follows:
import System from "../ecs/system";
import CollisionComponent from "./collisionComponent";
export default class CollisionSystem extends System {
constructor() {
super();
}
update() {
const cells = {};
const checkedPairs = {};
const collisions = [];
for(let i = 0; i < this.components.length; i++) {
let collisionCells = calculateCells(this.components[i].bodyComponent);
for(let cellKey of collisionCells) {
if(!cells[cellKey]) {
cells[cellKey] = [];
}
cells[cellKey].push(this.components[i]);
}
}
for(let cell of Object.values(cells)) {
for(let i = 0; i < cell.length - 1; i++) {
for(let j = i + 1; j < cell.length; j++) {
if(!(checkedPairs[`${cell[i].id}|${cell[j].id}]`])) {
if(checkOverlap(cell[i].bodyComponent, cell[j].bodyComponent)) {
checkedPairs[`${cell[i].id}|${cell[j].id}`] = checkedPairs[`${cell[j].id}|${cell[i].id}`] = true;
if(cell[i].collisionCallbacks[cell[j].collisionTag]) {
collisions.push(cell[i].collisionCallbacks[cell[j].collisionTag]);
}
if(cell[j].collisionCallbacks[cell[i].collisionTag]) {
collisions.push(cell[j].collisionCallbacks[cell[i].collisionTag]);
}
}
}
}
}
}
for(let collisionInstance of collisions) {
collisionInstance();
}
}
createCollisionComponent(bodyComponent, collisionTag) {
let collisionComponent = new CollisionComponent(bodyComponent, collisionTag);
this.components.push(collisionComponent);
return collisionComponent;
}
}
function calculateCells(bodyComponent) {
const cellSize = 150;
const xCells = [];
const yCells = [];
const calculatedCells = [];
let maxX = Math.ceil((bodyComponent.position.x + bodyComponent.width)/cellSize)*cellSize;
let maxY = Math.ceil((bodyComponent.position.y + bodyComponent.height)/cellSize)*cellSize;
for(let x = bodyComponent.position.x; x <= maxX; x+=cellSize) {
xCells.push(Math.floor(x/cellSize)*cellSize);
}
for(let y = bodyComponent.position.y; y <= maxY; y+=cellSize) {
yCells.push(Math.floor(y/cellSize)*cellSize);
}
for(let i = 0;i<xCells.length;i++) {
for(let j = 0;j<yCells.length;j++) {
calculatedCells.push(`${xCells[i]}|${yCells[j]}`);
}
}
return calculatedCells;
}
function checkOverlap(b1, b2) {
if (b1.position.x + b1.width < b2.position.x ||
b1.position.x > b2.position.x + b2.width ||
b1.position.y + b1.height < b2.position.y ||
b1.position.y > b2.position.y + b2.height) {
return false;
}
return true;
}The system we just showed is organized as follows:
- In line 54, we define the calculateCells function, which calculates which cells does a body fit into
- In lines 14 - 22, we take each body and place them in the appropriate cells using the calculateCells function
- In lines 24 - 40, we iterate through each cell, and check each pair of bodies in that cell for collisions. If a collision is detected, we add the collision callback to the collisions array.
- In line 29 we add the pair to the list of already checked collisions, to ensure that the same pair of bodies is not checked twice. The actual check is done in line 27.
- In lines 42 - 44, we apply the collision callbacks that we stored earlier in the collisions array.
At this point, our updates to the CollisionSystem are complete. We can replace the old implemetation with the new one and we'll get a significant performance boost.
There are still two optimizations we can make to improve the performance even more. The first is to only check bodies if there are collision callbacks registered for it. For example, if we don't have any callbacks registered when a food touches a poison, we don't need to compare this pair. The second optimization is to only update the cells when the bodies inside them move. If a body did not move, we can be sure that it will still fit in the same cells as before, so we can just store these and use them again. These optimizations are left as an exercise to the reader.