The Quest for the Fast Collision Check

(Whenever you see text with colored background you can hover mouse over it to get some extra information.)

Original Paradroid uses VIC-II sprite-sprite collision register to check for collisions. Anyone who's tried using it knows that there is one major problem: there is no way knowing which sprites collided with which one if there are more than two sprites involved.

Andrew Braybrook tried to work around this by using collision interrupt to register the topmost collision, ignoring all others. This means ignoring a lot of collisions, most noticable when firing at overlapping enemy droids - laser just whizzles through them without effect. Fair enough, the same happens when enemy droid fires at player droid when it's colliding with another enemy or explosion.

Sprite positions were updated directly into registers while moving droids, and there was a lengthy screen redraw before reading the collision register. That meant that collision data was always up to date with the latest sprite positions, but sprite movements weren't in sync either with each other or with background graphics.

My first attempt to sync them was to update sprites only just before redraw, then reading the collision register at the bottom of screen. This meant that sprites were synced with each other, but they still wobbled around a bit compared to the background when screen was scrolling. Also, because collision register now contained all sprite-sprite collisions I needed to compare sprite coordinates to see which of the colliding sprites were close enough to collide with each other. That allowed detecting collisions in multiple groups around the screen, and worked reasonably well although it sometimes meant false collisions if there were several sprites close to each other.

To make everything move smoothly, I needed to delay sprite register writes one display frame. That way screen update was done just before sprite movements were done, and both changes were visible at the same time.


Game frame consists of two or more display frames and goes like this (simplified a bit)


  1. wait for raster beam to pass the first play area line
  2. copy current sprite positions from (G)ame buffer to D(isplay) buffer, set flag so interrupt routine updates them at the beginning of the next display frame
  3. redraw screen, this won't be visible until next display frame (which is coming soon enough, as redraw takes 15000+ cycles)
  4. move player & enemies, check collisions. All these update sprite positions in G buffer. Meanwhile raster interrupt reads sprite registers from D buffer and writes them into VIC-II.
End Loop

Because I start running droids before the previous positions are written into VIC-II, I can't use collision register at all. So I need to check all enabled sprites against each other.

Getting deep and personal with software collision check

First, if both sprites are explosions then I don't check them at all. Explosions use mask #0 so this is easy.

        lda     droidCollisionMask,x
        ora     droidCollisionMask,y
        beq     .skip                   ; explosion-explosion

I then calculate x & y coordinate distances between the two sprites. As I define collision as "overlap" instead of "adjanced" (just like VIC-II does), collision is possible only if dx is within [-23,23] and dy is within [-20,20].

        lda     droidPosX_lo,x
        sbc     droidPosX_lo,y
        sta     dx
        lda     droidPosX_hi,x
        sbc     droidPosX_hi,y
        bcc     .dxneg

        bne     .skip                   ; dx in [0,23] ?
        lda     dx
        cmp     #24
        bcc     .xok
        bcs     .skip

.dxneg  cmp     #$ff                    ; dx in [-23,-1] ?
        bne     .skip
        lda     dx
        cmp     #-23
        bcc     .skip
        eor     #$ff
        adc     #0
.xok    sta     absdx

        sec                             ; repeat with dy, range [-20,20]
        lda     ylo,x                   ; a bit easier, as we
        sbc     ylo,y                   ; don't have high byte
        sta     dy
        bcc     .dyneg
        cmp     #21
        bcc     .yok
        bcs     .skip

.dyneg  cmp     #-21
        bcc     .skip
        eor     #$ff
        adc     #0
.yok    sta     absdy

Next I check which types collided. I extract type (bits 5 & 6) from both droids, then combine them into 4-bit index into jump offset table. Bit 7 is guaranteed to be 0 for active droids/bullets/explosions.

        lda     droidType,y             ; 0YY. ....
        eor     droidType,x             ; 0XXy y...
        and     #$18
        eor     droidType,x             ; 0XXY Y...
        lsr                             ; 0000 XXYY
        lda     .typejump,x
        sta     .j+1
.j      bne     *                       ; jump into type-specific check

If this is droid-droid or droid-explosion check I can use the fact that both collision masks are symmetrical both horizontally and vertically. I use predefined table to see if ABS(dx) >= minimum distance at line ABS(dy). No collision if that's true. 2*21 bytes for two tables is a good tradeoff between speed and space, especially as droid-droid collisions are common.

Entry points are at labels.

.dr_dr  ldx     absdy
        lda     absdx
        cmp     DroidDroidDX,x
        bcs     .skip                   ; no collision
        ...                             ; rest of code
        jmp     .next

