Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Like
20Likes
Dislike

Problem Solving Using Vectors

By James Lambert | Published Dec 23 2013 04:45 AM in Math and Physics
Peer Reviewed by (Dragonsoulj, CRFaithMusic, apatriarca)

vectors

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

250px-CircularCoordinates.svg.png
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

250px-Cartesian-coordinate-system.svg.pn
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

220px-Rtriangle.svg.png
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.

Attached Image: Slerp.png

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



License


GDOL (Gamedev.net Open License)




Comments

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. 

 

 

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.

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.

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[0]*P[0]+P[1]*P[1] ) ;
 if ( dist>=-EPS && dist<= EPS ) dist=0.00000001f; // very near to zero
 if ( P[1]>=0.0f ) return acos( P[0]/dist );
 else return acos( -P[0]/dist ) + __PI; 
}

 

 

 

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)

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.

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.

I like the simplicity of things. Well done.

I think there are more core level articles on gamedev itself that were done way back.

`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 to;
  return from * (std::imag(z) > 0 ? max_rotation : std::conj(max_rotation));
}
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?

Thank you for the concise explanation with clear code examples.


Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS