This page is a mirror of Tepples' nesdev forum mirror (URL TBD).

# How to describe a circle trajectory on nes?

Simple, I know radius and angle.

I want to obtain X and Y positions

In real life, I would simply use sinus for the first unknown, then pythagore for the second one.

However I don't have a sin function neither a square root function.

I wouldn't want to enter values by hand in an array...

is there a better way?
A lookup table is effective, but since you've ruled that out...

If you can compromise on the shape a little bit, and would accept a circle-like curve, you might try a second-order approximation by just accelerating something alternately up, right, left, down at a fixed rate. i.e. accelerate right for 1 second, then accelerate down for 1 second... the object should travel in a stable curved path. Controlling the speed and radius specifically is a bit tricky, but it's not too hard to just tweak it until it looks right as an easier method.

* Also your starting velocity has to be 90 degrees rotated from your starting acceleration, or else you might get a diagonal oscillation instead of circular, i.e. if you start by accelerating up, set the initial velocity to full left, etc.

You can also use this kind of thing to seek toward a point, the value you clamp velocity at will determine the radius of the orbit.

You can also use this idea in 2D for a simple up-down sine-like motion (e.g. castlevania medusa).
MartsINY wrote:
Simple, I know radius and angle.

I want to obtain X and Y positions
[...]
I wouldn't want to enter values by hand in an array...

is there a better way?

Yes: a Python script to generate the array that you bake into the ROM.
tepples wrote:
MartsINY wrote:
Simple, I know radius and angle.

I want to obtain X and Y positions
[...]
I wouldn't want to enter values by hand in an array...

is there a better way?

Yes: a Python script to generate the array that you bake into the ROM.

Is that easy to incorporate the python script? Can you export the assembly and use it somehow?
A table generator program just needs to write a file full of .byte statements that you .include in your main assembly file. An example of such a table generator for an exponential function is at APU period table. It should be straightforward to adapt it to a sine table.
Isn't that doing exactly what you said you didn't want to do? rainwarrior's solution looks good.
A table generator avoids the "by hand" in "I wouldn't want to enter values by hand in an array."
nesrocks wrote:
Isn't that doing exactly what you said you didn't want to do? rainwarrior's solution looks good.

yeah I though of a table with X and Y this I didn't want.

However a table with sin and cos values would be better.

I will generate one through matlab

thanks!!
MartsINY wrote:
However a table with sin and cos values would be better.

But then you need multiplications to do anything useful with those look-up tables. The 6502 isn't particularly good with multiplications, but you can do a handful of them per frame if you really need to. Just something to keep in mind.
tokumaru wrote:
MartsINY wrote:
However a table with sin and cos values would be better.

But then you need multiplications to do anything useful with those look-up tables. The 6502 isn't particularly good with multiplications, but you can do a handful of them per frame if you really need to. Just something to keep in mind.

thanks!! actually I'm lucky mega man has a multiplication function!!
There is a way to multiplying a sine wave by adding two sine waves. I'm not sure how much precision it would have.
If you really want to do it without a lookup table, you could approximate the value using the Taylor series for sin/cos, calculated out to some degree of precision.
https://en.wikipedia.org/wiki/Taylor_series#Trigonometric_functions

But then you'd need functions for division, exponentiation, and factorial all without lookup tables...
By the time you coded that all up, it would likely use more ROM than just having the original, single lookup table.
Those Taylor series are just one of many ways to compute that stuff, and they're really not a good way to go about it on 6502.

This is a well known set of techniques that's actually designed for this kind of hardware:
https://en.wikipedia.org/wiki/CORDIC

psycopathicteen wrote:
There is a way to multiplying a sine wave by adding two sine waves. I'm not sure how much precision it would have.

Yes, it's due to the family of identities that relate multiplication to sum and difference, e.g.:

cos(a) * cos(b) = (cos(a+b) + cos(a-b)) / 2

So if you have a cosine/sine table, you can get the multiplied result with a few sums, a few lookups, and a shift. Each step loses some precision, yes. I've half-written an NES demo experimenting with this concept but I haven't gotten around to finishing it yet.

Though, if you only need one size of circle you don't need any multiplication, just scale your sine table to the size of the circle to begin with. You only need to be multiplying if you are trying to reuse one sine table at various scales.
If the sine table goes from -127 to 127, you would need at least 1024 sine table entries for every step.
Where does the number 1024 come from?

The table is not a sine table but a sine * radius table. If you want to make a circle trajectory with a table, you only need as many entries as desired angles and radii. The only reason to have a sine table with separate multiplication step is if you need to have many different radius trajectories, or some other use for the sine.

e.g. If you only wanted a single radius, and to travel the circle in 64 frames, you could just have 64 entries in the table. You could also interpolate entries to shrink the table size as well, if you wanted to make some size/accuracy trade.
I was responding to your above post.

Quote:
Yes, it's due to the family of identities that relate multiplication to sum and difference, e.g.:

cos(a) * cos(b) = (cos(a+b) + cos(a-b)) / 2

So if you have a cosine/sine table, you can get the multiplied result with a few sums, a few lookups, and a shift. Each step loses some precision, yes. I've half-written an NES demo experimenting with this concept but I haven't gotten around to finishing it yet.

