This app moved from a floating point to a fixed point physics engine, to ensure it behaved the same way on all platforms.
The fixed point API
The API for dealing with the fixed point numbers is pretty simple:
typedef struct {long long v;} real;
static inline real real_i(int v);
static inline real real_f(double v);
static inline real real_0(void);
static inline real real_1(void);
static inline real real_mpy(real a, real b);
static inline real real_square(real a);
static inline real real_sub(real a, real b);
static inline real real_neg(real a);
static inline int real_to_int(real a);
static inline double real_to_double(real a);
static inline real real_add(real a, real b);
static inline real real_div(real a, real b);
static inline real real_sqrt(real a);
static inline int real_gt(real a, real b);
static inline int real_lt(real a, real b);
static inline int real_lte(real a, real b);
static inline real real_abs(real a);
static inline int real_eq(real a, real b);
static inline real real_from_bytes(unsigned char b0, unsigned char b1, unsigned char b2, unsigned char b3);
static inline void real_to_bytes(real r, unsigned char *b0, unsigned char *b1, unsigned char *b2, unsigned char *b3);
static inline unsigned long real_to_u32(real r);
static inline real real_random(real min, real max);The philosophy used is to just implement the functions needed, so while there is a “>” (real_gt()), a “<” (real_lt()) and a “<=’ (real_lte()), there is no “>=” – purely because it wasn’t ever needed.
Most of the functions are trivial – conversion to and from this representation is just scaling by powers of two. Convenience functions for “1.0” and “0.0” help. Multiply is just an integer multiply and scale, addition, subtraction, and negation are just addition, subtraction, and negation.
The only function that needed more creativity was real_sqrt(). In this game, it is used in two places:
- When the slingshot is pulled back too far (easy to calculate without sqrt), where should the stone be? (use sqrt to normalize vector, then multiply by maximum distance).
- When a circular object (bird or stone) hits another (easy to calculate without sqrt), which direction should the collision force act in? (normalize the vector from on object to the other, and use that)
Both of these cases are executed infrequently (maximum of once per frame for the first case, and just a handful of times per “launch” in the second), and if things aren’t perfect, then they are fine:
- It isn’t really a problem if the player can pull the sling back a bit too far, or not quite far enough, as long as it looks and feels right.
- If the collisions aren’t mathematically perfect, then we have to remember that a bird isn’t a perfect circle, nor is a stone.
Aside: Other shapes
The world of Two Birds One Stone consists of the ground (a rectangle covering half the plane), a circular stone, and some circular birds. It is possible to make things different by introducing different shapes.
Early on, experiments were done with triangular objects, and it never felt as fun as the simple world we have now. One of the nice things about these shapes is that the collisions are all predictable – a triangular bird hitting another triangular bird will result in very different outcomes depending on the rotation of the two triangles. It ends up feeling chaotic, and as the player, you don’t really feel like you are in control.
As a result, these other shapes were removed, and we have the simple, but nice and predictable world of circles (plus a giant fixed rectangle).
Representation
I represented numbers as a struct like this:
typedef struct {long long v;} real; Wrapping it in a struct means that I (deliberately) lose the ability to use the built in operators like +, *, ==, etc. It isn’t strictly necessary, and things would be fine without, but it can catch silly mistakes, and make sure it is possible to do things like add an extra element with a double in it which we can use to track how different our results would be if we used floating point.
I let the bottom 16 bits of v be fractional, which leaves at least 47 bits of integer range (plus 1 sign bit). I didn’t fiddle around with this too much, 47 bits is heaps of range, and 16 bits is heaps of precision.
It would probably be possible to fit everything in just a long (which is only guaranteed to be 32-bits or more – and is indeed only 32-bits for iOS builds), and indeed I did originally do this, however then I would only have 15 bits of integer range (32767 being the largest 15-bit integer), which we overflow when we try to square anything from 182 up – we do a lot of squaring to find the distance between things, and frequently things are more than 182 units apart with my scaling. To fit things in 32-bits, we could reduce precision, but it seems much easier to just throw another 32-bits at the range and be done with it.
With this, we can think of v as just storing the fractional value, but scaled by 0x10000.
Multiply and Divide
Multiplying two fixed point numbers is easy (provided no overflow). We just use an integer multiply. This multiplies the numbers, but also the scaling factor of 0x10000, we want our result to still be scaled by 0x10000, so all we need to do is divide by 0x10000 again, and we are back to the correct scaling.
Division uses the reverse logic – do an integer divide, but now we have cancelled out our scale factor, so we need to multiply by 0x10000 – but if we do things in this order, we lose precision – so instead we multiply by 0x10000 first then do the integer divide.
Aside: Divide and multiply not shift?
I have been talking about dividing and multiplying by 0x10000 which is a nice power of two. Should I instead talk about shifts of 16 either left (multiply) or right (divide)? In short – no.
Shifts in C on signed types are weird. I’m a C90 lover, and I can never read the spec on what is and isn’t defined here and come away feeling confident that I’ve got it right. C99 cleaned up the specification’s language around this topic, and from memory made it clear that you should be scared if the sign bit is set and you are doing shifts (which is reasonable, since the C standard allows for two’s complement, one’s complement, and sign magnitude representations of signed numbers).
For division, even if your shift right is “arithmetic”, the behaviour is unhelpful – the rounding goes the wrong way: -1 >> 16 == -1. Probably not an issue for two birds, but I’ve seen it cause problems where IIR filters are a bit more “Infinite” in their impulse response than intended.
Since I just want division and multiplication, I write them plain, but make sure the factor they are dividing or multiplying by is a constant that the compiler can see, so it can generate the best code (which tends to be shifts).
Square Root Implementation
Multiplication and division are pretty trivial (well, division could be trickier if we decided to avoid the multiply or division operator, but that isn’t solving any problems we have here). Square root is a little bit more involved, but doesn’t need to be too tricky:
I use the Newton-Rhapson method. It looks like this:
sqrt(a)
1. x = initial_estimate
2. repeat until good enough
3. x = x + (a - x*x)/2x
4. return xHow good is good enough? I hardcoded 10 repetitions. Checking for how much error and declaring that to be good enough is possible, but probably not appropriate here – predictable timing and simplicity is more helpful than accuracy.
My simple attempt to calculate the initial estimate resulted in integer overflows for some of the numbers I was dealing with, so I needed to do something to fix this. My approach was to first try to calculate the integer square root, using the same approach, but this time instead of using fixed point arithmetic, I used integer arithmetic.
Is that all?
There is actually plenty of floating point code in Two Birds One Stone – only the core game logic is fixed point, once it comes to displaying it on the screen, there is plenty of floating point – e.g. the sprite rotations and camera zooming. It doesn’t really matter if this behaves slightly differently across different devices (and in fact, we expect zooming to behave differently, because we will have different screen resolutions).