table of contents

SECTION 0: General Introduction

The previous tutorial examined how “narrow-phase” collision detection works in N; given two shapes (a dynamic AABB or circle, and a static tile), we learned how to project the dynamic object out of the tile.

This tutorial deals with “broad-phase” collision detection: given a dynamic object in a world full of tiles, how do we know which objects and tiles it should be tested with during the narrow phase? The solution used in N was to split the world into a uniform grid of square “cells”; instead of testing the dynamic object against all the tiles in the world, we only need to test against the tiles contained in the cells which are touching the dynamic object.

The one problem with our approach is that all dynamic objects must be smaller than a grid cell; while this limitation can be circumvented (for instance, by representing a single large object as multiple smaller objects), in actionscript, it really helps keep things running fast. Thus, it was a self-imposed design constraint.

Grids tend to work best when all game objects are of roughly the same size and the game world is relatively small; an NxN grid requires N^2 cells, so for larger worlds the memory requirements might be prohibitive. More complex structures which are used to partition game worlds, such as quadtrees or multi-resolution grids, save memory and/or make it easier to support objects of vastly different size.

[ back to table of contents ]

SECTION 1: Basic Tile Grid

The first use of the grid was to store the tilemap data which defines the “solid” parts of the world; since tile-based games use a grid of tiles, a grid seemed like a good fit ;)

The grid itself is simply a 2D array; each entry in the array is a cell object. In N, each cell is occupied by a single tile-shape.

The first thing we’d like to be able to do is to determine, given a position, which cell contains this position. This is easily done:

          grid_column = Math.floor(pos.x / cell_width);
          grid_row = Math.floor(pos.y / cell_height);
        

Now we can easily determine which cell contains our dynamic object’s center; we call this cell the current cell of the object. Since we’ve restricted the object’s size to less than the size of a cell, we know that the object can only overlap at most 4 cells.

Figure 0. The Cells Touched by an Object

We can safely assume that the object will, at most, be overlapping the current cell, a horizontal neighbor of the current cell, a vertical neighbor of the current cell, and a diagonal neighbor of the current cell; the diagonal neighbor is also a neighbor of the horiz/vert. neighbors.

Determining which cells an object overlaps can be done is various ways:

. you can simply use 4 position-lookups (one for each of the object’s corners).
. you can use one position lookup (with the object’s center) to determine the current cell’s index in the 2D grid, and then use offsets from this index based on the object’s position relative to the current cell’s position (i.e. if the object’s center is left and below the current cell’s center, and the current cell’s index is [i][j], we know we have to look at the left, down, and left-down neighbors, or [i-1][j], [i][j+1], [i-1][j+1]).

We can run into problems if part of the object is outside of the boundary of the grid; this results in the above methods generating cell indices which don’t exist.

This can be avoided by using min/max to keep the indices within the limits of the grid, or by using modulo to “wrap” the indices to the other side of the grid.

A much simpler solution is to pad the outside edges of the grid with “border” cells, which can’t be occupied by an object; this prevents objects from leaving the boundary of the grid.

–= collision vs. a tilemap using the grid =–

Now that we know the 4 cells touched by our dynamic object, we need to collide the object against the tiles contained in those cells. The actual collision process is described in the first tutorial.

Each cell in the grid stores tile information describing the tile contained in that cell. this includes a flag indicating the shape of the tile, as well as any tile-specific properties needed by the collision routines (i.e. x-width, center position, surface normal).

To implement this, you can define a set of tile objects; each tile is responsible for generating collision results between itself and a dynamic object:

          tile.Collide_Circle(myCircle)
        

Or, you can use a simpler c-like approach where both the tile and the object are simply containers of data, and collision functions are stored in a 2D hash-list of collision functions; the shape-flags of the objects being collided are used as hash keys to select the appropriate function:

          Collide[tile.shape][myObj.shape](tile, myObj)
        

[ back to table of contents ]

SECTION 2: Advanced Tile Grid

–= grid improvements =–

Now that we have a simple grid in place for use with object-vs.-tilemap collision, there are certain things we could do to make it more efficient.

The first thing is to store, in each cell, direct references to that cell’s 4 neighbors. This way, once we’ve determined an object’s current cell, we can access the neighboring cells using a single property lookup; this results in a smaller number of calculations when accessing neighboring cells but causes each cell to occupy more memory. Since the cost of calculating cell indices is likely to be negligible in many programming environments, this trade-off might not always be worthwhile.

In N we implemented these neighbor “pointers” separately:

          cell.nR //right, left, up, down neighbors
          cell.nL
          cell.nU
          cell.nD
        

–= edge info =–

One major enhancement we made to our grid is to store information, not only about each cell, but about each of the cell’s 4 edges. This idea was borrowed from an article in Game Programming Gems 3 [Forsyth] which mentioned that the game X-Com used a similar structure.

The edge data we stored was very minimal; a single flag which indicates the state of the edge:

. empty: neither of the cells which share this edge contains a solid tile shape
. solid: each tile shape has at least one edge which matches a grid edge perfectly; these edges were labeled solid.
. interesting: edges which were adjacent to a cell containing a solid tile shape, but which didn’t match the shape perfectly were labeled “interesting”, indicating that we needed to perform further collision tests. For instance, the two edges on the outside of a triangle’s hypotenuse are “interesting”.

Once each tile has been assigned a set of edge states, we then need to compare the edge states of neighboring tiles; any edge at which both tiles have solid edge states should be considered empty, as such a configuration only exists below the surface of the world. Such a change will have no impact on the correctness of the collision results, since objects should only collide with the world’s surface.

Figure 1. The 9 Tile Shapes Used in N, and their Corresponding Edge States
Solid edges are highlighted in red and interesting edges in grey.

Having this edge info let us skip a lot of tile-specific collision routines; if an object overlaps a solid edge (which is very common in tile-based games), we simply project it out of that edge instead of having to resort to a more complex object-vs.-tile collision test. Since the only edges which were labeled “solid” are those which perfectly match the shape of a tile, the result is the same as if we had used an object-vs.-tile test, but it’s much simpler to compute. The only time we have to resort to tile-specific collision routines is when an object touches an “interesting” edge.

This edge information can be considered a coarse approximation of the surface of the world described by the tilemap; this is sometimes useful since a normal tilemap doesn’t contain any explicit surface information, and knowing the surface of the world is often useful — for instance to allow enemies to move along the world’s surface.

Figure 2. An Example Tile Map Containing Chunks of Contiguous Tiles and their Edge States
Solid edges are highlighted in red and interesting edges in grey.
Note that the non-empty edges form a perimeter around each chunk which approximates the chunk’s surface.

Having this extra edge info for each cell may or may not be useful in your game.

In N, doors were easily implemented as objects which changed the value of a cell’s edge states. This was a pleasant side-effect of using edges. Additionally, the enemy AI uses edge states for pathfinding; this lets enemies respond to doors, and follow the (approximate) surface of the world. Our ray-queries were also sped up by using this edge info.

Unfortunately, the state of each edge is determined by the state of the two cells adjacent to it; the logic we implemented to correctly setup the edges was complex and quite prone to bugs, since we had to consider each possible combination of cell states. A simpler method to setup/define edge states probably exists; please let us know if you come up with anything.

[ back to table of contents ]

SECTION 3: Object Grid

The grid structure described above can also double as a spatial database used to manage dynamic objects.

Just as each cell contains information about the tile located in that cell, it can also contain information about each dynamic object currently located in the cell. Each cell contains a list of dynamic objects; as an object moves through the grid, we insert/remove it from each cell’s list as appropriate.

There are two approaches that can be taken when using a grid with dynamic objects:

“normal” grid: each object is associated with all of the cells it touches. In our case, this would be from 1 to 4 cells. Every time the object moves, it’s removed from the cells which it used to touch, and inserted into the cells which it now touches. When we collide an object, we only need to test it against the contents of any cell it touches.

. pros: each object needs to look in at most 4 cells to find other objects it might collide with
. cons: each object needs to be inserted/removed from up to 4 cells every time it moves; also, additional logic needs to be added to the collision code to deal with a case where, for instance, two objects touch the same two cells. Since we only want to test that pair of objects once, we’d have to add a “tested” flag or similar code to deal with this.

“loose” grid: each object is placed in a single cell: that which contains its centre. When an object moves, it’s removed from that (single) cell and inserted into the cell which contains its new position. When testing for collision, we have to check not only the current cell, but the 8 cells neighboring the current cell. The idea of a “loose” grid can be a bit confusing until it clicks, at which point everything will make perfect sense. You can find more details here: [Ulrich]

. pros: each object needs to be inserted/removed from only 1 cell when it moves.
. cons: each object always needs to look in 9 cells to find other objects it might collide with

We chose to use a loose grid in N because it simplified handling moving objects; however, most of the ideas mentioned in this tutorial apply to any kind of grid.

Each cell in our grid stores a double-linked-list of references to objects; the objects in a cell’s list are those whose centers are contained in the cell. (If you’re not familiar with linked-lists, googling “linked list” is probably a good way to learn about them.)

In our implementation, each cell has:

.next   //the head of the linked list
.prev   //always equal to null since .next is the first list entry

and each object has:

.cell    //reference to the cell in which it’s contained
.prev   //reference to the object before this object in .cell’s linked list
.next   //reference to the object after this object in .cell’s linked list

Whenever an object moves, its position in the grid is updated and changes to the linked lists are made as appropriate.

–= more details =–

There are two ways to approach broad-phase collision. One is to let each object query the world to find other objects it might be colliding with. Another is for a manager to find all possible collisions, and notify the objects involved.

In N, we used the first method because it allowed a very simple design: only the ninja queries for collision, and the other objects are notified if the ninja’s query results in a collision event. While this is good from the point of view of execution speed, it also limits possible designs. For instance, enemies can’t react to each other (as in Super Mario Bros., where goombas which walk into each other change direction).

