2
\$\begingroup\$

I'm trying to solve the classic shoot moving object problem but with acceleration attached to that changes it from a quadratic to quartic formula but my math skills are not this good sadly as i prefer to speak in code and not formulas.

i found this https://wiki.beyondunreal.com/Legacy:Projectile_Aiming. i ported it and it's almost what i'm looking for but missing control over the acceleration as its only made for gravity or no gravity and even this i got working only with tricks and modifying it without knowing what i'm doing is getting me only that far.

I made myself a Prototype Interface for the minimum of what i'm trying to get out of it

public class PredictionResult {
    public bool IsInRange; // can we even hit the target?
    public Vector3[] ShotVelocity; // should be up to 4 possible values
    public float[] ShotImpactTime; // how long each shot takes to arrive at the predicted target
    public Vector3[] ShotImpactLocation; // somewhat redundant yet still useful if available
}
// only really the delta between start and target matter but its up to the function
// same for startVel and targetVel where startVel is the shooters speed that gets added to the bullet
// the bullet and target can have different accelerations (standing on ground => no gravity or bullet is not affect by gravity)
public PredictionResult ShootAtTarget(Vector3 start, Vector3 target, Vector3 startVel, Vector3 targetVel, Vector3 bulletAccel, Vector3 targetAccel, float bulletSpeed);

any help solving this would be great

\$\endgroup\$
  • \$\begingroup\$ I don't quite understand what you mean by "with acceleration". \$\endgroup\$ – Bálint Oct 9 '17 at 6:55
  • \$\begingroup\$ @Bálint both the target and the projectile are affected by acceleration. it might be just gravity or something more complex. the projectile will most likely have something between gravity and nothing while the target acceleration can be anything. also this is only for the initial launch so the values are constants. if they change, it will miss \$\endgroup\$ – HellGate Oct 9 '17 at 12:36
  • \$\begingroup\$ Can we summarize the problem as follows? At the time of firing t_0, the Target is at some offset T_p from the firing location, moving with relative velocity T_v, and acceleration (assumed to be constant) T_a. We need to choose an initial velocity for our projectile P_v up to a maximum speed s so that, moving under a possibly different constant acceleration we can't control, P_a, the projectile will at some future time strike the target. Is that right? \$\endgroup\$ – DMGregory Oct 9 '17 at 15:18
  • \$\begingroup\$ @DMGregory yes pretty much but the projectile speed 's' is fixed and not "up to". think about shooting a rifle over a big distance on a moving target or maybe an accelerating car. what i will be using it is more like try to shoot a player with a rocket or grenade in quake midair or on ground. doing this without acceleration ends up in a quadratic formula and has been solved on stackexchange before gamedev.stackexchange.com/a/35869/40960 but with it, its a whole lot more complex \$\endgroup\$ – HellGate Oct 9 '17 at 20:15
  • \$\begingroup\$ Maybe this may help: iforce2d.net/b2dtut/projected-trajectory \$\endgroup\$ – Gustavo Maciel Oct 18 '17 at 1:55
4
\$\begingroup\$

To make things a little simpler, let's work within the inertial frame of our launcher. That means our projectile will be firing from the point (0, 0, 0).

(You can subtract any arbitrary firing position from the target position to get this state of affairs for the purpose of the calculations, then add it back when you need work with the resulting path)

Let's define:

unknowns

  • v_p the launch velocity of our projectile relative to the launcher (vector)
  • t the time after launch when our projectile impacts the target (scalar)

knowns

  • s the speed of our projectile (scalar)
  • p_T the offset from the launcher to the target at the time of firing (vector)
  • v_T the velocity of the target relative to the launcher at the time of firing (vector)
  • a_T the constant acceleration of the target (vector)
  • a_p the constant acceleration of the projectile (vector)

Using our parametric equation for motion over time under constant acceleration...

p(t) = p(0) + v * t + (a/2.0) * t^2

We know that at the time of impact we want:

v_p * t + (a_p/2.0) * t^2 = p_T + v_T * t + (a_T/2.0) * t^2

Rearranging to isolate v_p, we get:

v_p = (1/t)(t^2(a_T - a_p)/2.0 + t * v_T + p_T)

Let's define a = a_T - a_p since they'll appear paired from here on in.

Applying our speed constraint: (Here · refers to a dot product between vectors)

s = ||v_p||

s^2 = v_p·v_p
s^2 = (1/t^2)(t^4(a·a/4.0) + t^3(a·v_t) + t^2(a·p_T + v_T·v_T) + t(2.0 * v_T·p_T) + p_T·p_T)

Rearranging:

  t^4 * (a·a/4.0)
+ t^3 * (a·v_T)
+ t^2 * (a·p_T + v_T·v_T - s^2)
+ t   * (2.0 * v_T·p_T)
+       p_T·p_T
= 0

That's a quartic equation in t, which is not the most fun to solve. When the target is stationary, the t^3 and t terms vanish and we can use quadratic formula to solve for t^2, but for the general case of a moving target there's not much we can do but bite the bullet.

You can either plug this into a math library to solve the polynomial, write your own polynomial solver, or approximate a solution using an iterative method like Newton's.

