Tile-Based Collision

A platform game’s level can hold hundreds of walls, floors and ledges. Testing the player against each of them every frame would swamp an 8-bit processor. A tile-based game does not have to. Its world is already a grid of small numbered pictures, the tile map, so the question “am I touching a wall?” becomes “which cells does my body cover, and what is in them?” Dividing a pixel position by the tile size gives a cell; reading the map gives a tile number; a small table says what that number means. The cost is the same whether the level has three platforms or three hundred.

The screen was the first map

Home computer programmers met the idea in BASIC, where the screen itself served as the map. The partwork INPUT explained it in an article called “Detecting things on screen”: checking a moving ball against a curved object with IF … THEN tests on coordinates would need so many checks that “the movement on the screen would appear jerky”. Instead, each machine could be asked what was already in a character square. The Spectrum’s ATTR (y,x) returned the square’s colour attributes, the Commodore 64 gave its colour code with a PEEK of colour memory, and the Acorn, Dragon and Tandy machines had POINT or PPOINT. INPUT’s Spectrum demonstration bounced a ball round a screen of yellow squares, testing ATTR of the square the ball was about to move into and turning it round when the answer was 48, yellow paper.

Assembly-language games on the Commodore 64 kept the idea and read the screen’s character codes directly. A programmer called Achim sets out the routine on the Codebase64 wiki. Take the sprite’s X position, subtract $18 because “visible screen area starts at x=$18”, and shift right three times to divide by 8; do the same with Y and $32; look up the screen row’s address in a table; read the character code at that column. “The result is the top left screen position of the sprite.” The neighbouring cells are the same address plus 1 and 2 for the columns to the right, and plus 40 and 80 for the rows below.

The C64 also offered hardware help. The Commodore 64 Programmer’s Reference Guide describes a sprite-to-data collision register at 53279 ($D01F): one bit per sprite, set when the sprite overlaps background graphics and held “until read (PEEKed)”. The guide’s advice reads like a tile-design rule: in multicolour mode, colour pair 01 “is considered transparent for collisions”, so “it is a good idea to make everything that should not cause a collision 01”. The register reports that a sprite touched something, but not what or where, so a game that needs to know whether it hit a floor, a ladder or a spike still has to look at the map.

Reading the map

The routines below are 6502 assembly in ca65 syntax. They assume a map 32 tiles wide and 24 high, one byte per cell, with 8×8-pixel tiles. That keeps every pixel coordinate in one byte (32 × 8 = 256); a 40-column C64 screen is 320 pixels wide and needs a second byte for X.

Multiplying the row by the map width on every lookup is slow on a 6502, and a 768-byte map does not fit in an 8-bit index. A table of row addresses, worked out by the assembler, avoids both problems. A second table gives each tile number a collision class, so the graphics can use any tile numbers they like.

MAP_W         = 32
MAP_H         = 24
TILE_EMPTY    = 0     ; passable
TILE_SOLID    = 1     ; blocks from every side
TILE_PLATFORM = 2     ; holds only from above
TILE_LADDER   = 3
TILE_HAZARD   = 4

; Collision class of the map cell under pixel (check_x, check_y).
; check_y must be below 192. Returns the class in A. Uses A and Y.
get_tile_at_point:
        lda check_y
        lsr
        lsr
        lsr             ; row = y / 8
        tay
        lda row_lo,y
        sta ptr         ; ptr is a two-byte zero-page pointer
        lda row_hi,y
        sta ptr+1
        lda check_x
        lsr
        lsr
        lsr             ; column = x / 8
        tay
        lda (ptr),y     ; the tile number in the map
        tay
        lda tile_type,y ; its class, from a 256-byte table
        rts

row_lo:
.repeat MAP_H, i
        .byte <(map_data + i * MAP_W)
.endrep
row_hi:
.repeat MAP_H, i
        .byte >(map_data + i * MAP_W)
.endrep

Which points to test

The player below is 16×16 pixels. An edge 16 pixels long can lie across three rows of 8-pixel tiles, so testing only the two corners would miss a single solid tile level with the middle of the body. Testing three points along an edge, at 0, 8 and 15 pixels, covers every tile it can touch, because no two neighbouring points are more than one tile apart.

edge_offsets:
        .byte 0, 8, 15

; Is any point (check_x, player_y + 0, 8 or 15) solid?
; Carry set if so. Uses A, X and Y.
test_column:
        ldx #2
@loop:  lda player_y
        clc
        adc edge_offsets,x
        sta check_y
        jsr get_tile_at_point
        cmp #TILE_SOLID
        beq @hit
        dex
        bpl @loop
        clc
        rts
@hit:   sec
        rts

Walls

Move the player first, then test the edge that is leading. If it has gone into a solid tile, push the player back to the tile boundary. Because the player is 16 pixels wide, a multiple of the tile size, clearing the bottom three bits of X lines its right-hand edge up with the last pixel before the wall. These routines assume a speed of under 8 pixels a frame, so a move can never jump right over a tile.

