Collision Detection and Spatial Indexes

Andy Korth Scott Lembcke — May 11, 2012

“Ninety percent of your time is spent in ten percent of your code”, as the old adage goes, so choosing the proper algorithms for that 10% of the code in your game can be key. In the realm of collision detection and other game code, a good broadphase algorithm can be vital for many kinds of games to run in real time if they have a lot of moving objects in the game. A lot of game developers treat this as some sort of voodoo that only middleware can provide for them, but this isn’t the case. A good collision detection broadphase algorithm doesn’t need to be difficult or hopelessly complicated. In some cases, writing your own can be very beneficial when you run into performance problems. If you wrote it and know how it works, you can fix it yourself without needing to guess.

Collision detection broadphase:

Determining if two shapes intersect can become very computationally expensive, increasingly so based on their complexity. Why waste this computation time when they might be on completely opposite sides of the screen anyway? Broadphase algorithms, which cheaply return lists of possible collisions, alleviate this problem. They usually make as few comparisons as possible based on simplified bounding volumes (such as axis-aligned bounding boxes) to eliminate obvious non-collisions. Then you can apply the much more expensive collision check on a significantly smaller list of potential collisions. This article will discuss two simple broadphase algorithms, each with different strengths and weaknesses. Collision detection of specific kinds of shapes (polygons, circles, etc) and collision response is beyond the scope of this article, although many other helpful resources in that area can be found online.

The simplest possible broadphase would be to keep a list of all the shapes in your game and check each one against all others. It’s a naive, brute force algorithm, and it won’t scale to large numbers of shapes, but don’t completely discount it. If you only have a couple dozen interactive objects in your game, a simple list will perform just fine and is very, very easy to implement. In an Asteroids-like game, because only asteroids and bullets and asteroids and the ship collide, you can already skip most of the potential collision pairs. A broadphase wouldn’t help your performance much in that case. Until you profile and identify a performance problem, don’t spend time doing something you don’t need. It should generally be easy to plug a broadphase into your API after the fact, once you determine that it is necessary.

Single Axis Sweep

Single axis sweep is a very simple but effective broadphase algorithm. It is very easy to implement and is well suited for many types of 2D games, especially those where most of the action is spread out across a single axis. A horizontally scrolling motorbike game or a vertically scrolling space shooter are particularly good candidates. A similar algorithm called sweep and prune can efficiently operate on full 2D and 3D data, but is more complicated to implement.

Starting at the blue dot, sweep to the right until you hit the blue dotted line. The red dot lies within this range so blue and red may be colliding. Continuing on to the red dot and sweeping right until the red dotted line you find the yellow dot. Yellow and red should be checked for collisions. When sweeping the yellow and green ranges, you find no more dots, so there are no more potential collisions to report.

To implement single axis sweep, axis aligned bounding boxes are computed for each element under consideration, and then sorted by their minimum bound on one of the axes. Now with the sorted list of shapes, the collision detection is just a simple set of for loops.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void
Sweep(List objects, CollisionCallback callback)
{
	// Sort the objects by their minimum bounds on one of the axes
	// Insertion sort is recommended as the list should already be mostly sorted from the last frame.
	SortByXMin(objects);
	
	int count = objects.count;
	for(int i = 0; i < count; i++){
		Object object = objects[i];
		float max = cell.bounds.max;
		
		// 'object' overlaps other objects in the list until 'object[j].aabb.xmin' is greater than 'max'
		for(int j = i+1; objects[j].aabb.xmin < max && j < count; j++){
			// 'object' and 'objects[j]' may be colliding.
			// Use the callback to pass the pair of objects back to the game's code for a better check.
			callback(object, objects[j]);
		}
	}
}

Additionally, because the shapes generally don’t move very far from frame to frame, their sorting order doesn’t change much either, if at all. This is known as temporal coherence, and it can really speed up your collision detection if you can take advantage of it. In the case of single axis sweep, all we need to do is select a sorting algorithm such as insertion sort that performs best on nearly sorted lists.

In the average case when you have smoothly moving objects mostly spread out over a single axis, the algorithm runs in O(n) time when using insertion sort, which is very good. However, if your objects aren’t well spread out, or they don’t move smoothly and their position is unrelated to the previous frame’s position, it runs in O(n^2) time which is no better than the naive brute force algorithm.

Another advantage of single axis sort is that it can be trivially parallelized. This works especially well for implementing a GPGPU accelerated broadphase where it’s better to be simple and wasteful instead of complex. The GPU gives you a massive amount of CPU power for simple parallelizable tasks, but works very poorly when given complex tasks that require a lot of synchronization. This approach has been mentioned in a number of GPGPU papers.

However, an issue that you might run into with single axis sweep is that it can’t efficiently be used for positional queries from your game code. Even with the sorted list, you still need to check against every object in the list for a random query when doing a raycast or an explosion in your game. To perform such queries efficiently, you need a spatial index algorithm. It’s also not optimal when you are comparing a small number of moving objects to a large number of stationary objects. You’ll spend a lot of time resorting the stationary objects even though they never move.

Spatial indexing algorithms:

Spatial indexing algorithms focus on finding objects based on positional queries, much like how a database uses an index to quickly find records based on a search query. To use a spatial index as a collision detection broadphase, you run a query for each object to find the other objects around it. A good spatial index has many uses beyond just collision detection though! AI will frequently query for nearby entities or use raycasts for line of sight checks when making behavioral decisions. One time events such as explosions may occur where you need to efficiently find which objects are within the blast range. Another benefit is that you can split up your moving and stationary objects into separate indexes. The index of stationary objects would only need to be updated when one was aded, moved or destroyed. Compare this to a broadphase which can only give you pairs of colliding objects for one large list.

When working with a spatial index, there are a few core operations. Insertion, removal, querying, and reindexing are the most important. Also when using a spatial index for a broadphase, it’s also useful to combine reindexing and querying for all collisions into one operation. An advantage of this reindex/query operation is that you can make it avoid returning duplicate collision pairs. If shapes A and B are colliding, a query using A’s bounding box will return shapes A and B, and a query using B’s bounding box will also return A and B. The list of collision pairs you get would be (A, A), (A, B), (B, A), and (B, B), but you really only want (A, B). Normally you’d have to filter these out afterwards.

Simple Grids:

Placing your game entities into a grid is a natural and easy way of indexing them. Visualize drawing a grid over your world that maps onto a 2D or 3D array. Each grid cell stores references to shapes if the AABB of the shape intersects the grid cell. Tile maps can be thought of as a simple grid, although they usually have a single tile per grid cell. In general though, you can have many shapes overlapping a single grid cell, and a single shape can overlap many grid cells. While there are a lot of variations to grid algorithms, we’ll walk through one simple and flexible implementation.

In a game that takes place on a single screen or on a fixed size map, your grid size matches the size of your world. The size of the cells within the grid should match the size of the objects in your game. The broadphase search becomes quite simple, since you’re just checking each cell for multiple objects.

With a grid, you store lists of overlapping shapes into each cell. The purple and orange grid cells show places where multiple shapes have been inserted into a cell. The shapes in these cells may be colliding and should be checked closer.

Time for some pseudo code! First the simple data structure for the grid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
SimpleGrid {
	// 2D array of lists. Each is a list of proxies.
	// I prefer to use a linked list here like in a chained hash table.
	List[][] array;
	
	// Width and height of the array.
	int width;
	int height;
	
	// Size of the grid cells.
	float cellSize;
	
	// Hashtable of proxies so you can look them up by object.
	HashTable objectsProxies;
}

Instead of storing references to the objects directly in the grid’s array, we’ll be creating proxies. We’ll perform simple retain counting on these (in non GC languages) and keep a stamp to avoid duplicate results when querying. The reason for this will be explained later.

1
2
3
4
5
6
7
8
9
10
GridProxy {
	// The object this proxy is for.
	Object object;
	
	// Used during query operations to avoid duplicate results.
	int queryStamp;
	
	// Use retain counting on the handle so you know when it can be released.
	int retainCount;
}

Let’s start with the code for the insert operation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void SimpleGrid_Insert(SimpleGrid grid, Object object)
{
	AABB aabb = object.aabb;
	GridProxy proxy = GridProxyNew(object);
	HashTableSet(grid.objectsProxies, object, proxy);
	
	// Convert the object's AABB to integer grid coordinates.
	// Objects outside of the grid are clamped to the edge.
	float cellSize = grid.cellSize;
	int xmin = max(floor(aabb.xmin/cellSize), 0.0);
	int xmax = min(floor(aabb.xmax/cellSize), grid.width - 1);
	int ymin = max(floor(aabb.ymin/cellSize), 0.0);
	int ymax = min(floor(aabb.ymax/cellSize), grid.height - 1);
	
	// Loop over the cells and insert the proxy into their lists.
	for(int y = ymin; y <= ymax; y++){
		for(int x = xmin; x <= xmax; x++){
			List proxiesInCell = grid.array[x][y];
			List_Append(proxiesInCell, proxy);
			
			// Retain the proxy for each cell it's inserted into.
			GridProxyRetain(proxy);
		}
	}
}

