How to describe a circle trajectory on nes?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: How to describe a circle trajectory on nes?

Post by psycopathicteen »

I was responding to your above post.
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.
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: How to describe a circle trajectory on nes?

Post by rainwarrior »

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.
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: How to describe a circle trajectory on nes?

Post by psycopathicteen »

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
bogax
Posts: 34
Joined: Wed Jul 30, 2008 12:03 am

Re: How to describe a circle trajectory on nes?

Post by bogax »

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.
zzo38
Posts: 1096
Joined: Mon Feb 07, 2011 12:46 pm

Re: How to describe a circle trajectory on nes?

Post by zzo38 »

One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:

Code: Select all

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.
(Free Hero Mesh - FOSS puzzle game engine)
kuja killer
Posts: 130
Joined: Mon May 25, 2009 2:20 pm

Re: How to describe a circle trajectory on nes?

Post by kuja killer »

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 :(
User avatar
rainwarrior
Posts: 8734
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: How to describe a circle trajectory on nes?

Post by rainwarrior »

zzo38 wrote:One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:

Code: Select all

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: Select all

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.
Attachments
minsky_test.zip
(546 Bytes) Downloaded 171 times
bogax
Posts: 34
Joined: Wed Jul 30, 2008 12:03 am

Re: How to describe a circle trajectory on nes?

Post by bogax »

rainwarrior wrote:
zzo38 wrote:One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:

Code: Select all

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: Select all

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)
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: How to describe a circle trajectory on nes?

Post by psycopathicteen »

Here's a similar question. Has anybody ever did a sine*amplitude thing on an SNES without using the mode 7 registers?
Post Reply