Aiming bullets and heavy computation...

[Sivak]

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
-X2-X1 and Y2-Y1 (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((X2-X1)^2 + (Y2-Y1)^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.

[ReaperSMS]

Cut the distance down to distance in tiles, and use that X/Y to index some LUTs. Anything on-screen 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.

[tepples]

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.

1. Reflect displacement (Δx, Δy) into first octant, producing run (longer distance) and rise (shorter distance).
2. Slope = rise/run.
3. Angle = arctan(slope) = table lookup.
4. Unit vector along this angle = (cos(angle), sin(angle)).
5. Distance to target = (run, rise) projected onto unit vector = unit vector dot (run, rise) = cos(angle) * rise + sin(angle) * run.
6. Travel time = distance / speed (not counted as a division because it's constant and can be inlined with shifts).
7. Velocity = displacement / travel time.

It's accurate to within one or two pixels even with only 32 angle units, and it also produces angle (used to choose which frame of rotation the sprite uses) and 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 2-5 with Distance = run - rise / 2.

[Sivak]

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 pre-determined angle. I had this vision of a tri-gunner 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.

[doynax]

I used a rather table-heavy 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 fixed-point 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.

[bogax]

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

Bresenhams seems an obvious choice but I don't think sqrt(2) for a
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

[Tom]

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

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

Then used a small table from the quantized angles to precomputed x and y speeds.

[doynax]

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

Bresenhams seems an obvious choice but I don't think sqrt(2) for a
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)

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.

Here's a quick-and-dirty example which plots an x-major 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 pre-squared 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;
		}
	}
}

[bogax]

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.

Actually I rather like that because I'm always trying to think of ways
to "leverage" a table of squares in case I have one laying around
(eg for quarter-square multiplication)

[psycopathicteen]

1) delta x = x1-x2 and delta y = y1-y2

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

[Sivak]

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