• Problem Solving Using Vectors

Math and Physics

A few common problems game developers run into is how to rotate a sprite to face a specific direction, finding the angle between two headings, or rotating from one direction to another given a specific turn rate. It is quite common for beginners to try and tackle this problem using an angle to represent rotations and directions. There is a better way.

Overview of Vectors

Polar Coordinates A vector has a direction and magnitude, or length. One way to represent a vector is uing polar coordinates. In polar coordinates the vector's direction is measured by the angle it forms with the positive x-axis. So a vector pointing right is 0 at degress and a vector pointing up is 90 at degress. The vector also has magnitude. This is measured by the distance from the origin of the vector to its end. Rotating a vector in polar coordinates is trivial. You simply change the angle. This simple rotation operation makes the polar representation appealing, but don't take the bait. The polar representation makes other operations more difficult. As a simple example, adding two vectors in polar cannot be done. You would have to convert to rectangular first then back to polar.

Rectangular Coordinates A vector in rectangular coordinates is repesented by an x and y value. This is the location of the head of the vector if you were to plot it on the Cartesian plane. The appeal of rectangular coordinates may not be immediately apparent but as we go over some of the uses of vectors it becomes clear why they are preferred.

Conversion Between Representations While it is better to do all of the mathematical operations in one representation when possible, it is sometimes necessary to convert between the two representations. The conversions are based on the properties of a right triangle. To convert from polar to rectangular:  x = cos(angle) * magnitude y = sin(angle) * magnitude  And to convert back to polar:  // to get the magnitude, use the pathagorean theorem magnitude = sqrt(x * x + y * y) angle = atan2(y, x)  That is it. Just some basic trigonometry.

Unit Vectors

There is a class of vectors called Unit Vectors. Simply put, they have a length of one. This property is very useful when dealing with angles. More on that later. Any vector with a length greater than zero can be normalized or, in other words, be modified to have a length of one. In rectangular coordintes you simply divide both x and y by the magnitude. Normalize a vector:  function normalize() { float magnitude = sqrt(x * x + y * y) x = x / magnitude y = y / magnitude }  The above code has a problem. If the length of the vector is 0 then the x and y values will become invalid. In many languages they become NAN or infinity. If you were to normalize a zero vector with the above code and then try and use it other numbers added to or multiplied by the infinity result, these values will also become infinity. For example, if you normalized the player's velocity that was zero the velocity will be infinite. When you then try and update the position using the infinite velocity, the position will become infinite as well. These invalid values can propogate through the code causing weird things to happen. The fix is fairly easy though.  function normalize() { magnitude = sqrt(x * x + y * y) if (magnitude > 0.0) { x = x / magnitude y = y / magnitude } }  Now the code will leave a zero vector as is, so it wont go corrupting all of the floating point values in the game.

Applications of Vectors

Moving Towards a Target

Let's take an example where we have a turret and we want the turret to fire at the player. How do we calculate the heading of the bullet? Well, it is pretty straight-forward. The first step is finding a vector that represents the direction from the turret to the player.  // subtract the player position from the turret position // to get the direction direction = player.position - turret.position // the above code is really just shorthand for direction.x = player.position.x - turret.position.x direction.y = player.position.y - turret.position.y // when using vectors you should use a vector class that lets you write out // operations like a - b, or a.sub(b) instead of having to subtract // each component individually  Now we have a vector, in rectangular coordinates, that represents the direction from the turret to the player with the magnitude of the vector being distance between the two. If we used that vector as it is for the velocity then the bullet would always take one second regardless of how far the two objects were from each other. We want to be able to control the velocity of the bullet, however. If we were to use polar coordinates we could simply set the magnitude to be the velocity we want, but that would require us to convert to polar to make the change, then back to rectangular in order to update the bullet's position. We want to take the rectangular approach here.  // make the length of direction one direction.normalize() // set the velocity of the bullet bullet.velocity = speed * direction // remember, the above code is the same as bullet.velocity.x = speed * direction.x bullet.velocity.y = speed * direction.y // since speed is just a number value, not a vector, it // scales both components equalily  And that's it. The unit vector direction could also be used to rotate a sprite to face in the same direction, but that will depend on how your graphics library handles the rotation of sprites. If the graphics library expects an angle you will have to extract the angle of direction using atan2 as shown previously in convertering from rectangular to polar.

Angle Between Two Directions

