Collision Detection

Every action game asks the same question dozens of times a frame: are these two things touching? The answer decides whether a bullet kills, a player lands on a platform or walks through a wall. The simplest answers treat every object as a rectangle and cost a handful of comparisons. The exact answer compares every pixel and costs far more. Most 8-bit and 16-bit games settled somewhere in between, and on the Commodore 64 and the Atari 8-bit computers the video chip itself would report when pixels overlapped.

This entry covers the methods. For the design of hitboxes, what shape they should be and where they go, see Hitboxes; for collision against a tile map see Tile-based collision.

Bounding boxes

Two rectangles that line up with the screen axes overlap only if they overlap on both axes:

// Axis-aligned bounding box (AABB) test
if (a.x < b.x + b.width &&
    a.x + a.width > b.x &&
    a.y < b.y + b.height &&
    a.y + a.height > b.y)
{
    // Collision
}

Four comparisons, and on an 8-bit processor each is a subtraction or a compare, so this is cheap enough to run for every pair of objects every frame. Its weakness is the empty corners: a round ball in a square box “hits” things it visibly missed. Games usually make the box smaller than the sprite so that near misses count as misses, which players feel as fairness.

A Codebase64 routine for the C64 shows the 6502 version. It builds a box around the player sprite from its position and four size constants, one for each side, then compares the enemy sprite’s coordinates against the box’s edges four times, giving up at the first comparison that fails.

Circles

Two circles overlap if the distance between their centres is less than the sum of their radii. Comparing squared distances avoids a square root:

float dx = a.cx - b.cx;
float dy = a.cy - b.cy;
float radiusSum = a.r + b.r;
if (dx*dx + dy*dy < radiusSum*radiusSum) {
    // Collision
}

The test gives the same answer at any angle, which suits balls and round bullets. It needs multiplication, which the 6502 and Z80 do not have as instructions, so 8-bit programs used a table of squares or a shift-and-add routine.

Pixel-perfect collision

When two boxes overlap, check the pixels in the overlapping area: if any position is solid in both sprites, they have collided. Done as a broad phase (the box test) followed by a narrow phase (the pixel test), it only costs time when objects are already close, but in software it means shifting and masking sprite data to line the two images up. The C64 and Atari video chips did exactly this job in hardware, as the image was drawn.

Hardware collision on the Commodore 64

The VIC-II compares sprite pixels as it draws the screen and records any overlap in two registers, one bit per sprite:

The Programmer’s Reference Guide sets out the rules. The bits stay set until the register is read, and reading clears it, so a program should read each register once and keep the value. Sprite–sprite collisions are detected “even when the sprites are off screen”. In multicolour modes the 01 bit pair counts as background: it “is considered transparent for collisions, even though it shows up on the screen”. The chip can also raise an interrupt on the first collision of each type, through bits 1 and 2 of $D019 and $D01A.

Reading the registers from machine code:

        lda $d01e          ; sprite-sprite collisions (reading clears the register)
        sta sprite_hits
        lda $d01f          ; sprite-background collisions
        sta bg_hits

        lda sprite_hits
        and #%00000010     ; was sprite 1 involved?
        beq no_hit1
        inc $d020          ; stand-in for "handle the hit"
no_hit1

With sprites 0 and 1 overlapping and sprite 2 over the text on screen, this reads %00000011 from $D01E and %00000100 from $D01F; a second read straight afterwards gives zero.

For BASIC programmers the registers were a gift, because checking coordinates in BASIC is slow. Commodore told readers that thanks to the hardware sprites “it is even possible to write a good quality game in BASIC!” Robert Camp’s Creating Arcade Games on the Commodore 64 (1984) taught the registers as V+30 and V+31 and showed how the multicolour rule could be put to work. In a game like Pac-Man, he wrote, you would not want the ghosts to set the collision register “when moving over the dots in the maze”, but you would want them to detect the walls. Draw the dots with only the 00 and 01 bit pairs and the chip ignores them; draw the walls with 10 and 11 and it does not.

