Smooth physics with fixed point numbers

Even on a primitive system like the NES, gamers will want something that feels like it matches their real-world intuition. That means at least some rudimentary physics. The problem is computation time and space to put all the necessary data. All hope is not lost though, and we can simulate some useful real-world-ish behavior.

In this chapter, we'll build up a jump action for our player, one that's fast to simulate, but still accurate enough to feel inuitive. To achieve the right accuracy, our regular 8-bit integers won't cut it. We'll need fractions, and we'll need fractions that are fast to compute with.

Representing fractional values as integers

Modern computers contain hardware to deal with non-integer values. This hardware is known as floating point hardware. I'll talk more about the name later, but it's important to realize the NES (really the 6502) contains no such hardware. So what do we do when we want to work with fractional values?

One easy way to think about this is to think about currency, let's say dollars and cents, or whatever your local equivalent is. Suppose you want to represent the value $12.34, but you can only use integers. Well, what if we decided, as a matter of convention, that we will represent monetary values in cents? So $12.34 becomes the integer 1234. Now, when I tell you the number 1234, you will mentally divide by 100 and understand I was trying to tell you the value $12.34. This only works because I'm always giving you the real value multiplied by 100. That means if I want to represent $12 as an integer, I have to say 1200, even though 12 is already an integer. The value 12 means $0.12.

To build our intuition before talking binary representations, let's explore this in base-10. Click on the digits to change their values. Note the "weight" of each digit under that digit. See how each digit decreases in weight by a factor of ten, including in the fractional part of the number?

This is known as a fixed point representation, because the decimal point is always at a fixed location. In the above example, the decimal point is always two spaces from the right, meaning you always divide any value by 100 to get the actual (potentially non-integer) value we wanted to represent. We would call this a 3.2 base-10 fixed point representation, as we have three digits before the decimal point and two digits after.

Fixed point in binary

Representing a non-integer number with a fixed point binary representation works the same way as above, just with powers of two instead of powers of ten. Try representing the number 2.5 by changing the binary digits below:

Notice we might not not use all the digits in the fractional part, but we have to leave space for them and set them to zero. To be fair, we have to do the same for the integer part, where we may not use all the high-weight digits. This particular example uses four integer bits and four fractional bits, so the number above is in a 4.4 binary fixed point representation.

Multi-byte numbers

A big problem with fixed point (and the reason for using floating point in modern hardware) is the inherent trade-off between more fractional precision and less integer range. For example, in the 3.2 base-10 example above, we can only represent numbers as high as 999.99, even though we have five digits to work with. If we didn't use up two digits for the fractional part, we could have gone up to 99999. The same applies for the 4.4 binary example, where we can only represent numbers as high as 15.9375 despite having eight bits.

This is going to be a problem when trying to represent fractional y-coordinates for our player. We want fractions, but we still want the full 0-255 range of an 8-bit integer. To solve this problem, we can use a little extra space: two bytes to represent a single number. That gives us sixteen bits total, which we can use with an 8.8 binary fixed point representation.

TODO: show representation in memory, and how to add and round this number

Representing negative values

Implementing a jump with fixed point

64
(01000000)

0
(00000000)

64
 

252
(11111100)

112
(01110000)

-3.5625
 

0
(00000000)

32
(00100000)

0.125