Started by Nov 01 2011 03:15 PM

,
9 replies to this topic

Posted 01 November 2011 - 03:15 PM

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.

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.

Posted 01 November 2011 - 04:26 PM

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

Posted 01 November 2011 - 04:49 PM

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:

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:

3) The impact point is where the target is the same distance from Gun as the projectile is at time t.

4) Armed with these expressions, we can do substitute the equations for Target.X and Target.Y from (2) into (3)

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:

6) Re-arrange and simplify the expression:

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:

You can find the solution of a quadratic equation by

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.

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.

Posted 01 November 2011 - 05:39 PM

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.)

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.)

Posted 01 November 2011 - 10:41 PM

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

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

Posted 01 November 2011 - 11:30 PM

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 :-)

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 :-)

Posted 02 November 2011 - 09:31 AM

Here's my code (AS3). I'm multiplying the time by the player's speed.

Hope I've not done anything too dumb

//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

Posted 02 November 2011 - 10:36 AM

Here is a drop-in implementation of the algorithm I posted earlier:

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.

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.

Posted 02 November 2011 - 12:06 PM

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.

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.

Posted 02 November 2011 - 12:19 PM

An outside the box solution, which may not be what you are looking for, is to have an enemy that paths differently than other enemies. Performing flanking behavior essentially. That removes circling the enemies and creates some cool emergent behavior including the semblance of AI that has teamwork, even though the ai isn't really working together.

You could do something as simple as the way the pacman ghosts work. One ghost sets his navigation target to the player's position, one sets his target to a position behind the player, and one sets his target to a position in front of the player.

If you look at geometry wars enemies you'll get a good idea of how this effect works. With just the blue diamonds (enemies that just follow the player) you can easily fly in circles around the flock. Introducing the green squares (enemies that follow the player and are faster than the player, but avoid the player's bullets) the player now has to juggle the flocking behavior of two enemies. Then you add enemies who just wonder around aimlessly and now the player has to keep moving to avoid blue diamonds, keep herding the green squares to keep them from catching him, and dodge random floating pinwheels.

Your solution is just as viable, just making sure you account for other possible solutions that might also make your game interesting.

You could do something as simple as the way the pacman ghosts work. One ghost sets his navigation target to the player's position, one sets his target to a position behind the player, and one sets his target to a position in front of the player.

If you look at geometry wars enemies you'll get a good idea of how this effect works. With just the blue diamonds (enemies that just follow the player) you can easily fly in circles around the flock. Introducing the green squares (enemies that follow the player and are faster than the player, but avoid the player's bullets) the player now has to juggle the flocking behavior of two enemies. Then you add enemies who just wonder around aimlessly and now the player has to keep moving to avoid blue diamonds, keep herding the green squares to keep them from catching him, and dodge random floating pinwheels.

Your solution is just as viable, just making sure you account for other possible solutions that might also make your game interesting.