Trajectory shooting

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
User avatar
Diskover
Posts: 219
Joined: Thu Nov 24, 2011 7:16 am
Contact:

Trajectory shooting

Post by Diskover »

Suppose an enemy shoots our player . The shooting comes on the enemy and should reach the position that had the player when he made ​​his appearance .
It not what is the formula to calculate the trajectory programming in C ( with cc65 ) .

Someone help me? :cry:
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Trajectory shooting

Post by tepples »

Are the projectiles affected by gravity? Does this happen in two dimensions (side view), two dimensions (top view), or three dimensions (where a projectile is lobbed from one place to the other and has to land in the right spot)?
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Trajectory shooting

Post by rainwarrior »

The simple version of trajectory is a quadratic equation.

To solve this, you might use the quadratic formula, though the exact computation you'll want to do depends a lot on which variables are free, etc.

Alternatively you could just simulate the trajectory (each frame add velocity to position, then add gravity to velocity) to see where it would hit, and if it's too far adjust one way, if it's too near, adjust the other way, and stop once you reach the target. Depending on how many trajectories you need to simulate before you get a hit (recommend: binary search), this might be easier/faster to accomplish on the NES than trying to solve a quadratic equation directly.
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Trajectory shooting

Post by tokumaru »

Or do you mean just shooting at an angle? If so, this usually involves some trigonometry. The enemy and the player form a right triangle, and you have to use the legs (delta X and delta Y) of this triangle and an arctangent function (or lookup table) to figure out the angle of the shot, and in possession of the angle you can calculate the vertical and horizontal speeds of the shot by multiplying the base speed by the cosine and sine of the angle.

This would be the "correct" way to do it, but since this is the NES we're talking about, you should probably take a few shortcuts, and use mostly lookup tables instead of actual calculations. For example, instead of dividing the legs to find the angle, you could maybe take the most significant bits of each leg and combine them to form an index, and use this index to read the vertical and horizontal speeds of the bullet from a lookup table. The angles will not be exact, because you'll be throwing some bits of information away, but maybe the result is good enough.
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Trajectory shooting

Post by rainwarrior »

tokumaru wrote:lookup table
Yes, this is probably an appropriate approach.

As an aside, books of trajectory calculations were used in cannon warfare in the 17th century. They would literally look up the angle and amount of gunpowder to use in a table. The history of using lookup tables to overcome a slow computer goes back a long way. ;)
User avatar
Diskover
Posts: 219
Joined: Thu Nov 24, 2011 7:16 am
Contact:

Re: Trajectory shooting

Post by Diskover »

tepples wrote:Are the projectiles affected by gravity? Does this happen in two dimensions (side view), two dimensions (top view), or three dimensions (where a projectile is lobbed from one place to the other and has to land in the right spot)?
It is a game in aerial view (two dimensions -top view).
rainwarrior wrote: Alternatively you could just simulate the trajectory (each frame add velocity to position, then add gravity to velocity) to see where it would hit, and if it's too far adjust one way, if it's too near, adjust the other way, and stop once you reach the target. Depending on how many trajectories you need to simulate before you get a hit (recommend: binary search), this might be easier/faster to accomplish on the NES than trying to solve a quadratic equation directly.
That solution had passed through my head but I saw unprofessional.

However , if there is no other way to make it simpler , it might be a good solution.
tepples
Posts: 22705
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Trajectory shooting

Post by tepples »

In Thwaite, I calculated the angle of the vector from the missile silo to the cursor using a partly table-based atan2 routine that took less than 400 cycles. This involves reflecting the coordinate into the first octant, calculating the slope of the vector (1 division), looking up the slope in a table, and undoing the reflection. I used this angle to determine the approximate direction of the missile (out of 32) so that I could choose the appropriate sprite tile for the direction.

Because I felt like implementing atan2 and not hypot (length of a vector) that day, I took a dot product with the corresponding unit vector (2 multiplications) to determine the length of the path.

Define unit(theta) = (cos(theta), sin(theta)).
Define (a, b) dot (c, d) = a*b + c*d.
Calculate theta = atan2(x, y), based on atan(y/x).
Then hypot(x, y) = unit(theta) dot (x, y).

This is exact if atan2 is exact, and even with the 32-step atan2 that Thwaite uses, it's still within half a percent. (Reasoning: cos(tau/64) = 0.995.) Then I converted that to a reciprocal of flight time in frames-1 (1 division), and scaled the vector to the cursor by that amount (2 multiplications) to form the missile's velocity.

For RHDE, I did the homing missile "cheat": call atan2 on the vector to the target, set the missile's frame based on that angle and its velocity based on that angle's unit vector, and update the atan2-based estimate every few frames. Each player is allowed only a limited number of missiles in flight at once, and updating some of the missiles each frame was deemed close enough.
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Trajectory shooting

Post by rainwarrior »

Are they supposed to hit the target on the first try, or it supposed to take more than one attempt?