Removal from a grid can be tricky, since an object can be in several grid cells. There are several approaches, such as iterating over all the grid cells and removing the object from each one it’s present in. Fortunately, with the proxies removal becomes very simple. All you need to do is to invalidate the proxy by setting it’s object to NULL. Don’t forget to release the proxy as well so the next time the grid is reindexed so it won’t be leaked.

1
2
3
4
5
6
7
8
9
10
void SimpleGrid_Remove(SimpleGrid grid, Object object)
{
	GridProxy proxy = HashTableGet(grid.objectsProxies, object);
	HashTableRemove(grid.objectsProxies, object);
	
	// Set the object to NULL to mark the proxy as invalid.
	proxy.object = NULL;
	
	GridProxyRelease(proxy);
}

While there are a number of queries that you might want to implement (point, line, AABB, etc) the AABB query is good starting place. Much of it should look familiar from the SimpleGrid_Insert() function. The first thing you should do is to increment the grid’s query stamp. This is used to uniquely identify the query. All proxies that are visited get marked with this stamp value. It’s very likely that you’ll encounter a proxy several times in the neighboring cells. This way you know to only report each object once for each query.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void SimpleGrid_AABBQuery(SimpleGrid grid, AABB aabb, Function callback)
{
	// Increment the grid's queryStamp so it's unique.
	grid.queryStamp++;
	
	// Convert the object's AABB to integer grid coordinates.
	float cellSize = grid.cellSize;
	int xmin = max(floor(aabb.xmin/cellSize), 0.0);
	int xmax = min(floor(aabb.xmax/cellSize), grid.width - 1);
	int ymin = max(floor(aabb.ymin/cellSize), 0.0);
	int ymax = min(floor(aabb.ymax/cellSize), grid.height - 1);
	
	for(int y = ymin; y <= ymax; y++){
		for(int x = xmin; x <= xmax; x++){
			List proxiesInCell = grid.array[x][y];
			
			for(GridProxy proxy in proxiesInCell){
				Object object = proxy.object;
				
				// Check that the proxy hasn't already been processed by this query in a neighboring cell.
				// Also check that the proxy's object hasn't been removed.
				if(proxy.queryStamp != hash.queryStamp && object != NULL){
					// Stamp the proxy so it won't been visited again.
					proxy.queryStamp = grid.queryStamp;
					callback(object);
				}
			}
		}
	}
}

Reindexing a grid basically involves temporarily removing all of the objects, clearing the grid, and then reinserting the objects. A good first optimization is to reuse the proxy objects. This was ommitted to keep the sample code short however.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void SimpleGrid_Reindex(SimpleGrid grid)
{
	List objects = HastTableKeys(objects);
	
	// Remove all the objects. We'll readd them later.
	for(Object object in objects){
		SimpleGrid_Remove(grid, object)
	}
	
	// Clear out all the cells
	// This gets slower the bigger your grid is.
	for(int y = 0; y < grid.height; y++){
		for(int x = 0; x <= grid.width; x++){
			List proxiesInCell = grid.array[x][y];
			for(GridProxy proxy in proxiesInCell){
				GridProxy_Release(proxy);
			}
			
			// Reset the list for that cell
			grid.array[x][y] = EmptyList;
		}
	}
	
	// Readd the objects.
	for(Object object in objects){
		SimpleGrid_Insert(grid, object);
	}
}

Lastly, it was mentioned that a reindex/query operation is useful. This is easy enough to implement by performing a query immediately before inserting each object during the reindexing operation. This way you’ll never have an object get itself back from querying it’s own bounding box. Also, because the objects are inserted and queried incrementally, you won’t get both an (A, B) and (B, A) collision pair. You can even combine the insert and query operations together to avoid iterating the same grid cells separately for each.

An advantage of a grid based index is the ease of efficiently running queries. Point queries simply need to check the cell that contains that point, and a raycast implementation only needs to check grid cells the ray travels though, much like Bresenham’s line drawing algorithm. Unlike the single axis sweep, the grid is a full spatial index that can be efficiently queried by the rest of the game code.

Grids do have a couple problems though. Large worlds require a large grid and thus a large 2D or 3D array to store it. This introduces some potential problems with memory usage. Infinitely sized procedural worlds are increasingly popular, and raises the question about what you’d do when your grid’s array size gets unreasonably large. Additionally, a simple grid can be wasteful since they often end up being almost entirely empty. At a minimum, empty grid cells still use at least as much memory as a pointer. Imagine a 1000×1000 grid with 5000 objects inserted into it. If each object was inserted into 4 cells each, you would at most be using 2% of the cells. Fortunately, these concerns are addressed by the spatial hash algorithm.

