It is currently Thu May 23, 2019 7:48 pm

 All times are UTC - 7 hours

 Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Game math libraryPosted: Thu Jul 11, 2013 5:44 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21397
Location: NE Indiana, USA (NTSC)
I began a library of 6502 game math subroutines when building the game Thwaite. And with the announcement that uc65 would likely ship without multiply and divide operators, I'm considering offering it as a self-contained library. Here's what I have so far:
• Multiply A by Y, 8 bits, about 150 cycles
• Divide floor(256 * A / Y), for converting rise and run to an 0.8 fixed-point slope
• Arctangent, producing the angle of the vector from (a, b) to (c, d) in units of 1/32 turn, within 380 cycles
• Square root of a 16-bit number within 520 cycles
• Unrolled binary to decimal conversion, 8 bits to 3 digits, within 80 cycles
• Looping binary to decimal conversion, 16 bits to 5 digits, within 652 cycles
• Percentage calculator, producing the decimal expansion of a/b with 16-bit numerator and denominator to up to five digits at 230 cycles per digit. Useful for accuracy counters like the one on Galaga's debrief screen.

I built it alongside a basic 6502 simulator written in Python so that I could exhaustively verify the subroutines' correctness. This way I make sure that what the subroutine thinks is 23 * 45 matches what Python thinks is 23 * 45. I tested the simulator itself using nestest, including the official instructions and the useful unofficial instructions, to make sure it matches the register values on each line of the Nintendulator golden log.

There are two ways to calculate the length of a vector (a, b). Normally, you'd do sqrt(a * a + b * b). But Thwaite uses a shortcut to skip the square root. If you already have the angle theta, the length is two table lookups and two multiplies: a * cos(theta) + b * sin(theta).

Who is interested in having a look at this library? Are there any additions you think others might use?

_________________
Pin Eight | Twitter | GitHub | Patreon

Top

 Post subject: Re: Game math libraryPosted: Thu Jul 11, 2013 5:56 pm

Joined: Sun Apr 13, 2008 11:12 am
Posts: 8370
Location: Seattle
Is the multiplication the difference-of-squares method, or binary long multiplication?
In light of the types supported by uc65, it might be nice to provide the full set of up-to-32-bit-result multiplications (8x8, 8x16, 8x24, 16x16).

Top

 Post subject: Re: Game math libraryPosted: Thu Jul 11, 2013 7:47 pm

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 21397
Location: NE Indiana, USA (NTSC)
I tried difference of squares years ago, and it took about 90 cycles and a lot more bytes than the 8x8 long mul that Thwaite uses. I was trying to keep routines short enough to keep in a fixed bank as opposed to swapping all the time, seeing as how binary code size is a common complaint against cc65. But I could consider adding difference of squares for completeness, along with mul subroutines for larger integers that call this one in a loop.

_________________
Pin Eight | Twitter | GitHub | Patreon

Top

 Post subject: Re: Game math libraryPosted: Fri Jul 12, 2013 1:52 pm

Joined: Wed Jul 30, 2008 12:03 am
Posts: 34
tepples wrote:
I tried difference of squares years ago, and it took about 90 cycles and a lot more bytes than the 8x8 long mul that Thwaite uses.

It does take a lot of bytes both for tables and on zp but it's a lot faster than 90 cycles.
in the version attributed to George Taylor (who said he got it from someone else)
in (A+B)^2-(A-B)^2 the A+B and A-B are done using the indexing mechanism
it's basically just a 16 bit indirect indexed addition with some set up of pointers
(and negation of B) that only needs to be done once if B doesn't change
(without checking) my recollection is it's about 28 cycles
I believe there're slightly faster versions that build more into the tables

Top

 Post subject: Re: Game math libraryPosted: Fri Jul 12, 2013 2:02 pm

Joined: Sat Jan 23, 2010 11:41 pm
Posts: 1161
tepples wrote:
[*]Arctangent, producing the angle of the vector from (a, b) to (c, d) in units of 1/32 turn, within 380 cycles

This should be much faster, although it uses relatively large tables.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 5 posts ]

 All times are UTC - 7 hours

Who is online

Users browsing this forum: No registered users and 8 guests

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

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki