Aimed missiles and fixed-point divisions

[phx]

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?

[deimos]

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.

[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.

[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

[phx]

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.

Originally Posted by deimos

Don't know how big your lut would have to be

Maybe 320 * 256, for each dx and dy?

[deimos]

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.

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

[phx]

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.

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.

[DanScott]

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

[chb]

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.

[Thomas Richter]

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:

 

                 ? = 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.

[Antiriad_UK]

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.

[phx]

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...

[deimos]

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.

[phx]

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:

/*
 * 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
 * dy=0:       <gradx>,<grady> <gradx>,<grady>     <gradx>,<grady>
 * dy=1:       <gradx>,<grady> <gradx>,<grady>     <gradx>,<grady>
 *  ...
 * dy=range-1: <gradx>,<grady> <gradx>,<grady>     <gradx>,<grady>
 */

#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:

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.

[phx]

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.

[deimos]

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.

[redblade]

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/

[Docent]

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.

[Antiriad_UK]

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