English Amiga Board Aimed missiles and fixed-point divisions
 User Name Remember Me? Password
 Register Amiga FAQ Rules & Help Members List  /  Moderators List Today's Posts Mark Forums Read

 06 November 2019, 13:05 #1 phx Natteravn   Join Date: Nov 2009 Location: Herford / Germany Posts: 1,538 Aimed missiles and fixed-point divisions Most shooters might have solved this problem. An enemy object decides to shoot at the player, from any x1/y1 to any x2/y2 coordinate. I have to admit that I am struggling to find a performant implementation. Of course, there is the well-known Bresenham algorithm: https://en.wikipedia.org/wiki/Bresen...line_algorithm But it would only easily allow me to move the missile one step in x- or y-direction, while calculating whether an increment in the other direction is needed. This would result in different speeds, depending on the angle. Better might be to calculate a dx/dy in fixed-point format depending on the vector's length, which I could simply add in every step. The problem is to calculate the vector length in fixed-point, preferably in 68k assembler. I do not dare to think about the square-root, but already a fixed point division is not trivial. How is this problem generally solved in Amiga shooters?
 06 November 2019, 13:31 #2 deimos Registered User   Join Date: Jul 2018 Location: France Posts: 536 A look up table of inverse square roots? That way you get rid of both the square root operation and the division. Don't know how big your lut would have to be, but maybe it's worth playing with a spreadsheet to see what it might look like. Maybe a lut to get an upper and lower bound then binary chop to get the level of accuracy you consider necessary.
 06 November 2019, 14:44 #3 grond Registered User   Join Date: Jun 2015 Location: Germany Posts: 682 Why do you want to consider the distance? You could do a dx/dy and then use the result to look up suitable DeltaX and DeltaY from a small table.
 06 November 2019, 14:54 #4 DanScott Lemon. / Core Design   Join Date: Mar 2016 Location: Sunny Bournemouth, UK Posts: 518 https://plutiedev.com/angle-math#get-angle You could shift down your dx and dy until both are in a range that allows you to use a smaller lookup
06 November 2019, 14:59   #5
phx
Natteravn

Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,538
Quote:
 Originally Posted by deimos A look up table of inverse square roots? That way you get rid of both the square root operation and the division.
Hmm, ok. Then I would need two fixed point multiplications with it (dx*invsqr and dy*invsqr) to get my pixels/frame movement. Still expensive, but much better.

Quote:
 Originally Posted by deimos Don't know how big your lut would have to be
Maybe 320 * 256, for each dx and dy?

06 November 2019, 15:07   #6
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 536
Quote:
 Originally Posted by phx Hmm, ok. Then I would need two fixed point multiplications with it (dx*invsqr and dy*invsqr) to get my pixels/frame movement. Still expensive, but much better. Maybe 320 * 256, for each dx and dy?
I think you could probably make do with around 410, if you're looking up the square through a binary search.

Code:
```1584	107
1577	108
1569	109
1562	110
1555	111
1548	112
1541	113
1535	114
1528	115
1521	116
1515	117
1508	118```

06 November 2019, 15:08   #7
phx
Natteravn

Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,538
Quote:
 Originally Posted by grond Why do you want to consider the distance? You could do a dx/dy and then use the result to look up suitable DeltaX and DeltaY from a small table.
Quote:
 Originally Posted by DanScott https://plutiedev.com/angle-math#get-angle You could shift down your dx and dy until both are in a range that allows you to use a smaller lookup
Yes! These two replies together might be the solution! I don't need that much precision, so a small table will work. Thanks.

 06 November 2019, 15:09 #8 DanScott Lemon. / Core Design   Join Date: Mar 2016 Location: Sunny Bournemouth, UK Posts: 518 you will probably find in most shooters, that a bullet travelling along the X axis would have a velocity of (16,0), along the Y axis (0,16) and at 45 degrees (16,16) This is much simpler to calculate
06 November 2019, 15:10   #9
chb
Registered User

Join Date: Dec 2014
Location: germany
Posts: 203
Quote:
 Originally Posted by phx Hmm, ok. Then I would need two fixed point multiplications with it (dx*invsqr and dy*invsqr) to get my pixels/frame movement. Still expensive, but much better.
Have you considered using log tables for multiplication? Like x*y = b^(log_b x + log_b y)? Needs a log table entry for every possible value x or invsqr can take, and an inverse one for every one the sum can take. Those tables wouldn'be huge, as your dx and dy values are integers <320, and your invsqr values can also quantized, as deimos pointed out.

EDIT: better approach would be using a log table to compute dy/dx resp. (log dy - log dx) and then do a table lookup as grond pointed out. Then the inverse table is small, as dx and dy are from the same range.

Last edited by chb; 06 November 2019 at 15:17. Reason: deimos already answered that question

09 November 2019, 00:56   #10
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 298
Quote:
 Originally Posted by phx Better might be to calculate a dx/dy in fixed-point format depending on the vector's length, which I could simply add in every step. The problem is to calculate the vector length in fixed-point, preferably in 68k assembler. I do not dare to think about the square-root, but already a fixed point division is not trivial.
A fixed point division is easily done by prescaling the divident by the fractional bits of the quotient and perform an integer division. That is, if your numbers have f fractional bits, the divident needs to be prescaled by 2f bits instead of f bits (i.e. left-shift by f).

A square root is also easily done. The important observation here is that squares are the sum of odd numbers, so a (not yet ideal) simplistic implementation adds up odd numbers until the original number is exceeded, where the number of iterations gives the square root. This can now be converted into a scaled version by noting that two left shifts of the original number is equivalent to a single left shift of its root. This results in an algorithm that looks approximately identical to a (manual) binary division, and is about of the same complexity. Turning this into a fix-point number is also simple, just pre-scale the input by 2f instead of f bits (again using the observation that 2f bits corresponds to f bits of the root).

The following code computes the square root of a number v with Bw bits:
Code:
```

? = 0
for(? = 0 ;? < Bw ;?=?+1) {
? = ? << 1
v = v << 2
if ((v >> Bw) > ?) {
v = v – ((? + 1) << Bw)
? = ? + 2
}
}
v = ? >> 1
}```
The result is returned in v as well.

09 November 2019, 11:59   #11
OCS forever!

Join Date: Mar 2019
Location: Birmingham, UK
Posts: 151
Quote:
 Originally Posted by phx Yes! These two replies together might be the solution! I don't need that much precision, so a small table will work. Thanks.
Please post back the high level of whatever you come up with. I want to move hundreds of dots from a given x,y to another point which sounds like the same thing. The implementation I did in the 90s is horrible and I’m a bit dim these days and struggling to understand these solutions.

09 November 2019, 19:22   #12
phx
Natteravn

Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,538
Quote:
 Originally Posted by Thomas Richter The following code computes the square root of a number v with Bw bits:
That's great! Looks like a performant implementation! Can you please check the code? I guess the '?' is just any iteration variable. Semicolons are missing and there is one closing-brace too much.

With some fixes I get 15 as a result for v=10...

09 November 2019, 19:31   #13
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 536
Quote:
 Originally Posted by phx That's great! Looks like a performant implementation! Can you please check the code? I guess the '?' is just any iteration variable. Semicolons are missing and there is one closing-brace too much. With some fixes I get 15 as a result for v=10...
Don't forget that Graphics Gems 5 has a fixed point square root algorithm.

09 November 2019, 19:59   #14
phx
Natteravn

Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,538
Quote:
 Originally Posted by Antiriad_UK Please post back the high level of whatever you come up with. I want to move hundreds of dots from a given x,y to another point which sounds like the same thing.
Yes, I think so.
Today I finally implemented everything and it is working nicely.

I am generating a table for 64 values of dx and dy. Which means the table has 64*64 (4096) normalized gradients (I hope this is the correct mathmatical term - Thomas will certainly correct me) in the range of 0.0 to 1.0. I am using 1.7 bits fixed point, so each entry has one byte for the x- and one byte for the y-component. That yields a total table size of 8192 bytes.