Like, if it's a guaranteed hit, you might find some sort of animation that's easy to just place where you want it. E.g. if the target is at the same height as the shooter, you could just use a generic quadratic curve animation for the vertical, but control the landing position with horizontal velocity alone. (If you don't have to worry about the vertical, the problem of landing a shot is reduced to a simple linear equation.)

If it's not a guaranteed hit, just having it make some sort of rough estimate at first and progressively adjusting for each attempt could make for useful gameplay.
Diskover wrote:That solution had passed through my head but I saw unprofessional.
I don't know what's "unprofessional" about it. Even if you solved a quadratic equation instead, it's a somewhat equivalent method. For example, Newton's method is an iterative "guess and check and adjust" approach, and is actually a practical method for computing square roots (solving a quadratic requires a square root). The real difference is just that you'd be hiding the iterative approach inside a math library.

The question of whether it's an acceptable solution has to do with:
  • How much time does it take to calculate vs. how much time are you allowed.
  • How much code does it take to calculate vs. how much space do you have, or how easy is it to maintain.
The simulate-and-try-again is probably the slowest approach, but the code involved is very light (probably 2 16-bit adds, and some logic to test and adjust). You can probably calculate many arcs in a single frame. How long a wait is acceptable for the required gameplay?
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: Trajectory shooting

Post by psycopathicteen »

This is similar to the chain physics demo I once did. The way I did the chain physics demo (if I remember correctly) is the following:

1) Check if the X and Y displacements are positive or negative, store the result, and convert to positive if negative.
2) Then figure out which is larger, the Y displacement or X displacement and store the result.
3) Divide the small displacement by the large displacement.
4) Use the result as an index to a sinarctan and cosarctan LUT.
5) Give the big axis the result from cosarctan, and the small axis the result from sinarctan.
6) Give the X and Y values their +/- signs back.
na_th_an
Posts: 558
Joined: Mon May 27, 2013 9:40 am

Re: Trajectory shooting

Post by na_th_an »

I've thought several time of using LUTs, but I can't come up with something useable (relatively small LUTs, I mean). So this is my method, which has several shortcuts and relies on some math simplifications. But it contains divisions and multiplications (2 of each) which are slooooow in cc65 when coding in C, so I'm open for suggestions.

First of all, I calculate a very raw (but accurate enough) estimation of the distance. All variables are unsigned chars (8 bits). x? and y? are measured in pixels (I use fixed point variables, but those shown here are converted to pixel coordinates before, to simplify calculations).

Code: Select all

dx = DELTA (x0, x1);
dy = DELTA (y0, y1);
dd = MIN (dx, dy);
d = dx + dy - (dd >> 1) - (dd >> 2) - (dd >> 4);
DELTA and MIN are macros. DELTA (a, b) is just ABS (a-b); MIN is self-explanatory.

Now, the vx and vy (which will be used to be added each frame to a fixed point integer variable) can be easily calculated:

Code: Select all

vx = ADD_SIGN (x1 - x0, VELOCITY * dx / d);
vy = ADD_SIGN (y1 - y0, VELOCITY * dy / d);
ADD_SIGN is yet another macro; ADD_SIGN (a, b) just gives the sign of a to b.

That seems to work, but I'm not keen on the couple of multiplications and divisions there, and I'm not sure how could I benefit from a LUT in this scenario.
User avatar
rainwarrior
Posts: 8731
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Trajectory shooting

Post by rainwarrior »

na_th_an wrote:

Code: Select all

d = dx + dy - (dd >> 1) - (dd >> 2) - (dd >> 4);
Small optimization opportunity here:

Code: Select all

d/2 + d/4 + d/8 = d - d/8
d = dx + dy - (dd - (dd >> 4));
It's not identical, due to truncation, but if you didn't want truncation in the first place, it's more accurate too.
na_th_an wrote:I'm not sure how could I benefit from a LUT in this scenario.
Perhaps make one with a coarse grid of dx,dy pairs. Maybe sample at every 8x8 pixels? Then just do a linear interpolation between sample points to reach your target- it won't be as accurate as doing the full calculation, but it's probably going to close enough, especially if your target is more than one pixel wide.
na_th_an
Posts: 558
Joined: Mon May 27, 2013 9:40 am

Re: Trajectory shooting

Post by na_th_an »

That's very clever, I'll try such approach. In fact, I don't need this to be really accurate. It's intended for platform games where some baddies throws random stuff at where you are. The target has a collision box of 8x16 and the projectile is 8x8, so I guess the precision is more than enough.

Thanks for the insight!
User avatar
Diskover
Posts: 219
Joined: Thu Nov 24, 2011 7:16 am
Contact:

Re: Trajectory shooting

Post by Diskover »

I have not been able to make the shot.

In fact, I have understood almost nothing of what you have put :?

I have these variables:

player_X
player_Y
player_X_old
player_Y_old
shot_exists
shot_x
shot_y

What is missing and how can I make what I want written in C language?
Post Reply