This is where using rectangular coordinates really starts to make sense. You may have come across this problem before. Let's imagine there are two objects moving in different directions and you want to find the angle between their movement. Let's first look at this problem using polar coordinates. This may seem like a simple problem. Simply take the absolute value of one angle minus the other. For example, given the two angles are 50 and 90, you subtract one from the other and are left with 40 degrees. But what if one angle is 310 degress and the other is 20 degrees? Since degrees go up to 360 for a full circle, 360 degrees is the same as 0 degrees, and 20 degrees is the same as 380. If we applied the basic algorithm to 20 and 310 we get 290 degrees. However, since 20 is the same direction as 380 we can substitute them out and using 380 and 310 we are left with 70 degrees, the actual rotation we were after. There are algorithms that can handle this problem while staying in polar coordinates but I am not going to show that here. We are interested in using rectangular coordinates. To find the angle between vectors, we will use a useful little equation called the dot product and is defined as follows:  // dot product dot(a, b) = a.magnitude * b.magnitude * cos(angleBetween(a,b)) // also equal to dot(a, b) = a.x * b.x + a.y * b.y  So how can we use this equation to find the angle between a and b in rectangular coordinates? Simply set the two equations equal to each other and solve for the angle. The angle measure calculated here is smallest angle between to vectors meaning it could be a clockwise or a counter clockwise direction and the angle measure returned will always be between 0 and pi radians, or 0 to 180 degrees.  angleBetween(a,b) = acos((a.x * b.x + a.y * b.y) / (a.magnitude * b.magnitude))  This equation can be even simpler if we represent directions using unit vectors, since the magnitude of a unit vector is one. Keep in mind this only works if the two vectors are unit vectors.  angleBetweenUnitVectors(a,b) = acos(a.x * b.x + a.y * b.y) // also the same as angleBetweenUnitVectors(a,b) = acos(dot(a,b))  And there we have it, the angle between two unit vectors. This is a simple, elegant solution to the problem written as a single line of code.

Rotate by Another Angle

Another common problem in games is changing an object's heading by a certian amount. For example, if we need to rotate the heading of an object by five degrees every frame. It isn't immediately apparent how to do this in rectagular coordinates. The answer is fairly simple. You simply multiply the two vectors together as if they were imaginary numbers. Actually, 2D vectors in essence are complex numbers where x is the real part and y is the imaginary part.  (a + bi) * (c + di) = (a*c - b*d) + (b*c + a*d)i // or using x and y function rotateVector(Vector2 a, Vector2 b) { float x = a.x * b.x - a.y * b.y; float y = a.x * b.y + a.y * b.x; return new Vector2(x, y); }  For 2D vectors, it doesn't matter the order of a and b. Switching them will give the same answer. However, this function also has the effect where the resulting vector's magnitude is a.magnitude * b.magnitude. So when rotating vectors where you want to preserve the magnitude, use a unit vector.  function unitVector(float angle) { // this returns a unit vector in the direction of angle // it will always be of length 1 since, in this case // magnitude = cos(angle)^2 + sin(angle)^2 = 1 return new Vector2(cos(angle), sin(angle)); } // rotate the velocity by 10 degress velocity = rotateVector(velocity, unitVector(degToRads(10))) 

Rotate Towards Target

In this situation we want to take the current heading of the object and rotate to face a new heading. A great example is a turret that can only turn a certain amount of degrees per second. We want to make sure it always turns in the most direct way. For example, if the player is directly to the turret's left we don't want the turret to turn 270 degrees to the right, we want it to turn 90 to the left. To do this, we will need to add one more tool in our toolbox: Slerping. Slerp is short for Spherical linear interpolation. To understand how it works first imagine two vectors both coming out of the origin. Then draw a path from the end of one vector to the other. In reality, there are an infinite number of ways to get from point a to point b, but we are interested in a direct path that smoothly changes the angle of a vector. The the path we want the point to travel along is a curved path between the ends of the vectors forming circles or sections of circles. This is what slerping is and is implemented as follows:  // a and b should be unit vectors // t is a value in the range [0, 1] // when t = 0, slerp returns a // when t = 1, slerp returns b // any value between 1 and 0 will be // vector between a and b function slerp(Vector2 vectorA, Vector2 vectorB, float t) { float cosAngle = dot(vectorA, vectorB); float angle = acos(cosAngle); return (vectorA * sin((1 - t) * angle) + vectorB * sin(t * angle)) / sin(angle); }  There is a lot there to take in. You might have to do a little more research on slerping to fully understand it. You will want to use somebody else's implementation of it however, the simple implimentation shown here will have some stability issues when vectorA and vectorB are pointing nearly in the same direction due to floating point rounding errors. Anyway, now we have our slerp so let's use it to help us rotate towards a target.  // rotates rotateFrom towards rotateTo by maxDeltaTheta radians and returns // the result. If the angle between them is less than maxDeltaTheta then it // simply returns rotateTo // rotateFrom and rotateTo should both be unit vectors function rotateTowards(Vector2 rotateFrom, Vector2 rotateTo, float maxDeltaTheta) { float angleBetween = acos(dot(rotateFrom, rotateTo)); if (angleBetween <= maxDeltaTheta) { return rotateTo; } else { return slerp(rotateFrom, rotateTo, angleBetween / maxDeltaTheta); } } // and an example of how it can be used Vector2 playerOffset = player.position - turret.position // the input to rotates towards needs to be a unit vector playerOffset.normalize() // turretDirection is a unit vector specifying where the turret is pointing // delta time is a float holding the number of seconds between this frame and the last // turretTurnRate is the turn rate of the turret in radians/second turretDirection = rotateTowards(turretDirection, playerOffset, turretTurnRate * deltaTime)  You may have noticed how rotateTowards calculates the angle between the two vectors and that some calculation is done right away inside of slerp. It would probably be a good idea to inline the slerp code into rotateTowards so it doesn't have to do the redundant calculation, but I will keep it seperate here for simplicity.

