Wednesday, 26 September 2007

Java Fixed Point Maths

One of the first things I wrote when I started J2ME was a set of fixed point maths routines. I've seen quite a few others over the years, for Java and other languages, and they all seemed to follow the same pattern: sin and cos tables, plus a few methods for basic operations (multiply and divide, usually). The one I offer here, which in various guises and languages has served me well since forever, is a little more advanced (not much, but enough for most mobile games and applications).

The sin and cos (and by extension tan) routines are still table based, but instead of providing the table in-line with the code, it's generated using recursive synthesis at runtime. The advantage here is that the class can be quickly tailored for less or more fixed point precision, depending on the use (16.16 for general usage, 12.20 for audio work, etc.). There's also a fast atan, which was most useful for the physics and AI in Jet Set Racing (seen here, and Opposite Lock, seen here), plus a few other bits and bobs.

Most of the algorithms I devised myself, unless otherwise noted in the comments. The precision is pretty good (I have a test suite for it somewhere) but don't go taking my word for it, find out for yourself!

9 comments:

Sergey said...

It would be nice If you clarify the license. The preferable licenses are Public Domain and BSD considering the size of the code.

Otherwise the code can only be used as reference which probably was not your intention :)

Carl Woffenden said...

Hi! My intention with anything on my blog, unless specifically stated, is that it's all under a permissive licence with attribution. That's all a little vague, I realise, so let's say that it's BSD.

Carl

Cyber Axe said...
This comment has been removed by the author.
Carl Woffenden said...

Hi! It's in there, it's the two parameter atan call.

Cyber Axe said...

Thanks, I'd figured that was the case (hence why I deleted my comment after asking),

I've been unable to get the correct angle since converting from doubles to fixed point using that atan function and I'm pretty confident that's where the problem lies as everything else seems to work fine from testing.

Carl Woffenden said...

Send me a quick example of where it's going wrong and I'll take a look. One thing that may be happening is overflow in the fixed point calculations (for example, in 16:16 fixed point 256 * 128 will overflow).

Cyber Axe said...

final Viewport viewport = player.getViewport();

final int playerX = player.getX();
final int playerY = player.getY();

// Calculate the Direction to fire in.
final int fDirectionX = Fixed.intToFixed(player.getPlayerMovement().pointerX() - (playerX - viewport.getCamX()));
final int fDirectionY = Fixed.intToFixed(player.getPlayerMovement().pointerY() - (playerY - viewport.getCamY()));

final int fAngle = Fixed.atan(fDirectionX, fDirectionY);

fAngle is then used to fire a bullet in that direction, but I'm only getting a small cone left and right regardless, it's very possibly an overflow issue as you suggest.

Also tried it with fDirection variables being non fixed point numbers.

Thanks

Carl Woffenden said...

What are typical values for fDirectionX and fDirectionY?

Cyber Axe said...

typically in the range of -512 to 512 before fixed point converstion