Older Games (PSX hardware, but also N64) used 16 bit integers for their angles.
I grasp that 0 = 0rad and 65535 = Pi*2rad.
But how would someone generate directions out of it, since the range from sine/cosine are [-1,1]
\$\begingroup\$
\$\endgroup\$
Add a comment
|
2 Answers
\$\begingroup\$
\$\endgroup\$
2
First of all, games of that generation did not calculate sine and cosine values in real-time. The hardware back then was too slow at trigonometric functions to do that. Instead they used sine tables. They had precomputed arrays of angles and their sines in memory and then just did lookups (We don't do that anymore today because on modern CPUs and GPUs, calculating a sine is actually cheaper than looking up the value in memory).
But those sine tables still had integers. So how do you represent the value of 0.7071 in it?
One option is to multiply it by a fixed factor like 1000. So sin[45] = 707. If you then want to turn a direction and an angle into a vector, you would calculate vector.x = (dist * sin[angle]) / 1000.
But divisions are also rather expensive. But do you know what is actually a really fast operation? Bit-shifts! The bit-shift operation means to move all the bits in a value left or right by a certain number of places. Many programming languages use the operators << and >> for left-shift and right-shift respectively. This is an operation which is lightning-fast on many CPUs. What do you need that for? If you multiply or divide by a pwer of 2, then you can substitute this by a bit-shifting. It's basically the binary equivalent of multiplying or dividing by powers of 10 by adding or removing zeros.
So you don't fill your sine table by the values multiplied by 1000 but by some power of 2. For example 2^10 which is 1024. So sin[45] is 0.7071 * 1024 or 724. Then you can substitute the division by a much faster bit-shift of 10 places: vector.x = (dist * sin[angle]) >> 10.
-
1\$\begingroup\$ "(...) on modern CPUs and GPUs, calculating a sine is actually cheaper than looking up the value in memory". I'd love to read more about this! \$\endgroup\$ Nov 11, 2022 at 11:52
-
1\$\begingroup\$ @liggiorgio Here is a question on Stackoverflow about this subject. It comes to the conclusion that on 2009 hardware, sine tables were still marginally faster. But keep in mind that this only tests for CPU time. It doesn't consider that a sine table of sufficient precision requires valuable CPU cache space you could probably use better for something else. And then there are also GPUs, which are a completely different topic. \$\endgroup\$– PhilippNov 11, 2022 at 14:01
\$\begingroup\$
\$\endgroup\$
Use fixed-point arithmetic, which means putting an implicit binary (or decimal, or some other base) point somewhere in the number.
For instance, in a 16 bit number, you could decide to have 8 bits before the binary point, and 8 bits after, which would give you a range of 0 to 255.99609375 (or -128 to 127.99609375 if treating it as signed), with a precision of 1/256.
For this particular example, 2 bits before the binary point and 14 after would give the best precision (it gets you numbers from -2 to 1.99993896484375 with a precision of 1/16384), which may or may not be suitable depending what you wanted to do with the numbers afterwards.
This has applications on very old or low end hardware that doesn't support floating point, and also cases where you want determinism that floating point rounding might get in the way of.
As an aside, trigonometry is expensive (which can be of extra importance on old and low end hardware), and it may be better to avoid the trigonometry altogether where possible, by for instance transforming a problem to use vector geometry (e.g. with dot products) instead.
