Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length

 
Advanced search

1055342 Posts in 42851 Topics- by 34776 Members - Latest Member: chronopulse

October 20, 2014, 04:32:33 PM
TIGSource ForumsDeveloperTutorialsVector Arithmetic For The Complete Novice
Pages: [1]
Print
Author Topic: Vector Arithmetic For The Complete Novice  (Read 14515 times)
Theotherguy
Level 1
*



View Profile Email
« on: July 31, 2010, 06:05:57 PM »

Intro
If there was one field of mathematics that has helped me the most in game development and many other areas of computer programming, it is linear algebra. Calculus and discrete math are all fine and good, but there are so many things that can be represented easily and beautifully as vectors in game programming, that knowledge of linear algebra has been completely invaluable to me.

So, I thought I would make this tutorial to help complete math novices with the basic concepts of vector arithmetic and linear algebra.

This tutorial will only assume that you know something about programming, and a little bit about physics.

Part I: Pong
Let's say that you're writing a clone of pong. Pong is a very simple game, and it's often one of the first that game programmers write. It was my first game, as well.

For those not familiar, pong is a game in which a ball bounces around the screen. Two players with paddles face off on opposite sides of the screen, and try to knock the ball  onto the opposite side of the screen before the other player can stop it.

It looks kind of like this:



How would we go about coding this sort of game? Assuming that we have a way of drawing circles and rectangles, a good idea would first be to store the position of the ball on the screen.

Screen coordinates are typically represented as a pair of numbers called the row and column. The row is the number of pixels down from the top of the screen, and the column is the number of pixels to the left from the left side of the screen. Typically, the column is referred to as the "x" coordinate of the ball, and the row is referred to as the "y" coordinate of the ball.


These are known as the "Cartesian coordinates" of the ball, named after the famous mathematician, Renes Descartes. In the Cartesian coordinate system, every point on a plane can be represented as two numbers, x and y. In this case, the plane is the computer screen, and the x and y coordinates refer to the number of pixels from the left and top of the screen.

