The following code can be used to accurately determine the direction that a projectile should be fired at in order to collide with the target.
This code is capable of accurately targetting moving targets, falling targets, and projectiles uniformly accelerating in any direction. It was originally written for use in Deathball by UsAaR33
Contents
The Code
struct QuartSolution{ //solutions to quart! var float u[4]; }; //quadratic solver (using everybody's favorite algebra formula) static function calculateQuadRoots(float a, float b, float c, out QuartSolution Q){ local float sqterm; sqterm = b*b - 4*a*c; if (sqterm<0){ //imaginary root. return t=1 Q.u[0]=-1; Q.u[1]=-1; } else{ sqterm=sqrt(sqterm); a*=2; b*=-1; Q.u[0]=(b+sqterm)/(a); Q.u[1]=(b-sqterm)/(a); } } //Solve a 4th Degree Polynomial (Quartic) equation for 0s. //taken from a javascript webpage (Explicitly states in source that source may be reused in any way) //uses the quartic formula! :) static function calculateQ(float aq, float bq, float cq, float dq, float eqin, out QuartSolution Q){ local float eq; local float fq; local float gq; //local float hq; // These are the squares of the local floatiables used to calculate the 4 roots--> local float kq; local float lq; local float mq; local float nq; local float mq2; local float compsw; local float kqsw; local float lqsw; local float mqsw; // Switch used in calculating REAL quartic roots)--> local float sw; // local floatiables for calculating REAL quartic roots)--> local float kans; local float lans; local float theta; local float x1; local float x2; local float x3; local float x4; local float x2a, x2b, x2c, x2d; //local float x1b, x1b2, x2b2, x3b, x3b2, x4b, x4b2; //more: local float dnm; local float a, b, c, d, f, g, h, k, m, m2,n,n2,r,rc; local float calcy, calcp, calcr, calcq, calcx, calcmod; local float dnmsw; local int i; // the 'q' suffix denotes local floatiables used in the quartic equation for (i=0;i<4;i++) Q.u[i]=-1.0; //set to complex solutions compsw=0; kqsw=0; lqsw=0; mqsw=0; dnmsw=0; sw=0; dnm=aq; //note: this assumes aq is non-zero. Of course it should be (eval 0.25g!) //Simplifying by dividing all terms by the aq term called 'dnm' meaning denominator aq=bq/dnm; bq=cq/dnm; cq=dq/dnm; dq=eqin/dnm; //Which yields an equation of the form X^4 + AX^3 + BX^2 + CX + D = 0 eq= bq-((3*aq*aq)/8); fq= cq+ (aq*aq*aq/8) -(aq*bq/2); gq= dq- (3*aq*aq*aq*aq/256) + (aq*aq*bq/16) - (aq*cq/4); // SOLVING THE RESULTANT CUBIC EQUATION // EVALUATING THE 'f'TERM a=1; b=eq/2; c=((eq*eq)-(4*gq))/16; d= ((fq*fq)/64)*-1; f = (((3*c)/a) - (((b*b)/(a*a))))/3; //EVALUATING THE 'g'TERM g = ((2*((b*b*b)/(a*a*a))-(9*b*c/(a*a)) + ((27*(d/a)))))/27; //EVALUATING THE 'h'TERM h = (((g*g)/4) + ((f*f*f)/27)); if (h > 0){ compsw=2; m = (-(g/2)+ (sqrt(h))); // K is used because math.pow cannot compute negative cube roots? k=1; if (m < 0) k=-1; else k=1; m2 = ((m*k)**(1.0/3.0)); m2 = m2*k; k=1; n = (-(g/2)- (sqrt(h))); if (n < 0) k=-1; else k=1; n2 = (n*k)**(1.0/3.0); n2 *=k; k=1; kq= ((m2 + n2) - (b/(3*a))); kq=sqrt(kq); // ((S+U) - (b/(3*a))) calcmod= sqrt((-1*(m2 + n2)/2 - (b/(3*a)))*(-1*(m2 + n2)/2 - (b/(3*a))) + (((m2 - n2)/2)*sqrt(3))*(((m2 - n2)/2)*sqrt(3))); calcy=sqrt((calcmod-(-1*(m2 + n2)/2 - (b/(3*a))))/2); calcx=(((m2 - n2)/2)*sqrt(3))/(2*calcy); calcp=calcx+calcy; calcq=calcx-calcy; calcr=kq; nq=(aq/4); x1=kq+calcp+calcq-nq; x4=kq-calcp-calcq-nq; Q.u[0]=-x1; //appearently was incorrect by a factor of -1 Q.u[1]=-1; //complex Q.u[2]=-1; //complex Q.u[3]=-x4; } // FOR H < 0 if (h<=0){ r = sqrt((g*g/4)-h); k=1; if (r<0) k=-1; // rc is the cube root of 'r' rc = ((r*k)**(1.0/3.0))*k; k=1; theta =acos((-g/(2*r))); kq= (2*(rc*cos(theta/3))-(b/(3*a))); x2a=rc*-1; x2b= cos(theta/3.0); x2c= sqrt(3)*(sin(theta/3)); x2d= (b/3.0*a)*-1; lq=(x2a*(x2b + x2c))-(b/(3*a)); mq=(x2a*(x2b - x2c))-(b/(3*a)); nq=(aq/4.0); } if (h<=0){ // psudo-fix 0 bug.. not the best.. but works if (abs(kq)<1.0/(10000.0)) kq=0; if (abs(lq)<1.0/(10000.0)) lq=0; if (abs(mq)<-1.0/(10000.0)) mq=0; if (kq<0) {return;} else {kq=sqrt(kq);} if (lq<0) {return;} else {lq=sqrt(lq);} if (mq<0) {return;} else {mq=sqrt(mq);} if (kq*lq>0){mq2=((fq*-1)/(8*kq*lq));kans=kq;lans=lq;} if (kq*mq>0){mq2=((fq*-1)/(8*kq*mq));kans=kq;lans=mq;} if (lq*mq>0){mq2=((fq*-1)/(8*lq*mq));kans=lq;lans=mq;} if (compsw==0){ x1=kans+lans+mq2-nq; Q.u[0]=x1; x2=kans-lans-mq2-nq; Q.u[1]=x2; x3=(kans*-1)+lans-mq2-nq; Q.u[2]=x3; x4=(kans*-1)-lans+mq2-nq; Q.u[3]=x4; } } } /*Calculate aiming ideal rotation for firing a projectile at a potentially moving target (assumes pawn physics) IN: -StartLoc = world location where projectile is starting at -EndLoc = world Location we wish to Target (should lie in the targetted actor) -ProjSpeed = speed of the projectile being fired -Gravity = a vector describing the gravity -Target = the actual targetted ACTOR -bLeadTarget = Can we track the target? (the entire point of this function) OUT: -dest: Location where the projectile will collide with Target -returns vector describing direction for projectile to leave at */ static function vector GetShootVect(vector StartLoc, vector EndLoc, float ProjSpeed, vector Gravity, actor Target, bool bLeadTarget, out vector Dest) { local QuartSolution Q; local float best, speed2D, HitTime; local vector Pr; local int i; local vector HitNorm, HitLoc; local vector D; //EndLoc-StartLoc local vector V; //Target.velocity D = EndLoc-StartLoc; V = Target.Velocity; //track falling actors if (bLeadTarget && Target.Physics==Phys_Falling){ calculateQuadRoots(V dot V - ProjSpeed*ProjSpeed, 2*(V dot D),D dot D,Q); //use quadratic formula for (i=0;i<2;i++) if (best<=0||(q.u[i]>0 && q.u[i]<best)) best=q.u[i]; Pr = normal(D/best + V)*ProjSpeed; if (best<=0 || Target.Trace(HitLoc,HitNorm,EndLoc+V*best+0.5*Gravity*best *best,EndLoc+vect(1,1,0)*V*best) == none){ //will be falling: Dest = StartLoc + PR*best+0.5*Gravity*best*best; return normal(PR)*ProjSpeed; } else if (best>0) //determine how long actor will be in air HitTime = vsize(HitLoc - (EndLoc+vect(1,1,0)*V*best))/vsize(vect(0,0,1)*V*best+0.5*Gravity*best); else HitTime = 0; //assume most time not in air? } //ASSUME GROUND TRACKING if (bLeadTarget && Target.Physics==Phys_Falling){ //trace down from target to get ground normal Target.Trace(HitLoc,HitNorm,EndLoc+normal(Gravity)*5000,EndLoc); D.z=HitLoc.z-StartLoc.Z; //set destination.z to floor, wipe out velocity.z and re-eval assuming ground V.z=0; //no longer falling - view velcocity in 2D if (HitTime>0.5){ //True if likely in air most of time (in which case keep current V.X and V.y) V.z -= HitNorm.Z * (V dot HitNorm); } else{ //otherwise alter all of velocity vector, but keep current 2D speed speed2D = vsize(V); V=normal(V)*speed2D; //assume the same x and y speed if in air most time V -= HitNorm * (V dot HitNorm); //recalculate players velocity on a slope using hitnormal (assumes v.x and v.y is "ground speed") V=normal(V)*speed2D; //assume the same x and y speed if in air most time } } //todo: add traces to check side walls? //note: walking velocity *should* factor in current slope best=0; if (bLeadTarget && V!=vect(0,0,0)){ calculateQ(0.25*(Gravity dot Gravity),(-Gravity) dot V,(-Gravity) dot D + V dot V - ProjSpeed*ProjSpeed,2*(V dot D),D dot D,Q); for (i=0;i<4;i++) if (best<=0||(q.u[i]>0 && q.u[i]<best)) best=q.u[i]; } else{ //don't lead. assume stationary target calculateQuadRoots(0.25*(Gravity dot Gravity),(-Gravity) dot D - ProjSpeed*ProjSpeed,D dot D,Q); for (i=0;i<2;i++) if (best<=0||(q.u[i]>0 && q.u[i]<best)) best=q.u[i]; if (best>0) best=sqrt(best); } if (best<=0){ //projectile is out of range //Warning: Out of range adjustments assume gravity is parallel to the z axis and pointed downward!! Pr.z =ProjSpeed/sqrt(2.0); //determine z direction of firing best = -2*Pr.z/Gravity.z; best+=(vsize(D)-pr.Z*best)/ProjSpeed; //note p.z = 2D vsize(p) (this assumes ball travels in a straight line after bounce) //now recalculate PR to handle velocity prediction (so ball at least partially moves in direction of player) Pr = D/best + V - 0.5*Gravity*best; //now force maximum height again: Pr.z=0; Pr = (ProjSpeed/sqrt(2.0))*normal(Pr); Pr.z = ProjSpeed/sqrt(2.0); //maxmimum Dest = StartLoc + PR*best+0.5*Gravity*best*best; return Pr; } Pr = normal(D/best + V - 0.5*Gravity*best)*ProjSpeed; Dest = StartLoc + PR*best+0.5*Gravity*best*best; return Pr; }
How To Use It
Simply call the function GetShootVec() with the following parameters:
- StartLoc is the world location where the projectile is going to be spawned at.
- EndLoc is the world Location that is being targetted (it should lie within the targetted actor)
- ProjSpeed is speed at which the projectile being fired at
- Gravity is a vector describing any uniform acceleration the projectile is under (gravity, "english", etc.)
- Target is the actor being targetted. Generally it should be a pawn, but any class will work.
- bLeadTarget. If this is true, then "velocity prediction" will occur (that is the projectile will be fired ahead of the target and still collide withit, assuming its velocity does not change in a nonpredictable way. If false, the projectile is guarenteed to collide with the targetted location
The function will return a vector in the direction the projectile be launched at and with a magnitude equal to the speed of the projectile (as passed in the parameters).
In addition, a vector dest is returned. This specifies the world location where the projectile will collide with the Target (if the target is moving and bLeadTarget is enabled this vector will differ from endloc).
Notes
Speed
If the target is stationary or bLeadTarget is false, then the quadratic formula can be applied to the 4th degree polynomial that is the core of this algorithm. (the coefficients of t^3 and t^1 become 0). The algorithm takes roughly 0.20 ms to complete (on an AMD Athlon XP 2100+ test machine), equivilent to a drop from 80.0 to 78.7 fps if this GetShootVec() is called once per frame.
If velocity prediction is needed, then the quartic formula (calculateQ) must be applied. This increases the algorithm's time to 0.28 ms (on an AMD Athlon XP 2100+ test machine),, equivilent to a drop from 80.0 to 78.2 fps if this GetShootVec() is called once per frame.
Falling Targets
If a target is falling, the algorithm will verify that the target will not land before the projectile reaches it. If it is determined that the target will land, then the target's position will be re-evaluated, assuming any movement made on the ground is modeled under phys_walking. (thus, this algorithm likely will cause the fired projectile to miss a bBounce=true projectile target).
Please note that it is assumed that the net acceleration of the target is equal to the gravity vector of the projectile. If this is not the case, the code should not be too hard to modify.
Out of Range Targets
Should a target be out of range, this algorithm will attempt to bring the projectile as close as possible to the target. It does make the "appoximate" assumption that the projectile being fired will travel in an "approximately" straight line at its specifified speed toward the target.
Furthermore, the out-of-range routine assumes that the projectile's acceleration direction passed is parallel to the Z axis and pointed downward. It should not be too hard to extend this code to handle different acceleration.
Projectiles under constant acceleration
If you wish your projectile to undergo other constant acceleration (that is curving), this is entire possible. Simply be sure that the gravity vector reflects this. Please note though that the Out Of Range routine does not properly handle this.
That structure that has nothing more than an array
I was thinking of eventually adding other variables to that structure, but I'm not sure if that will ever be needed. Feel free to remove the structure altogether and just make the variable the array.
The Quartic Equation solver
It is converted javascript code that is available on the internet (used with permission). Note that the code is highly unoptimized. Feel free to fix that.
How does this work?
Physics
Basically nothing more than simple kinematics.
Abbriviation notes:
D=Displacement
Vp=launch velocity of Projectile
Vps = launch speed of projectile
Va=velocity of target
t=time
G=acceleration of projectile
The displacement of a projectile can be described with the following vector equation:
D=Vp*t + 0.5*G*t^2
The size of V must be the speed of the projectile.
From this, two equations (four in scalar form) can be derived:
vsize(Vp) = Vp
Vp*t + 0.5*G*t^2 = Va*t + D
(Note that in the case where the target is also falling (under the same acceleration as the projectile), G becomes 0.)
After a bunch of math, the following equation pops out:
0=0.25*(G dot G)*t^4+((-G) dot Va)*t^3 + ((Va dot Va) - Vps^2 + (-G) dot D) * t^2 + 2*(Va dot D)*t + (D^2)
This is a 4th degree polynomial, which can be solved with the Quartic equation.
In the case when Va = 0 (stationary or no leading), the t and t^3 terms become 0, allowing the much nicer quadratic equation to be used. (the result simply needs to be squarerooted).
Once the time is found, the launch velocity is easily calculated (by using the above simultaneous equations):
Vp= normal(D/lowestpostitivetime + Vp - 0.5*Gravity*lowestpostitivetime )*Vps
And that's pretty much it. The details of the code should be explained well enough through comments.