Conclusion

As I have created games I have found using vectors to be vastly more useful than trying to represent directions using angles. Vectors have always led me to more robust and elegant solutions that always seems to exhibit correct behavior, even in the odd cases that I didn't think to try. The more familiar you get with them the easier it becomes to manipulate a game world with ease, allowing you to complete seemingly hard challenges simply by building off the basic building blocks of vector operations. If you are serious about game development then you should understand how vectors work as they are a powerful asset to have in your toolbox. This article explained how things work in 2D space. To make the step into 3D you will need to work with Quaternions. They are a great way to represent 3D rotations and have many of the same properties as 2D unit vectors.

Article Update Log

20 Dec 2013: First publish of the article 23 Dec 2013: Small revisions to clarify some things 11 Jan 2014: Fixed some typos

Report Article

User Feedback

There are some good starting info but you should read over again and fix the typos (minor though, we still get the idea) and make sure you use the same convention between the article and the pictures. For instance, your slerp example uses a and b while the picture shows q1, q2.

Nonetheless this could be a good vector and matrix explanation starting point.

Share on other sites

angleBetweenUnitVectors(a,b) = acos(dot(a,b))

This may be not sufficient. The function acos() is defined for angles from range [0,pi]. You may need to check also asin(length(cross(normalize(a),normalize(b)))) - if it is negative then you need to add pi to angle from the first formula. Nonetheless, this is minor case - as mostly we don't want to have the bigger angle.

Share on other sites

It is generally better to avoid the use of angles. However, a more robust formula to get the angle between two vectors in 2D is the following one:

atan2(perp_dot(a,b), dot(a,b))

where perp_dot is defined as a.x*b.y - a.y*b.x . In 3D it is necessary to use the length of the cross product instead.

EDIT: The formula above returns the (smallest) angle you should rotate a to align it with b. The main difference with the acos formula is thus its anti-commutative nature. If you swap the two vectors you get the opposite angle. Since dot is commutative, this does not happen using the acos based formula.

Share on other sites

there you go:

// computes angle in radians given a point
// coordinate from origin , from any other
// starting point, just subtract from the the
// new origin point

double AngleOf( const CVec2d &P )
{
double  dist=sqrt( P*P+P*P ) ;
if ( dist>=-EPS && dist<= EPS ) dist=0.00000001f; // very near to zero
if ( P>=0.0f ) return acos( P/dist );
else return acos( -P/dist ) + __PI;
}

Share on other sites

angleBetweenUnitVectors(a,b) = acos(dot(a,b))

This may be not sufficient. The function acos() is defined for angles from range [0,pi]. You may need to check also asin(length(cross(normalize(a),normalize(b)))) - if it is negative then you need to add pi to angle from the first formula. Nonetheless, this is minor case - as mostly we don't want to have the bigger angle.

I guess I wasn't clear in the article that the point of the equation I gave was to find the shortest angle measure between the two vectors. If you want to find the angle between two vectors always in the counter clockwise direction you can use

// angle from a to b in the counter clockwise direction
atan2(a.x * b.y + a.y * b.x, a.x * b.x - a.y * b.y)


Share on other sites

Nice article. I would like to mention a small typo. In the section Angles Between Two Directions, I guess it is magnitude, instead of mangitude in the two given snippets of code.

Share on other sites
If you think of the vector (x,y) as the complex number (x + y*i), the formula for rotation is just complex multiplication, and if you want the signed angle between two vectors you can divide them as complex numbers and look at the "argument" of the result (the argument of x+y*i being atan2(y,x)). It's the same formulas that have been presented above, but in complex-number form they are trivial to remember.

Share on other sites

rotateTowards' can be rewritten without trigonometric functions. Using complex numbers in C++ it would look like this:

typedef std::complex<float> Complex;

Complex rotate_towards(Complex from, Complex to, Complex max_rotation) {
Complex z = to * std::conj(from);
if (std::real(z) >= std::real(max_rotation))
return from * (std::imag(z) > 0 ? max_rotation : std::conj(max_rotation));
}

Share on other sites
function rotateTowards(Vector2 rotateFrom, Vector2 rotateTo, float maxDeltaTheta)
{
float angleBetween = acos(dot(rotateFrom, rotateTo));

if (angleBetween <= maxDeltaTheta)
{
return rotateTo;
}
else
{
return slerp(rotateFrom, rotateTo, maxDeltaTheta / angleBetween );
}
}

`

i think this is correct?

Create an account

Register a new account

• 2
• 0
• 1
• 0

• 16
• 9
• 10
• 17
• 12
×