Given two game objects, how do we determine if they overlap? By far the most common technique in 8-bit game development is to compare the extents of the two objects and see if they overlap. The extents will normally be chosen to be fair - i.e. lie entirely inside the player sprite and be a bit more generous for enemy sprites. As testing boxes only requires 4 or so comparisons, this kind of test is quick even on primitive 80s computers, providing the number of objects remains reasonably low.
In flying shark, there can be as many as 8 enemy objects, 5 enemy bullets, 6 player bullets and the player themself. All enemy objects need to be tested for collisions against all player bullets and some ( air-based ) against the player. All enemy bullets must be tested against the player. For the enemy vs bullet alone, this could be as many as 56 tests.
The approach taken in flying shark is to create two 256 byte collision arrays. One array has one entry for every horizontal pixel of the screen, the other for every vertical entry. Note that although sprites are not drawn outside the play area, their positions are screen relative rather than buffer/play area relative, which no doubt makes the code more reusable.
Each entry has a bit set if a corresponding object is in this column ( horizontal array ) or row ( vertical array ). The meaning of the bits is as follows:
7 6 5 4 3 2 1 0
Player Bomb ........Up to 6 player bullets................ During WriteCollisions the vertical extent of each player bullet is projected onto the vertical collision array and its horizontal extent projected onto the horizontal array. This is followed by the player.
NextBullet
LD H,0x7e ; MSB of vert collision array addr
LD A,(IY +0xd ) ; IY is object ptr
AND 0xe0 ; floor Y pos
OR (IY +0xe )
RLCA
RLCA
RLCA
INC A
LD L,A
LD A,( HL ) ; or into array
OR E
LD (HL ), A
INC L
:
repeat 'or into array' another 7 times
:
LD H,0x7f ; high byte of horizontal collision
LD A,(IY +0xb ) ; floor xpos
AND 0xe0
OR (IY +0xc )
RLCA
RLCA
RLCA
LD L,A
LD A,( HL ) ; or into array
OR E
LD (HL ), A
INC L
:
repeat 'or into array' another 11 times
:
LD (IY +0x14 ),C
RLC C ; shift bit for next bullet
LD SP ,IY ; follow list next pointer
POP IY
DJNZ NextBullet
:
and so the same thing for player ( 8x8, offset by (4,4 ) In DoCollisions, each object samples these two arrays and writes the bitwise AND into its collision field ( IY+014 ). Bit 6 is also set at this point if a bomb has been triggered and the object is above ( "higher on the screen" ) than the player. No response to the overlap is made here - this is done inside the object tick routines. Ultimately the union of all the collision fields of all objects that could hit the player is used to determine if the player has been killed.
I am unsure whether this is faster for the actual number of objects that the game ultimately uses, but it definitely scales better. It also results in a clean separation of concerns, with collision code running independently of the object logic. It does, of course, require more memory. 512 bytes was considered acceptable, but if you wanted to handle more objects ( say 16 ) then the amount of memory required - at least on an eight bit machine - would become prohibitive.
The Ghidra disassembly from which these fragments were pulled is here : https://github.com/tomgrove/FlyingSharkBlog