AI algorithm "shoot" at the target in the 2nd game

Question

In my 2nd game, I would like to create a smart bot that can “shoot” the player. Suppose I can go to my bot:

actual xEnemy, yEnemy also enemy speed and angle direction 

How can I calculate where to shoot, given that Bot should rotate the weapon in the right direction?

This is really a big problem for me because .. I absolutely don't understand math! Thanks in advance for your precious help!

Answer 1

Designation: I write vectors in capital letters, scalars in lower case and ∠V for the angle that the vector V makes with the x axis. (Which you can calculate using the atan2 function in many languages.)

The simplest case is a stationary shooter that can rotate instantly.

Let the target be in position A and move with speed VA, and the shooter will be stationary in position B and can shoot bullets with speed s. Let the shooter shoot at time 0. The bullet hits at time t such that | A - B + t VA | = t s. This is a direct quadratic equation with respect to t, which you should easily solve (or determine that there is no solution). By defining t, you can now design the angle of fire, which is simply ∠ (A - B + t VA).

Now suppose that the shooter is not stationary, but has a constant speed VB. (I am assuming Newtonian relativity here, that is, the speed of the bullet is added to the speed of the shooter.)

This is still a simple quadratic equation for determining impact time: | A - B + t (VA - VB) | = t s. In this case, the angle of fire is ∠ (A - B + t (VA - VB)).

What should I do if the shooter waits before the start of shooting? Then the bullet hits the target when | A - B + t (VA - VB) | = (t - u) s. The firing angle is still ∠ (A - B + t (VA - VB)).

Now for your problem. Suppose that the shooter can complete half the rotation in time r. Then it can certainly be triggered at time r. (In principle: to develop the required angle of fire, if any, for a shot at time r, as described above, turn this angle, stop, wait until time r, then shoot.)

But you probably want to know the earliest time that the shooter can shoot. Here, where you probably want to use a sequential approximation to find it. (Sketch of the algorithm: Can you shoot at time 0? No. Can you shoot at time? Yes. Can you shoot at that time ½ r? No, etc.).

Answer 2

What you ask is non-trivial. I will start with the simplest solution and expand it.

First, assume that you and your enemy are motionless. You need to calculate the angle between you and your enemy, turn your weapon to point at the enemy, and then shoot. Use your favorite search engine to find a description of how to find the angle between two points on the plane (you said that 2D).

Once you write the code that can do the above, go to:

Your enemy moves in a constant direction at a constant speed. You are still motionless. This is a surprisingly difficult problem. To simplify, we assume that you can aim at your weapon instantly.

If you know where you are and the enemy, as well as the speed and direction of the enemy, you can at any time determine the position of the enemy (and, therefore, his distance and direction from you).

You know how fast your shell can travel. Therefore, if you draw a line from your current position to intercept any position on the expected path of the enemy’s movement, you can determine how long it will take for your projectile to hit the enemy. Thus, the key is to find a point on the enemy’s path, that if you shot a shell immediately, it crossed the enemy at one time. This usually requires consistent approximations.

If you cannot rotate your weapon instantly, the problem becomes more complex, because the time it takes to rotate your weapon to point at the enemy depends on how fast and in which direction the enemy moves. Additional approximations are required.

Things become even more active when you and the enemy move, although you can build the math so that you "stay motionless." That is, do the conversion of the speed and trajectory of the enemy to reflect how the enemy moves towards you. Then the math becomes identical to the fact that you are motionless.

Mathematics itself is the most elementary trigonometry. You need to know how to calculate the distance between two points, the distance between a line and a point, the angle between two points, calculate the points on a line with a given starting point and direction, and how to rotate around an arbitrary point. These are all well-known issues in which there are many good examples on the Internet. However, you will have to do a little research to find them.

It is probably best to find a good computer graphics tutorial.

Answer 3

The solution to this problem for the “simple” case, when the gun should NOT rotate, was asked and answered several times. I found the best answer in this post (Jeffrey Huntin has a good explanation).

As Jim Michelle said, the answer to the spinning case is not even a little trivial. This is because the amount of rotation you need to do depends on the position of the interception of the target (where the collision occurs). I don’t know if there is a clean, closed solution for this (it seems unlikely given the formulas), but I was able to solve it by working back and iterating to the solution.

The basic idea works as follows:

Suppose your “entity” rotates from its current position to counter the intercept position and then fire immediately.

• Select exposure time.
• Calculate the final position of the target at this time if it moves at a constant speed.
• Calculate how long it takes for the projectile to move to this position.
• Calculate how long it takes for your entity to turn to look at the intercept position.
• Calculate the difference between the stroke time and the rotation / stroke time.
• Adjust the exposure time up / down so that the difference decreases each time (e.g. binary search).
• When you get close, you're done. Otherwise, start the calculation again.

In the simple case, you can find out the quadratic discriminant if you have 0, 1 or 2 solutions and choose the best one. I don’t think you can guarantee it here, but you can relate the range of time that you want to complete and how many iterations you will look for. This works very well in practice.

Since I could not find a solution to this on the Internet, I am going to publish mine. I wrote a function to solve this problem. I have a blog entry around the calculator here . There is also a nice video showing it here .

The code:

 /* 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; }