Jump to content
  • Advertisement
  • 11/07/14 08:21 PM
    Sign in to follow this  

    Throwing a Winning Pass

    General and Gameplay Programming

    In a previous article, the problem of hitting a target with a fixed velocity was discussed and a solution described. In that case, the shooter had the ability to launch the projectile immediately at the direction where the target would eventually intercept it. While this is true for many cases, it is also true that the effect of having an AI turn and shoot at a moving target, and hit it, is more realistic and just plain awesome. It raises the bar significantly above "shoot at stuff" to "I can pick which target I want to hit, turn to shoot at it before it knows what's going on, and move on to the next target with ease." As you would expect, this does raise the bar a bit in the algorithm area.

    Approaching the Problem

    Looking at the picture below, it can be seen that the dynamics of the problem are very similar to the case from before.
    The equations derived in the previous article still describe the situation: (1) \(\vec{P_T^1} = \vec{P_T^0} + \vec{v_T} *(t_B+t_R)\) (2) \((P_{Tx}^1 - P_{Sx})^2 +(P_{Ty}^1 - P_{Sy})^2 = S_b^2 * (t_B+t_R)^2\) However, now instead of the time being just \(t_B\), the term includes \(t_R\), which is the amount of time needed to rotate through \(\theta_R\) radians. Defining a few new variables:
    1. The unit vector for the "facing" direction of the shooter when the calculation begins: \(\hat{P_{ST}^0}\)
    2. The unit vector for the "facing" direction of the shooter when the shot is fired; this points towards \(\vec{P_T^1}\): \(\hat{P_{ST}^1}\)
    3. The rate at which the shooter rotates its body: \(\omega_R\)
    When the body rotates at a rate of \(\omega_R\) for \(t_R\) seconds, it rotates through \(\theta_R\) radians. \(\omega_R * t_R =\theta_R\) Given the unit vectors defined above and using the definition of the dot product: (3) \(\omega_R * t_R = acos(\hat{P_{ST}^0}\cdot\hat{P_{ST}^1})\) In the previous case, the situation was "static". You fire the projectile and it heads towards a location. The only thing you need to know is the time of flight. But now you need to know how long you have to wait before you can shoot. But the longer you wait, the further your target will have traveled. So the solution "moves" as the rotation time increases. That is a fairly "ugly" set of equations to try and solve. The static case's quadratic solution and evaluation of its descriminant gave us a good picture of the number of solutions possible. In this case, because of the quadratic/transcendental nature of the formuals, there may or may not be a closed form solution to it. So what do we do? Instead of asking ourselves how can we find the answer directly, ask ourselves how we would know if we found an answer that worked at all.

    Pick A Number Between...

    If we were to pick a random number for the total time, \(t_{impact} = t_R + t_B\), we could calculate the intercept position because that is how far the target would have traveled in that time, equation (1). Since we know the final position, we can calculate how far the projectile must have traveled to hit the target and also the time to rotate to that position from (2) and (3). If the value we chose for \(t_{impact}\) is a solution, then: \(t_{impact} = t_R + t_B\) But, if it is not, then \(t_{impact}\) will either be greater than or less than the sum. Using this, we can propose an answer, test it, and decide if that answer lies to the "left" or "right" of the proposed solution. Then propose (read: guess) again, using the answer we just got to get a little closer. Using this approach, we can iterate towards a solution in a (hopefully) bounded number of steps. Not as clean as a simple "plug and chug" formula, but very serviceable.

    Binary Search

    It is tempting to use a fast-converging numerical technique like Newton's Method to try and solve this. But the shape of the space that the solution lies in is unknown. We haven't even proven that the "left" or "right" decision process won't stick us in some thorny cyclic patch of non-convergence. Shooting off towards infinity on a small derivative estimate is also something that would be undesirable and hard to bound. We want this to be executed in an AI for a game that is running out in the field, not in a lab. So, we're going to trade something that *might* converge faster for a search algorithm that will guarantee cutting the search space in half each time, the binary search. Here is how it will work:
    1. Define the minimum value, \(t_{min}\) that will be the smallest value for \(t_{impact}\) that will be allowed.
    2. Define the maximum value, \(t_{max}\) that will be the largest value for \(t_{impact}\) that will be allowed.
    3. Start with the value that is between the minimum and maximum as the first proposed value.
    4. Loop:
      1. Calculate the final impact location.
      2. Calculate the rotation time necessary to face the impact location, \(t_{rot}\).
      3. Calculate the flight time from the shooter to the final impact location, \(t_{flight}\).
      4. \(t_{shot} = t_{impact} - (t_{rot} + t_{flight})\)
      5. if \(t_{shot} > 0\), then set the upper limit to the proposed value and propose a new value between the upper and lower limits.
      6. if \(t_{shot} < 0\), then set the lower limit to the proposed value and propose a new value between the upper and lower limits.
      7. If the value of value of \(t_{impact}\) is changing within less than a specified tolerance, the algorithm has converged.
      8. If the number of loops gets too high, fail.
    5. Return success and the final position or failure.

    The Code

    The following function calculates whether or not the target can be hit and then returns the result. If the target could not be hit, the return value is "false". If it could, the return value is "true" and the solution, the position vector of the impact. /* Calculate the future position of a moving target so that * a turret can turn to face the position and fire a projectile. * * This algorithm works by "guessing" an intial time of impact * for the projectile 0.5*(tMin + tMax). It then calculates * the position of the target at that time and computes what the * time for the turret to rotate to that position (tRot0) and * the flight time of the projectile (tFlight). The algorithms * drives the difference between tImpact and (tFlight + tRot) to * zero using a binary search. * * The "solution" returned by the algorithm is the impact * location. The shooter should rotate towards this * position and fire immediately. * * The algorithm will fail (and return false) under the * following conditions: * 1. The target is out of range. It is possible that the * target is out of range only for a short time but in * range the rest of the time, but this seems like an * unnecessary edge case. The turret is assumed to * "react" by checking range first, then plot to shoot. * 2. The target is heading away from the shooter too fast * for the projectile to reach it before tMax. * 3. The solution cannot be reached in the number of steps * allocated to the algorithm. This seems very unlikely * since the default value is 40 steps. * * This algorithm uses a call to sqrt and atan2, so it * should NOT be run continuously. * * On the other hand, nominal runs show convergence usually * in about 7 steps, so this may be a good 'do a step per * frame' calculation target. * */ bool CalculateInterceptShotPosition(const Vec2& pShooter, const Vec2& vShooter, const Vec2& pSFacing0, const Vec2& pTarget0, const Vec2& vTarget, float64 sProjectile, float64 wShooter, float64 maxDist, Vec2& solution, float64 tMax = 4.0, float64 tMin = 0.0 ) { cout << "----------------------------------------------" << endl; cout << " Starting Calculation [" << tMin << "," << tMax << "]" << endl; cout << "----------------------------------------------" << endl; float64 tImpact = (tMin + tMax)/2; float64 tImpactLast = tImpact; // Tolerance in seconds float64 SOLUTION_TOLERANCE_SECONDS = 0.01; const int MAX_STEPS = 40; for(int idx = 0; idx < MAX_STEPS; idx++) { // Calculate the position of the target at time tImpact. Vec2 pTarget = pTarget0 + tImpact*vTarget; // Calulate the angle between the shooter and the target // when the impact occurs. Vec2 toTarget = pTarget - pShooter; float64 dist = toTarget.Length(); Vec2 pSFacing = (pTarget - pShooter); float64 pShootRots = pSFacing.AngleRads(); float64 tRot = fabs(pShootRots)/wShooter; float64 tFlight = dist/sProjectile; float64 tShot = tImpact - (tRot + tFlight); cout << "Iteration: " << idx << " tMin: " << tMin << " tMax: " << tMax << " tShot: " << tShot << " tImpact: " << tImpact << " tRot: " << tRot << " tFlight: " << tFlight << " Impact: " << pTarget.ToString() << endl; if(dist >= maxDist) { cout << "FAIL: TARGET OUT OF RANGE (" << dist << "m >= " << maxDist << "m)" << endl; return false; } tImpactLast = tImpact; if(tShot > 0.0) { tMax = tImpact; tImpact = (tMin + tMax)/2; } else { tMin = tImpact; tImpact = (tMin + tMax)/2; } if(fabs(tImpact - tImpactLast) < SOLUTION_TOLERANCE_SECONDS) { // WE HAVE A WINNER!!! solution = pTarget; return true; } } return false; }
    The algorithm takes not only the position of the shooter, but its velocity as well. This is provision for a small modification where the shooter could be moving. In development of Star Crossing thus far, it has not been necessary to put in this modification. Feel free to let us know via feedback if you work it in (and it works for you).

    The Video

    Instead of cooking up a video just to demonstrate the basic use of the algorithm, it is going to be more effective to let you see it in action. The video below is a clip from a game we are actively working on called Star Crossing. In the clip, the ship pulls the Defense Drone behind it like a tail gunner. The Defense Drone turns to shoot at the Snakes as the ship drags it around. Go about a minute into the video and you'll see it.
    This game is in work and the art is all drawn by hand to have something to look at while the mechanics are worked out. It looks pretty...well...crayolaish...that's not even a word but it probably has the right feel. If you would like to help the project with some art skill, feel free to contact us.

    The Demo

    I put together a small console application as a test bed to develop the algorithm initially. The simulation allows you to tinker with the parameters and see the running of the algorithm. You can download the source code for it using the link below. It is written in C++ and should compile on any modern compiler. We used XCode on a Macbook Pro, but the code has no graphics or special libraries associated with it.

    The (Rest of the) Code

    Get the Source Code for this article hosted on GitHub by clicking here.

    Interesting Points

    • While there is a bound on the algorithm, it usually converges in less than 10 steps in our testing.
    • (Proposed...not proven) Knowing your turn rate in radians/sec, you can modify the SOLUTION_TOLERANCE_SECONDS value so that it converges to a resoluion in terms of arc seconds from the target. That is to say, you don't have to shoot dead at the target positiion to hit it, you just have to be really close. This gives you a good way to set your tolerance and save some loops. You could change the algorithm to take a tolerance in degrees or radians to set the convergence limit.
    • You need to handle the case where the target is heading right at you. We use the dot product for this and just "fire now". This is done before the algorithm is even called.
    • Our initial algorithm shot at the location of the target instead of leading it. When we put the new algorithm into effect at first, it was not too exciting, but much better. When we put in the "shoot if it is in front of you" addition, the combo pack was devastating and we had to turn down the Defense Drone weapon power to stop it from decimating the snakes too fast. Be careful what you wish for.
    • While I haven't tried it, it seems reasonable you could pick a "better" start value for \(t_{impact}\) by using the non-rotating solution plus a little slop time (maybe the amount of time to rotate to face that position). This has the right "feel" for an initial estimate and seems worth exploring in the future.


    This article presented an approach for predicting the future position of a moving target based on having to rotate to shoot it. A simulation of using the algorithm was also created for you to tinker with. The solution appears to work well for our current needs.

    Article Update Log

    30 October 2014: Initial release

      Report Article
    Sign in to follow this  

    User Feedback

    There's a simple way to get t_min and t_max usefully bounded: think in 1D.
    t_R is easy to bound, since it's between 0 and the time it takes to turn 180 degrees.
    t_B is smallest if they're moving straight at you, and largest if they're moving away


    So that means the following sound like good starting values:

    t_min = |P_s - P_t^1| / (S_b + |v_T|)

    t_max = pi/w_r + |P_s - P_t^0| / |(S_b - |v_T|)|

    Share this comment

    Link to comment
    Share on other sites

    There's a simple way to get t_min and t_max usefully bounded: think in 1D.
    t_R is easy to bound, since it's between 0 and the time it takes to turn 180 degrees.
    t_B is smallest if they're moving straight at you, and largest if they're moving away


    So that means the following sound like good starting values:

    t_min = |P_s - P_t^1| / (S_b + |v_T|)

    t_max = pi/w_r + |P_s - P_t^0| / |(S_b - |v_T|)|


    The idea behind the min/max times looks like a solid approach.  Good feedback.


    I think you meant "P_t^0", not "P_t^1" in the t_min calculation, right?


    The t_max calculation should be checked to make sure S_b != |v_T|. If they are "pretty close" to each other, you may get a t_max that is very large.  I think it is valid to take min(t_max,"reasonable shot window") to prevent this.  Thoughts?

    Share this comment

    Link to comment
    Share on other sites

    Yes, I definitely meant "P_t^0".  Apparently I only fixed one when I noticed it :|


    Good point on the possibly-infinite (in floating-point) t_max.  I suppose another possible parameter would be D_b, the range of the bullets, which would bound the B part of t_max by D_b/S_b.  In 2D I suppose that D_b is the diagonal of the screen, but if you have gravity, then (without air friction) D_b = (S_b)^2 / g.  Or of course it can be an arbitrary choice to get the weapon feelings right (no pistol sniping).


    Have you compared convergence of the binary-search method with other options?  Once you're allowed iterative methods, there are some unsophisticated options.  For example, figure out how long it would take for a bullet to get where he is.  Since you're pretending he's not moving, this is trivial.  Then figure out where he'd be then, and repeat until you're close enough either in time or in space.


    I'd be curious how the costs in iterations and complexity compared.  One advantage of the above approach is that it works best when the target is stationary (only one iteration), whereas a divide-and-conquer approach takes the most iterations at the edges of the range.

    Share this comment

    Link to comment
    Share on other sites

    The value of maxDist is part of the loop and should represent how far you are willing to shoot.  You could calculate t_max from this and compare it to the other calculations to further bound it in.  I haven't factored in gravity.  


    I'm actually somewhat reluctant to add many bounds to the time ranges, other than a simple time limit (and max range, and I think your t_max/t_min calcs), because I may end up constraining the calculation unnecessarily and miss some opportunities to shoot.  These calculations are not run in a tight loop, but on an as-needed basis...and they could even be spread out over frames.  A few extra tiny spikes vs. some riskier shots by the AI seems like a good balance.


    As to comparison of timing, I have watched my game simulations and output the data.  But I'm going to ignore that and propose a thought experiment instead.  This is a binary search, which cuts the search range in half every time.  If your goal is to get a value that is accurate to within, say, 1 degree.  And you start out with a range of 180 degrees, the progression should be (I think) 180, 90, 45, 22.5, 11.25, 5.625, 2.8,1.4,0.7, done.  So about 8 iterations.  At 30 fps if you spread this out, that's 8 frames or about 1/3 of a second.  Which seems like a reasonable time to make a "where do I shoot" choice.  Or if you do it faster, who will notice.  


    There are probably other iterative ways to solve this...they may converge faster.  I favor the predictable nature and lack of numerical divergence in this option.  I'd be happy to see other examples.  

    Share this comment

    Link to comment
    Share on other sites

    The next time I read a website, I expect that it doesnt disappoint me as much as this one. I mean, I understand it was my choice to read, but I really thought youd have something fascinating to say. All I hear is a group of whining about something you could fix if you werent too busy looking for focus. lords mobile hacks

    Share this comment

    Link to comment
    Share on other sites

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!