However you choose to go about it, you'll come out with up to 4 time values at which you can successfully intercept the target. Some could be negative, corresponding to projectiles being lobbed from the target sometime in the past to arrive at the firing position at time zero travelling at the desired speed - discard those and consider only the positive time values. (You might get none, if the target is simply out of firing range or moving too fast to intercept)

To turn any of these remaining valid time values into a launch velocity, do the following:

  1. Plug your t value into the formula for the target's position

    p(t) = p_T + v_T * t + (a_T/2.0) * t^2

    This gives you the position of the target at the time of impact. Since this is the net offset in space that your projectile will have to bridge, we'll call this vector travel

  2. Calculate the initial velocity (aim direction & speed) of an arc travelling to this point in space & time:

    v_p = travel / t - (a_p/2.0) * t

By construction, launching the projectile with this velocity v_p will intersect the target's movement while respecting the initial speed constraint we started with, to within the numerical accuracy of the operations we took to get here. (Some rounding can be introduced at each step)

Here's an animation of this formula at work:

Animated gif of projectile interceptions

This little test rig generates random target positions/velocities/accelerations and projectile gravity values, then calculates up to four intercept trajectories.

The white ball is the target, moving along its trajectory before t=0 (black curve) to its position at the time of firing (grey dot) and continuing along its future trajectory t > 0 (greycurve). Its path is marked by red dots at the solution points.

The intercepting projectiles and their trajectories appear in cyan & green at t = 0 and arc to intercept the target at their corresponding impact times.

For completeness, I also show the negative solutions if there are any, in yellow or magenta, firing from the target when it crosses a negative solution time and arriving at the firing point in the center at t = 0.

\$\endgroup\$
  • \$\begingroup\$ was away for some days so sadly i missed the award bounty time... well now i'm back and had to implement it right away and it mostly works. however something with acceleration is not quite right. for testing i only use gravity and 0 bullet and/or target. i have to swap bullet and target acceleration around randomly based on different scenarios for it to work. did not test anything more complex yet. any ideas? \$\endgroup\$ – HellGate Oct 21 '17 at 1:06
  • \$\begingroup\$ Nothing off the top of my head. Want to link your current code so we can step through it? \$\endgroup\$ – DMGregory Oct 21 '17 at 1:08
  • \$\begingroup\$ sure. i'm using unity for prototyping right now in addition to sunflow quartic solver (ported from java to c#). gist.github.com/HellGate94/3b3c4b0b26a9a467d5807be3af4a1a85 \$\endgroup\$ – HellGate Oct 21 '17 at 11:06
  • \$\begingroup\$ @HellGate I haven't been able to reproduce the problem. I built a testing rig that generates random targets to shoot at (see it animated above), and every result is giving me a correct interception if there are any feasible velocities at all. I notice you're not adding startVel back into the firing velocity at the end though - is firing from the inertial frame of the launcher handled elsewhere in your code? \$\endgroup\$ – DMGregory Oct 21 '17 at 14:26
  • \$\begingroup\$ hmm i think i found the problem. the solver i chose seems to have issues in some situations and sometimes return wrong or no results for whatever reason (decimal places problem i guess, works a lot better already when changing float to double but still wonky). what did you use for your demo? other than that is seems to work perfectly thank you so much for your help \$\endgroup\$ – HellGate Oct 21 '17 at 16:57
0
\$\begingroup\$

You mention "a rifle firing at an accelerating car."

Note that the rifle's bullet has its maximum speed at the nozzle, and will only slow down from there, in real-life.

For simplicity, I will assume that the bullet will not noticeably slow down before hitting the car: most games don't even model air-resistance for bullets.

So the acceleration to compensate for, is the car's, and not the bullet's. Correct?

So the travel time for the bullet to where the car currently is, is easily determined.

What the car does during that travel time (dt), will impact the aim of the rifle, but hardly that travel time itself.

So in my games, I neglect the difference with the actual travel time it takes to the car at time of impact.

Then your aiming problem simply comes down to predicting the car's position at t + dt.

This prediction requires the car's current position, current velocity and current acceleration.

I would add some additional simplifications to this problem, which probably have little impact in accuracy: You calculate the car's speed at t+dt, and then assume on average, the speed of the car between firing and impact lies half-way between the car's current speed and the predicted speed. With that, you can estimate the car's position at t+dt.

In pseudo code I would do:

traveltime = distance_to_car / bullet_nozzle_velocity
current_speed = car.speed
predicted_speed = car.speed + traveltime * car.acceleration
average_speed = ( current_speed + predicted_speed ) / 2
predicted_pos = car.pos + average_speed * traveltime
\$\endgroup\$
  • \$\begingroup\$ i don't account for friction yes but other than that i can not really neglect anything in my case. i need the full model including target acceleration (any 3d vector) and projectile acceleration (and 3d vector, but most likely something between zero and gravity). should be kinda this formula (might made an error): p_t + (v_t + a_t * t) * t = p_b + (v_b + a_b * t) * t; v_b.length = speed; solve for v_b \$\endgroup\$ – HellGate Oct 11 '17 at 13:20
  • \$\begingroup\$ just saw i messed up my euler integration... should be: p_t + v_t * t + 0.5 * a_t * t * t = p_b + v_b * t + 0.5 * a_b * t * t and v_b.length = speed \$\endgroup\$ – HellGate Oct 14 '17 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.