[A83] Re: fixed point numbers
[Prev][Index][Thread]
[A83] Re: fixed point numbers
> Last week i was talking to Crashman, and he told me to do it with a look
up
> table for sinus and cosinus. He told me also to work with fixed point
> numbers (so i would place the part after the comma in that look up table
> (the part before the comma is most of the time zero, so i don't have to
put
> it in another table)). But i'm not sure how to work with those fixed point
> numbers, here's the two options i've come up with (maybe there's a better,
> that's way i ask you guys)
He is indeed correct. Fixed point is the way to go, and for something as
simple as you are doing, it is quite simple. I used this technique in a
simple pong game for the Game Boy, and I believe that James Rubingh's and
Matthew Shepcar's 360 degree snake games work in this manner.
> 1. Say you have the number 0.531287 as a sinus, then you have to put 53
(if
> you want to use 1 byte) or 531 (if you want to use 2 bytes) in that look
up
> table: so that would be .db ...,53,... ( '...' stands for other values in
> the table). Then you recall 53 and put it in h for example, you multiply
it
> with 3 (for example) and then....? i think you would have to divide it by
> 100 and round it so you get an integer ('cause i need integers for my
> coordinates for my sprite) But with this first method, you would still
have
> a fp number when you divide by 100 and can you put a fp number in a
register
> to round it? (also is there a routine to round a fp number to an integer?)
You don't do fixed point this way. There are plenty of references for this
in game programming books and sites, although on modern cpu's it is more
efficient to simply use floating point operations as the fpu takes less
cycles than the equivalent integer operations. And saying equivalent really
isn't accurate, since you will get much better results using true floating
point instead of fixed point. For a more technical and less practical
explanation, a logic and computer design book will probably be benficial.
Fixed point and floating point are very different, as the name implies.
With a fixed point number, the decimal point is "fixed". This gives an
exact range for the number, the same way an integer has an exact range. But
this also means that the acuracy is fixed. A certain number of bits are
always the whole number part, and the rest are the decimal part. With a
floating point number, the decimal point is not fixed. A certain number of
bits holds the mantissa, certain number hold the exponent. The exponent
portion indicates how many places to move the decimal point, and the
mantissa stores the actual numerical value. A floating point value used by
the rom has one byte to store if it is real/complex and positive/negative,
two bytes to store the exponent, and seven bytes to store the mantissa. The
mantissa is stored in bcd format.
bcd stands for binary coded decimal. This is important to understand both
while programming and when building circuits and hardware. Each bcd digit
is four bits, or one hexadecimal digit. Thus a byte holds two bcd digits.
Decimal values are stored natively in each nibble (four bits). When viewed
as a hexadecimal value, a bcd number will look like its decimal equivalent.
This makes it very easy to print bcd numbers as decimal, because it does not
require dividing by ten to get each digit. It only requires shifting.
The easiest way to use fixed point when working with sine/cosine values is
to use an 8.8 representation. The top byte is the integer portion, and the
lower portion is the decimal portion. When treating it, you work with it as
a 16 bit value, but when you need an integer value for say the sprite
coordinates, you just take the top 8 bits.
When working with sine/cosine, you need to remember that units you work with
are arbitrary and do not matter, as long as they are kept consistent.
Instead of using two radians or 360 degrees, it is common to use 256
degrees. Thus each quadrant of the circle is made up of 64 degrees. Thus,
when you pregenerate the sine table, you store 64 different values. The
rest of the table can be generated at run time by addition and subtraction.
An example table is as follows:
SineTable:
.db 0, 3, 6, 9, 12, 15, 18, 21, 24, 27
.db 30, 33, 36, 39, 42, 45, 48, 51, 53, 56
.db 59, 62, 64, 67, 70, 72, 75, 77, 79, 82
.db 84, 86, 89, 91, 93, 95, 97, 99, 101, 103
.db 104, 106, 108, 109, 111, 112, 113, 115, 116, 117
.db 118, 119, 120, 121, 122, 122, 123, 124, 124, 125
.db 125, 125, 125, 126
To get a cosine value from the table, simply add 64 onto the angle before
looking it up in the table. Because you are using bytes, the value will
wrap around at 0. What you must remember is that these are signed values.
128 to 255 will be negative. 255 is -1, and 128 is -127. This matters when
you are adding these as 16 bit values, because you must sign extend the
value. In other words, when converting an 8 bit signed number to a 16 bit
signed number, the sign bit, which is always the most significant bit, must
be moved.
What you can do is store the x and y coordinates of an object's position
each as 16 bit numbers. The value from the table will go into the lower
byte of the number, as the decimal portion. Thus, when adding them, it will
take several values to equal a single whole number. When determining where
to draw the object, use the top byte.
An example routine to load a sine and cosine value into a 16 bit register is
shown:
; input: a = angle (0 - 255)
; returns: de = sign extended cosine value
LoadCosine16:
add a,64
; input: a = angle (0 - 255)
; returns: de = sign extended sine value
LoadSine16:
ld d,0
ld e,a
ld hl,SineTable
add hl,de
ld a,(hl)
ld e,a
rla
jr nc,notneg
dec d
res 7,e
notneg:
ret
Using this to update an object's position is easy:
ld a,(BallAngle)
call LoadSine16
ld hl,(BallY)
add hl,de
ld (BallY),hl
ld a,(BallAngle)
call LoadCosine16
ld hl,(BallX)
add hl,de
ld (BallX),hl
For some good working code, I suggest taking a look at Matthew Shepcar's
peaworm game. You can probably just steal the trig routines from there, but
I highly suggest understanding how they work before just pasting them into
your code.
> 2. A second option would be to just put fp numbers in the table (if that's
> possible) so you would get something like this: .db ...,0.531287,...
> (This would also be more precise) and then you load that number directly
in
> a register (ld hl,(sintable+5) for example), but then i have another
> problem: how do you multiply a register pair with a certain number? (with
> single registers i would use (_htimesl))
This would be very inefficient, and not recommended.
> 3. Maybe the third option is for you guys?
If you were going to do floating point numbers yourself on the z80, which
doesn't have an fpu, a good method would be to use bcd. This is how the rom
handles floating point numbers. Some bcd operations can take a lot of
memory, such as multiplication and division. But it is still decently fact
and is accurate.
References: