# Circular motion on low powered hardware

I was thinking about platforms and enemies moving in circles in old 2D games, and I was wondering how that was done. I understand parametric equations, and it's trivial to use sin and cos to do it, but could an NES or SNES make real time trig calls? I admit heavy ignorance, but I thought those were expensive operations. Is there some clever way to calculate that motion more cheaply?

I've been working on deriving an algorithm from trig sum identities that would only use precalculated trig, but that seems convoluted.

• I was actually asked this question during a job interview several years ago. Jun 18 '12 at 4:10

On hardware such as you are describing, a common solution to the general case is to simply produce a look-up table for the trigonometry functions one was interested in, sometimes in conjunction with fixed-point representations for values.

The potential issue with this technique is that it consumes memory space, although you can downplay this by settling for a lower resolution of data in your table or by taking advantage of the periodic nature of some functions to store less data and mirror it at runtime.

However, for specifically traversing circles -- either to rasterize them or to move something along one, a variation of Bresenham's line algorithm can be employed. Bresenham's actual algorithm, of course, is also useful for traversing lines that are not in the eight "primary" directions quite cheaply.

• True story. LUT and a circle is defined as 256 degrees yield cheap trig, mirroring was only done if memory was tight and as a last resort to gain a few bytes. The Bresenham reference is spot on for different movement, too. Jun 18 '12 at 3:43
• Even on modern hardware, a trig call is still a lookup table. It's just a lookup table in hardware, with some refinement via a Taylor expansion. (In fact one major console manufacturer's implementation of a SIMD sin() function is simply a hardcoded Taylor series.) Jun 18 '12 at 4:07
• @Crashworks: there is absolutely no way it's a Taylor series, it would be really stupid of them. It's most probably a minimax polynomial. Actually, all modern implementations of sin() I have ever seen are based on minimax polynomials. Jun 18 '12 at 15:01
• @SamHocevar Could be. I just saw the summing up of ax + bx^3 + cx^5 + ... and assumed "Taylor series". Jun 18 '12 at 22:45

There's a variation of Bresenham's algorithm by James Frith, which should be even faster since it completely eliminates multiplication. It doesn't need any lookup table to achieve this, although one could store the results in a table if the radius stays constant. Since both Bresenham's and Frith's algorithm use 8-fold symmetry, this lookup table would be relatively short.

// FCircle.c - Draws a circle using Frith's algorithm.
// Email:  jfrith@compumedia.com

typedef unsigned char   uchar;
typedef unsigned int    uint;

extern void SetPixel(uint x, uint y, uchar color);

// FCircle --------------------------------------------
// Draws a circle using Frith's Algorithm.

void FCircle(int x, int y, int radius, uchar color)
{
int balance, xoff, yoff;

xoff = 0;

do {
SetPixel(x+xoff, y+yoff, color);
SetPixel(x-xoff, y+yoff, color);
SetPixel(x-xoff, y-yoff, color);
SetPixel(x+xoff, y-yoff, color);
SetPixel(x+yoff, y+xoff, color);
SetPixel(x-yoff, y+xoff, color);
SetPixel(x-yoff, y-xoff, color);
SetPixel(x+yoff, y-xoff, color);

balance += xoff++;
if ((balance += xoff) >= 0)
balance -= --yoff * 2;

} while (xoff <= yoff);
} // FCircle //

• If you're getting weird results, it's because you're invoking undefined (or at least unspecified) behavior. C++ doesn't specify which call is evaluated first when evaluating "a() + b()", and further calls out modifying integrals. To avoid this, don't modify a variable in the same expression you read it as in xoff++ + xoff and --yoff + yoff. Your changelist will fix this, consider fixing it in place instead of as a tack on note. (See section 5 paragraph 4 of the C++ standard for examples and the standardese that explicitly calls this out) Jun 20 '12 at 16:22
• @MaulingMonkey: You're right about the problematic evaluation order of balance += xoff++ + xoff and balance -= --yoff + yoff. I left this unchanged, as this was the way Frith's algorithm was originally written, with the fix later added by himself (see here). Fixed now. Jun 20 '12 at 19:16

You can also use an approximated version of trig functions using Taylor Expansions http://en.wikipedia.org/wiki/Taylor_series

For example, you can have a reasonable approximation of sine using it's first four taylor series terms

• This is generally true, but comes with so many caveats that I'd go so far as to say you should virtually never write your own sin() code unless you're very familiar with what you're doing. In particular, there are (marginally) better polynomials than the one listed, even better rational approximations, and you need to understand where to apply the formula and how to use the periodicity of sin and cos to narrow down your argument to a range where the series applies. This is one of those cases where the old aphorism 'a little knowledge is a dangerous thing' rings true. Jun 20 '12 at 21:28
• Can you give some references so I can learn this polynomials or other better approximations? I really want to learn that. This series thing were the most mind blowing part of my calculus course.
– user9471
Jun 21 '12 at 0:12
• The classic place to start is the book Numerical Recipes, which gives a fair bit of information on computing the core numerical functions and the mathematics behind their approximations. Another place that you might look, for an approach that's a bit outdated but still worth knowing about, is to look up the so-called CORDIC algorithm. Jun 21 '12 at 0:27
• @Vandell: if you want to create minimax polynomials, I'd be happy to hear your thoughts about LolRemez. Jun 21 '12 at 0:38
• The Taylor series approximates the behaviour of a function around a single point, not on an interval. The polynomial is great for evaluating sin(0) or its seventh derivative around x=0, but the error at x=pi/2, after which you can simply mirror and repeat, is quite large. You can do about fifty times better by evaluating the Taylor series around x=pi/4 instead, but what you really want is a polynomial that minimises the maximum error on the interval, at the cost of precision near a single point. Jun 21 '12 at 11:37

One awesome algorithm to travel uniformly over a circle is the Goertzel algorithm. It requires only 2 multiplications and 2 additions per step, no lookup table, and a very minimal state (4 numbers).

First define some constants, possibly hardcoded, based on the required step size (in this case, 2π/64):

float const step = 2.f * M_PI / 64;
float const s = sin(step);
float const c = cos(step);
float const m = 2.f * c;


The algorithm uses 4 numbers as its state, initialised like this:

float t[4] = { s, c, 2.f * s * c, 1.f - 2.f * s * s };


And finally the main loop:

for (int i = 0; ; i++)
{
float x = m * t[2] - t[0];
float y = m * t[3] - t[1];
t[0] = t[2]; t[1] = t[3]; t[2] = x; t[3] = y;
printf("%f %f\n", x, y);
}


It can then go forever. Here are the first 50 points:

The algorithm can of course work on fixed point hardware. The clear win against Bresenham is the constant speed over the circle.