Public Group

This topic is 2568 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've tried looking this up but couldn't find anything basic enough for my beginner maths skills to understand.
Isn't much more than what's in the Topic title, would like monsters to be able to shoot at where a player is moving to rather than just directly at them.

##### Share on other sites
Assuming you're comfortable with basic algebra and at least rudimentary vector arithmetic:

• Compute the distance between the player and the enemy
• Divide the distance by the speed of the projectile to determine how long it will take for the shot to reach the player
• Take the player's current velocity vector
• Scale the velocity vector by the time taken for the shot to arrive
• Sum this vector with the player's current position
• This gives you the target location you should aim at

##### Share on other sites
It's actually a bit more complicated than that in truth, as you aren't trying to calculate the time to get to where the player is currently at, but rather the time where the player will be when the bullet hits. This resolves to a quadratic equation.

Assume the shooter is at position Gun and is stationary, the target is at position TargetStart and is moving along the velocity vector TargetVel . Gun shoots a bullet that travels at BulletSpeed, that starts at Gun and moves along the vector BulletVec to strike the target at the impact point, called Bullet. Okay?

The time, t, denotes the time it takes for the bullet to strike the target. So at time t, the bullet will have traveled a distance of t*BulletSpeed and the Target will have moved a distance t*TargetSpeed. The impact point will be at a distance t*BulletSpeed from Gun and t*TargetSpeed from TargetStart, where TargetSpeed is the speed component, or length, of TargetVel. Armed with this knowledge, we can begin deriving some equations.

1) Impact will be at a distance of t*BulletSpeed from Gun, so that suggests the equation for the projectile as a parametric circle centered at Gun. Recall that a circle, of course, is all points that are a given distance from the center. In this case, all points that are t*BulletSpeed distance from center:
 (Bullet.X - Gun.X) * (Bullet.X - Gun.X) + (Bullet.Y - Gun.Y) * (Bullet.Y - Gun.Y) = (t * BulletSpeed) * (t * BulletSpeed) 

2) In the time, t, that it takes the bullet to reach the impact point, Bullet, the target is also moving a distance equal to t*TargetSpeed. So the location that the target will be at at time t can be calculated as:
 Target.X = TargetStart.X + TargetVel.X * t; Target.Y = TargetStart.Y + TargetVel.Y * t; 

3) The impact point is where the target is the same distance from Gun as the projectile is at time t.
 (Target.X - Gun.X) * (Target.X - Gun.X) + (Target.Y - Gun.Y) * (Target.Y - Gun.Y) = (Bullet.X - Gun.X) * (Bullet.X - Gun.X) + (Bullet.Y - Gun.Y) * (Bullet.Y - Gun.Y) 

4) Armed with these expressions, we can do substitute the equations for Target.X and Target.Y from (2) into (3)
 ((TargetStart.X + TargetVel.X*t) - Gun.X) * ((TargetStart.X + TargetVel.X*t) - Gun.X) + ((TargetStart.Y +TargetVel.Y * t) - Gun.Y) * ((TargetStart.Y + TargetVel.Y * t) - Gun.Y) = (Bullet.X - Gun.X) * (Bullet.X - Gun.X) + (Bullet.Y - Gun.Y) * (Bullet.Y - Gun.Y) 

5) Now, for the other side of the equation, we can substitute in (1) to get rid of the unknowns, Bullet.X and Bullet.Y:
 ((TargetStart.X + TargetVel.X*t) - Gun.X) * ((TargetStart.X + TargetVel.X*t) - Gun.X) + ((TargetStart.Y +TargetVel.Y * t) - Gun.Y) * ((TargetStart.Y + TargetVel.Y * t) - Gun.Y) = (t * BulletSpeed) * (t * BulletSpeed) 