I wrote the following portable C source to generate the table as part of my build-process:
Code:
```/*
* Calculates a gradient table for pairs of dx/dy in a given range.
* Format: 8-bit 1.7 unsigned fixed point values between 0.0 and 1.0
*             dx=0            dx=1            ... dx=range-1
*  ...
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

static void writebyte(FILE *f,uint8_t b)
{
if (fwrite(&b,1,1,f) != 1) {
fprintf(stderr,"Write error!\n");
fclose(f);
exit(1);
}
}

#if 0
static void writebe16(FILE *f,uint16_t v)
{
writebyte(f,v>>8);
writebyte(f,v&0xff);
}
#endif

int main(int argc,char *argv[])
{
FILE *f;
int entries,i;

if (argc != 3) {
printf("Usage: %s <entries in one dimension> <file name>\n",argv[0]);
return 1;
}

/* check if number of entries is a power of 2, below 512 */
entries = atoi(argv[1]);
for (i=0; i<8; i++) {
if (entries & (1<<i))
break;
}
if (entries & ~(1<<i)) {
fprintf(stderr,"%d is not a power of 2, or greater than 256!\n",entries);
return 1;
}

if (f = fopen(argv[2],"wb")) {
double dx,dy,len;
int row,col;

/* calculate and write the table */
for (row=0; row<entries; row++) {
for (col=0; col<entries; col++) {
dx = (double)col;
dy = (double)row;
if (len = sqrt(dx*dx+dy*dy)) {
dx = 128.0*dx/len;
dy = 128.0*dy/len;
}
else
dx = dy = 0.0;

/* write two 8-bit 1.7 fixed-point values for the gradient */
writebyte(f,(uint8_t)dx);
writebyte(f,(uint8_t)dy);
}
}
fclose(f);
}
else {
fprintf(stderr,"Cannot open \"%s\" for writing!\n",argv[2]);
return 1;
}

return 0;
}```
This table is included with INCBIN in my program's data section. For a C project you could put it into a separate object and link with it - or just generate the table on startup.

Using the table:
Assuming you have a starting point x1/y1 and a target at x2/y2. First you calculate the delta on both axes, which defines the gradient(? "Steigung" in german) dx/dy of the aiming vector:
Code:
```dx = x2 - x1
dy = y2 - y1```
As our table can only deal with positive values you have to calculate the absolute values |dx| and |dy|, but remember their sign for later.
The next step is to normalize |dx| and |dy| for the table's maximum range of 0..63. So, as long as |dx| is >= 64 divide |dx| AND |dy| by 2. Then do the same for |dy| (if it is still >= 64). Use these normalized values as two-dimensional index into the table. In C the table could have been defined as
`unsigned char gradients[64][64][2];`

Read gradients[dy][dx][0] as DX and gradients[dy][dx][1] as DY. DX and DY are 1.7 bits fixed point values in the range [0.0,1.0], which you can add every frame to the x- and y-position of your missile. When the missile should fly 2 pixels/frame, multiply DX/DY by two first. Also don't forget to fix the sign: Now assign DX the same sign as the original dx and DY the same sign as the original dy.

Example: In my game I have the missile's x- and y-position as 24.8 bits fixed point and want it to fly 2 pixels/frame, so I multiply DX/DY by 4 (*2 to adapt the 1.7-format to 24.8 and another *2 for the 2 pixels/frame) and add it to the current position.

Last edited by phx; 09 November 2019 at 20:05. Reason: copy/paste error in source

09 November 2019, 20:00   #15
phx
Natteravn

Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,538
Quote:
 Originally Posted by deimos Don't forget that Graphics Gems 5 has a fixed point square root algorithm.
Thanks. Will probably find it, now that I know it exists.

09 November 2019, 20:07   #16
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 536
Quote:
 Originally Posted by phx Thanks. Will probably find it, now that I know it exists.
I used code from Graphics Gems 1 in my very first paid coding job. In '92, I think.

09 November 2019, 20:24   #17
Zone Friend

Join Date: Mar 2004
Location: Middle Earth
Age: 35
Posts: 1,395
Quote:
 Originally Posted by deimos Don't forget that Graphics Gems 5 has a fixed point square root algorithm.