Spatial Hash:

Spatial hashes are special type of the grid index that uses memory more efficiently. Instead of creating a large multidimensional array, you create a small 1D array, and then semi-randomly map the grid cells onto that array using a hashing function. This has a lot of benefits. You no longer need to think about grid bounds or size. Any grid cell can be mapped onto the hash table, limited only by the size of your integer type. Sparsely populated grids won’t eat up your memory either. If the array is mostly empty, you can just make it smaller. This is also good for when you want to clear the grid as a smaller array can be cleared faster.

There are a couple of minor downsides however. Because many grid cells can be mapped onto the same array location, it’s possible for two objects that are far away to be returned as a false positive by the spatial hash. However this is fairly rare and can be quickly rejected by a bounding box check. Another issue is that it’s possible for a single object to be inserted into the same array index more than once from two separate grid cells. You’ll either need to catch this condition, or make sure that you never assume that the list for a cell contains all unique entries.

What makes a good hashing function? A poor hashing function could result in an uneven distribution of objects into the array, negating some of the benefits. On the other hand, the hashing function may easily be called hundreds of thousands of times per second, so it should be fairly efficient. In Chipmunk, I use the following hash function in conjunction with prime sized hash tables. This has proven to provide a reasonable level of performance.

1
2
3
4
5
int HashFunc(int x, int y, int tableSize){
	// multiplying the coordinates by large primes, XORing them together and then
	// modding by a prime table size makes a pretty good hash function
	return (x*1640531513 ^ y*2654435789) % tableSize;
}

Implementing the insert, delete, query, and reindex operations for a spatial hash are almost identical to a spatial hash. You can remove the min/max clamping when calculating the grid coordinates as they are no longer needed to protect against array indexing errors. Instead of accessing the grid’s array as a 2D array, you just need to swap in the hash function.

1
2
3
4
5
6
for(int y = ymin; y <= ymax; y++){
	for(int x = xmin; x <= xmax; x++){
		List proxiesInCell = grid.array[HashFunc(x, y, grid.arraySize)];
		// ...
	}
}

The efficency of the spatial hash and simple grid depends on the grid cell size roughly matching the sizes of the shapes being put into it. If your grid cells are much smaller than your objects, each object will be in a handful of cells, so you’ll be checking and inserting into a lot more cells than you need to. If your grid cells much larger than your objects, you might end up with a lot of non-colliding objects in a single cell generating a lot of false-positives. Adjust your grid size to be comparable to the size of typical objects. For this reason, grids work best when all your objects are roughly the same size.

The grid cell size is much too big. Too many shapes are inserted into each cell, and each cell requires n^2 collision checks. The grid cells are the grey squares; A darker color means there are more shapes in a cell.

This grid cell size is much too small. Each shape is inserted into many grid cells. Notice the speckles between shapes. These are grid cells that map to the same hash table index as another grid cell where a shape was inserted.

The size of the grid cells is just right.

Spatial hashes require an additional tuning parameter compared to a simple grid, the hash table size. When working with a grid, you simply need to worry about making it’s dimensions big enough to fit all your objects in it and and then tuning the cell size. With a spatial hash, you also must tune the size of the hash table itself. If the hash table size is too small, you will get many false positives because too many grid cells that are far away from each other will map onto the same hash table index. If the hash table size is too big, you’ll just be wasting memory and making clearing operations take longer. You’ll have to tune this by hand a little, but a good rule of thumb is that your hash table should be 10x bigger than the number of objects you insert into it.

When simple grids and spatial hashes are properly tuned, they also have an O(n) running time to all the collisions. This is very good and means that they scale very well to huge numbers objects. You could easily expect to collide 10k to 20k shapes at 60 hz on a modern desktop CPU. Despite the linear running time, because of the number of memory operations grids and spatial hashes use to access each grid cell, they have a high constant cost associated with them. For smaller numbers of shapes, or shapes that aren’t the all about the same size, there may be more optimal spatial indexes.

Conclusion:

So now that you’ve seen that spatial index and collision detection broadphase algorithms don’t have to be hard, I hope you’ll try writing some of your own! It’s a very interesting topic with a wide variety of ideas that has filled many books. If you are interested in learning more, bounding volume hierarchies such as quadtrees, k-d trees, and axis aligned bounding box trees are a good next step.


Scott Lembcke and Andy Korth have been developing games for the last four years. Scott wrote the Chipmunk Physics engine, and together they have offered game physics consulting services, iOS development, and Unity development services. They are located in Minnesota, USA.

References:

Optimized Spatial Hashing for Collision Detection of Deformable Objects