.xpl_dr jsr     swap
.dr_xpl ldx     absdy
        lda     absdx
        cmp     DroidXplosDX,x          ; dx>=noncollision
        bcs     .skip
        jmp     .next

DroidDroidDX    dc.b    23,23,23,23,22,22,21,21,20,19
                dc.b    18,17,16,15,13,11, 7, 3, 0, 0, 0
DroidXplosDX    dc.b    19,19,19,19,18,18,17,17,16,15
                dc.b    14,13,12,10, 8, 4, 0, 0, 0, 0, 0

All other collision types need something better. That's what the subroutine below does. It doesn't use sprites themselves for checking, I have simplified collision masks for that.

  1. Animated sprites have been combined into single mask, and
  2. Every sprite row has only one span, ie. no "holes" in line
It's clear that there's no need to check non-overlapping lines when dy <> 0. Most masks also have empty lines at top/bottom and it would be waste of time to check them. So I have tables telling how many empty lines there are at the top, and how many non-empty lines there are in each mask.

We'll start by checking if sprites are too narrow to overlap.

        lda     droidCollisionMask,x    ; get mask indexes
        lda     droidCollisionMask,y

        lda     absdx
        adc     minxskip,x
        adc     minxskip,y
        cmp     #24
        bcs     .no2

;	4+2+4+2 +2+3+4+4+2+2 = 29 cycles

To see which sprite has non-empty-line higher:

T1 = y1top = y1 + empty_top[mask1]
T2 = y2top = y2 + empty_top[mask2]

real_dy = T1 - T2
= (y1 + empty_top[mask1]) - (y2 + empty_top[mask2])
= (y1 - y2) + empty_top[mask1] - empty_top[mask2]
= dy + empty_top[mask1] - empty_top[mask2]

;       clc
        lda     dy                      ; y1 - y2
        adc     empty_top,x             ; + empty_top[mask1]
        sbc     empty_top,y             ; - empty_top[mask2]
        bpl     .y2                     ; go handle sprite 1 below sprite 2

;       2+3+4+2+4+2 = 17 (+1) cycles

Now we are ready to handle case where sprite1 is above sprite2.
First we need to check if it reaches top of sprite2 at all. This also gives us number of overlapping lines.

        adc     height,x                ; + height[mask1]-1
        bmi     .no                     ; spr1 doesn't reach spr2
        sta     num_lines               ; overlap - 1

Ok, we have overlapping lines. Sprite2 mask starts from the beginning, sprite1 mask gets it's first (T2-T1) lines skipped. Instead of calculating that again we undo the above ADC and negate result. Each line takes two bytes so skip must be doubled.

;       sec                             ; restore skip
        sbc     height,x
        eor     #$ff                    ; make it positive
;       clc
        adc     #1

        asl                             ; pt1 = base[mask1] + 2*skip
;       clc
        adc     collmask_lo,x
        sta     pt1
        lda     #0
        adc     collmask_hi,x
        sta     pt1+1

        lda     collmask_lo,y           ; pt2 = base[mask2]
        sta     pt2
        lda     collmask_hi,y
        sta     pt2+1
        bcc     .chkx

;       2+4+2+3 +0+4+2+0+2 +2+4+3+2+4+3 +4+3+4+3 +3 = 54 cycles

Now, this looks like a suitable place for non-collision exit. Sign flag will be set to tell caller there was no collision.

.no2    lda     #-1
.no     rts

Here comes the check for the case where sprite1 is lower than spr2, or at the same height. It's quite similar with the above, we just start with positive number in A.

.y2     sta     .skip2+1                ; remember #lines to skip

        clc                             ; extra -1 to get real height
        sbc     height,y                ; - height[mask2]
        bpl     .no2                    ; spr2 doesn't reach spr1
        eor     #$ff
        sta     num_lines               ; overlap - 1

        lda     collmask_lo,x           ; pt1 = base[mask1]
        sta     pt1
        lda     collmask_hi,x
        sta     pt1+1

.skip2  lda     #0                      ; pt2 = base[mask2] + 2*skip
        adc     collmask_lo,y
        sta     pt2
        lda     #0
        adc     collmask_hi,y
        sta     pt2+1

;       4 +2+4+2+2+3 +4+3+4+3 +2+2+4+3+2+4+3 = 51 cycles

Phew! Finally we know which mask lines to check against each other. It took just over 100 cycles to get here.

; pt1 = spr1 mask
; pt2 = spr2 mask
; num_lines = lines_to_check-1

.chkx   ldx     num_lines
        ldy     #0

Horizontal check is done exactly like vertical check, but there's no need to calculate overlap or skip.

