Note: This article was originally written by Jonathan Cauldwell and is reproduced here with permission.
Adding and subtracting is straightforward enough on the Spectrum’s CPU, we have an abundance of instructions to perform these tasks. But unlike some later processors in the series, the programmer of the Z80A has to do his own multiplication and division. While such calculations are rare, they have their uses in certain types of game, and until you have routines to do the job, certain things are very tricky to do. For example, without Pythagoras’ theorem, it can be difficult to program an enemy sprite to shoot at the player with any degree of accuracy.
Suppose sprite A needs to fire a shot at sprite B. We need to find the angle at which sprite A is to fire, and some trigonometry is necessary to do this. We know the coordinates of the sprite, Ax, Ay, Bx and By, and the distances between these, Bx-Ax and By-Ay, will give us the opposite and adjacent line lengths. Unfortunately, the only way to calculate the angle from the opposite and adjacent is to use arctangent, and as tangents are only suitable for certain angles, we are better off using sine or cosine instead. So in order to find the angle from sprite A to sprite B, we need to find the length of the hypotenuse.
The hypotenuse is calculated by squaring the x distance, adding it to the square of the y distance, then finding the square root. There are routines in the Sinclair ROM to do all of this, but there is one serious drawback: as anyone who has ever used Sinclair BASIC will tell you, the maths routines are incredibly slow for writing games. So we have to knuckle down and write our own.
Squaring our x and y distances means using a multiplication routine and multiplying the numbers by themselves. Thankfully, this part is relatively painless. Multiplication is achieved in the same way as you would perform long multiplication on paper, although this time we are working in binary. All that is required is shifting, testing bits, and adding. Where a bit exists in our first factor, we add the second factor to the total. Then we shift the second factor left, and test the next bit along in our first factor. The routine below, taken from Kuiper Pursuit, demonstrates the technique by multiplying H by D and returning the result in HL.
imul ld e,d ; HL = H * D ld a,h ; make accumulator first multiplier. ld hl,0 ; zeroise total. ld d,h ; zeroise high byte so de=multiplier. ld b,8 ; repeat 8 times. imul1 rra ; rotate rightmost bit into carry. jr nc,imul2 ; wasn't set. add hl,de ; bit was set, so add de. and a ; reset carry. imul2 rl e ; shift de 1 bit left. rl d djnz imul1 ; repeat 8 times. ret
Now we need a square root, which is where our problems begin. Square roots are a lot more complicated. This means doing a lot of divisions, so first we need a division routine. This can be seen to work in the opposite way to multiplication, by shifting and subtracting. The next routine, also from Kuiper Pursuit, divides HL by D and returns the result in HL.
idiv ld b,8 ; bits to check. ld a,d ; number by which to divide. idiv3 rla ; check leftmost bit. jr c,idiv2 ; no more shifts required. inc b ; extra shift needed. cp h jr nc,idiv2 jp idiv3 ; repeat. idiv2 xor a ld e,a ld c,a ; result. idiv1 sbc hl,de ; do subtraction. jr nc,idiv0 ; no carry, keep the result. add hl,de ; restore original value of hl. idiv0 ccf ; reverse carry bit. rl c ; rotate in to ac. rla rr d ; divide de by 2. rr e djnz idiv1 ; repeat. ld h,a ; copy result to hl. ld l,c ret
In the same way that multiplication is made up of shifting and adding, and division is done via shifting and subtracting, so square roots can be calculated by shifting and dividing. We’re simply trying to find the “best fit” number which, when multiplied by itself, gives us the number with which we started. I won’t go into detailed explanation as to how the following routine works – if you really are that interested, follow my comments and step it through a debugger. Taken from Blizzard’s Rift, it returns the square root of HL in the accumulator.
isqr ld (sqbuf0),hl ; number for which we want to find square root. xor a ; zeroise accumulator. ld (sqbuf2),a ; result buffer. ld a,128 ; start division with highest bit. ld (sqbuf1),a ; next divisor. ld b,8 ; 8 bits to divide. isqr1 push bc ; store loop counter. ld a,(sqbuf2) ; current result. ld d,a ld a,(sqbuf1) ; next bit to check. or d ; combine with divisor. ld d,a ; store low byte. xor a ; HL = HL / D ld c,a ; zeroise c. ld e,a ; zeroise e. push de ; remember divisor. ld hl,(sqbuf0) ; original number. call idiv4 ; divide number by d. pop de ; restore divisor. cp d ; is divisor greater than result? jr c,isqr0 ; yes, don't store this bit then. ld a,d ld (sqbuf2),a ; store new divisor. isqr0 ld hl,sqbuf1 ; bit we tested. and a ; clear carry flag. rr (hl) ; next bit to right. pop bc ; restore loop counter. djnz isqr1 ; repeat ld a,(sqbuf2) ; return result in hl. ret sqbuf0 defw 0 sqbuf1 defb 0 sqbuf2 defb 0
With the length of the hypotenuse calculated, we can simply divide the opposite line by the hypotenuse to find the cosine of the angle. A quick search of our sine table will then tell us what that angle is. Phew!
This is the entire calculation taken from Blizzard’s Rift. Note that it uses the adjacent line length rather than the opposite, so finds the arccosine instead of the arcsine. It is also only used when the ship is above the gun turret, giving the player the opportunity to sneak up and attack from underneath. Nevertheless, it demonstrates how a sprite can fire at another with deadly accuracy. If you have ever played Blizzard’s Rift, you will know exactly how lethal those gun turrets can be.
; Ship is above the gun so we can employ some basic trigonometry to aim it. ; We need to find the angle and to do this we divide the adjacent by ; the hypotenuse and find the arccosine. ; First of all we put the length of the opposite on the stack: mgunx ld a,(nshipy) ; ship y coordinate. ld hl,guny ; gun y coord. sub (hl) ; find difference. jr nc,mgun0 ; result was positive. neg ; negative, make it positive. mgun0 cp 5 ; y difference less than 5? jr c,mgunu ; yes, point straight up. push af ; place length of opposite on stack. ; Next we require the length of the hypotenuse and we can use good ; old Pythagoras' theorem for this. ld h,a ; copy a to h. ld d,h ; copy h to d. call imul ; multiply integer parts to get 16-bit result. push hl ; remember squared value. ld hl,nshipx ; gun x coordinate. ld a,(gunx) ; ship x coordinate. sub (hl) ; find difference, will always be positive. ld h,a ; put x difference in h. ld d,h ; copy h to d. call imul ; multiply h by d to get square. pop de ; get last squared result. add hl,de ; want the sum of the two. call isqr ; find the square root, hypotenuse in a. pop de ; opposite line now in d register. ld h,a ; length of hypotenuse. ld l,0 ; no fraction or sign. ex de,hl ; switch 'em. ; Opposite and hypotenuse are now in de and hl. ; We now divide the first by the second and find the arcsine. ; Remember - sine = opposite over hypotenuse. call div ; division will give us the sine. ex de,hl ; want result in de. call asn ; get arcsine to find the angle. push af ; Okay, we have the angle but it's only 0 to half-pi radians (64 angles) ; so we need to make an adjustment based upon the quarter of the circle. ; We can establish which quarter of the circle our angle lies in by ; examining the differences between the ship and gun coordinates. ld a,(guny) ; gun y position. ld hl,shipy ; ship y. cp (hl) ; is ship to the right? jr nc,mgun2 ; player to the left, angle in second quarter. ; Angle to play is in first quarter, so it needs subtracting from 64. ld a,64 ; pi/2 radians = 64 angles. pop bc ; angle in b. sub b ; do the subtraction. ld (ix+1),a ; new angle. ret ; we have our angle. ; Second quarter - add literal 64 to our angle. mgun2 pop af ; original angle. add a,192 ; add pi/2 radians. ld (ix+1),a ; new angle. ret ; job's a good 'un!