It is currently Sun Oct 22, 2017 10:34 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Basic 6502 Trigonometry
PostPosted: Wed Aug 24, 2016 5:22 am 
Offline
User avatar

Joined: Sun May 27, 2012 8:43 pm
Posts: 1306
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?


Top
 Profile  
 
PostPosted: Wed Aug 24, 2016 5:56 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 19115
Location: NE Indiana, USA (NTSC)
I wrote some multiply, divide, sine, cosine, arctangent, and distance routines for Thwaite and RHDE.


Top
 Profile  
 
PostPosted: Wed Aug 24, 2016 6:14 am 
Offline
User avatar

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 3943
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!


Top
 Profile  
 
PostPosted: Wed Aug 24, 2016 8:43 am 
Offline
User avatar

Joined: Sat Feb 12, 2005 9:43 pm
Posts: 10066
Location: Rio de Janeiro - Brazil
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.


Top
 Profile  
 
PostPosted: Wed Aug 24, 2016 11:25 am 
Offline
User avatar

Joined: Fri Nov 19, 2004 7:35 pm
Posts: 3943
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!


Top
 Profile  
 
PostPosted: Wed Aug 24, 2016 11:27 am 
Offline
User avatar

Joined: Fri Nov 12, 2004 2:49 pm
Posts: 7234
Location: Chexbres, VD, Switzerland
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.


Top
 Profile  
 
PostPosted: Wed Aug 24, 2016 8:53 pm 
Offline
User avatar

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

_________________
.


Top
 Profile  
 
PostPosted: Sun Aug 28, 2016 5:11 am 
Offline
User avatar

Joined: Mon Nov 27, 2006 11:56 pm
Posts: 85
Location: Sollentuna, Sweden
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group