So, let's define our ball's position like this (here I'm assuming the language is based on C):

Code:
// The ball's Cartesian coordinates.
float ballPositionX;
float ballPositionY;

Okay, so now we know where the ball is, and know where to draw it. How do we make it move? To move the ball, we need to change its x and y coordinates, and re-draw it. The first thing we'll try to do is make it move in a straight line.

When I first tried to code Pong (over a decade ago, now!) this part confused me. I had learned from algebra that I could represent straight lines as functions where the y coordinate depended on the x coordinate, so the first thing I tried was to get the ball to move on a straight line by following the equation:

Code:
// This is BAD, don't do it!
ballPositionY = (ballPositionX)*m + b;

Where m is the slope of the line, and b is the Y offset from the origin. This worked fine for some lines, but it quickly became apparent to me that the number of possible lines the ball could travel along was very large! And, what if I wanted the ball to change speed, or direction in mid-flight?

What I hadn't realized at the time was that what I needed was a concept of time. I didn't need to be modeling the ball's motion as a line, but instead I needed to simulate the motion of a ball through space.

The best way to get the ball to move along a straight line is to introduce a velocity for the ball. What do I mean by this?

Imagine you have the ball at position (50,100) at time t (say, 1 second after starting your program). Now, imagine that at time t2 (say, 2 seconds after starting your program), the ball has traveled to position (55, 101). Then, between t and t2, the ball has moved five pixels to the right, and one pixel down. So, the ball's velocity at this time can be represented as another pair of numbers : (5, 1) pixels per second.



So, we can represent the ball's motion over time without any special equations or modeling. We can simply add two more quantities, the ball's x velocity and y velocity.

Code:
// The ball's Cartesian coordinates.
float ballPositionX;
float ballPositionY;

// The ball's Cartesian velocity.
float ballVelocityX;
float ballVelocityY;


Then, in our method where we're updating the ball's position, we simply do this:

Code:

void update( float dt)
{
// Add x velocity to x position.
ballPositionX+=(ballVelocityX/dt);

// Add y velocity to y position.
ballPositionY+=(ballVelocityY/dt);
}

Where dt is the time in seconds passed since the last update. (For now you can ignore this. The important part is that the ball's velocity is ADDED to its position with each update loop!)

Now, you can get the ball to move in whatever way you want by changing its velocity! There is no need for complicated equations to model the movement of the ball. All of this is done automatically. If the ball's velocity remains constant, it will move in a straight line. If the ball's velocity changes over time, it will change direction! For instance, if you negated (multiplied by -1) the ball's y velocity, it would turn upwards, as if it were bouncing off of the floor. In fact, this is how you get the ball to bounce off of the floor and walls in a pong game. If it's y position is greater than the screen height,or less than 0, you multiply its y velocity by -1. If it's x position is greater than the screen width, or less than 0, you multiply its x velocity by -1 also.



So what have we just done here?

We've simplified the representation of a ball moving on the screen down to just four numbers, its x position, its y position, and its x and y velocities. Manipulating the ball's position and velocity is as simple as changing these four values. Easy, right?

Part II: Vectors
Using groups of numbers in this way is called vector arithmetic. A Vector is simply an ordered set of numbers. In the previous example, the ball's position, a pair of numbers, was a vector. The first number in the pair always corresponded to the x-coordinate of the ball, and the second number always corresponded to the y-coordinate of the ball. It's velocity was also a vector in which the first number corresponded to a quantity in the x direction, and the second number corresponded to a quantity in the y direction.

We can modify our previous example by making a simple Vector structure that contains two numbers.

Code:
// A simple structure containing two floats.
struct Vector2f
{
float x;
float y;
};


// Now the ball's position and velocity
// are in structures.
Vector2f ballPosition;
Vector2f ballVelocity;


The numbers inside a vector are called its components. The ball's position and velocity each have two components, x, and y. People will often call the components of a vector scalars, which is another name for ordinary numbers. Scalars can interact with vectors to produce interesting results.

Vectors don't have to have just two components. A Vector that has two components is called a 2-dimensional vector, a vector that has k components is called a k-dimensional vector. For instance, 3-dimensional vectors with quantities called (x,y,z) are often used to represent positions and directions in 3D games. 4-dimensional vectors called quaternions are often used to represent orientation in 3D games by adding a fourth quantity, (x,y,z,w) corresponding to rotation around a line.

Vector Addition

A key property of vectors is that they can be added together. As we saw with the pong example, we could add the ball's velocity to its position by adding the components together. This property is called "linearity," and it is why doing math with vectors is often called "linear algebra."

Let's make things easier by using the plus sign (+) to define addition of vectors, implying that we are adding together their components. This will be especially useful for you if you are using a language with operator overloading, like C++ or C#.

Code:
// Adding the ball's velocity to its position is done like this:
// NOTE: + sign is vector addition!
ballPosition = ballPosition + ballVelocity;

In this sense, you can add and subtract vectors exactly as you would ordinary numbers. If you have vectors A, B, C, and D, then if (A = B+C), and (D = C+B), then (A = D).

However, you can only add two vectors together if they have the same number of components, and never if they have more or less! For instance, this is not possible:

Code:
// It's impossible to add scalars to vectors!
// A scalar is a one-dimensional vector.
ballPosition = ballPosition + 5;

Intuitively, we can look at 2-dimensional vectors as arrows with a direction and a length. The two components of the vector form the legs of a right triange, and the hypotenuse of the triangle is the arrow we can draw to represent it.



What, then, happens to two vectors when we add them together in this intiutive sense? If we represent both vectors as arrows, their sum can be found by taking one of arrows, and placing its "tail" on the other's "tip," as in this diagram:



If you try this out yourself, you can get an intuitive understanding of what happens to vectors as you add them together. You can also confirm that A + B = B + A for vectors A and B, though this should be obvious from the definition of vector addition.

It's important, though, not to get caught up in all of this arrow stuff. It can be somewhat appealing to see vectors as little directional arrows, but at heart vectors are simply lists of numbers with very simple properties.

Subtraction is exactly the same as you would expect. Subtracting vectors means subtracting their x and y components. In the intuitive arrow representation, (A-B) is done the same way as (A+B), except B's direction is reversed before adding it to A.

Some applications of vector addition include our use of it to add the ball's velocity to its position.

Scaling

Remember when I said that scalars couldn't be added to vectors? Although they cannot be added to vectors, they can be multiplied with vectors. This is called "scalar multiplication," or sometimes "scaling."

When you multiply a scalar with a vector, you simply multiply each of the vector's componenents by the scalar.

For instance:

Code:
// Create a vector called A.
// A = (1,3)
Vector2f A = new Vector2f(1,3);

// Create a scalar called s.
float s = 2;

//Multiply A by s
// A = (1*2, 3*2) = (2, 6)
A = A*s;

// This is equivalent to:
A.x = A.x*s;
A.y = A.y*s;


Using our intuitive arrow representation, scaling a vector means changing the length of the arrow. Scaling a vector by 0.5, for instance, would make the arrow half as long. Scaling it by -1 would reverse its direction.



Scaling a vector can be incredibly useful for a variety of purposes, from reversing its direction to finding points along a line, etc.


Part III: Cool Stuff You Can Do With Just This

Usually, vector tutorials will diverge at this point into discussions of things like vector multiplication and matrix-vector transforms; but before we do that, there is a lot of cool stuff you can do by just using vector addition and multiplication!

Let's see what fun we can have with our simple pong game.

Reflecting a Vector

As mentioned before, we can reflect a vector by multiplying either its x or y components by -1. The following code will cause the ball to bounce around on the walls:

Code:

void bounceBall()
{
if(ballPosition.x > SCREEN_WIDTH
  || ballPosition.x < 0)
{
ballVelocity.x *= -1;
}

if(ballPosition.y > SCREEN_HEIGHT
  || ballPosition.y < 0)
{
ballVelocity.y *= -1;
}


}


Adding Forces And Gravity

So, we have the ball's position and velocity as vectors. What if we wanted to change the ball's velocity without accessing it directly? Well, we could add another vector, the acceleration vector, to the ball. This acceleration vector will be added to the ball's velocity with each frame, and then cleared.

We can also define a scalar for the ball's mass.

Code:
// New Vector for acceleration
Vector2f ballPosition;
Vector2f ballVelocity;
Vector2f ballAcceleration;
float mass;


void update(float dt)
{

// What to do in the update loop:
// Get the change in position over time
// by scalar multiplying it by 1 over the
// change in time.
Vector2f changeInPosition = ballVelocity * (1/dt);

// Bouncing method we implemented earlier
bounceBall();

// Move the ball.
ballPosition += changeInPosition;

// Compute the amount the velocity has
// changed over time.
Vector2f changeInVelocity = ballAcceleration * (1/dt);

// Adjust the ball's velocity.
ballVelocity += changeInVelocity;

// Clear the ball's acceleration
// (in newtonian physics, acceleration is
//  not preserved, unlike velocity and position)

ballAcceleration = ballAcceleration * (0);

}

Now, we can add a force to the ball with the following function:

Code:

// Changes the ball's acceleration
// by a force.
void addForce(Vector2f force)
{
// Newton's third law F = ma
Vector2f dv = force*(1/mass);

// Add to the ball's acceleration.
ballAcceleration += dv;
}


By adding force to the pong game, we can create a whole variety of interesting effects. For instance, we can add simple downward gravity by doing the following in each update loop:


Code:

// Gravity is one pixel per second squared
// downwards in our simulation!
Vector2f gravity = (0, 1);

// Make the ball accelerate downwards.
addForce(gravity * mass);


This will make the ball move in a parabolic arc, and if you've already implemented ball bouncing on the walls, it will cause it to bounce around the screen!


Add Friction

We can use scalar multiplication to modify our bounceBall method and add friciton to the ball's motion. Each time the ball hits a wall, it will lose some energy, and its velocity will be reduced rather than perfectly reflected. Typically, we'll want to reduce its velocity by a tiny amount.

Code:

// Modified bounceBall function that
// will cause the ball to lose energy
// with subsequent bounces.
void bounceBall(float wallFriction)
{
if(ballPosition.x > SCREEN_WIDTH
  || ballPosition.x < 0)
{
ballVelocity.x *= -(wallFriciton);
}

if(ballPosition.y > SCREEN_HEIGHT
  || ballPosition.y < 0)
{
ballVelocity.y *= -(wallFriction);
}


}

With this implemented, and using a reasonable number like 0.999, the ball will slowly lose energy, bouncing lower and lower until it eventually stops. Interestingly, if you use a number greater than 1, the ball will gain energy and go out of control!

Next Time

This is about all the time I have for today, but I hope this has been enlightening for beginning game programmers! Using vectors can make things very simple in game programming, especially for simulation-based games.

Next time, we'll go over some common vector problems you will encounter in games, such as finding a vector from one position to another, finding the angle of a vector, and other stuff!




« Last Edit: August 02, 2010, 04:24:34 PM by Theotherguy » Logged

Swattkidd
Level 0
***


View Profile
« Reply #1 on: August 01, 2010, 03:27:56 AM »

Ha what a coincidence, I was looking for something almost EXACTLY like this for the past couple of days, I have a fairly good understanding of Vectors but like reading up on them and especially seeing them applied in examples like you did.

These are great, keep them up!
Logged
lasttea999
Level 2
**



View Profile
« Reply #2 on: August 01, 2010, 06:07:02 PM »

Wow, this is really great! May I suggest making a PDF of this?
Logged

Vertex: Exploration platformer by iMoose
HARA HARA DUEL: Dueling game
Solving stuttering: fixed timesteps
Theotherguy
Level 1
*



View Profile Email
« Reply #3 on: August 03, 2010, 06:11:39 PM »

Part III: Reference Frames

You may have noticed from the previous sections that in the arrow representation of vectors, I was always clear on where the arrows ended, but not often where they began. For instance, when I scaled the vectors by scalar multiples, I moved them around the page as well as changing their lengths.

This is because all vectors are relative, rather than absolute, measurements. A ball's velocity vector of (5,3) remains a velocity vector of (5,3) no matter where the ball is in space. This is because the ball's velocity vector is a relative measurement from the ball's position. If the ball is moving 5 pixels to the right, and 3 pixels down, it does not matter where it is positioned, it will still move 5 pixels to the right of wherever it is at that moment, and 3 pixels down.

However, the ball's position is itself a vector. Isn't this vector an absolute measurment? No, in fact it is not! The top left corner of your screen is an abitrary point in space that has no real significance. The ball's position is a relative measurement from the top left corner of the screen. You could just as easily compute a vector from the center of the screen and call it the ball's position, and all of the math would work out exactly the same way!



The arbitrary point from which a vector is measured is called the vector's reference frame. All vectors can be considered to have a reference frame, but it is not inherent in the definition of a vector. Just remember that vectors are lists of numbers, and nothing more. This buisness with arrows pointing from one place to another is just an abstraction to help us vizualize the nubmers.

In the previous pong example, the reference frame of the ball's position was the top left corner of the screen, and the reference frame of the ball's velocity was the ball's position.

Now, let's imagine a different game altogether, in which the player is trying to avoid the shots of an enemy turret on the ground.

Here's what it looks like:



The enemy turret only has control of theta, the angle of its turret, and can shoot a laser from the turret to hit the player.

Let's outline some basic variables in this game:

Code:

// Player's position relative to top left corner
Vector2f playerPosition;

// Turret's position relative to top left corner
Vector2f turretPosition;

// Angle of the turret in radians.
float turretAngle;


How can the enemy turret find theta such that it is pointing at the player?

One way to solve this problem is to use reference frames and vector addition.

Step 1: Find the Position of the Player Relative to The Turret

The turret has a position in space, we'll assume from the top left corner of the screen. The player also has a position in space from the top left corner of the screen. How do we find the player's position relative to the turret?



This is actually extremely simple using vectors and reference frames. Instead of trying to figure out where the player's position is relative to the enemy turret, we can simply assume that the enemy turret is at position (0,0), and then EVERY vector will be relative to the turret's reference frame.

To do this, we simply subtract the position vector of the enemy turret from any vectors we want to translate into its coordinate space.

In essence, we are undoing the offset of the enemy turret's position, and assuming that the enemy turret is at the origin.

For instance, if the enemy turret were at position E = (10, -30), and the player were at position P = (15, -28), then the player's position relative to the turret is simply (P - E) = (15 - 10, (-28) - (-30)) = (5, 2).

You can observe this for yourself using arrows and tip-to-tail addition.

Here is an extremely simple function for computing the vector from one vector to another:

Code:

// Gets vector from reference frame to other.
Vector2f getVectorFrom(Vector2f referenceFrame, Vector2f other)
{
return (other - referenceFrame);
}



Step 2: From this, Compute Theta

Okay, so now we have a vector from one position to another? How do we compute the angle that the turret has to fire in?

We can use the fact that the arrow representation of a vector can be thought of as forming the hypotenuse of a right triangle from it's components, and use trigonometry to find the angle.

In an ideal world, the angle formed by the vector and the x axis would always be acute. We'll ride with this assumption for now, and then dispel it later. Using this assumption, we can use the trigonmentric identity that for any right triangle with side lengths H, O,and A, where H is the hypotenuse, O is the opposite side to the angle (called theta), and A is the adjacent side to the angle, then tangent(theta) = (O/A).

What is the right triangle formed by our vector? In this case, the opposite side is the y coordinate, and the adjacent side is the x coordinate. From this, we can easily derive that (theta) = arctangent(y/x).



Remember when I said we were assuming the angle was acute? Well, if it's not, our definition falls apart, and the arc tangent of y/x will not give us the value for theta we desire at all! In fact, it will often be completely ambiguous what theta really is, in positive and negative cases, because (y/x) will be the same value for (-y/x) and (y/-x).

How do we solve this problem? Well, we can use a handy function called "atan2" provided in almost every math package in existence. Atan2 takes the y coordinate as the first argument, and the x coordinate as the second argument, and returns a normalized value between -PI and PI. I won't get into the details of exactly how it works, but suffice to say, it gives us what we want Smiley

Here is an article on atan 2 if you would like to implement it yoursef:
http://en.wikipedia.org/wiki/Atan2

So, here is the code for finding the angle of a vector, assuming you have a sufficient atan2 defined:

Code:
// Returns the angle of a vector between -PI and PI.
float getAngleOf(Vector2f vector)
{
return (atan2(vector.y, vector.x));
}

Step 3: Putting it All Together

Here is the code your enemy would need to target the player:


Code:

// Shoots a laser towards the player from the turret!
void enemyAI()
{
Vector2f relativeVect = getVectorFrom(playerPosition, turretPosition);
turretAngle = getAngleOf(relativeVect);
shoot();
}


Next Time

That's all the time I have for today. Next time, we'll go over more things to do with reference frames, and we'll talk about how to implement a simple camera in your game!
« Last Edit: August 03, 2010, 06:17:40 PM by Theotherguy » Logged

dontkickpenguins
Level 1
*


Used to be known as Penguinhat


View Profile Email
« Reply #4 on: August 04, 2010, 09:26:01 AM »

This is really useful stuff, thanks a lot for posting!
Logged

sm
Level 0
*



View Profile WWW Email
« Reply #5 on: August 06, 2010, 12:04:03 AM »

Actually I like the way you approach the subject and especially you're introducing the applications of vector stuff (the physics stuff in the first post) in a nice way eventhough you could've introduce the definitions of velocity and acceleration in the vector form (v = dx / dt, ...). The definition of angle of vector is kinda.. well, strange. Couldn't you just introduce the definition of the angle between two vectors?

All in all, the tutorial is overally nice and I'm pretty sure that the novices will find out this tutorial useful. Thumbs up! Hand Thumbs Up Right
Logged
Theotherguy
Level 1
*



View Profile Email
« Reply #6 on: August 06, 2010, 04:09:58 PM »

Actually I like the way you approach the subject and especially you're introducing the applications of vector stuff (the physics stuff in the first post) in a nice way eventhough you could've introduce the definitions of velocity and acceleration in the vector form (v = dx / dt, ...). The definition of angle of vector is kinda.. well, strange. Couldn't you just introduce the definition of the angle between two vectors?

All in all, the tutorial is overally nice and I'm pretty sure that the novices will find out this tutorial useful. Thumbs up! Hand Thumbs Up Right

Thanks for the suggestions.

The definition of the angle between two vectors (and angle in general) requires an understanding of the dot product, which I don't want to introduce yet. I wanted to use the first definition there because it uses trigonometry and geometry, which I assumed the reader knew something about.
Logged

Theotherguy
Level 1
*



View Profile Email
« Reply #7 on: August 14, 2010, 01:58:04 PM »

Part IV: More Reference Frames : Implementing a Camera

As we have seen, vectors can easily be translated from one reference frame to another one via vector addition and subtraction. As a general rule, if you want to undo a movement from one reference frame to another from a vector, you have to subtract the reference frame's origin from the vector, and if you want to impose a movement from one reference frame to another on a vector, you have to add the reference frame's origin to the vector.

As we saw with the turret's shooting example, we could undo the translation from the top-left corner of the screen to the turret's position on the screen by subtracting the turret's position. Similarly, if we know the position of any object relative to the turret's position on the screen, we can get the position of the object relative to the top-left corner of the screen by adding the turret's position to it.

We could continually translate a vector back and forth through reference frames as much as we like, to get it in any reference frame that we want, because of linearity.

The movement of a vector from one reference frame to another is known as vector transformation reference frames can be translated (by vector addition), scaled (by vector-scalar multiplication), or even rotated and distorted (by matrix-vector multiplication, which we will cover later.)




First, Some History
Many novice game developers often feel compelled to be stuck to the size of a single screen. They put all of their game entity positions in pixel coordinates, and never allow the player to move beyond the boundaries of the screen.

For example, in pong we assumed that the ball would always be somewhere within the boundaries of the screen, and would bounce around whenever it got outside of those boundaries.

As you can probably imagine, this can be extremely limiting. Your game is inherently constrained to a box, which makes design rather challenging.

Some game developers compensate by having multiple "screens" or "levels," or by faking motion in their games by moving the environment around a stationary player.

For example, the original Legend of Zelda divided the enormous world into a series of screen-sized bins. The player could move freely inside each bin, but when he got to the edge of the screen, he would be transported to the adjacent bin.



Early space shooters faked camera motion by having a constantly moving field of stars in the background, and enemies and environments pop into existence at the top of the screen, move to the bottom, and then disappear.



These tricks were employed mainly to save memory and processor power by only considering objects which were on the screen, and saved the processor from having to do constant vector additions and subtractions.

Today, however, computers are much faster than in the 70's and 80's, and can easily support more complicated methods of camera motion and representation of objects in space. 3D graphics cards are essentially enormously parallel processors whose sole purpose is to constantly do millions of vector/matrix transformations every second. In a 3D game, the graphics card is chugging along and transforming vectors from the reference frames of models to the reference frame of the world, to the reference frame of the camera, and finally projecting all of those vectors to your screen.

In short, linear algebra is a big deal in computer graphics. What we are about to do here is done constantly in modern games, and on a much larger scale.

Making A 2D Camera
So, how do we detach our game from a single screen? I've hinted at it for a bit in the previous sections, and the answer is to use a standard reference frame, called the "world frame" in which to store the positions of all the entities in the world, and a second reference frame, called the "camera frame" in which to draw them.



It's important to note that all of these frames are completely seperate from the top-left corner of the screen, and should even be removed from the notion of "pixels" entirely. That means that before we draw anything in the game, it must go through several vector transformations, from world coordinates, to camera coordinates, to screen coordinates.

Here's basically what we have to do:



Then, we can move the camera around just like any other game entitiy, and it will look just like we are scrolling our view seamlessly around the world! So, we're going to make a very simple 2D camera that can move around using vector addition, and which can zoom in and out using scalar multiplication. In this sense "zooming in" means multiplying every vector in the frame by a factor greater than 1.0, and "zooming out" menas multiplying every vector in the frame by a factor less than 1.0 (but never less than 0!)

So, let's define a few necessary classes to do this. First, let's assume we have a standard game entity class that stores its world position and sprite.

Code:
// A simple stub for a game entity class.
class Entity
{
// Position of the entity relative to the world.
Vector2f worldPosition;

// What will be drawn.
Sprite sprite;
}

We also create a simple camera class which stores its positon relative to the world, and a zoom factor (which we will discuss later):

Code:
//A simple stub for a camera class
class Camera
{
// What the camera is looking at.
Vector2f worldPosition;

// Scaling factor on the camera's reference frame.
float zoom;

//Constructor
public Camera(float x, float y, float zoom)
{
this.worldPosition = new Vector2f(x,y);
this.zoom = zoom;
}
}

Now, we can also define some constants which will help us in doing our reference frame transformations:

Code:
// Location of the world's reference frame in game units.
// It's at 0 here for simplicity, but you can change it
// for constant offsets.
Vector2f WORLD_ORIGIN = new Vector2f(0,0);

// This represents what a game unit means in terms of
// pixels when the reference frame is not scaled.
// i.e. a circle that is 1 unit in radius will appear to
// be 30 pixels in radius on the screen when the camera's
// zoom is 1.0.
Vector2f PIXELS_PER_UNIT = 30.0f;

// The number of entities in our game.
int NUM_ENTITIES = 50;

// An array of game entities.
Entity[] ENTITIES = new Entity[NUM_ENTITIES];

// The game's camera.
Camera CAMERA = new Camera();

// The size of the screen in pixels.
int SCREEN_WIDTH = 1024;
int SCREEN_HEIGHT = 768;

// Center of the screen relative to the top left in pixels.
Vector2f SCREEN_CENTER= new Vector2f(SCREEN_WIDTH/2, SCREEN_HEIGHT/2);


Now, let's assume that we have an array of entities at various locations in the world, then, when we draw them all, we can do the following:

Code:

// Assume we have this method, which draws a sprite at the
// specified position and scale.
void drawSprite(Sprite s, float scale, int row, int col);

// Given the position of an object in the world in
// game units, returns a screen coordinate in
// pixels corresponding to its position on the screen.
Vector2f transformToScreen(Vector2f worldPosition)
{
//First transform to camera reference frame.
Vector2f relativeToCamera = (worldPosition - CAMERA.worldPosition);

//Scale to deal with camera zooming effect.
Vector2f zoomed = relativeToCamera*CAMERA.zoom;

//Scale to turn into pixels coordinates, rather than game units.
Vector2f inPixels = zoomed*PIXELS_PER_UNIT;

//Finally, translate from the center of the screen (where the camera is)
// To the top-left corner
Vector2f toReturn = (inPixels - SCREEN_CENTER);

return toReturn;
}

// Stub of a method that draws all the
// game entities with reference frame
// transformations
void draw()
{
// For each entitiy...
for(int i = 0; i<NUM_ENTITIES; i++)
{
// Get the ith entity.
Entity e = ENTITIES[i];

// Transform its position to the screen.
Vector2f pos = transformToScreen(e.worldPosition);

// Draw its sprite in screen coordinates.
drawSprite(e.sprite, CAMERA.zoom, pos.x, pos.y);
}
}



And that's it! Of course, your game's code is going to be a bit more complicated than this, but that's the gist of it. You can move the camera around and zoom it in and out at will, and all of the objects in your game world will follow it along, giving a very nice looking effect, without having to rely on traditional tricks.

This code will also be quite a bit slow. You see, rather than multiplying every entity position to screen coordinates and drawing them one by one, it's probably a much better idea to batch all of your transformations and drawing together, and do them in parallel if necessary. This is far beyond the scope of this tutorial, but many graphics packages have the ability to do all of this for you on the graphics card. XNA, for instance, has a "spritebatch" class that takes in transformation parameters (usually in the form of a matrix) and will draw all of your sprites and do the transformations on the graphics card, which is much faster.

Next Time

That's it for today! Next time we'll talk about vector multiplication, the dot product, the cross product, and matricies!


« Last Edit: August 14, 2010, 04:27:47 PM by Theotherguy » Logged

iffi
Guest
« Reply #8 on: August 14, 2010, 03:01:19 PM »

Great tutorial! A while ago when I was trying to program a game, I hadn't even heard of using vectors and thus ended up wasting a lot of time thinking of a good way to represent position, velocity, and acceleration data. The system I ended up with was actually very similar to the vectors you describe here!
I'm finding this tutorial, especially the part you just posted (since I've never learned it before), to be very useful to me, and I'm looking forward to the next part!
Thanks, and keep up the good work! Beer!
Logged
Theotherguy
Level 1
*



View Profile Email
« Reply #9 on: August 21, 2010, 07:17:33 PM »

Part V: More Advanced Vector Topics

Vector Length

It's often useful to figure out what the length of a vector is. If we drew out the vector as an arrow, the length or magnitude of a vector is the distance from the tip of the arrow to its tail.



How can we figure out how long a vector's length is? Well, we can use the distance formula from geometry, which is derived from the Pythagorean theorem. The vector can be thought of as the hypotenuse of a right triangle made from its x and y components. Then, using the Pythagorean theorem, we can derive that the length of the vector is in fact the square root of the sum of each of its components squared. We can define a simple length function as follows:

Code:
// * Pythagorean theorem *
// Given a right triangle with hypotenuse C, and legs A and B,
// (C)^2 = (A)^2 + (B)^2
// Therefore: C = sqrt(A^2 + B^2);

float length(Vector2f vector)
{
return sqrt(vector.x*vector.x + vector.y*vector.y);
}

This definition holds true for vectors of ANY dimension. A three dimensional vector with components x, y and z, for instance, has a length of sqrt(x^2 + y^2 + z^2).

In math, we put absolute value bars around a vector name to describe its length. So, if we have a vector called A, then |A| is its length.

Normalization

A vector with a length of exactly 1 is called a normal vector. Normal vectors have interesting properties. They behave sort of like the number "1" when used in vector addition and multiplication. For instance, scalar multiplying a normal vector "N" by a scalar "s" gives a new vector whose direction is the same as N, but whose length is equal to s.

To normalize a vector, we simply divide it by its length. So, the normal vector of a vector "A" is simply (A)*(1/|A|).

Here's a simple function for normalizing a vector:

Code:
//Returns a new vector with length 1
Vector2f normalize(Vector2f vector)
{
return (vector*(1.0f/length(vector));
}

Normalization is often useful when you need to preserve the direction of a vector but not its length. That means you will be using it a lot for finding points along a vector (such as in raycasting.)

The Dot Product

So far we've talked about a few of the major operations involving vectors and scalars. We discussed vector addition, scalar multiplication, and normalization and length. There are a couple of other operators we will have to discuss. The first is called the dot product .

The dot product is a very strange and special operator. While vector addition, subtraction, and scaling all produce vectors as results, the dot product takes two vectors and produces a scalar. From here on out, we will show the dot product as the symbol (.*).

Here is the definition of a dot product: suppose we have two k-dimensional vectors A and B, with elements A[1], A[2], A[3], ..., A[k] and B[1], B[2], B[3], ... ,B[k].

Then:

Code:
//DEFINITION OF THE DOT PRODUCT:

(A).*(B) = (A[1]*B[1] + A[2]*B[2] + A[3]*B[3] + ... + A[k]*B[k])


Seem confusing? I'll try to make it a bit clearer.

Suppose we have two 3D vectors "C" and "D", then:

Code:

// Dotting two 3D vectors
(C).*(D) = (C.x*D.x + C.y*D.y + C.z*D.z)


To do the dot product, we simply multiply each of the vector's corresponding elements together, and then add them together. Here's a more concrete example: suppose we have two 2D vectors A = (1,2) B = (-5, 3). Then, (A).*(B) = ((1)*(-5) + (2)*(3)) = (6 - 5) = 1.

Again, it's important to notice that the dot product produces a scalar, and that it can only be used with vectors that are the same size as one another.

Here is a simple function for computing the dot product between two Vector2fs.

Code:

float dot(Vector2f A, Vector2f B)
{
return (A.x*B.x + A.y*B.y);
}


The dot product is communitive and associative. That means:

A.*B = B.*A

and:

A.*(B+C) = A.*(B) + A.*(C)

Another interesting property of the dot product is that, given scalars s1 and s2:

((A)*(c1)).*((B)*(c2)) = (A.*B)*(c1*c2)

That is, scalar multiplication distributes with the dot product.

Uses of the dot product: Angle Between Two Vectors

An interesting property of the dot product is that it can be used to find the angle between two vectors. We will see why this is the case later, but this identity is quite important:

Code:
//ANGLE BETWEEN TWO VECTORS
// Where A and B are vectors,
// and || is the length operator,
// and theta is the angle between them.
(A).*(B) = |A|*|B|*cos(theta)




So it follows that theta = acos((A).*(B))/(|A|*|B|)).




In fact, this is how the notion of angle itself is defined in linear algebra. It has no other meaning. Even our atan definition from before reduces to this one.

Here is a simple method for finding the angle between two vectors:

Code:

// Gets the angle between two vectors using the
// dot product identity.
float angleBetween(Vector2f A, Vector2f B)
{
float lengthOfA = length(A);
float lengthOfB = length(B);
float aDotB = dot(A, B);

return acos(aDotB/(lengthOfA*lengthOfB));
}

This is one of the geometric interpretation of what the dot product "means".


Uses of the dot product: Vector Projection

Another use of the dot product is finding how much of a vector is made up of a second vector. This is called the projection of one vector onto another. We will call the projection of A onto B to be "A proj B."



You can think of the projection of one vector onto another like this: imagine that a spot light is shining down on one of the vectors. The projection of the first vector onto the second is the same as the shadow that the first vector would make on the second one. (In fact, this property was often used to fake shadows in the early days of computer graphics.)

Here is how you find the projection of a vector onto another one:

Suppose you are getting the projection of vector A onto vector B. Then, the dot product of A and (B/|B|) is the length of the projection vector. This is derived from trigonometry, and the earlier identity that |A||B|cos(theta) is equal to the dot product of A and B. (In fact, this is where the dot product itself comes from.) The direction of the projected vector is the same as B.

Therefore:

Code:

// Definition of the projection vector
A proj B = (A .* (B/|B|)) * (B/|B|)



Here is a simple function for getting the projection of one vector onto another:


Code:
// Gets the projection fo Vector A onto Vector B
Vector2f project(Vector2f A, Vector2f B)
{
// (B/|B|)
Vector2f normB = normalize(B);
float dotProduct = dot(A, normB);

// (B/|B|) * (A .* (B/|B|))
return (normB*dotProduct);
}


This definition has interesting geometric consequences. For instance, I have often used it to compute the velocity "towards" a particular point in games of an entity moving at an arbitrary speed (this can be used to do things like make an AI lead a target in a shooter, etc.)

Another interesting and extremely important consequence of the dot product and the projection vector is that two vectors which are offset 90 degrees from one another have a projection vector of Zero, and therefore their dot product must also be zero.. This property is called orthogonality.



Aside: You have have heard this term when used in 3D computer graphics to describe a type of projection called "orthographic projection." In this sort of projection, all rays are parallel to the view of the camera, (and thus are orthogonal to the screen.)

The Cross Product

There is another kind of vector multiplication known as the cross product which is even weirder than the dot product. Wheras the dot product takes two vectors and produces another vector, the cross product takes two vectors and produces a vector orthogonal to both of them. The symbol we will use for the cross product is the capital X.




Since the vector produced is orthogonal to both of the vectors being crossed, the cross product of two vectors is never in the same 2D plane. Because of this, the cross product is not defined for two dimensional vectors. In fact, the cross product is only defined for three and seven dimensional vectors!

The entire definition of the cross product hinges on the fact that 3D unit vectors in the X, Y and Z directions cross with one other to produce other unit vectors. For instance, a unit vector in the X direction crossed with a unit vector in the Y direction produces one in the Z direction.

Here is a quick way to compute the cross product of two three-dimensional vectors:

Code:
// CROSS PRODUCT DEFINITION
//Given vectors A and B with components A[1]...A[3] and
// B[1]...B[3]
A X B = (A[2]*B[3] - A[3]*B[2], A[3]*B[1] - A[1]*B[3], A[1]*B[2] - A[2]*B[1])

This is quite hard to remember, but there is another definition that is slightly easier to remember which follows the "right hand rule."



Point your pointer finger in the direction of the first vector to be crossed, and your middle finger in the direction of the second vector to be crossed. Then, point your thumb straight out. Your thumb represents the direction of the cross product vector.

The length of the cross product vector is |A|*|B|*sin(theta), where theta is the angle between the vectors. You might notice that this is extremely similar to the dot product's definition.

Unlike the dot product, the cross product is not commutative, nor is it associative.

 (A X B) != (B X A),
 and (A X (B X C)) != ((A X B) X C).

This is because of the right hand rule, and the fact that the direction of the cross vector matters.

However,

|A X B| = |B X A|,

and

(A X B) = (-B X A).


Here is a simple function for computing the cross product of two 3D vectors:

Code:
// Returns the cross product of vectors A and B
Vector3f cross(Vector3f A, Vector3f B)
{
// Cross each component
float xComponent = (A.y)*(B.z) - (A.z)*(B.y);
float yComponent = (A.z)*(B.x) - (A.x)*(B.z);
float zComponent = (A.x)*(B.y) - (A.y)*(B.x);

// Return a vector with these components.
return new Vector3f(xComponent, yComponent, zComponent);
}


Applications of the Cross Product: Normals

One of the most common applications of the cross product is finding the "normal vector" of a plane. Suppose you have a character in a 3D game walking over a bit of terrain. How do we figure out what direction the character should be rotated in order to have his feet on the ground?

In most 3D games, models and terrain are divided into triangles. Let's assume we know what triangle the character is walking on, and it has points f, g, and h.




Then, we can figure out the "normal vector" (ie, the direction that the triangle is facing) by taking the cross product of the vector between points f and g (which we will call A), and points f and h (which we will call B).



In this case, its ambiguous as to whether the vector will be facing into or out of the terrain, so it may be necessary to look at both A X B and B X A, and determine which of the vectors is closest to your character's current orientation.

Then, we can simply rotate the character to face this direction.


NEXT TIME

Sorry, I've run out of time, and I didn't even get to matricies! So, next time we will go over matricies and matrix transformations.
Logged

dave
Level 0
***

aim+marine
View Profile WWW
« Reply #10 on: September 29, 2010, 12:08:24 PM »

Epic review man. You're doing an excellent job.
Logged

pixhead
Guest
« Reply #11 on: January 08, 2011, 01:04:37 PM »

This is so helpful one of the most helpful threads Ive seen on TIG so far.
Logged
dmreichard
Manbaby
*


View Profile Email
« Reply #12 on: January 25, 2011, 05:40:37 PM »

Looking forward to those matrices and matrix transformation tutorials, hopefully they are still in the works!   Wink
Logged
Thraka
Level 0
*


View Profile Email
« Reply #13 on: March 02, 2011, 06:53:55 AM »

This should be stickied Smiley

I'm really looking forward to some time to sit down and read through this whole thing. I could tell right away it will be most helpful.
Logged
AlexTes
Manbaby
*


View Profile Email
« Reply #14 on: March 05, 2011, 07:49:12 AM »

All really useful. Very important for even the simplest games. Thanks!
Logged
Dataflashsabot
Level 2
**


View Profile
« Reply #15 on: March 05, 2011, 08:12:42 AM »

This is excellent! Seconding making a PDF.
Logged
Pages: [1]
Print
Jump to:  

Theme orange-lt created by panic