Collision detection is an ongoing source of research and constant optimization in game development. It can be a source of exuberance or nearly infinite frustration. Rolling your own is typically the best way to make sure your game is never finished! However, knowing what an engine does internally to make your life easier is extremely beneficial to you as a developer. In addition to increasing your knowledge and understanding, it also helps you appreciate the hard work wrought by the giants whose shoulders you’re standing on.

This article focuses on two approaches to broad phase detection of collisions. The first is a brute force method that, while simple, quickly becomes wildly inefficient at typical game entity counts. The second is a form of spatial partitioning called a spatial grid. It is relatively simple, yet handles large numbers of game entities efficiently.

What is Broad-Phase Collision Detection?

Collision detection is usually performed in two phases: broad phase and narrrow phase.

Broad phase detection is typically a computationally low cost operation that quickly answers the question, “Which objects have a strong possibility of colliding?” Approaches include Sweep and Prune, and Spatial Partitioning.

Narrow phase is the fine grained, “What part of object A colided with object B?” step. It is typically computationally intense, and thus cannot be performed on every pair of objects in the time between game updates (e.g. the next drawn frame). Examples of narrow phase techniques are the Hyperplane Separation Theorem (also known as the Separating Axis Theorem) ¹, Pixel Perfect Collision Detection ², and Swept Tests.

Collision Detection vs Collision Response

There are two phases when attempting to update a game world: detection of the collision, followed by the response, or the result of that collision (e.g. two balls bounce off of each other). This article will focus exclusively on the detection of a collision, not the response.

Our World and Demos

The same basic setup will be used for each example of collision detection. We have a global namespace, ro (which is also the name of the basic engine), which will contain the following components:

• ro.World: responsible for adding entities, stepping/updating, and tying everything together.
• ro.Entity: a single “thing” that will exist in our game. It has basic properties, like position, size, acceleration, and more.
• ro.Screen: responsible for providing a drawing context and drawing management. Simple boxes are all that will be needed to be drawn, but separating out drawing state from the state of the world itself is good practice.
• ro.math: some common math utilities, like line intersection.
• ro.ov3: vector operations for generic objects with x/y properties
• ro.coltech: Short for “collision technique”, this object will hold the constructors for our collision detection interface.

Each demo will be using squares, and this is by no accident; most engines use a concept known as an Axis-Aligned Bounding Box (AABB) to simplify and speed up broad phase detection. An AABB is a rectangular approximation for the position and amount of space an entity occupies, and can be used in both 2D and 3D. In this article’s 2D demos, an AABB will be defined by two points: a minimum and maximum. Together, these can be used to extrapolate the remaining two points, but this is usually not necessary. Axis-aligned implies that the sides of the box are parallel to the major axes of the coordinate system, which in the demos are positive X moving right across the screen, and positive Y moving down the screen.

JSFiddle will be used to sandbox the demos. This means that the following will be valid for each demo:

The world also uses the following order for each step of the simulation:

• Clear the screen
• Call World.draw
• Accelerate all entities, update their AABBs
• Call the collision system’s update method
• Call the collision system’s queryForCollisionPairs method
• Call the user-defined handleCollisions
• Apply inertia to all entities ³, update their AABBs
• Call the user-defined update

All demos can be stopped/paused and started by mouseover/mouseout.

Let’s get started!

Approach #1: Brute Force

In nearly any collision detection scheme, every object must be tested or touched by code at least once. The most simple form is called a brute force test, where every object is uniquely tested (no duplication of tests) for collision with every other object. For games with very few objects, this is more than likely the fastest and simplest method. However, the computational complexity of this method increases quadratically for every object you add:

This quickly becomes the biggest bottleneck of the game. But here’s how to do it anyway! It is often used as an internal component of other broad phase techniques (and will be used in the second approach, the spatial grid), and occasionally is the most appropriate choice for your game.

Brute force is accomplished by a nested loop:

BruteForceTech.prototype.queryForCollisionPairs = function(){

    var i, j, e1, e2, pairs = [], entityLen = this.entities.length;

    this.collisionTests = 0;

    for( i = 0; i < entityLen; i++ ){
        e1 = this.entities[i];

        for( j = i+1; j < entityLen; j++ ){
            e2 = this.entities[j];

            this.collisionTests += 1;

            if( this.aabb2DIntersection(e1, e2) === true ){
                pairs.push( [e1, e2] );
            }
        }
    }

    return pairs;
}

BruteForceTech.prototype.aabb2DIntersection = function( objA, objB ){
    var  a = objA.getAABB()
        ,b = objB.getAABB();

    if(
        a.min[0] > b.max[0] || a.min[1] > b.max[1]
        || a.max[0] < b.min[0] || a.max[1] < b.min[1]
    ){
        return false;
    } else {
        return true;
    }
}
    