6) Re-arrange and simplify the expression:
 ((TargetVel.X * TargetVel.X) + (TargetVel.Y * TargetVel.Y) - (BulletSpeed * BulletSpeed)) * t*t + 2*(TargetVel.X * (TargetStart.X - Gun.X) + TargetVel.Y * (TargetStart.Y - Gun.Y)) * t + ((TargetStart.X - Gun.X) * (TargetStart.X - Gun.X)) + ((TargetStart.Y - Gun.Y) * (TargetStart.Y - Gun.Y) = 0 

7) (6) Looks a bit ugly, and I glossed over a bit of simplification, but if you look at it what you have is a quadratic equation. Recall that a quadratic equation is of the form a*t*t + b*t + c = 0. The above equation follows this form, with values for a,b,c as follows:

 a = ((TargetVel.X * TargetVel.X) + (TargetVel.Y * TargetVel.Y) - (BulletSpeed * BulletSpeed)) b = 2*(TargetVel.X * (TargetStart.X - Gun.X) + TargetVel.Y * (TargetStart.Y - Gun.Y)) c = ((TargetStart.X - Gun.X) * (TargetStart.X - Gun.X)) + ((TargetStart.Y - Gun.Y) * (TargetStart.Y - Gun.Y) 

You can find the solution of a quadratic equation by
 t = (-b (+ or -) sqrt(b*b - 4 * a * c)) / (2 * a) 

8) 7 can have either 0, 1 or 2 possible solutions. Cases in which there are 0 solutions include instances where the projectile could not possibly hit the target in any given amount of time, given the target position and velocity and the bullet velocity. ie, the target moves out of range too fast, was never in range to start with, etc... Cases where there are 2 solutions include solutions with a -t value, or time-traveling bullets that can go back in time to hit the target where it was back then. Which would be kind of awesome if you think about it, but I bet they'd be way overpowered.

Bear in mind the above was taken from some rather chicken-scratch notes I had made a long time ago when I was deriving this solution, so I'm not actually 100% sure it's all correct, but it seems right. It's not an extremely complicated problem, but it does take a bit of figuring.

##### Share on other sites
The method I described is certainly approximate, but it goes a long way towards preventing your enemies from being impossibly hard to dodge. It's also a lot simpler to calculate, which IMO makes it advantageous for a beginner.

You are absolutely correct that it is not perfect, though!

(Of course you can always go super-overkill and compute the actual equation that includes the acceleration and velocity of both the player and the enemy, includes windage effects, etc. etc., but the calculus gets a bit hairy.)

##### Share on other sites
Hidden
I am planning to release a paper which can explain how to make any type of projectile (instance-fire, straight rockets, grenades, wavy alien guns, etc.) hit any target as long as its path is not interrupted by player input.
That is, the target can just fall and accelerate, or it could land on the ground and stop, or bounce off a wall, etc. Since all of these can be predicted and measured, an AI can account for them while taking aim.

While some of these resolve to quartic functions, and if you want to account for the target hitting walls or floors you will need to have a collision-detection routine handy, but I will also present a fairly intuitive and straight-forward method that handles every gun type and target-motion type. If you don't have the ability to account for hitting walls etc., you can still use the method (without accounting for every type of target motion) and it is simple to implement.

Unfortunately you will have to wait a while. I am very busy these days.

L. Spiro

Thanks for the replies! I briefly tried ApochPiQ's technique...it didn't seem to work until I tried multiplying the time up at which point the leading seemed to start having an effect. I don't know if at this point I'm just scaling up the player's velocity by a random amount that happens to be about right and aiming at that though

However the game in question is a horde based shooter and I was mainly looking for a way to prevent circling monsters from rendering them harmless. This actually seems to be close to what I need as the bit of inaccuracy only increases the apparent chaos around the player, which is great

I'm interested in looking into it further...though I don't really understand FLeBlanc right now. I need to read over that again :E

##### Share on other sites
I realize that I omitted one important detail, assuming it would be clear enough, but that may not be the case: when you scale the player's velocity by the estimated impact time, you should first normalize the velocity then multiply by the time factor. Although honestly unless your world units are at a very different order of magnitude than I usually use, that should result in overcorrection instead of what you describe, so... maybe it's something else :-)

Any chance you could post the aiming code for examination? Shouldn't be more than 15-20 lines worth of stuff, ideally, so no big deal for us to help check your math :-)

##### Share on other sites
Here's my code (AS3). I'm multiplying the time by the player's speed.

//Compute the distance between the player and the enemy var v1:Vector2D = new Vector2D(newBullet.position.x - player.position.x, newBullet.position.y - player.position.y); var dist:Number = Math.sqrt(v1.a * v1.a + v1.b * v1.b); //Divide the distance by the speed of the projectile to determine how long it will take for the shot to reach the player var time:Number = dist / Monsters.trooperRangedSpeed; // RangedSpeed = 6 //Take the player's current velocity vector var v2:Vector2D = new Vector2D(player.movement.a, player.movement.b); //Scale the velocity vector by the time taken for the shot to arrive v2.a = v2.a / v2.magnitude; v2.b = v2.b / v2.magnitude; v2.a *= time * 4; // <--- scaling time by player velocity seems to give closer results v2.b *= time * 4; //Sum this vector with the player's current position v2.a += player.position.x; v2.b += player.position.y; //This gives you the target location you should aim at // Shoot

Hope I've not done anything too dumb

##### Share on other sites
Here is a drop-in implementation of the algorithm I posted earlier:

 bool calcInterceptTrajectory(vec2 &gun, vec2 &targetstart, vec2 &targetvel, float bulletspeed, vec2 &impactpoint, vec2 &bullettrajectory) { // The coefficients of the quadratic equation: // a = ((TargetVel.X * TargetVel.X) + (TargetVel.Y * TargetVel.Y) - (BulletSpeed * BulletSpeed)) // b = 2*(TargetVel.X * (TargetStart.X - Gun.X) + TargetVel.Y * (TargetStart.Y - Gun.Y)) // c = ((TargetStart.X - Gun.X) * (TargetStart.X - Gun.X)) + ((TargetStart.Y - Gun.Y) * (TargetStart.Y - Gun.Y) float a = ((targetvel.x * targetvel.x) + (targetvel.y * targetvel.y) - (bulletspeed * bulletspeed)); float b = 2.0f * (targetvel.x * (targetstart.x - gun.x) + targetvel.y * (targetstart.y - gun.y)); float c = ((targetstart.x - gun.x) * (targetstart.x - gun.x)) + ((targetstart.y - gun.y) * (targetstart.y - gun.y)); // First, calculate the discriminant to see if we can even make the shot float disc = b*b - 4.0f*a*c; // If the discriminant is <0, there is no chance of hitting the target. Just not gonna happen, not in this universe of real numbers if (disc < 0.0f) return false; if (a==0.0f) return false; // Avoid the case of a divide-by-zero // Calculate the possible solutions float t1 = (-b + sqrt(disc)) / (2.0f * a); float t2 = (-b - sqrt(disc)) / (2.0f * a); float t = std::max(t1, t2); if (t < 0.0f) return false; // Time-traveling bullets are, sadly, not allowed // We get here, we have a valid time. Use it to extrapolate the target's position at time t, or the impact point impactpoint=vec2(targetstart.x + t * targetvel.x, targetstart.y + t*targetvel.y); // And subtract to obtain the vector along which to shoot bullettrajectory = vec2(impactpoint.x - gun.x, impactpoint.y - gun.y); // Normalize it to unit length float len=sqrt(bullettrajectory.x * bullettrajectory.x + bullettrajectory.y * bullettrajectory.y); bullettrajectory.x /= len; bullettrajectory.y /= len; return true; } 

To use the above, pass in the gun location, the target starting location, the target velocity vector and the bullet speed. The function will return false if the shot can not be made, and will calculate impact and bullettrajectory then return true if the shot can be made. I just now tested it in a quick and dirty SFML app and it seems to work fine.

Note that as others noted, this is a linear simplification of general-case trajectory calculation. It doesn't take into account curved target trajectories, accel/decel, etc... So in your use-case of shooting at an opponent circling around you, this method would be little better than an approximation, since the target's trajectory is always changing. Target prediction that takes into account accel/decel and also the possibilities of a target randomly changing direction, even if the constraints of the target's possible movement (maximum acceleration and deceleration, turn radius, etc..) are known, is a god-awful ugly problem that may be ultimately unsolvable in many cases, and probably outside of your requirements. Sure, the Navy might need to know exactly where and when to put their torpedo in the water, but shit son, this is video games.

##### Share on other sites
I feel a bit like a moron now, but your math should actually do the right thing. (You of course have to take the player's actual velocity into account, because failing to do this will result in pointing in the correct general direction but not the right spot in time, if that makes sense. A good technique for checking your math is to try extreme cases; so compare the results of a player moving 1 pixel per hour to 100 pixels per second; in the latter case, it's pretty obvious that you have to multiply by the player velocity to get to the right target point. So your solution looks fine.)

Only possible mistake I see is the use of v2.magnitude in the middle of changing the components of v2; depending on how magnitude is computed, you might get bad answers when adjusting v2.b because the vector is already partially scaled the second time you ask for its magnitude. If nothing else, I would change this to store v2.magnitude in a temporary variable and divide a and b by that instead, just to make things clear in the code.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633293
• Total Posts
3011236
• ### Who's Online (See full list)

There are no registered users currently online

×