English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Asm / Hardware

 
 
Thread Tools
Old 06 November 2019, 13:05   #1
phx
Natteravn

phx's Avatar
 
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484
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?
phx is offline  
Old 06 November 2019, 13:31   #2
deimos
Registered User

 
Join Date: Jul 2018
Location: Londonish / UK
Posts: 489
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.
deimos is offline  
Old 06 November 2019, 14:44   #3
grond
Registered User

 
Join Date: Jun 2015
Location: Germany
Posts: 657
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.
grond is offline  
Old 06 November 2019, 14:54   #4
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Sunny Bournemouth, UK
Posts: 479
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
DanScott is offline  
Old 06 November 2019, 14:59   #5
phx
Natteravn

phx's Avatar
 
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484
Quote:
Originally Posted by deimos View Post
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 View Post
Don't know how big your lut would have to be
Maybe 320 * 256, for each dx and dy?
phx is offline  
Old 06 November 2019, 15:07   #6
deimos
Registered User

 
Join Date: Jul 2018
Location: Londonish / UK
Posts: 489
Quote:
Originally Posted by phx View Post
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
deimos is offline  
Old 06 November 2019, 15:08   #7
phx
Natteravn

phx's Avatar
 
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484
Quote:
Originally Posted by grond View Post
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 View Post
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.
phx is offline  
Old 06 November 2019, 15:09   #8
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Sunny Bournemouth, UK
Posts: 479
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
DanScott is offline  
Old 06 November 2019, 15:10   #9
chb
Registered User

 
Join Date: Dec 2014
Location: germany
Posts: 197
Quote:
Originally Posted by phx View Post
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
chb is offline  
Old 09 November 2019, 00:56   #10
Thomas Richter
Registered User
 
Join Date: Jan 2019
Location: Germany
Posts: 280
Quote:
Originally Posted by phx View Post
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.
Thomas Richter is offline  
Old 09 November 2019, 11:59   #11
Antiriad_UK
Registered User

 
Join Date: Mar 2019
Location: Birmingham, UK
Posts: 142
Quote:
Originally Posted by phx View Post
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.
Antiriad_UK is offline  
Old 09 November 2019, 19:22   #12
phx
Natteravn

phx's Avatar
 
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484
Quote:
Originally Posted by Thomas Richter View Post
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...
phx is offline  
Old 09 November 2019, 19:31   #13
deimos
Registered User

 
Join Date: Jul 2018
Location: Londonish / UK
Posts: 489
Quote:
Originally Posted by phx View Post
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.
deimos is offline  
Old 09 November 2019, 19:59   #14
phx
Natteravn

phx's Avatar
 
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484
Quote:
Originally Posted by Antiriad_UK View Post
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
 * 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:
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
phx is offline  
Old 09 November 2019, 20:00   #15
phx
Natteravn

phx's Avatar
 
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484
Quote:
Originally Posted by deimos View Post
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.
phx is offline  
Old 09 November 2019, 20:07   #16
deimos
Registered User

 
Join Date: Jul 2018
Location: Londonish / UK
Posts: 489
Quote:
Originally Posted by phx View Post
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.
deimos is offline  
Old 09 November 2019, 20:24   #17
redblade
Zone Friend

redblade's Avatar
 
Join Date: Mar 2004
Location: Middle Earth
Age: 35
Posts: 1,362
Quote:
Originally Posted by deimos View Post
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/
redblade is offline  
Old 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.
Docent is offline  
Old 10 November 2019, 11:48   #19
Antiriad_UK
Registered User

 
Join Date: Mar 2019
Location: Birmingham, UK
Posts: 142
Quote:
Originally Posted by phx View Post
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
Antiriad_UK is offline  
 


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

Similar Threads
Thread Thread Starter Forum Replies Last Post
WinUAE Assembly dump from point to point? Sim085 support.WinUAE 3 11 April 2017 20:43
Maths question, divisions, remainders etc. h0ffman Coders. General 15 25 June 2011 22:44
Classic Workbench 1.3 :( (aimed at Bloodwych) Kitty project.ClassicWB 1 04 October 2010 17:17
REQ: Missiles Over Xerion Masterek request.Old Rare Games 5 20 September 2006 11:05
Commodore 64 ad aimed at the sexually ambiguous & Un***n_k 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 Jump


All times are GMT +2. The time now is 18:16.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.
Page generated in 0.08825 seconds with 13 queries