Aiming bullets and heavy computation...

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

Post Reply
User avatar
Sivak
Posts: 316
Joined: Tue Jul 17, 2007 9:04 am
Location: Somewhere
Contact:

Aiming bullets and heavy computation...

Post by Sivak » Thu Aug 12, 2010 10:34 pm

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
Posts: 174
Joined: Sun Sep 19, 2004 11:07 pm
Contact:

Post by ReaperSMS » Thu Aug 12, 2010 11:20 pm

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
Posts: 22281
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples » Fri Aug 13, 2010 5:26 am

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.

User avatar
Sivak
Posts: 316
Joined: Tue Jul 17, 2007 9:04 am
Location: Somewhere
Contact:

Post by Sivak » Fri Aug 13, 2010 7:47 am

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
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:

Post by doynax » Fri Aug 13, 2010 9:03 am

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.
Last edited by doynax on Fri Aug 13, 2010 10:18 am, edited 2 times in total.

bogax
Posts: 34
Joined: Wed Jul 30, 2008 12:03 am

Post by bogax » Fri Aug 13, 2010 10:00 am

doynax 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 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
Last edited by bogax on Fri Aug 13, 2010 10:33 am, edited 1 time in total.

Tom
Posts: 68
Joined: Wed Apr 06, 2005 5:36 am
Location: Massachusetts

Post by Tom » Fri Aug 13, 2010 10:04 am

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
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:

Post by doynax » Fri Aug 13, 2010 10:20 am

bogax wrote:
doynax 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 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
Posts: 34
Joined: Wed Jul 30, 2008 12:03 am

Post by bogax » Fri Aug 13, 2010 10:52 am

doynax 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.
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
Posts: 2980
Joined: Wed May 19, 2010 6:12 pm

Post by psycopathicteen » Sat Aug 14, 2010 4:42 pm

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

User avatar
Sivak
Posts: 316
Joined: Tue Jul 17, 2007 9:04 am
Location: Somewhere
Contact:

Post by Sivak » Tue Aug 17, 2010 9:51 pm

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

Post Reply