• 12/23/13 10:45 AM
    Sign in to follow this  
    Followers 0

    Problem Solving Using Vectors

    Math and Physics

    HappyCoder
    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. 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
    0


    Sign in to follow this  
    Followers 0


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!


    Register a new account

    Sign in

    Already have an account? Sign in here.


    Sign In Now

    jbadams

    • 5
      
    0

    Share this review


    Link to review
    Thiatsii

    • 5
      
    0

    Share this review


    Link to review
    jsvcycling

    • 5
      
    0

    Share this review


    Link to review
    Rifts605

    • 5
      
    0

    Share this review


    Link to review
    tnovelli

    • 5
      
    0

    Share this review


    Link to review
    theatron

      
    0

    Share this review


    Link to review
    pressgreen

    • 5
      
    0

    Share this review


    Link to review
    Irlan

    • 5
      
    0

    Share this review


    Link to review
    3Ddreamer

    • 5
      
    0

    Share this review


    Link to review
    Miklas

    • 5
      
    0

    Share this review


    Link to review
    J. Faraday

    • 5
      
    0

    Share this review


    Link to review
    IgnatusZul

    • 5
      
    0

    Share this review


    Link to review
    Philip Borgstr

    • 5
      
    0

    Share this review


    Link to review
    Diusrex

    • 5
      
    0

    Share this review


    Link to review
    Wrathnut

    • 5
      
    0

    Share this review


    Link to review
    Czar05

    • 5
      
    0

    Share this review


    Link to review
    mousetail

    • 5
      
    0

    Share this review


    Link to review
    CalebFaithMusic

    • 5
      
    0

    Share this review


    Link to review
    Kaptein

    • 5
      
    0

    Share this review


    Link to review
    Zaoshi Kaba

    • 5
      
    0

    Share this review


    Link to review
    Dragonsoulj

    • 5
      
    0

    Share this review


    Link to review
    lightxbulb

    • 5
      
    0

    Share this review


    Link to review