1024 angle steps gives you no gaps in amplitude for 8-bit values.
psycopathicteen wrote:
1024 angle steps gives you no gaps in amplitude for 8-bit values.

Oh, well the precision of your angle is one thing, and the precision of the sine/cosine result is another, and both of them have a bearing on how precise things are. Being able to represent every integer output value is not sufficient to make it completely precise (to that output grandularity). So, 1024 steps is more accurate than 256, but there's lots of precision lost from the 8-bit output quantization too, so you'd also get improvements from making the output wider too. There's not really a clear break point to me for precision, it's a big pile of tradeoffs.

MartsINY wrote:
In real life, I would simply use sinus for the first unknown, then pythagore for the second one.

From the way you described this, might be worth pointing out that cos(x) = sin(x+90°) so if you have sine you have cosine available as well. If it's a table lookup, one table does both.
This has some nice multiplication algorithms. It uses some self modifying code, so you might want to change abs,x to (dp),y for it to run on the NES.

http://codebase64.org/doku.php?id=base: ... iplication
Here's code (6502.org) for a simple parabolic approximation of a sine wave.

If you run two instances 90 degrees apart that will give you something like a circle.

Of course, it's incremental not random access.

There's an example here (AtariAge) in Batari Basic.
One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:
Code:
for(;;) {
y-=epsilon*x;
x+=epsilon*y;
plot(x,y);
}

The value epsilon is less than one. If it is 1/256 then you do not need to implement multiplication/division; you can just use the carrying (you do not even need bit shifting). Note that these coordinates are signed numbers, which complicates the implementation a bit.
https://pastebin.com/tFdQj6VC

here's a really interesting file from Puresabe, ..from rockman 4 minus infinity, which i've been able to implement into my game.

I only had to change the raw hex numbers on a couple of the JSR's, and stuff, to match the megaman 3 versions, and then it worked like a charm.
This is the un-edited rockman 4 minus infinity file i gotten from him originally

I do not really understand how this works, but it can do circles very "butter smooth" though ..oh yea, it uses the MMC5's multiply registers 5205/5206 though. (not shown here)

comments are in japanese though..sorry zzo38 wrote:
One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:
Code:
for(;;) {
y-=epsilon*x;
x+=epsilon*y;
plot(x,y);
}

The value epsilon is less than one. If it is 1/256 then you do not need to implement multiplication/division; you can just use the carrying (you do not even need bit shifting). Note that these coordinates are signed numbers, which complicates the implementation a bit.

This is very interesting!

It seems that as epsilon gets larger, it becomes more elliptical, diagonally oblong. As epsilon gets smaller it becomes more circular.

At first glance it seems similar to just rotating a 2D point, which is one of the "normal" ways to produce a circle:
Code:
ox = x;
oy = y;
a = cos(angle); // constant
b = sin(angle); // constant
x = a * ox - b * oy;
y = b * ox + a * oy;

But in your Minsky example only has one multiply, not two, and the way the Y update feeds back into the X update instead of using a temporary value makes the actual result kinda complicated to analyze. I feel like each iteration does like half of an approximation of the rotation somehow?

The speed of the rotation is dependent on epsilon, so probably you're limited to power-of-2-ish factors for epsilon unless you want a full generic multiply, but it does appear to be quite stable (I was testing it with 8.8 fixed point) and easy to control the radius because it stays on the circle you start X/Y on!

I wrote a simple processing sketch to test it, attached below. Click the mouse to pick a starting point for X/Y, and press A/Z to adjust epsilon.
rainwarrior wrote:
zzo38 wrote:
One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:
Code:
for(;;) {
y-=epsilon*x;
x+=epsilon*y;
plot(x,y);
}

The value epsilon is less than one. If it is 1/256 then you do not need to implement multiplication/division; you can just use the carrying (you do not even need bit shifting). Note that these coordinates are signed numbers, which complicates the implementation a bit.

This is very interesting!

It seems that as epsilon gets larger, it becomes more elliptical, diagonally oblong. As epsilon gets smaller it becomes more circular.

At first glance it seems similar to just rotating a 2D point, which is one of the "normal" ways to produce a circle:
Code:
ox = x;
oy = y;
a = cos(angle); // constant
b = sin(angle); // constant
x = a * ox - b * oy;
y = b * ox + a * oy;

But in your Minsky example only has one multiply, not two, and the way the Y update feeds back into the X update instead of using a temporary value makes the actual result kinda complicated to analyze. I feel like each iteration does like half of an approximation of the rotation somehow?

The speed of the rotation is dependent on epsilon, so probably you're limited to power-of-2-ish factors for epsilon unless you want a full generic multiply, but it does appear to be quite stable (I was testing it with 8.8 fixed point) and easy to control the radius because it stays on the circle you start X/Y on!

I wrote a simple processing sketch to test it, attached below. Click the mouse to pick a starting point for X/Y, and press A/Z to adjust epsilon.

Some discussion here (HACKMEM in html)
Here's a similar question. Has anybody ever did a sine*amplitude thing on an SNES without using the mode 7 registers?