06 November 2019, 13:05  #1 
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484

Aimed missiles and fixedpoint 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 wellknown 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 ydirection, 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 fixedpoint format depending on the vector's length, which I could simply add in every step. The problem is to calculate the vector length in fixedpoint, preferably in 68k assembler. I do not dare to think about the squareroot, but already a fixed point division is not trivial. How is this problem generally solved in Amiga shooters? 
06 November 2019, 13:31  #2 
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.

06 November 2019, 14:44  #3 
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. 
06 November 2019, 14:54  #4 
Lemon. / Core Design
Join Date: Mar 2016
Location: Sunny Bournemouth, UK
Posts: 479

https://plutiedev.com/anglemath#getangle
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  
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484

Quote:
Maybe 320 * 256, for each dx and dy? 

06 November 2019, 15:07  #6  
Registered User
Join Date: Jul 2018
Location: Londonish / UK
Posts: 489

Quote:
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  
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484

Quote:
Quote:


06 November 2019, 15:09  #8 
Lemon. / Core Design
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 
06 November 2019, 15:10  #9  
Registered User
Join Date: Dec 2014
Location: germany
Posts: 197

Quote:
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  
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 280

Quote:
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 fixpoint number is also simple, just prescale 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 } 

09 November 2019, 11:59  #11 
Registered User
Join Date: Mar 2019
Location: Birmingham, UK
Posts: 142

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  
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484

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

09 November 2019, 19:31  #13 
Registered User
Join Date: Jul 2018
Location: Londonish / UK
Posts: 489

Don't forget that Graphics Gems 5 has a fixed point square root algorithm.

09 November 2019, 19:59  #14  
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484

Quote:
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 ycomponent. That yields a total table size of 8192 bytes. I wrote the following portable C source to generate the table as part of my buildprocess: Code:
/* * Calculates a gradient table for pairs of dx/dy in a given range. * Format: 8bit 1.7 unsigned fixed point values between 0.0 and 1.0 * dx=0 dx=1 ... dx=range1 * dy=0: <gradx>,<grady> <gradx>,<grady> <gradx>,<grady> * dy=1: <gradx>,<grady> <gradx>,<grady> <gradx>,<grady> * ... * dy=range1: <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 8bit 1.7 fixedpoint 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; } 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 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 twodimensional 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 yposition 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 yposition 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.7format 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 
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 1,484


09 November 2019, 20:07  #16 
Registered User
Join Date: Jul 2018
Location: Londonish / UK
Posts: 489


09 November 2019, 20:24  #17  
Zone Friend
Join Date: Mar 2004
Location: Middle Earth
Age: 35
Posts: 1,362

Quote:


10 November 2019, 01:27  #18 
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 
Registered User
Join Date: Mar 2019
Location: Birmingham, UK
Posts: 142


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 