In BASIC the test needs brackets. IF (PEEK(V+30) AND 2) = 2 checks sprite 1. Without them, = is worked out before AND, and the test fires when any sprite has collided; see Commodore BASIC V2.

Why many C64 programmers did their own sums

A set bit says that a sprite touched something. It does not say what, or where. Camp noted that the background register “will not tell you which screen character was bumped into”. With two sprite bits set you can guess they hit each other; with three or more you cannot tell who hit whom. And a bit is set only when the chip draws the overlapping pixels, so the answer can arrive up to a frame after the move that caused it.

A Codebase64 article introducing the hardware method talks readers out of it in the same breath: “Unfortunately with most games these days, $D01E is very useless, therefore a software collision is used.” Its companion article draws the line by genre: the register is fine “unless you do something like a simple dodge type of game. Now let us say you were making proper shoot ’em ups, etc, then a software collision would be much better to use.” A software box test tells the program which object hit which, and the box can be smaller or larger than the sprite as the design needs.

Hardware collision on the Atari 8-bit computers

Atari’s CTIA and GTIA video chips went further. De Re Atari (1982) describes a separate bit for each kind of meeting: missile with player, missile with playfield, player with player, and player with playfield. Chadwick’s Mapping the Atari lists the registers:

Each register uses its low four bits, one per playfield colour or player, so a program learns what an object hit as well as that it hit something: a missile that touched playfield colour 2, say, rather than just “a collision”. The registers accumulate until the program writes any value to HITCLR at 53278 ($D01E), which clears them all. Like the VIC-II, the chip sets a bit only as it draws the overlap, and De Re Atari recommends doing the work in the vertical blank: read the collisions first, then clear them, then move the players.

The NES: one sprite, and not for collisions

The NES picture chip has a single collision flag: sprite 0 hit, bit 6 of $2002, set when an opaque pixel of sprite 0 is drawn over an opaque background pixel. It does not detect sprites touching each other, and its main use is timing a split screen rather than gameplay; see PPU. NES games did their collision checks in software, as Spectrum games had to: the Spectrum has no collision hardware at all.

The Amiga: collisions by pairs

On the Amiga the Denise video chip keeps a collision register too. The Amiga Hardware Reference Manual describes CLXDAT ($DFF00E), read-only and “automatically cleared to 0 after it is read”, with fifteen bits for particular pairings: sprite pair against sprite pair, sprites against the odd or even bitplanes, and odd bitplanes against even. A companion register, CLXCON, chooses which bitplanes and which odd-numbered sprites take part. As on the C64, a set bit names the kind of meeting, not the objects’ positions.

Tiles

When the world is a grid of tiles, collision against the world becomes a lookup: turn the object’s position into a tile row and column, read the tile and check its properties (solid, empty, ladder, hazard). On 8-bit machines the conversion is a few shifts when tiles are 8 or 16 pixels wide. See Tile-based collision.

Fast objects and tunnelling

A test that only looks at where objects are now can miss a fast object that moved right through a thin one between frames:

Frame N:    [bullet]       [wall]
Frame N+1:               [bullet]   (passed through!)

Swept collision tests the path instead: it treats the box’s movement from its old position to its new one as a shape and checks that against the obstacle. The cheaper fixes are to limit an object’s speed to less than the thickness of anything it can hit, or to move it in several smaller steps per frame and test after each.

Testing fewer pairs

Checking every object against every other grows with the square of the number of objects. With the handful of sprites an 8-bit game moves, testing every pair is usually affordable, and the common saving is to test only the pairs that matter: player bullets against enemies, enemy bullets against the player. Larger games split the work further:

Common problems

See also

• Hitboxes
• Tile-based collision
• Tile maps
• Sprites
• VIC-II
• PPU
• Commodore Amiga
• Atari 8-bit computers
• Fixed-point maths
• Game loop