## Basic 6502 Trigonometry

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

mikejmoffitt
Posts: 1352
Joined: Sun May 27, 2012 8:43 pm

### Basic 6502 Trigonometry

I have two 8Q8 fixed point variables, dx and dy. As an object moves at some angle (calculated via arctan(dy/dx)) and some speed (sqrt((dx^2) + (dy^2))), I need to be able to change its angle on a whim.

Mathematically, we're looking at the following process:

* Get angle from arctan(dy/dx)
* Get speed from distance formula
* Use cosine and sine to get new dx/dy coefficients
* Multiply coefficients by stored speed

Does anybody have recommended 6502 routines and tables for this, before I have a go at doing it myself?

tepples
Posts: 22221
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

### Re: Basic 6502 Trigonometry

I wrote some multiply, divide, sine, cosine, arctangent, and distance routines for Thwaite and RHDE.

Dwedit
Posts: 4390
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

### Re: Basic 6502 Trigonometry

You can also normalize without trig. Convert to a unit vector (squares, square root, divisions) then multiply by magnitude.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

tokumaru
Posts: 11929
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

### Re: Basic 6502 Trigonometry

Whenever I need trigonometry, I try to pack as many operations at once into lookup tables, to reduce the overall number of steps necessary to accomplish something. In my raycaster, for example, I have a table of distances to the next wall boundary for each angle, and fish-eye corrected for each screen angle. If you have the ROM to spare, this can simplify things a bit.

Dwedit
Posts: 4390
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

### Re: Basic 6502 Trigonometry

There was that integer square root algorithm where you subtract 1, 3, 5, 7, 9... then the number of times you subtracted was the square root.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!

Posts: 8007
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

### Re: Basic 6502 Trigonometry

In the game I am developing there's somewhere where I used the integer square root algorithm to shoot homing projectiles, it works great, and uses half the ROM of what a lookup table did. So yeah, using tedious algorithms is sometimes worth it.

zzo38
Posts: 1076
Joined: Mon Feb 07, 2011 12:46 pm

### Re: Basic 6502 Trigonometry

One way to form almost a circle is by the circle algorithm described in HAKMEM; only addition, subtraction, and right-shifts, are needed. Depending on what needs to be done, this might be sufficient (you will still have to write in yourself the programming for dealing with positive/negative). (I suggest making the "epsilon" parameter to be 1/256 if programming it on 6502; now you do not even need shifts.) This might not be sufficient for what you need though (but see what Bregalad wrote for homing projectiles), however I mention it in case it is useful to you or anyone else for some other purpose.

Circle algorithm is:

Code: Select all

``````NEW_X = OLD_X - EPSILON * OLD_Y
NEW_Y = OLD_Y + EPSILON * NEW_X``````
For multiplication, one algorithm is "quarter square" algorithm (there is also the Russian algorithm, which is slower, but does not require a lookup table). By a bit of algebra, it can be seen that ((x+y)2-(x-y)2)/4=xy (when I learned about this algorithm, my first idea was to do such algebra in order to see that). You can round down (x+y)2/4 and (x-y)2/4 and it will still work. Therefore, you can store the quarter of the square of the numbers in a lookup table, and then look up (x+y) and (x-y) and subtract them. You can also use it with 16-bit numbers, you can consider the two numbers to multiply as (256a+b) and (256c+d) and then (256a+b)(256c+d)=65536ac+256bc+256ad+cd and if you keep only the low 16-bits (i.e. modulo 65536), same as 256(bc+ad)+cd.
Dwedit wrote:There was that integer square root algorithm where you subtract 1, 3, 5, 7, 9... then the number of times you subtracted was the square root.
While I have never heard of this algorithm before, it does make sense. The sum of (2x-1) for x from 1 to n equals n squared, so if you subtract such numbers to form part of the sequence then you can make the square root.
[url=gopher://zzo38computer.org/].[/url]

Anders_A
Posts: 88
Joined: Mon Nov 27, 2006 11:56 pm
Location: Sollentuna, Sweden

### Re: Basic 6502 Trigonometry

mikejmoffitt wrote: * Get angle from arctan(dy/dx)
* Get speed from distance formula
I would probably store the vector as angle and speed instead of dy and dx to get rid of this step, and simply represent your angle change as an addition.

For optimization I'd guess you'd want to store dx and dy everytime you recalculate for movement it as well, but not as your main definition of the vector.

Going from angle and speed to dx and dy is just a matter of two sin lookups and two multiplications.