views:

486

answers:

7

TL;dr: "I am not sure how to calculate a smooth transition of thrust between one vector and another."

I am programming a simple game where an enemy chases after the player in an open space (no walls). I was calculating the enemy's x & y velocities independently, accelerating them if they were taking them in the direction of the player and quickly slowing them if they were going the wrong way (e.g. EnemyVelocity.x > 0 & player.x < enemy.x, then EnemyVelocity.x - 2.)

While the gameplay is decently fun trying to dodge the enemy, it is my desire to have the enemy behave using proper physics. What I am currently doing is have the enemy set their thrust (think a spaceship) based on the angle between them and the player, and have their thrust accelerate up to a max speed (calculating side c of the EnemyVelocity triangle). Once that happens, I'm not sure the best way to have the thrust adjust itself. If I leave no max speed, the enemy accelerates nicely but will easily overshoot the player, and then take a long time to get enough momentum heading back in the player's direction.

What I'd like to happen is have the enemy constantly adjust their velocity on the way to the player, targeting wherever they are at (I don't want them to predict where you will be). Then, when they miss the player, I'd like for the same thrust & acceleration formulas to readjust their velocity and send them back at the player.

I'm thinking this will involve two vectors: one where the enemy is currently traveling, and one where the enemy wants to travel (the vector that will take them straight to the player). I am not sure how to calculate a smooth transition of thrust between one vector and another.

Any tips, formulas or questions will be much appreciated! Thank you Stack Overflow.

+2  A: 

You may get the effect you want by ensuring a smooth change in velocity, rather than thrust. That way, if the enemy overshoots the player, it can immediately reverse its acceleration, which will slow it down and eventually reverse its direction of travel.

You can accomplish this by changing the velocity during each iteration, by a small amount that's based on the distance from the enemy to the player:

while (game_in_progress)
{
    // Distance from enemy to player.  The larger the
    // distance, the greater the acceleration will be.
    delta.x = player.x - enemy.x
    delta.y = player.y - enemy.y

    // Accelerate by changing velocity based on distance,
    // where 'scale' is sufficiently small. (Limit v to
    // some maximum if you choose; likely to be unnecessary.)
    v.x += delta.x * scale
    v.y += delta.y * scale

    // Update the enemy's position.
    enemy.x += v.x
    enemy.y += v.y
}

By calculating the x and y values independently, you can save yourself the headache of dealing with vectors, angles, and simultaneous equiations.

Similarly, by recognizing that acceleration (thrust) is simply a change in velocity, which in turn is a change in position, you can create a discrete-time simulation using only simple algebra instead of calculus.

Have fun!

Adam Liss
+1  A: 

I wrote a simple asteroids game a while back that had an "ally" ship which would hunt down asteroids and shoot at them for you. Basically it found the closest asteroid then started smoothly turning towards it and going after it. Sadly i don't have the code anymore but if memory serves, i think i tured the ship a little each turn, then if the asteroid was far away i accelerated but if it was close i tried to match the asteroid's speed. It was pretty cool actually, and a minimum of algebra involved.

The best way to do it would be to take 2 radian values and lerp between them, handling wrapping. (perhaps by adding or subtracting 2pi where necessary). Then convert it to a unit vector. Subsequently multiply that by the speed you want the ship to accelerate, and there you go!

RCIX
+2  A: 

You need to think in proper physics terms. You have a velocity, and you want to add an acceleration. That's all there is to it - the acceleration is a gradual change in velocity that will draw the enemy towards to player, allow it to overshoot, slow down (or turn) and then head back towards the player.

Acceleration is measured as d(velocity)/time. You want to accelerate towards the player at any point in time, so every interval (second, hundredth of a second or whatever you choose) you need to add the vector between enemy and player, multiplied by some constant, to your velocity.

Velocity = Velocity + c * (Player-Enemy vector)

Constant c will depend on how fast you want to accelerate towards the player, and how often you are updating your velocity.

If you want to 'cap' the maximum speed of the enemy so that it doesn't continue to increase the magnitude of its velocity indefinitely, you can also do so.

Velocity = Velocity * (Maximum magniture / |Velocity|)

EDIT: to clarify further, adding a Velocity simply means adding the component vectors. So

Vx = Vx + c * Ax
Vy = Vy + c * Ay

where V is velocity and A is acceleration. Magnitude is measured as sqrt(Vx^2 + Vy^2), ie the hypotenuse of a right triangle. So if you want maximum speed of the enemy to be m,

