06 November 2019, 12:05 | #1 |
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,500
|
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, 12:31 | #2 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
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, 13:44 | #3 |
Registered User
Join Date: Jun 2015
Location: Germany
Posts: 1,918
|
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, 13:54 | #4 |
Lemon. / Core Design
Join Date: Mar 2016
Location: Tier 5
Posts: 1,212
|
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, 13:59 | #5 | |
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,500
|
Quote:
Maybe 320 * 256, for each dx and dy? |
|
06 November 2019, 14:07 | #6 | |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
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, 14:08 | #7 | ||
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,500
|
Quote:
Quote:
|
||
06 November 2019, 14:09 | #8 |
Lemon. / Core Design
Join Date: Mar 2016
Location: Tier 5
Posts: 1,212
|
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, 14:10 | #9 | |
Registered User
Join Date: Dec 2014
Location: germany
Posts: 439
|
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 14:17. Reason: deimos already answered that question |
|
08 November 2019, 23:56 | #10 | |
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,233
|
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 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 } |
|
09 November 2019, 10:59 | #11 |
OCS forever!
Join Date: Mar 2019
Location: Birmingham, UK
Posts: 418
|
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, 18:22 | #12 | |
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,500
|
Quote:
With some fixes I get 15 as a result for v=10... |
|
09 November 2019, 18:31 | #13 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
Don't forget that Graphics Gems 5 has a fixed point square root algorithm.
|
09 November 2019, 18:59 | #14 | |
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,500
|
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 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; } 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 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 19:05. Reason: copy/paste error in source |
|
09 November 2019, 19:00 | #15 |
Natteravn
Join Date: Nov 2009
Location: Herford / Germany
Posts: 2,500
|
|
09 November 2019, 19:07 | #16 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
|
09 November 2019, 19:24 | #17 | |
Zone Friend
Join Date: Mar 2004
Location: Middle Earth
Age: 40
Posts: 2,127
|
Quote:
|
|
10 November 2019, 00:27 | #18 |
Registered User
Join Date: Mar 2019
Location: Poland
Posts: 59
|
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, 10:48 | #19 |
OCS forever!
Join Date: Mar 2019
Location: Birmingham, UK
Posts: 418
|
|
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 19:43 |
Maths question, divisions, remainders etc. | h0ffman | Coders. General | 15 | 25 June 2011 21:44 |
Classic Workbench 1.3 :( (aimed at Bloodwych) | Kitty | project.ClassicWB | 1 | 04 October 2010 16:17 |
REQ: Missiles Over Xerion | Masterek | request.Old Rare Games | 5 | 20 September 2006 10:05 |
Commodore 64 ad aimed at the sexually ambiguous & Un***n_k | Fred the Fop | Nostalgia & memories | 0 | 19 February 2006 08:08 |
|
|