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.
Timing
Game frame consists of two or more display frames and goes like
this (simplified a bit)
Loop
- wait for raster beam to pass the first play area line
- 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
- redraw screen, this won't be visible until next display frame (which is coming soon enough, as redraw takes 15000+ cycles)
- 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.
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].
sec
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. ....
lsr
lsr
eor droidType,x ; 0XXy y...
and #$18
eor droidType,x ; 0XXY Y...
lsr
lsr
lsr ; 0000 XXYY
tax
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.
- Animated sprites have been combined into single mask, and
- Every sprite row has only one span, ie. no "holes" in line
We'll start by checking if sprites are too narrow to overlap.
Collision
lda droidCollisionMask,x ; get mask indexes
tax
lda droidCollisionMask,y
tay
clc
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]
sec
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.
clc
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
asl
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]
sec
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
iny
clc
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
rts
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
dex
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