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)
- 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