Calculating Angles on the Z80: Doing the Impossible at 3.5 MHz

Hello, friends! (Or just readers who are curious to peek under the hood of the good old retro games). How often do we recall that magical time when every kilobyte, every cycle of the Z80 processor on our beloved Speccy counted? We squeezed the maximum out of those 3.5 MHz so that magic would happen on screen – sprites moved, bombs exploded, enemies ran...

And what does it take for all of this to move not just anyhow, but smartly? For example, so that a bullet flies straight to the target? Or an enemy walks toward the player along the shortest path? Right – you need to know the direction. And direction is, essentially, an angle!

But here's the catch! Our good old Z80 is an integer processor. No fancy coprocessors, no native floating-point operations, sines, cosines, or, heaven forbid, arctangents! Calculating the angle between two points (or, well, a vector (dx, dy) – the difference of coordinates) is no easy task for it. It's not LD A,B or ADD HL,DE. It's something from higher mathematics that, it would seem, can't be handled at 3.5 MHz without slowdowns.

That's exactly why old games often used clever tricks, workarounds, and simplifications. After all, every extra millisecond spent on calculations means a drop in framerate, less responsive controls, or simply the game becoming boring because the enemies are dumb and can't properly find you.

But what if I told you that you can get a sufficiently accurate angle value for game purposes using only integer arithmetic and small tables? Without slowdowns and with the elegance worthy of a true assembly master! That's exactly what we'll talk about today. We'll go over the simplest (and crudest) approaches, hint at the complexities of more direct ones, and then I'll show how you can apply a bit of mathematics (but don't be scared, just a tiny bit!) and tables to make our Z80 calculate angles quickly and efficiently.

Get ready to dive into the world of integer magic!

Fast but crude... or accurate but slow?

When you need to find the angle of a vector (dx, dy) on the Z80, the first thought is "something simpler". The simplest thing is to look at the signs of dx and dy and determine which quarter (quadrant) the angle is in. Positive dx and dy? Then it's down-right (for Spectrum coordinates). Negative dx and positive dy? Down-left. This is instant, but gives accuracy within a 90-degree range, that is, +/- 45 degrees. For many tasks this is not enough. You can refine it by comparing the absolute values of dx and dy – this already gives 8 directions (45 degrees each). Fast, but still crude – like trying to aim while looking through a very blurry binoculars.

And what about the "direct" approach – angle = atan(dy / dx)? You need an arctangent! On a PC you take the atan2(x, y) function and you're done. On the Speccy? You could make an atan table and take a value from it by the index dy/dx. But there are two problems here:

So the direct table-based atan(y/x) on the Z80 is neither the most elegant nor the fastest solution. We need to work around this division problem!

Our trick: logarithms and two tables

And here's our trick! Instead of calculating dy/dx (which involves division), let's recall the property of logarithms: log2(Y / X) = log2(Y) - log2(X). Division has turned into subtraction! And the Z80 does subtraction instantly. Bingo!

The idea is this:

Total: Two small tables (256 bytes each), two lookups in the first table, one fast subtraction, one lookup in the second table – and we get a "base" angle in the 0-45 degree range! No slow division!

Putting it all together: the algorithm in plain terms

Here's how it looks as a whole, step by step:

And here's our result – a 16-bit number that precisely represents the angle of the vector (dx, dy)!

Here's what the table generators look like in JS (just so it's clear what's in them) and an approximate implementation in Z80 assembly:

1// JS код для генерации таблиц
2const log2tab = new Uint8Array(256); 
3const atan2pow_tab = new Uint8Array(256);
4
5function prepareTables() { 
6  // log2 
7  let i = 0; 
8  for (i = 0; i < 256; i ++) { 
9    log2tab[i] = (i > 0) ? Math.floor(Math.log2(i) * 32) : 0; 
10  }
11
12  // atan(2^k)\
13  for (i = 0; i < 256; i ++) {\
14    atan2pow_tab[i] = (i > 0) ? Math.floor(Math.atan(Math.pow(2, - i / 32)) * 256 / (Math.PI / 4)) : 255;\
15  }
16}
17
18prepareTables(); // Генерируем таблицы 
19// Теперь log2tab и atan2pow_tab можно скопировать в ассемблерный код как байтовые данные
20

And here's the Javascript code for calculating the angle using our method.

1function logAngle(x, y) { 
2  // Получаем "чистые" значения x, y в диапазоне от 0 до 45 градусов 
3  if (x === 0 && y === 0) { 
4    // Частный случай для нулевого отрезка return 0; 
5  }
6  let is_x_neg = 0;
7  if (x < 0) {
8    is_x_neg = 1;
9    x = 0 - x;
10  }
11  let is_y_neg = 0;
12  if (y < 0) {
13    is_y_neg = 1;
14    y = 0 - y;
15  }
16  let is_mirr = 0;
17  if (x < y) {
18    // Exchange x and y
19    is_mirr = 1;
20    let t = x;
21    x = y;
22    y = t;
23  }
24  // Now X and Y equals to angle from 0 to 45\
25  let ang = 0;
26  if (y == 0) {
27    // Частный случай - суб-угол 0 градусов\
28  } else {
29    // Считаем угол по упрощённой формуле atan(2^k), где k = log2(x) - log2(y)\
30    ang = atan2pow_tab[log2tab[x] - log2tab[y]];
31  }
32
33  // Полученное значение помещаем в нужный квадрант\
34  // Чтобы сохранить точность, сдвигаем значение влево на 5 бит и тем самым расширяем до 16 бит
35
36  let ang16 = (ang << 5);
37  if (is_mirr) {
38    ang16 = 0x4000 - ang16;
39  }
40  if (is_x_neg) {
41    ang16 = 0x8000 - ang16;
42  }
43  if (is_y_neg) {
44    ang16 = 0x10000 - ang16;
45  }
46
47  //ang16 = ang16 & 0xff00; // Если нужна 8-битная точность
48
49  return ang16 * 360 / 65536; // Если нужно значение в диапазоне от 0 до 360
50}
51

And finally, fanfare! Our final Z80 Assembler code that does the same thing as the Javascript code above, but tailored for our beloved Speccy.

1; Calculate 11-bit angle value (aligned to 16 bit)
2; Input: HL = (Y1, X1), DE = (Y2, X2) - Start and end points of the vector, [0, 0xff], non-signed values.
3; Output: HL = angle value from 0 to 0xffff (0 = 0 degrees, 0xffff = 359.9 degrees), only the most 11 bits have value
4math_angle8x8
5	ld c, 0		; Keep flags here. C.0 = is_x_neg, C.1 = is_y_neg, C.2 = is_mirror
6	ld a, e
7	sub l		; A = dx
8	jr nc, .a1	; dx >= 0
9	; dx < 0
10	set 0, c	; is_x_neg = 1
11	ld e, a
12	xor a
13	sub e		; dx = 0 - dx
14.a1	ld e, a
15	; check dy
16	ld a, d
17	sub h
18	jr nc, .a2
19	; dy < 0
20	set 1, c
21	ld d, a
22	xor a
23	sub d
24.a2 ld d, a
25	or e	; A = dx | dy
26	jr z, .a3	; dx = 0, dy = 0, special condition
27	ld a, e
28	cp d
29	jr nc, .a5	; dx >= dy
30	; dx < dy, we need mirroring
31	; A = E here
32 	set 2, c
33	ld e, d
34	ld d, a
35	; D and E was exchanged
36.a5	ld a, d
37	or a
38	jr z, .a4
39	; All flags were set, let's calculate
40	ld l, e
41	ld h, log2tab >> 8	; Upper byte of the table address
42	ld a, (hl)			; A = log2(dx)
43	ld l, d
44	sub (hl)		; A = log2(dx) - log2(dy)
45	ld l, a
46	ld h, atan2pow_tab >> 8	; Upper byte of the table address
47	ld a, (hl)		; A = atan2pow_tab(log2(dx) - log2(dy))
48	; We got angle value from 0 to 45
49	; Now mirror this value back
50	ld l, a
51	ld h, 0
52	add hl, hl
53	add hl, hl
54	add hl, hl
55	add hl, hl
56	add hl, hl
57	bit 2, c
58	jr z, .a6
59	; Mirror 0..45 to 45..90 if flag was set
60	ld de, 0x4000	
61	ex de, hl
62	sub hl, de
63.a6	bit 0, c
64	jr z, .a7
65	; Mirror X
66	ld de, 0x8000
67	ex de, hl
68	sub hl, de
69.a7 bit 1, c
70	jr z, .a8
71	; Mirror Y
72	ld de, 0
73	ex de, hl
74	sub hl, de
75.a8	; Result in HL
76	; Main return point
77	ret
78.a3 ; Special case: dx = 0, dy = 0
79	ld hl, 0
80	ret
81.a4 ; Special case: dy = 0
82	ld hl, 0
83	jr .a6	; Let's use correct quadrant
84
85; Those tables should be aligned by 256 bytes in RAM
86	align 256
87log2tab
88	; Those values are calculated as floor(log2(i) * 32) where i = 0..255
89	db 0, 0, 32, 50, 64, 74, 82, 89, 96, 101, 106, 110, 114, 118, 121, 125
90	db 128, 130, 133, 135, 138, 140, 142, 144, 146, 148, 150, 152, 153, 155, 157, 158
91	db 160, 161, 162, 164, 165, 166, 167, 169, 170, 171, 172, 173, 174, 175, 176, 177
92	db 178, 179, 180, 181, 182, 183, 184, 185, 185, 186, 187, 188, 189, 189, 190, 191
93	db 192, 192, 193, 194, 194, 195, 196, 196, 197, 198, 198, 199, 199, 200, 201, 201
94	db 202, 202, 203, 204, 204, 205, 205, 206, 206, 207, 207, 208, 208, 209, 209, 210
95	db 210, 211, 211, 212, 212, 213, 213, 213, 214, 214, 215, 215, 216, 216, 217, 217
96	db 217, 218, 218, 219, 219, 219, 220, 220, 221, 221, 221, 222, 222, 222, 223, 223
97	db 224, 224, 224, 225, 225, 225, 226, 226, 226, 227, 227, 227, 228, 228, 228, 229
98	db 229, 229, 230, 230, 230, 231, 231, 231, 231, 232, 232, 232, 233, 233, 233, 234
99	db 234, 234, 234, 235, 235, 235, 236, 236, 236, 236, 237, 237, 237, 237, 238, 238
100	db 238, 238, 239, 239, 239, 239, 240, 240, 240, 241, 241, 241, 241, 241, 242, 242
101	db 242, 242, 243, 243, 243, 243, 244, 244, 244, 244, 245, 245, 245, 245, 245, 246
102	db 246, 246, 246, 247, 247, 247, 247, 247, 248, 248, 248, 248, 249, 249, 249, 249
103	db 249, 250, 250, 250, 250, 250, 251, 251, 251, 251, 251, 252, 252, 252, 252, 252
104	db 253, 253, 253, 253, 253, 253, 254, 254, 254, 254, 254, 255, 255, 255, 255, 255
105
106atan2pow_tab
107	; Those values are calculated as floor(atan(pow(2, - i / 32)) * 256 / (PI / 4)) where i = 0..255
108	db 255, 252, 248, 245, 241, 238, 234, 231, 227, 224, 220, 217, 214, 210, 207, 203
109	db 200, 197, 194, 190, 187, 184, 181, 177, 174, 171, 168, 165, 162, 159, 156, 153
110	db 151, 148, 145, 142, 140, 137, 134, 132, 129, 127, 124, 122, 119, 117, 115, 113
111	db 110, 108, 106, 104, 102, 100, 98, 96, 94, 92, 90, 88, 86, 84, 83, 81
112	db 79, 78, 76, 75, 73, 71, 70, 68, 67, 66, 64, 63, 62, 60, 59, 58
113	db 57, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41
114	db 40, 39, 38, 38, 37, 36, 35, 34, 34, 33, 32, 32, 31, 30, 30, 29
115	db 28, 28, 27, 26, 26, 25, 25, 24, 24, 23, 23, 22, 22, 21, 21, 20
116	db 20, 19, 19, 19, 18, 18, 17, 17, 17, 16, 16, 16, 15, 15, 15, 14
117	db 14, 14, 13, 13, 13, 12, 12, 12, 12, 11, 11, 11, 11, 10, 10, 10
118	db 10, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7
119	db 7, 7, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5 
120	db 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3
121	db 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2
122	db 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1
123	db 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
124

Why is this cool? In the end, what did we get by using this trick with logarithms and tables?

Speed! No slow division subroutines! All the magic is memory lookups and fast integer operations. The angle is calculated very quickly, without "slowing down" the game.

Size! Only 512 bytes for two tables, plus a bit of code. This fits most games, even on 48K ZX models.

Accuracy! We get an 11-bit angle value, which gives very decent resolution (about 0.175 degrees per unit). For game tasks this discreteness is more than enough! If you don't need such precision and want to fit into 8 bits (that would be about 1.4 degrees per unit), you can simplify the code a little more.

Elegance! Turning division into subtraction using logarithms is a beautiful mathematical solution, perfectly suited to limited hardware.

This algorithm is an excellent example of how you can solve seemingly complex tasks on the Z80 using smart mathematical ideas and efficient memory handling. It was exactly such discoveries that made it possible to create those very unforgettable games on the Speccy!

Conclusion So we've gone through this path – from crude quadrants and rough estimates to obtaining a sufficiently accurate angle value using tables of logarithms and arctangents of powers of two. We saw how a task that seems impossible without floating point and trigonometric functions "out of the box" is solved quickly and efficiently on our good old 3.5-megahertz Z80.

This algorithm is just one of many examples of the tricks and elegant solutions developers used (and still use!) for retro platforms. Every clock cycle, every byte of memory mattered. And instead of moping about the limitations, people came up with algorithms like these, turning apparent drawbacks into a reason for a creative approach.

It is in such tasks and their solutions that the whole beauty and art of developing for retro hardware manifests itself. It's not just coding, it's optimization at the edge of the possible, the search for non-obvious paths and the use of mathematical tricks that may have long been forgotten in the world of gigahertz and gigabytes.

I hope this article was for you not just a technical breakdown, but also a little journey into the world of those very solutions that made games on the ZX Spectrum so special. Perhaps you saw how you can apply this algorithm in your own projects? Or maybe you remembered some other clever ways of calculating angles or other functions on the Z80?

Don't hesitate to share your thoughts, ask questions, or tell about your discoveries in the comments under this post! Sharing experience is the most valuable thing in our small but friendly retro community.

Thank you so much for your attention! See you again in the world of retro programming!

With love for the Speccy and its magic,

P.S. All the code can be downloaded in our Git.