Master Baboon

In games and other graphical applications one has to keep track multiple sprites and detect collisions between them. A naif approach would loop over all sprites and check for collision with *every other sprite*. This is, of course, terribly inefficient and can be very slow even for a small number of sprites.

One way out of this nightmare  is to register the sprites in a spatial database that stores them according to their position, and is able to determine which of them is close to a given point. As a result, one only needs to check for collision between neighboring sprites. There are many implementations of spatial databases, some of which are quite sophisticated. In this post I’m going to describe an ActionScript 3 implementation of a grid-based spatial database, that can be used for simple flash games.

Grid: 2D Array with neighborhood

A Grid is a two-dimensional array with a concept of neighborhood. In addition to be able to store and retrieve information on the 2D grid, one can request neighboring elements of a given array element.

For example, let’s create a simple 4×4 grid, and store at each point an increasing number:

1
2
3
4
5
6
7
var grid:Grid = new Grid(4, 4);

var k:int = 1;

for (var i:int = 0; i < 4; i++) {

    for (var j:int = 0; j < 4; j++) {

        grid.set(i, j, k++);

    }

}

This image shows the resulting grid, with small numbers indicating grid coordinates and large, bold ones the stored values:

We can now query the grid to get neighbors of a given position: For example, the following code

1
2
3
4
var neighbors:Array = grid.getNeighbors(1, 1);

trace(neighbors);

neighbors = grid.getNeighbors(1, 3);

trace(neighbors);

displays 1, 2, 3, 5, 7, 9, 10, 11 and 3, 4, 7, 11, 12, respectively, as shown here:

Note that, by default, the neighbors stop at the border. It is possible to work on a “toroidal” grid, meaning that the opposite borders of the grid are connected:

1
2
3
grid.setToroidal(true);

neighbors = grid.getNeighbors(1, 3);

trace(neighbors);

which prints 3,4,1,7,5,11,12,9 .

I added two functions that simplify working with neighbors. The first, mapOnNeighbors(x, y, fct), applies a function fct to all neighbors of (x,y). Let’s  see which of the neighbors of (1,3), are even numbers, just for fun:

1
2
3
function isEven(x:int):Boolean { return (x % 2 == 0); }

var neighborsAreEven:Array = grid.mapOnNeighbors(1, 3, isEven);

trace(neighborsAreEven);

This gives false,true,false,false,false,false,true,false. There are several interesting uses of this method: collecting information from elements in a region of the grid, activating neighboring elements, …

The second function, reduceOnNeighbors(x, y, fct), is a bit more difficult to explain, but equally useful: it returns a single value constructed by iterating over the neighbors of (x,y) and calling fct(a, b) on the first two items of the sequence, then on the result and the next item, and so on. We can use this function to compute the sum of all neighbors:

1
2
3
function sum(x:Number, y:Number):Number { return x + y; }

var sumOfNeighbors:Number = grid.reduceOnNeighbors(1, 1, sum);

trace(sumOfNeighbors);

prints 48 = 1+2+3+5+7+9+10+11 . This function could have been used for example in the previous post in the Cellular Automaton code, to compute the number of alive neighbors for every cell of the CA.

SpatialDatabase

The SpatialDatabase class registers sprites in a Grid with coarser resolution. For example, a Shape at position (31, 23) on the stage would be stored in element (3,2) if the resolution of the grid is 10 pixels.

That’s basically all there is to it! For collision detection, we can query the spatial database for sprites registered at neighboring elements in the grid:

1
2
3
4
5
6
7
8
9
10
// Check collision with shape:Shape

// 1. get neighbors

var neighbors:Array = spatialDatabase.getAllNeighbors(shape.x, shape.y);

// 2. loop over all neighbors and check collision

for each (var s:Shape in neighbors) {

    // check collision

    if (checkCollision(shape, s)) {

        // do something (bounce, explode, ...)

    }

}

A higher resolution gives an optimal performance. Just keep in mind that the grid size should be larger than the size of the largest sprite, otherwise some collisions may go undetected.

There exist much more sophisticated methods to improve the efficiency of collision detection (see for example this post and the excellent tutorial at metanet software). However, this simple grid-based approach can be *very* efficient for many applications!

You can grab the code for the Grid and SpatialData`base classes here (including AsUnit tests for the Grid class). I have a nice example of this class at work, but this post is already long enough, have a look at the next one!