They look like good books. http://index-of.co.uk/Game-Development/Programming/

 10 November 2019, 01:27 #18 Docent Registered User   Join Date: Mar 2019 Location: Poland Posts: 3 You can use polar coordinate system to store objects coordinates. For each object keep its x,y location, distance to move in one step and direction vector. New location you'll get from the following equation: dx = distance * cos (direction vector); dy = distance * sin (direction vector); Notice that changing the direction or speed is a simple and cheap modification of one object's parameters. Put sin and cos into tables and movement of one object will need just 2 lookups, 2 additions and 2 multiplications. For static distance, you can precalculate distance*sin, distance*cos and you will need just 2 lookups and 2 additions to move each object. You need to use fixed point for x,y,dx,dy for smooth movement.
10 November 2019, 11:48   #19
OCS forever!

Join Date: Mar 2019
Location: Birmingham, UK
Posts: 151
Quote:
 Originally Posted by phx Yes, I think so. Today I finally implemented everything and it is working nicely.
Cheers, I’ll check this out and see if I can get my head around it

 Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

 Similar Threads Thread Thread Starter Forum Replies Last Post Sim085 support.WinUAE 3 11 April 2017 20:43 h0ffman Coders. General 15 25 June 2011 22:44 Kitty project.ClassicWB 1 04 October 2010 17:17 Masterek request.Old Rare Games 5 20 September 2006 11:05 Fred the Fop Nostalgia & memories 0 19 February 2006 09:08

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home News Main     Amiga scene     Retrogaming General Discussion     Nostalgia & memories Support     New to Emulation or Amiga scene         Member Introductions     support.WinUAE     support.WinFellow     support.OtherUAE     support.FS-UAE         project.AmigaLive     support.Hardware         Hardware mods         Hardware pics     support.Games     support.Demos     support.Apps     support.Amiga Forever     support.Amix     support.Other Requests     request.UAE Wishlist     request.Old Rare Games     request.Demos     request.Apps     request.Modules     request.Music     request.Other     Looking for a game name ?     Games images which need to be WHDified abime.net - Hall Of Light     HOL news     HOL suggestions and feedback     HOL data problems     HOL contributions abime.net - Amiga Magazine Rack     AMR news     AMR suggestions and feedback     AMR data problems     AMR contributions abime.net - Home Projects     project.Amiga Lore     project.EAB     project.IRC     project.Mods Jukebox     project.Wiki abime.net - Hosted Projects     project.aGTW     project.APoV     project.ClassicWB     project.Jambo!     project.Green Amiga Alien GUIDES     project.Maptapper     project.Sprites     project.WinUAE - Kaillera Other Projects     project.Amiga Demo DVD     project.Amiga Game Factory     project.CARE     project.EAB File Server     project.CD32 Conversion     project.Game Cover Art         GCA.Feedback and Suggestions         GCA.Work in Progress         GCA.Cover Requests         GCA.Usefull Programs         GCA.Helpdesk     project.KGLoad     project.MAGE     project.Missing Full Shareware Games     project.SPS (was CAPS)     project.TOSEC (amiga only)     project.WHDLoad         project.Killergorilla's WHD packs Misc     Amiga websites reviews     MarketPlace         Swapshop     Kinky Amiga Stuff     Collections     EAB's competition Coders     Coders. General         Coders. Releases         Coders. Tutorials     Coders. Asm / Hardware     Coders. System         Coders. Scripting         Coders. Nextgen     Coders. Language         Coders. C/C++         Coders. AMOS         Coders. Blitz Basic     Coders. Contest         Coders. Entries Creation     Graphics         Graphics. Work In Progress         Graphics. Finished Work         Graphics. Tutorials     Music         Music. Work In Progress         Music. Finished Work         Music. Tutorials Off Topic     OT - General     OT - Entertainment     OT - Sports     OT - Technical     OT - Gaming

All times are GMT +2. The time now is 04:59.

 -- EAB3 skin ---- EAB2 skin ---- Mobile skin Archive - Top