So, each frame the ninja tests its current cell and the 8 neighboring cells for objects; it tests for collision against any objects found.

A more general, elegant system, which is useful in simulation-type environments where all objects must collide with each other, is to iterate over all moving objects, and test them against:

. any objects after them in the current cell’s list
. any objects in the lists of 4 cells which neighbor the current cell. You can use any contiguous set of 4 cells, for instance, [right, right-down, down, left-down], [up, up-left, left, left-down], etc.

It might seem like this technique will miss some collisions, but if you work it out on paper you’ll see that every possible collision between objects is found. This lets us reduce the number of per-object cell-list tests to 5 (from 9), without resorting to flags or any other awkward solution.

Collision detection in any game is very specific to the game’s design; usually you can achieve significant increases in efficiency by simply choosing good rules for your game world. For instance, in a game such as Soldat where there are many moving objects, most of which are bullets, a very good idea is to decide that bullets should not collide against other bullets.

This means that bullets don’t have to be moved in the grid every time they change positions — instead of being in the grid, they simply read from the grid to determine which objects they might collide with. This saves the cost of numerous linked-list insertion/removals; the tradeoff is that you can’t stop your opponent’s bullets with your own.

[ back to table of contents ]

SECTION 4: Raycasting

Aside from projection/collision queries, games often also need other types of queries; objects can invoke these queries when they need to know something about the world.

A good example of such a query is a raycast; a ray is simply a line with only one endpoint. Rays can be used to determine if two objects can “see” each other, or can model a fast-moving projectile — for instance, in Quake, many weapons (such as the railgun) are modeled as rays.

We might want to know the first thing that the ray intersects (by first we mean the intersection point closest to the ray’s origin); or, given two points we might want to know if the line which connects those two points intersects anything.

In N, we use raycasts to determine AI visibility, as well as for some of the weapons.
Colliding the ray against the world requires the two (hopefully now familiar) steps:

. broad phase: determine which things (tiles and objects) the ray might collide with
. narrow phase: test the ray against each thing to determine collision information, such as the point of intersection

–= broad phase =–

In our grid-based system, the broad phase amounts to determining which cells the ray touches; anything not contained in this set of cells can’t possibly touch the ray. (NOTE: since we use a loose grid for our objects, this isn’t strictly true; see below for more details)

A naive approach to determining which cells the ray touches might be to calculate the AABB containing the ray, and consider all cells touching this AABB as touching the ray. While this works well for short rays, or rays which are almost vertical or horizontal, it requires testing up to n^2 cells, which will get very slow very fast.

A better solution would be to determine EXACTLY which cells the ray touches; a great (and quite simple) algorithm to do this is described in [Amanatides] and [Bikker]; basically, it lets us step along the ray, visiting each cell the ray touches in the order it is touched by the ray.

For N, we simply implemented this algorithm; at each cell we test the ray against the cell contents, using our narrow-phase routines.

–= narrow phase: vs. tiles =–

Not only does the above ray-traversal algorithm tell us which cells the ray touches, it also allows us to efficiently calculate the points at which the ray enters and exists each cell — i.e. the points at which the ray crosses the edges of the grid. This is very useful because, since our grid stores edge info, we can stop as soon as the ray crosses over a solid edge — we know that this is an intersection without having to perform any special ray-vs.-tile intersection test.

If the ray crosses an interesting edge, we need to test the ray against the cell’s tile shape using a tile shape-specific test. Most of the tests we used were implemented as ray-vs.-line or ray-vs.-line-segment tests, based on the following sources: Geometry Algorithms and [O’Rourke]. For the circular shapes, we adapted a swept-circle test [Gomez].

–= narrow phase: vs. objects =–

One major problem with using a loose grid is that objects which aren’t contained in the cells touched by a ray might still touch the ray.

Figure 4. The Cells Touched by a Ray
Note that even though an object isn’t contained in a cell touched by the ray, it may still intersect the ray.

In N, this was a problem we could ignore — since the ninja was the only object which rays needed to be tested against, we simply performed a ray-vs.-tiles test to find the point at which the ray hits the tiles, and then we performed a ray-vs.-circle test against the ninja to see if the ray hit the ninja before hitting the tiles.

If intersecting rays with dynamic objects is an important feature of your game, you might be better off using a regular / non-loose grid, which doesn’t suffer from this problem.

[ back to table of contents ]

SECTION 5: Conclusion / Source Code

WORKS CITED

Amanatides, John. A Fast Voxel Traversal Algorithm for Ray Tracing ( mirror ).

Bikker, Jacco. Raytracing Topics & Techniques – Part 4: Spatial Subdivision ( archived ).

Forsyth, Tom. Cellular Automata for Physical Modelling ( mirror,  full book ).

Gomez, Miguel. Simple Intersection Tests for Games ( archived ).

O’Rourke, Joseph. Computational Geometry in C ( archived,  full book ).

Simpson, Zachary. Design Patterns for Computer Games

Ulrich, Thatcher. Spatial Partitioning with Loose Octrees ( mirror,  archived ).

[ back to table of contents ]