This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Basic 6502 Trigonometry

Basic 6502 Trigonometry
by on (#178115)
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
* Add or subtract angle
* 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?
Re: Basic 6502 Trigonometry
by on (#178118)
I wrote some multiply, divide, sine, cosine, arctangent, and distance routines for Thwaite and RHDE.
Re: Basic 6502 Trigonometry
by on (#178120)
You can also normalize without trig. Convert to a unit vector (squares, square root, divisions) then multiply by magnitude.
Re: Basic 6502 Trigonometry
by on (#178125)
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.
Re: Basic 6502 Trigonometry
by on (#178132)
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.
Re: Basic 6502 Trigonometry
by on (#178133)
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.
Re: Basic 6502 Trigonometry
by on (#178193)
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:
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.
Re: Basic 6502 Trigonometry
by on (#178482)
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.