There is a small trick here to make sure we don’t have to worry about testing objects more than once accidentally. The inner loop always starts at i + 1 as opposed to 0. This ensures that anything “behind” i is never touched by the inner loop. If this is confusing, the best way to understand is to work through what the loops and variables are doing using pen and paper.

This method also introduces a staple of collision detection: an AABB overlap test. As mentioned earlier, AABB stands for axis-aligned bounding box, and is the box that is used as a rough estimate of where and how big an entity is. Each entry in ro.coltech expects an AABB to consist of an object with min and max properties, each pointing to an array with at least 2 numbers denoting absolute game world coordinates:

var myAABB = {
    min: [ 10, 20 ], max: [ 20, 30 ]
}

The above example describes an AABB located at 10, 20, with a width and height of 10. Because the AABBs in ro use absolute coordinates, they must be updated whenever the entity’s position changes. This updating happens automatically in ro.world#step ⁴.

Since the box is axis-aligned, an overlap determination is as simple as comparing the min and max points of each object respectively ⁵. Please note that this test only returns a boolean, not information about how they are overlapping (how they are overlapping is a job for narrow phase detection). The code is contained within Fig. 2.

Fig. 3 demonstrates the result of the complete brute force technique, and visually also offers a potential optimization. In this example, all squares are being checked against all other squares, and yet only one square is actually moving. An optimization would be to construct a list of moving objects, and then compare them to all the static objects. If this is appropriate or not depends on the mechanics of the game.

Approach #2: Bins / Spatial Partioning / Simple Spatial Grid

Spatial Partitioning, for our purposes, is the act of dividing up a continuous space into several discrete areas based on a few simple rules (the rules change with each technique for spatial partioning). Common techniques include a Quadtree, a BSP tree, an R-tree, and Bins / Spatial Grids, which is the topic of this section.

The rules of our gridding system are as follows:

• A cell is defined as a square having discrete boundaries (e.g. it describes an exact “piece” of space). ⁶
• If an entity’s axis-aligned bounding box overlaps with a cell, the entity will be inserted into that cell.
• An entity can be inserted into multiple cells.
• The grid will be discarded and rebuilt after every world update.
• Looking for coliding pairs requires iterating over every occupied cell of the grid.
• We must track which pairs have already been tested against each other.

Representing the Grid

Spatial grids have a one-to-one mapping of world coordinates to a memory structure, represented by an array or linked list. Having a direct mapping to a physical space allows a spatial grid to be more easily visualized, aiding in debugging and understanding. Our grid will be represented by a 3D array. The indices of the first array will be columns, the indices of the inner array will be cells, and the innermost indices will be individual entities assigned to a cell:

Mapping a world position, for example { x: 46, y: 237 }, can be accomplished using the following formulas:

// Math.floor( (position - gridMinimum) / gridCellSize )

var  col = Math.floor( (46 - grid.min.x) / grid.pxCellSize )
    ,cell = Math.floor( (237 - grid.min.y) / grid.pxCellSize );

grid[col][cell] = ... // bucket to put entity into

grid.pxCellSize is the number of pixels each cell covers. Since each cell is assumed to be square, only one value is needed. grid.min.x/y allows for entities to have negative positions, and still produce a valid numerical array index. Typically the grid minimum will be { x: 0, y: 0 }, but you could have a grid that maps to a world like Fig. 5.

Choosing an Appropriate Cell Size

Cell size plays a large role in how efficient the grid can be. In Fig. 6, the effect of a very small cell size is seen when entities are large. Each entity overlaps many cells, and because the spatial grid iterates over cells, and not entities, there is actually more work for it to do than a brute force entity-to-entity comparison.

In Fig. 7, a very large cell size is paired with small entities. In this case, only one cell will need to be visited, but each entity will need to be tested against every other entity, which is, again, the same as a brute force entity-to-entity comparison.

Both Fig. 6 and Fig. 7 are worst case scenarios: the size of the entities is a complete mismatch for the size of the cells of the grid. Unfortunately, this is one of the downsides of a strict spatial grid: it must be tuned to the entities it will hold. In addition, if there are entities that vary greatly in size, it can be worse than a brute force comparison, as shown in Fig. 8. In this case, there is no appropriate cell size. A smaller cell size would cause too many cell-to-cell comparisons, while a large cell size would cause as many entity-to-entity checks as the brute force method.

To demonstrate the effect cell size can have, Fig. 9 allows for the cell size to be changed on the fly. In this case, all of the entities are similarly sized, so an efficient cell size can be found.