Vx = Vx * ( m / sqrt(Vx^2 + Vy^2)
Vy = Vy * ( m / sqrt(Vx^2 + Vy^2)
Kirk Broadhurst
Then obviously 'add' the new velocity to the enemy's position. :-)
Kirk Broadhurst
I'm not sure I understand the math in: Velocity = Velocity * (Maximum magniture / |Velocity|). In Vx = Vx + c * Ax, Ax would be the X component of the player-enemy vector, correct?
Yes, in this exercise Ax is the x component of the player-enemy vector. More generally Ax is the x component of acceleration, but it suffices to use the player-enemy vector as the acceleration.
Kirk Broadhurst
Kirk's is essentially the same as Imagists, except that Kirk has encapsulated (hidden) the vector math, whereas Imagist has made it explicit. That is why Kirk's seems simple but you can't figure out the math, but Imagist's seems too complicated, but the math is straight-forward.
RBarryYoung
Kirk Broadhurst
+1  A: 

One simple way (not proper physics) is to calculate your enemy's "desired velocity" and then adjust enemy's currently velocity towards that, minding whatever limits on top, or minimum speed it has.

For instance, in a little 2d game I wrote (http://wordwarvi.sourceforge.net) there are "heat seeking missiles." It looks pretty weird if the missiles stop in midair to turn around. So what I did was as follows: I calculate a "desired velocity" which is towards the player. This is just done by "similar triangles". I find the distance to the player in X, and in Y, and whichver is greater, I make the "desired (x or y) velocity be the maximum possible, and then scale the other one to fit the "similar triangle." Note, that's just the "desired velocity," not the current velocity. I take the current velocity and adjust it slowly (by a little bit per frame) towards the "desired" velocity (though the desired velocity is recalculated per frame as well,) mindimg minimums on vx and vy to keep them from stopping mid-air.

Dumb algorithm, but it works ok (nobody's complained that they are too easy, too hard, or too unrealistic.)

Edit: on re-reading the question, my answer is probably not what you're after.

smcameron
How do you calculate the adjustments? Do you take off x and add to y for example, if the target velocity was more "Y" away than "X" away?When you say "desired x or y" you mean based on whichever is greater to the player, right? (Just confirming what I think you said).
Why is this "not proper physics"? What you're describing is almost exactly what would happen if you were steering a space ship by changing the direction of its thruster. If the velocity adjustment varies, you're also controlling the power to the thruster. If it's constant, your thruster is stuck on full power. I'd suspect that's a case that NASA actually accounts for. :-)
Adam Liss
Adam Liss: It's not proper physics because I'm not doing anything like F = ma, and for instance, my max velocities are limited independently in x and y, so the thing can travel sqrt(2)*max in diagonal directions, but only max horizontally or vertically. It's a very very crude approximation good enough only to be fun in a video game.
smcameron
smcameron
+1  A: 

It all comes back to Newton's equations:

F = m * a
s = s_o + v * t + a * t^2 / 2
v = v_o + a * t

In this case F is the force (thrust), a is the acceleration, and m is the mass of the ship. s is the current location, s_o is the original location, v is the velocity, and t is the current time.

Of course this is along a straight line, so if you want to convert to two or three dimensions you'll have to do some math. F, s, v, and a are all vectors, meaning that their direction is equally important. Technically t is also a vector, but since time generally only goes one direction, we don't have to worry about that.

2d:
F^2 = F_x^2 + F_y^2 (use Pythagorean theorem to split force into components)
F_x = m * a_x
F_y = m * a_y
s_x = s_o_x + v_x * t + a_x * t^2 / 2
s_y = s_o_y + v_y * t + a_y * t^2 / 2
v_x = v_o_x + a_x * t
v_y = v_o_y + a_y * t

3d:
F^2 = F_x^2 + F_y^2 + F_z^2 (surprisingly, this works)
F_x = m * a_x
F_y = m * a_y
F_z = m * a_z
s_x = s_o_x + v_x * t + a_x * t^2 / 2
s_y = s_o_y + v_y * t + a_y * t^2 / 2
s_z = s_o_z + v_z * t + a_z * t^2 / 2
v_x = v_o_x + a_x * t
v_y = v_o_y + a_y * t
v_z = v_o_z + a_z * t

Now to adjust your velocity to the direction of the player, you've got a fixed total force (F) in order to change your current velocity toward the player. In physics things don't happen instantaneously, but your goal should be to minimize the time in which the change happens ('t').

This gives you an equation in terms of your current location ((s_o_x,s_o_y) or (s_o_x,s_o_y,s_o_z)) and your opponent's current location or your target location ((s_x,s_y) or (s_x,s_y,s_z)), for your target velocity (ignores acceleration).

v_x = (s_x - s_o_x) / t
v_y = (s_y - s_o_y) / t

v_x = (s_x - s_o_x) / t
v_y = (s_y - s_o_y) / t
v_z = (s_z - z_o_y) / t

We can substitute this for our other equation:

(s_x - s_o_x) / t = v_o_x + a_x * t
(s_y - s_o_y) / t = v_o_y + a_y * t

(s_x - s_o_x) / t = v_o_x + a_x * t
(s_y - s_o_y) / t = v_o_y + a_y * t
(s_z - z_o_y) / t = v_o_z + a_z * t

We then solve for the acceleration (this is related to the force, which is what we are trying to calculate).

(s_x - s_o_x) / t^2 - v_o_x / t = a_x
(s_y - s_o_y) / t^2 - v_o_y / t = a_y

(s_x - s_o_x) / t^2 - v_o_x / t = a_x
(s_y - s_o_y) / t^2 - v_o_y / t = a_y
(s_z - z_o_y) / t^2 - v_o_z / t = a_z

Plug this into the force equation:

F_x = m * (s_x - s_o_x) / t^2 - m * v_o_x / t
F_y = m * (s_y - s_o_y) / t^2 - m * v_o_y / t

F_x = m * (s_x - s_o_x) / t^2 - m * v_o_x / t
F_y = m * (s_y - s_o_y) / t^2 - m * v_o_y / t
F_z = m * (s_z - z_o_y) / t^2 - m * v_o_z / t

Now solve for t:

t = (-m * v_o_x +/- sqrt(m^2 * v_o_x^2 - 4 * F_x * m * (s_x - s_o_x))) / 2 / F_x
t = (-m * v_o_y +/- sqrt(m^2 * v_o_y^2 - 4 * F_y * m * (s_y - s_o_y))) / 2 / F_y

t = (-m * v_o_x +/- sqrt(m^2 * v_o_x^2 - 4 * F_x * m * (s_x - s_o_x))) / 2 / F_x
t = (-m * v_o_y +/- sqrt(m^2 * v_o_y^2 - 4 * F_y * m * (s_y - s_o_y))) / 2 / F_y
t = (-m * v_o_z +/- sqrt(m^2 * v_o_z^2 - 4 * F_z * m * (s_z - s_o_z))) / 2 / F_z

The times should converge, so the times will be equal! This gives us a system of equations for each coordinate (plane and sphere). Note that there are multiple possible values, but some involve imaginary numbers so you'll have to eliminate those solutions:

(-m * v_o_x +/- sqrt(m^2 * v_o_x^2 - 4 * F_x * m * (s_x - s_o_x))) / 2 / F_x
= (-m * v_o_y +/- sqrt(m^2 * v_o_y^2 - 4 * F_y * m * (s_y - s_o_y))) / 2 / F_y
F^2 = F_x^2 + F_y^2

(-m * v_o_x +/- sqrt(m^2 * v_o_x^2 - 4 * F_x * m * (s_x - s_o_x))) / 2 / F_x
= (-m * v_o_y +/- sqrt(m^2 * v_o_y^2 - 4 * F_y * m * (s_y - s_o_y))) / 2 / F_y
= (-m * v_o_z +/- sqrt(m^2 * v_o_z^2 - 4 * F_z * m * (s_z - s_o_z))) / 2 / F_z
F^2 = F_x^2 + F_y^2 + F_z^2

Solve for the (F_x,F_y) or (F_x,F_y,F_z) coordinates and you've got the force you need.

Let me know if you have any questions or if you find mistakes in my math.

Imagist
Thank you for your post. It looks the most complicated so I am going to try a few others before implementing this!
RBarryYoung
RBarryYoung is right, this is much cleaner with vector classes. Also, while this seems very complicated, it's also "how the real world does it". Getting used to using Newton's equations will make all the movement algorithms you do easier.
Imagist
Well, its a good approximation for "how the real world does it" and it stood the test of hundreds of years before Einstein offered alternatives :-)
Will
+1  A: 
Beta
+1  A: 

There are just a few pointers to get this right and easy. 1) it's easiest and most general to work with vectors rather that writing everything two or three times. 2) things will look right if you control the force (which is effectively the acceleration since A=F/mass) and then dynamically evolve the velocity and position.

Your basic loop for realistic motion looks like (where the CAPs are vectors and dt is your timestep):

while (motion) {
   A = get_acceleration(X, V, A, X_target, V_targer, A_target)
   V += A*dt       // V is the integral of A
   X += V*dt       // X is the integral of V
}

And really, this is about it for you're dynamic evolution.

Then you need to decide how to determine your acceleration, i.e. write get_acceleration. There are a number of options here that depend on multiple factors, and real-life chasers employ multiple strategies. For example, if you have a lot of thrust relative to your mass (i.e. high acceleration) you probably just want to head straight at the target; but if you have a lot of mass relative to your thrust you probably want to make an interception course. If you want to slow down as you approach the target, you could reverse the acceleration when |X-X_target| becomes small (i.e. they get close) and/or their velocities are close. Also, damping can help things not oscillate, and for this, add a term to the acceleration something like -c*(V-V_target). I suggest you play around with these until you get something that matches the physical look and feel that you're aiming for.

tom10