real_dx = L1 - L2
= (x1 + empty_left[mask1]) - (x2 + empty_left[mask2])
= (x1 - x2) + empty_left[mask1] - empty_left[mask2]
= dx + empty_left[mask1] - empty_left[mask2]

.loop   clc
        lda     dx                      ; x1 - x2
        adc     (pt1),y                 ; + empty_left[mask1]
        sbc     (pt2),y                 ; - empty_left[mask2]
        bpl     .x2                     ; span1 right of span2

;       2+3+5+2+5+2 = 19 (+1)

Span1 starts left of span2. If it reaches span2 then there's collision.

;       check if span1 reaches span2

        adc     (pt1),y                 ; + width[mask1]-1
        bmi     .next                   ; no overlap, check next line

;       19 + 2+2+5+3 = 31 cycles so far

Drop through into collision exit. Clear sign flag so caller knows sprites overlapped. (LSR is only necessary for lower code, but it's cheap.)

.coll2  lsr                             ; clear sign flag

You guessed it: check the opposite case.

.x2     iny
        clc                             ; extra -1 to get real width
        sbc     (pt2),y                 ; - width[mask1]
        bmi     .coll2

;       20 + 2+2+5+2 = 31 cycles so far

.next   iny
        bpl     .loop
        rts                             ; sign set, no collision

;       31 + 2+2+3 = 38 cycles per loop

The only thing left is some data...
Vertical skip + height + pointers = 5*14 = 70 bytes
+ 2*237 = 474 bytes for mask lines.

Total 544 bytes.

empty_top       hex     03 05010401 08010000 03000000 01        ; [0,20]
height          hex     0d 0a120c12 02131414 0e141414 11        ; [0,20]
minxskip        hex     04 05020602 00010901 00000300 00        ; [0,10]

collmask_lo     dc.b    <mask0,<mask1,<mask2,<mask3,<mask4,<mask5,<mask6
                dc.b    <mask7,<mask8,<mask9,<maskA,<maskB,<maskC,<maskD
collmask_hi     dc.b    >mask0,>mask1,>mask2,>mask3,>mask4,>mask5,>mask6
                dc.b    >mask7,>mask8,>mask9,>maskA,>maskB,>maskC,>maskD

mask0           hex     0904 0708 060a 050c 050c 040e 040e 040e
                hex     040e 050c 050c 060a 0708 0904

mask1           hex     060a 050c 050c 050c 050c 050c 050c 050c
                hex     050c 050c 060a
mask2           hex     0901 0803 0706 0608 040a 030b 020d 020f
                hex     0210 0310 0310 0410 060e 070e 080c 080b
                hex     0908 0a06 0d02
mask3           hex     0709 060b 060b 060b 060b 0709 0709 060b
                hex     060b 060b 060a 0709 0709
mask4           hex     0d01 0c03 0a06 0909 080b 080c 070e 060f
                hex     0411 0311 0311 0310 020f 020e 030c 040b
                hex     0608 0706 0802

mask5           hex     0312 0017 0212
mask6           hex     0200 0301 0304 0404 0503 0604 0605 0706
                hex     0806 0a04 0a05 0b05 0b06 0c06 0d05 0f04
                hex     1103 1301 1401 1501
mask7           hex     0b01 0b01 0b01 0a03 0a03 0a03 0a03 0a04
                hex     0905 0905 0905 0a04 0a03 0a03 0a04 0b03
                hex     0c02 0c01 0b02 0b01 0b01
mask8           hex     1501 1302 1104 1004 0f04 0f04 0e04 0d04
                hex     0b04 0a05 0905 0905 0804 0703 0504 0405
                hex     0404 0304 0303 0202 0200

mask9           hex     0808 0212 0017 0017 0017 0017 0017 0017
                hex     0017 0017 0017 0017 0017 0212 0806
maskA           hex     0701 0603 0407 030a 010d 000f 010e 020f
                hex     0210 0310 0311 0410 0510 070e 070f 080f
                hex     090d 0a0a 0c07 0e03 0f01
maskB           hex     050c 050c 050c 040d 040e 030f 040e 040e
                hex     050e 050e 050e 040f 040f 040e 030f 030f
                hex     040e 040d 050c 050c 060b
maskC           hex     0f01 0e03 0c07 0a0a 090d 090e 080e 060f
                hex     0510 0410 0311 0311 0210 020f 010f 000f
                hex     000e 010c 0308 0504 0701

maskD           hex     0a02 060a 040e 0310 0212 0114 0114 0016
                hex     0016 0016 0016 0114 0114 0212 0310 040e
                hex     060a 0a02