; Call after adding velocity_x to player_x.
check_walls:
        lda velocity_x
        bmi check_left
        beq done
        lda player_x    ; moving right: test the right-hand edge
        clc
        adc #15
        sta check_x
        jsr test_column
        bcc done
        lda player_x    ; back to the boundary
        and #$f8
        sta player_x
        lda #0
        sta velocity_x
done:   rts

check_left:
        lda player_x    ; moving left: test the left-hand edge
        sta check_x
        jsr test_column
        bcc done
        lda player_x    ; forward to the first pixel of the next tile
        and #$f8
        clc
        adc #8
        sta player_x
        lda #0
        sta velocity_x
        rts

Floors and one-way platforms

The floor test looks one pixel below the feet, at player_y + 16, across the same three points. A ledge that holds only from above needs one more fact: where the player was before this frame’s move. If the feet were already below the top of the platform, the player is jumping up through it and should pass.

; Call after adding velocity_y to player_y; old_y is player_y before the move.
check_floor:
        lda velocity_y
        bmi in_air      ; going up: no floor
        lda player_y
        clc
        adc #16         ; the row just below the feet
        sta check_y
        jsr test_row
        bcc in_air
        lda player_y    ; stand on top of the tile
        and #$f8
        sta player_y
        lda #0
        sta velocity_y
        sta is_falling
        rts
in_air: lda #1
        sta is_falling
        rts

; Is any point (player_x + 0, 8 or 15, check_y) a floor? Carry set if so.
test_row:
        ldx #2
@loop:  lda player_x
        clc
        adc edge_offsets,x
        sta check_x
        jsr get_tile_at_point
        cmp #TILE_SOLID
        beq @hit
        cmp #TILE_PLATFORM
        bne @next
        jsr platform_holds
        bcs @hit
@next:  dex
        bpl @loop
        clc
        rts
@hit:   sec
        rts

; A platform holds if the feet were at or above its top before the move.
platform_holds:
        lda check_y
        and #$f8        ; the platform's top pixel row
        sec
        sbc old_y
        bcc @pass       ; the head was already below it
        cmp #16         ; carry set if the feet were above the top
        rts
@pass:  clc
        rts

Snapping player_y down to a multiple of 8 works for the same reason as the walls: the player is two tiles tall, so the feet then sit on the last pixel row above the tile that holds them.

Slopes

A slope tile carries a height for each of its eight pixel columns: how far down from the top of the tile the surface lies. Test the column under the middle of the player, and if the feet have sunk below the surface, lift them onto it.

slope_up:
        .byte 7, 6, 5, 4, 3, 2, 1, 0    ; rises to the right

; check_x = player_x + 8 (the middle), check_y = player_y + 15 (the feet),
; and get_tile_at_point has said the tile there is this slope.
on_slope:
        lda check_x
        and #7
        tax             ; pixel column within the tile
        lda check_y
        and #$f8        ; the tile's top row
        clc
        adc slope_up,x  ; the surface in this column
        sec
        sbc #15         ; the player_y that puts the feet there
        cmp player_y
        bcs @done       ; feet on or above the surface
        sta player_y
@done:  rts

Doing less work

Most frames a player moves a pixel or two and touches no new tiles. Only the leading edge can enter a new one, so a game can compare that edge’s tile column before and after the move and skip the lookups when it has not changed. Comparing the player’s top-left tile is not enough: the left edge can stay in one tile while the right edge crosses into the next.

The C64 in practice: screen or world?

Reading the screen is fast, but it only knows what is on screen. Lasse Öörni, who writes C64 games as Cadaver, wrote about the consequences in an article on scrolling game worlds. He credits some of what he knew to Jukka Tapanimäki’s Finnish book C-64 Pelintekijän Opas (“C-64 Game Maker’s Guide”). He points to the “walker” enemies in Turrican, which “sometimes behave very erratically” near the edges of the screen. In his reading they check “only the characters on screen for background collisions”, and when a check falls outside the screen the routine “probably has a hardcoded response of either ‘obstacle’ or ‘free space’”: “fast, but honestly, incorrect”. For serious scrolling games he recommends world coordinates for every object and checking the map and block data instead.

His own games show the trade-off. Metal Warrior 1 and 2 measured positions in pixels from the top-left of the map, as 16-bit values; “the background collisions were slow and complicated and there was a complete lack of subpixel accuracy, making all accelerating movement look rough”. Metal Warrior 3 and BOFH changed the coordinates themselves. The high byte became the position in blocks of 4×4 characters, the low byte the position within the block. A block is 32 pixels wide, which leaves three spare bits of the low byte for movement finer than a pixel, and “background collision checking becomes very fast & easy to do, because the map position is directly the coordinate highbyte”. The cost moved elsewhere: drawing sprites and testing sprite against sprite now needed some bit shifts to throw the extra precision away.

See also

• Tile Maps: the grid the lookups read
• Tile-Based Graphics
• Screen Memory
• Fixed-Point Maths
• State Machine