Sprite to Background Collision Detection

The TMS9918/9929 VDP processor in the TI-99/4A is very advanced for its age (it was introduced circa 1980). It has 32 hardware sprites. Compare this to the Commodore 64, which has 8. Somewhat bizarrely, collision detection between sprites isn't very well catered for on the TI VDP, your only realistic option is compre coordinates of sprites and see if they overlap.

Checking sprites against background characters is not catered for in any way. One must do it in software. Consequently, I determined I would come up with a solution for TurboForth that would make it simple and as fast as possible.

The code presented below is only for use in 32 column mode (GMODE=1) and 16x16 un-magnified sprites (by far the most common sprite size).

It's Not as Simple as You Think!

The biggest issue when detecting the characters under a sprite is that characters are aligned on 8 pixel boundaries, whereas sprites have pixel-level freedom as to their position on the screen. Therefore, the issue of overlap, and, specifically, the degree of overlap occurs:

As illustrated here, a sprite (the red frame in this picture) can actually cover six background characters. Therefore, some approximation is neccesary. The code presented below can detect if a sprite is within +/- 4 pixels of a target character. Furthermore, a sprite is 16 pixels by 16 pixels (when MAGNIFY is set to 2) - made up of 4 8x8 characters in two rows of two, so the issue of which area of a sprite is covering a target character is also important. For example, if you have a sprite man who is falling down onto a platform (imagine something like Donkey Kong) and the platform is made up of background characters (very likely) then you'll want to detect when the bottom of the sprite hits the platform, not the top. Similarly, if he is jumping, you might want to detect the top of the sprite, and not care about the bottom. Similar issues arise when the sprite is walking left or right.

16x16 Pixel Sprites

As mentioned above, a 16x16 sprite is organised as 2 rows of 8x8 pixel squares, as shown on the left. We'll call them quadrants. The sprite on the left is showing the quadrants, A, B, C and D. It would be nice if, when checking to see if a particular background character is covered by our sprite, we can specifiy which quadrant of the sprite should be checked, or multiple, or even all quadrants. I pondered over this for a while, and, eventually, after quite a lot of experimentation, I came up with a solution which I think is quite neat, and, as far as I know, unique on the TI-99/4A.

UnderSprite

Step forward underSprite, which checks the background under a specific (or multiple) sprite quadrant(s) to see if it is covered by the sprite. Here's the stack signature:

underSprite ( char quadrants sprite# -- result )

Let's first look at the inputs to the word:

char	The ASCII code of the character to look for.
quadrants	The quadrant(s) of the sprite to check, as a bitmask.
sprite#	The sprite number to check.

Specifying the Sprite Quadrant Bitmask

The four sprite quadrants have their own value. These values can be combined to check more than one quadrant:

Quadrant	Value
A	1
B	2
C	4
D	8

So, for example, if you wanted to check all four quadrants, you'd specificy a value of 15₁₀.

Understanding the Result Code

underSprite returns a code that works in the same way as the quadrant bitmask, above. It tells you which area of the sprite is over the character, as follows:

Value	Meaning
0	The character is not under the sprite.
1	The character was detected under quadrant A.
2	The character was detected under quadrant B.
4	The character was detected under quadrant C.
8	The character was detected under quadrant D.

Some Examples

The best way to demonstrate how it works is by example, so here's a few:

Example Code	Description
ASCII F 3 0 underSprite	Check if the ascii character F is covered by quadrants A and B (top row) of sprite 0.
ASCII o 12 1 underSprite	Check if the ascii character o is covered by quadrants C and D (bottom row) of sprite 1.
ASCII r 5 2 underSprite	Check if the ascii character r is covered by quadrants A and C (left column) of sprite 2.
ASCII t 10 3 underSprite	Check if the ascii character t is covered by quadrants B and D (right column) of sprite 4.
ASCII h 15 4 underSprite	Check if the ascii character h is covered by any quadrant of sprite 4.

Demonstration Program

Here's a simple little demo program to show off sprite to background detection in action.

Type main to run the program. Use joystick #1 (or the PC cursor keys if you're running Classic99) to move the sprite around the screen. The code is looking for any quadrant of the sprite to pass over the * (asterisk) character. Press fire (TAB in Classic99) to exit.

Implementation Code

The following code implements the functionality described above, written with the TurboForth TMS9900 Assembler, which is on block 9 of the boot disk. It occupies a mere 114 bytes of memory - a small price to pay for a very powerful feature.

asm: underSprite ( char quadrants sprite# -- result ) *sp+ r1 mov, \ get sprite# *sp+ r9 mov, \ get quadrants \ look up sprite in sprite attribute list (SAL) in cpu ram r0 blk 298 - li, \ address of SAL r1 2 sla, \ multiply sprite# by 4 r1 r0 a, \ r0 points to entry in SAL r0 *+ r1 movb, \ get sprite row r1 $0400 ai, \ offset by 4 pixels r1 11 srl, \ clear high byte, move to low byte and divide by 8 r0 ** r2 movb, \ get sprite column r2 $0400 ai, \ offset by 4 pixels r2 11 srl, \ clear high byte, move to low byte and divide by 8 r1 5 sla, \ multiply row by 32 r2 r1 a, \ add column. Screen address now in r1 *sp r0 mov, \ get char from stack r0 swpb, \ move to high byte r6 clr, \ holds result r7 1 li, \ mask r13 2 li, \ outer loop counter begin, r1 swpb, \ get screen address low byte r1 $8c02 @@ movb, \ move to vdp address reg r1 swpb, \ get address high byte r1 $8c02 @@ movb, \ move to vdp address reg r14 2 li, \ inner loop counter & delay for VDP begin, $8800 @@ r2 movb, \ read the byte from vdp r9 1 src, lt if, \ are we interested in this quadrant? r0 r2 cb, eq if, \ compare char from screen with char r7 r6 soc, \ set mask bit endif, endif, r7 1 sla, \ shift mask to the left r14 dec, eq until, r1 32 ai, \ next screen line r13 dec, eq until, r6 *sp mov, \ place result on stack ;asm

CODE Version

It is undesirable to have to load the assembler just to use one word, therefore, a pre-assembled CODE equivalent is presented here:

base @ HEX CODE: underSprite ( char quadrants sprite# -- result ) C074 C274 0200 A088 0A21 A001 D070 0221 0400 09B1 D090 0222 0400 09B2 0A51 A042 C014 06C0 04C6 0207 0001 020D 0002 06C1 D801 8C02 06C1 D801 8C02 020E 0002 D0A0 8800 0B19 1101 1003 9080 1601 E187 0A17 060E 16F5 0221 0020 060D 16E9 C506 ;CODE base !

18th September 2015