Aiming bullets and heavy computation...
Moderator: Moderators
Aiming bullets and heavy computation...
Well, I DID accomplish aimed bullets in BK1, but the method was a little sloppy in order to avoid potential heavy computation.
Here's what I did and these were spread across two states to avoid a HUGE amount of computation:
Take the center points of player and bullet, call them X1,Y1 and X2,Y2
X2X1 and Y2Y1 (do 2's complement if neg and save a flag)
Determine which is bigger
Take the X difference as the high byte, 0 as the low byte and divide the Y difference. A decimal value is then stored.
Whichever was bigger from before moves at a speed of 1. The smaller moves at the decimal point speed.
If the flag was set for either of these, do the 2's complement on either one.
In the next state, I'd do multiplication for faster speeds on the values. Generally just with shifting.
So anyway, this WORKED and the shots were indeed aimed, but the downside is that the closer a bullet got to a 45 degree angle, the faster it went. At exactly 45, it'd be moving the square root of 2 times faster than the intended speed. Not horrible, but still not as nice as I would like.
An approach of possibly using look up tables has been proposed, although that sounds like one gigantic table.
The other approach is doing the computation of: sqrt((X2X1)^2 + (Y2Y1)^2)
Y speed = Y / distance * speed
X speed = X / distance * speed
Square root alone is a huge operation, not to mention that I'd probably need the possibility of 4 bytes if the differences are huge.
I guess I'm at a point of wondering what would be best... The old imperfect method or something different.
Here's what I did and these were spread across two states to avoid a HUGE amount of computation:
Take the center points of player and bullet, call them X1,Y1 and X2,Y2
X2X1 and Y2Y1 (do 2's complement if neg and save a flag)
Determine which is bigger
Take the X difference as the high byte, 0 as the low byte and divide the Y difference. A decimal value is then stored.
Whichever was bigger from before moves at a speed of 1. The smaller moves at the decimal point speed.
If the flag was set for either of these, do the 2's complement on either one.
In the next state, I'd do multiplication for faster speeds on the values. Generally just with shifting.
So anyway, this WORKED and the shots were indeed aimed, but the downside is that the closer a bullet got to a 45 degree angle, the faster it went. At exactly 45, it'd be moving the square root of 2 times faster than the intended speed. Not horrible, but still not as nice as I would like.
An approach of possibly using look up tables has been proposed, although that sounds like one gigantic table.
The other approach is doing the computation of: sqrt((X2X1)^2 + (Y2Y1)^2)
Y speed = Y / distance * speed
X speed = X / distance * speed
Square root alone is a huge operation, not to mention that I'd probably need the possibility of 4 bytes if the differences are huge.
I guess I'm at a point of wondering what would be best... The old imperfect method or something different.
Cut the distance down to distance in tiles, and use that X/Y to index some LUTs. Anything onscreen is going to be < 32 tiles away in any direction, so 1024 entries in the LUT.
Cut it to 16x16 metatiles, and you're looking at a couple of 256 entry luts, though if you encoded the velocities as 1.3 unsigned fixed point in the table, and handled the signs seperately, you'd get x and y in one 256 byte table.
Cut it to 16x16 metatiles, and you're looking at a couple of 256 entry luts, though if you encoded the velocities as 1.3 unsigned fixed point in the table, and handled the signs seperately, you'd get x and y in one 256 byte table.
I adjust projectile speeds in one of my unreleased projects (which you might see as an entry in Jeroen's compo) with three divisions, two multiplications, and a few lookup tables for sine, cosine, and tangent, in a space where 32 angle units make 1 rotation.
To save one div and two muls if you don't need angle and can afford distance being off by up to 10.6% (but not 41.4%), I found one shortcut to approximate distance in Black Art of 3D Game Programming by Andre LaMothe: replace steps 25 with Distance = run  rise / 2.
 Reflect displacement (Δx, Δy) into first octant, producing run (longer distance) and rise (shorter distance).
 Slope = rise/run.
 Angle = arctan(slope) = table lookup.
 Unit vector along this angle = (cos(angle), sin(angle)).
 Distance to target = (run, rise) projected onto unit vector = unit vector dot (run, rise) = cos(angle) * rise + sin(angle) * run.
 Travel time = distance / speed (not counted as a division because it's constant and can be inlined with shifts).
 Velocity = displacement / travel time.
To save one div and two muls if you don't need angle and can afford distance being off by up to 10.6% (but not 41.4%), I found one shortcut to approximate distance in Black Art of 3D Game Programming by Andre LaMothe: replace steps 25 with Distance = run  rise / 2.
Interesting approaches.
I was thinking of making some kind of LUT that has values for the various angles in case I want an enemy that's shoot them in a predetermined angle. I had this vision of a trigunner that'd shoot one in straight line and others at maybe 30 degrees or something.
I don't think I'd use values for ALL the angles of course... Plus anything beyond 180 could be flipped horizonally pretty easily.
Thanks for the insight. I'll look into it.
I was thinking of making some kind of LUT that has values for the various angles in case I want an enemy that's shoot them in a predetermined angle. I had this vision of a trigunner that'd shoot one in straight line and others at maybe 30 degrees or something.
I don't think I'd use values for ALL the angles of course... Plus anything beyond 180 could be flipped horizonally pretty easily.
Thanks for the insight. I'll look into it.
I used a rather tableheavy method to aim bullets towards the player in my old shooter project.
Essentially I calculated the angle for one octant with the usual arctan(y / x) formula, using a logarithm table for the division and an arctan table with logarithmic indices. Then there was a bit of twiddling to expand the result to every octant, and finally a sine table to calculate final velocities. Feel free to use the code if you feel like wasting some ROM: http://codebase64.org/doku.php?id=base: ... bit_angle
Another possible method, if you want to avoid bulky tables but have cycles to spare, is to trace the bullet's path using Bresenham's line algorithm while limiting the number of steps taken each frame. That is every frame you'd add the desired speed to a fixedpoint distance allowance, then keep taking Bresenham steps and subtracting one for a straight step and sqrt(2) for a diagonal one until the counter reaches zero.
To be honest I've never actually gotten around to testing this approach, but it ought to work.. ;)
edit: Actually, I doesn't seem to be anywhere near accurate. Oh well.
Essentially I calculated the angle for one octant with the usual arctan(y / x) formula, using a logarithm table for the division and an arctan table with logarithmic indices. Then there was a bit of twiddling to expand the result to every octant, and finally a sine table to calculate final velocities. Feel free to use the code if you feel like wasting some ROM: http://codebase64.org/doku.php?id=base: ... bit_angle
Another possible method, if you want to avoid bulky tables but have cycles to spare, is to trace the bullet's path using Bresenham's line algorithm while limiting the number of steps taken each frame. That is every frame you'd add the desired speed to a fixedpoint distance allowance, then keep taking Bresenham steps and subtracting one for a straight step and sqrt(2) for a diagonal one until the counter reaches zero.
To be honest I've never actually gotten around to testing this approach, but it ought to work.. ;)
edit: Actually, I doesn't seem to be anywhere near accurate. Oh well.
Last edited by doynax on Fri Aug 13, 2010 10:18 am, edited 2 times in total.
Bresenhams seems an obvious choice but I don't think sqrt(2) for adoynax wrote: Another possible method, if you want to avoid bulky tables but have cycles to spare, is to trace the bullet's path using Bresenham's line algorithm while limiting the number of steps taken each frame. That is every frame you'd add the desired speed to a fixedpoint distance allowance, then keep taking Bresenham steps and subtracting one for a straight step and sqrt(2) for a diagonal one until the counter reaches zero.
To be honest I've never actually gotten around to testing this approach, but it ought to work..
edit: Actually, I doesn't seem to be anywhere near accurate. Oh well.
diagonal step is going to be very accurate.
eg for one horizontal and one diagonal ie for tan= .5, angle= 26.56
the distance would be 2/cos (26.56) = 2.23
sqrt(2) + 1 would give you 2.4
you'll lose one pixel for every 24 or something like that (at 26.56 degrees)
edit:
that didn't come out right I'm trying to agree and disagree at the same
time
probably good enough especially for speed
certainly better than 1 : 1.4
I'd guess that you could do better for similar effort
Last edited by bogax on Fri Aug 13, 2010 10:33 am, edited 1 time in total.
For the tanks/turrets in Wraith I did something similar to the arctan approach, but did a bunch of comparisons to compute a quantized
arctan. Something like
Then used a small table from the quantized angles to precomputed x and y speeds.
arctan. Something like
Code: Select all
dx =  x0  x1 
dy =  y0  y1 
if dx < 2*dy
angle = 90
else if dy < 2*dx
angle = 0
else
angle = 45
This probably is quite useless but just to satisfy my own curiosity I tried to work out something similar, and it does seem that you can draw a Bresenham line at a constant speed without any arithmetic beyond addition and subtraction if you keep a running count of the squared x, y, and hypotenuse terms.bogax wrote:Bresenhams seems an obvious choice but I don't think sqrt(2) for adoynax wrote: Another possible method, if you want to avoid bulky tables but have cycles to spare, is to trace the bullet's path using Bresenham's line algorithm while limiting the number of steps taken each frame. That is every frame you'd add the desired speed to a fixedpoint distance allowance, then keep taking Bresenham steps and subtracting one for a straight step and sqrt(2) for a diagonal one until the counter reaches zero.
To be honest I've never actually gotten around to testing this approach, but it ought to work.. ;)
edit: Actually, I doesn't seem to be anywhere near accurate. Oh well.
diagonal step is going to be very accurate.
eg for one horizontal and one diagonal ie for tan= .5, angle= 26.56
the distance would be 2/cos (26.56) = 2.23
sqrt(2) + 1 would give you 2.4
you'll lose one pixel for every 24 or something like that (at 26.56 degrees)
Here's a quickanddirty example which plots an xmajor line towards dx/dy at speed v.
Code: Select all
void trace(int dx, int dy, int v) {
int x, y;
int e, d;
int v2;
x = 0;
y = 0;
e = dy;
dx *= 2;
dy *= 2;
/* In practice you'd avoid this multiplication by keeping presquared velocities */
v *= v;
v2 = v;
v *= 2;
d = 0;
for(;;) {
printf("(%d, %d)  %f\n", x, y, sqrt(x * x + y * y));
getchar();
d += v2;
v2 += v;
while(d >= 0) {
if(e = dy, e < 0) {
e += dx;
d = y++ * 2 + 1;
}
d = x++ * 2 + 1;
}
}
}
Actually I rather like that because I'm always trying to think of waysdoynax wrote: This probably is quite useless but just to satisfy my own curiosity I tried to work out something similar, and it does seem that you can draw a Bresenham line at a constant speed without any arithmetic beyond addition and subtraction if you keep a running count of the squared x, y, and hypotenuse terms.
to "leverage" a table of squares in case I have one laying around
(eg for quartersquare multiplication)

 Posts: 2980
 Joined: Wed May 19, 2010 6:12 pm
1) delta x = x1x2 and delta y = y1y2
2) determine the +/ signs of delta x and delta y
3) find delta x and delta y
4) slope = delta y / delta x
5) velocity x = cos(arctan(slope)) and velocity y = sin(arctan(slope). Use a look up table for each.
6) apply delta x and delta y +/ signs to velocity x and velocity y
7) add the signed velocity values to both coordinates
2) determine the +/ signs of delta x and delta y
3) find delta x and delta y
4) slope = delta y / delta x
5) velocity x = cos(arctan(slope)) and velocity y = sin(arctan(slope). Use a look up table for each.
6) apply delta x and delta y +/ signs to velocity x and velocity y
7) add the signed velocity values to both coordinates
Well, I managed to get something utilizing that atan2 routine that was suggested. I already had angular bullets, so using the atan2 thing, I just applied the angle I got to the angular bullet routine and bingo.
So thanks for suggesting that routine. It's bulky, but I have 256kb to work with. Heheheh...
So thanks for suggesting that routine. It's bulky, but I have 256kb to work with. Heheheh...