In addition to computational power required, another concern is the memory consumption of the number of allocated cells. As the grid gets more and more fine, more memory will be allocated and released after each update, causing garbage collection churn. This can cause noticeable pauses and hiccups. While it’s difficult to track using user-built tools, Chrome’s Memory Profiler can be used to see the effect each cell size has on memory consumption.

Grid Population

As said before, the spatial grid is recreated for each world step. This avoids needing to keep track of updating which cells an entity is overlapping once the entity’s position has changed. The general algorithm for constructing and populating the grid is specified in Fig. 11.

Querying For Collision Pairs

Querying for collision pairs is relatively straight forward, and involves visiting each occupied cell of the grid, and comparing all objects in that cell with each other. Fig. 12 has the full algorithm.

The only tricky part of the algorithm is making sure that each pair is only tested once. This is easily done by ensuring that each entity has some way to uniquely identify it, aside from a strict object comparison. The easiest way to manage this in the context of a game engine is to assign an internal number to each entity when it is added to the game world, as shown in Fig. 13.

World.prototype.addEntity = function(entity){
    entity._roId = this.uniq++;
    entity.world = this;
    this.entities.push( entity );
    this.broadPhase.addEntity( entity );
}
    

Once we have unique ids, it’s trivial to track which object pairs have been tested. Each pair forms two keys, A:B and B:A. These keys are then set in an object that functions as a cache. If the keys already exist, then there is no need to test a pair.

hashA = entityA._roId + ':' + entityB._roId;
hashB = entityB._roId + ':' + entityA._roId;

if( !checked[hashA] && !checked[hashB] ){

    // mark this pair as checked
    checked[hashA] = checked[hashB] = true;

    if( this.aabb2DIntersection( entityA, entityB ) ){
        pairs.push( [entityA, entityB] );
    }
}
    

This cache allows the grid to perform well enough even when using a very small cell size. In that case more cache checks will be performed, which are relatively cheap compared to the brute force method that would be required if the cell size were set very large.

Problems

As stated before, inefficiencies can arise under certain conditions:

• Entities that vary greatly in size
• Improperly tuned cell size

The simplicity of spatial grids can often outweigh their limitation of needing to be hand-tuned. When entities are relatively close in size, and their possible bounds are well defined, spatial grids can be an excellent choice. However, in any situation where there are many entities that vary greatly in size (many large entities colliding with many small entities), then the simple grid demonstrated here falls down, devolving into nearly a brute force test.

Future Expansion

There are a few ways to improve this current grid implementation.

One change that is most obvious in practice is the API of the grid itself. In a non-simulation setting, collision queries are usually performed only when needed, and not globally. For example, in your player update logic for a Mario clone, you may want to know if the player is colliding with a powerup. You wouldn’t want all of the various objects that are colliding, only the player and the powerups.

One way around this would be to use different grids for different types of tests. For example, a single grid could be used for the player and powerups, while a second grid could be used for the player vs enemies. Another way is to cache the grand, global collision pairs result, and provide another interface. An example could be isColliding( a, b ), which could then loop through (or use some sort of lookup optimization) the cached result, and return true or false.

Another options may be to reduce the amount of discarded arrays by retaining the grid structure, and actually updating entities’ positions in the structure. While this sounds great in practice, it is actually quite difficult to do in linear time. One would have to maintain a list, for each entity, of its grid locations. During the update phase, each entity would need to be removed from cells it was no longer touching, added to new cells, and also updating its list of grid locations. This adds a lot of complexity to a relatively simple idea.

As an alternative, each entity could be limited to a single cell. Then, at query time, the cells that the entity overlaps could be calculated relatively easily, and all the entities contained within could be tested. The cache of checked pairs would still have to be kept. This would greatly simplify the update phase, while increasing the computational cost of the query phase.

An enterprising developer might be thinking, “What about writing code that manages querying and creating grids for objects of varying size?” Definitely attempt the challenge! But this would greatly complicate querying for collision pairs (you would have to traverse a hierarchy of grids), as well as destroy the simplicity of the grid.

Closing Thoughts

There are few reasons to use brute force instead of a spatial grid. At the worst case, the spatial grid will devolve into the same performance as the brute force, but in the best case be at least 100x faster, usually more.

A situation where a spatial grid would be inappropriate are when memory usage, garbage collection churn, or code size is a concern (such as for a contest). The memory usage of a spatial grid is minimal, but it’s definitely more than the brute force method. The grid is relatively deterministic in its extreme cases, given set variables, such as number of entities, cell size, and grid dimensions.

For example, given a cell size of 15, 100 entities each 10x10, and a grid that is 150x150:

Note that in both cases, if the brute force method were used, there would be 10,000 collision checks.

Hopefully you now have a basic understanding of spatial partitioning in terms of collision detection. If not, please give feedback on what could be improved!