Wednesday, May 9, 2012

An aside. Vector maths for games


Most people, when they start writing games, run up against having to rotate and move objects.  Generally speaking, they attack this problem "head on" using using trigonometry, specifically using sines, cosines and arctangents.  This is a direct application of the SOH/CAH/TOA trigonometry you learned (or are in the process of learning, or will be learning later on) at secondary school.

Although simple and easy to understand, this approach has a few drawbacks.


  • The first (and usually most noticeable) of these is that it's quite slow.  It's manageable for a small amount of objects, but if, for example, you're trying to do something like "Geometry Wars" with thousands of objects rotating and moving at the same time, you're soon going to find that all the trig rapidly becomes a bit of a bottleneck.  It gets even worse if you move into 3 dimensions.
  • The second is related to the first, and, in these days where GPU acceleration and multi-core processing are commonplace, can be a major sticking point - Trigonometry can be hard to efficiently parallelise.
  • The third, and perhaps most important despite being the least obvious, is accuracy.  Floating point calculations are never exact, and the errors in a purely trigonometric approach are usually cumulative.  Generally speaking, this means that if you rotate an object by 1° clockwise, 360 times, it will not end up where it started.


Luckily, there exists a way to almost totally bypass the trigonometry.  Let's recap what state we usually end up using for an object.


  • We keep track of its location in space.  We typically do this using a pair of co-ordinates.
  • We keep track of the direction it's facing.  Typically using an angle.
  • We keep track of the direction in which it is moving, again using an angle.
  • We keep track of its current speed.


We also know how to convert from cartesian co-ordinates (x and y) to polar coordinates (angle and size) and vice versa, we know that polar co-ordinates are equivalent to cartesian co-ordinates, and we've seen that, for some tasks, it's easier to use polar co-ordinates than cartesian ones.

What we're going to do is get rid of all the references to angles, and all the trigonometry.  We're going to do this by using vector mathematics.

So, we have location.  This is a set of co-ordinates, and thus a vector. So far, so good.

By combining direction of movement and speed into a single conceptual value, we get velocity, which is a set of (polar) co-ordinates, and also a vector.  Unfortunately, it has an angle embedded in it, but as we know that polar and cartesian co-ordinates are equivalent, we can represent it in cartesian form (velocity-x and velocity-y).

Which leaves us with that unfortunate direction we're facing, which is a single value indicating angle, and thus a scalar.  However, the only bit we're interested in is the angle, so we can convert it into a vector with a size of 1 (a unit vector), and then get rid of the 'angle' part by converting it to cartesian form (facing-x and facing-y).

So what does that get us?

Well, let's look at the tasks we have done so far.

Moving an object from its current location to the next location


This is the most basic task we want to do, and it's also the most simple.  It's a trivial vector addition of location and velocity, which is to say :

location-x = location-x + velocity-x
location-y = location-y + velocity-y

Accelerating an object in a particular direction


Again, this is pretty simple.  We represent the acceleration as a vector quantity, and add it to velocity :

velocity-x = velocity-x + acceleration-x
velocity-y = velocity-y + acceleration-y

That's the basics of acceleration, but how do we get the acceleration value?

I'm going to explain a basic model of Newtonian physics.  Newton's Second Law is most commonly stated as *F=ma*, where F is the force applied to an object, m is its mass, and a is the acceleration - it can be restated as *a=F/m*.  So to calculate the acceleration of each object, we need to know the force acting on it, and its mass.

We'll assume the mass of the object is constant, for the moment (no near-light-speed effects here, thank you), so what wee need to calculate is the force acting on the object.  Force is a vector value, and the overall force acting on the object is simply the addition of all the forces acting on it.  So, we'll start each "step" of the game with a clean slate, and add the forces up as we go:

force-x = 0
force-y = 0

... Accumulate forces

acceleration-x = force-x / mass
acceleration-y = force-y / mass

So, let's look at the common forces we might

"Thrusting"


To apply a "thrust" in the direction we're facing, we can use the unit vector *facing*, multiplied by some constant of "thrust strength", as follows (remember, *facing* is a unit vector, so it always has a length of 1) :

force-x += facing-x * thrust-strength
force-y += facing-y * thrust-strength

Acceleration towards the floor due to gravity


Assuming that gravity always works downwards, and that our co-ordinate system starts at the bottom left, we can make gravity work as follows (obviously, the value of gravity-constant should be chosen to work with whatever system of units we're using):

force-y -= gravity-constant

Acceleration towards (or away from) other objects


There's 2 cases here.

The first is a very simplistic "chasing" behaviour, where an object "chases" another one.  This is usually best done by rotating the object to point at its target (see later) and then "thrusting" as above, but it can also be useful to carry out a simple "go that way" approach.

The second is a more complex simulation of gravity - if we were implementing something like Geometry Wars, we might have "black holes" that pull objects towards them.  In this case, gravity is a bit more complex, as it not only works in a different direction for each pair of objects, but it gets stronger depending on how close the objects are to each other.

In both cases, the first thing we do is to create a vector that gives both the direction in which we are going to be pulled, and the distance between the objects:

vector-x = other.location-x - location-x
vector-y = other.location-y - location-y

In both cases, we need to know the distance between the two objects.  For the simple chasing case, we'll calculate it directly:

distance = size(vector)

Now, gravity usually works according to what's known as an inverse square law, which is to say that it's inversely proportional to the square of the distance between the two objects.

Remember, Pythagorus tells us that, for any right angled triangle, the sum of the squares on the short sides are equal to the square on the hypotenuse - the square on the hypotenuse is, in this case, equal to the distance squared, so rather that calculating the distance in a single step, we do it in 2 steps so that we can keep the "distance-squared" value :

distance-squared = (vector.x * vector.x) + (vector.y * vector.y)
distance = sqrt(distance)

Now, in both cases, we want to scale the vector by a factor.  To do this, we need to scale the vector to a unit size, and then multiply it by our factor.  To scale to a unit size, we divide each co-ordinate by "distance" :

vector-x = vector-x / distance
vector-y = vector-y / distance

For the simple chasing case, we now multiply by our "chasing strength", and we have our force :

force-x = vector-x * chase-strength
force-y = vector-y * chase-strength

For the attraction due to gravity case, we divide by the distance squared, and then multiply by some constant to get a usable value :

force-x = (vector-x * gravity-constant) / distance-squared
force-y = (vector-y * gravity-constant) / distance-squared

Braking / Friction


Braking is a special case.  We could implement it by making a force vector that points in the opposite direction to the current velocity, but it's simpler (and faster) to simply multiply the current velocity by a factor.

"Proportional" braking is very simple.  If we wanted, for example, to brake by 5% every "step", we would do this:

braking-factor = 0.95
velocity-x = velocity-x * 0.95
velocity-y = velocity-y * 0.95

This makes a very realistic simulation of friction.

"Fixed amount" braking is a tiny bit more tricky - we need to know the size of the current velocity (using Pythagoras' theorem) and work out the factor from there:

speed = size(velocity)
if speed < braking-amount
braking-factor = 0
else
braking-factor = (speed - braking-amount) / speed
endif
velocity-x = (velocity-x * braking-factor)
velocity-y = (velocity-y * braking-factor)

Rotating


Now, so far, everything we've done is incredibly simple - the most complex thing we've come across is a square root, and we haven't had to bother with angles *at all*.

Rotating objects is a bit more complex.  After all, how can we rotate something to a given angle if we don't know what angle it's already at?

The short answer to this is

 I lied.  It's not complex at all.

but the short answer isn't very interesting (and, above all, doesn't tell us anything useful).  The long answer follows, and is based on matrix multiplication.  As a reminder (or a first taste, if you've never seen this before), a matrix is a (conceptually) rectangular grid of values.

Given that we're dealing with 2 dimensions, one of the most useful matrices we can imagine is a 2 x 2 matrix; we can multiply a vector (x, y) by such a matrix as follows :

| a b | |x| = |(x * a) + (y * b)|
| c d | |y|   |(x * c) + (y * d)|

Now, that's pretty simple to understand, and it's trivially simple to implement in code. So, multiplying a matrix by a vector is going to return a vector with (potentially) different values, depending on what's in the matrix. So far, so good, right?

Now, let's go back to rotating stuff using SOHCAHTOA, keeping that in mind.  When we rotate a point (x, y) by an angle θ, we get a point whose x co-ordinate is given by (x * cos(θ)) - (y * sin(θ)), and whose y co-ordinate is given by (x * sin(θ)) + (y * cos(θ)).  Now that looks a lot like the matrix multiplication above, and indeed it is.  We can encode a rotation by some arbitrary angle θ as a matrix, as follows:

| cos θ -sin θ |
| sin θ  cos θ |

This is, in fact so useful that the majority of graphical toolkits (OpenGL, DirectX and so on) provide an API that uses matrices (actually, an extension of the rotation vector given above, but we'll see that later)

Now that in itself is pretty nifty, but here's where the real magick occurs.  Remember SOHCAHTOA?  Remember what it means?


  • Sin of angle = length of Opposite / length of Hypotenuse
  • Cos of angle = length of Adjacent / length of Hypotenuse
  • Tan of angle = length of Opposite / length of Adjacent


We've already used the TOA bit, when we used atan2 beforehand.  We're about to use the SOH and CAH bits to our profit.

Consider a unit vector. The length of its hypotenuse will always be 1.  And as any number divided by 1 is unchanged, we can see that the sin of the angle of that vector is given by the length of the opposite and the cos of the angle of that vector is given by the length of the adjacent.  And we know those values already - they are, quite simply, the co-ordinates of the vector.

So, rather than talking about angles, we can talk about unit vectors, and do away with all that messy trigonometry.  Well, at least when we're talking about taking something that's aligned at an angle of zero, and rotating it to a particular angle as described by a unit vector v - we use a rotation matrix like this:

| v.x -v.y |
| v.y  v.x |

giving us

new-x = v.x * x - v.y * y
new-y = v.y * x + v.x * y

What does this mean?


  • We can, using our handy unit "facing" vector, draw a graphic of our object, rotated to the correct angle, without having to call any trigonometric functions whatsoever.
  • We can make an object A point at another object B by calculating the vector A->B (trivial, this is given by B.location - A.location) and then scaling it to unit size (again, pretty easy - divide each coordinate by the length of the original vector), and using that as the new "facing" vector for object A.
  • If we need "increment" or "decrement" ability (for example, "rotate by 5° CCW") we can precalculate unit vectors describing the angles we need (obviously, this would need to be done using trigonometric functions, but it would only need to be done once), and then use those vectors to create our rotation matrices.


The only thing that's really left is rotating one object rotate towards another (think turret slowly rotating to face player) in increments.  To do this we need to know whether we are going to rotate clockwise or anticlockwise.  The easiest (although probably not the fastest) way to do this is to use atan2() to get the angles of the current "facing" vector and the vector A->B, to decide which way to rotate, and then use the incremental approach above.

Earlier, I touched on the fact that the various toolkits all provide matrix APIs.  How these work is by combining both a rotation and translation matrix (yes, we can deal with translations too) into one matrix.  For a 2-d case, we would do something like this:

|  cosθ -sinθ  t.x  |   | x |
|  sinθ  cosθ  t.y  | * | y |
|   0     0     1   |   | 1 |

Ignoring the pointless result given by the 1 in the vector, we would get :

x = (x * cosθ) - (y * sinθ) + t.x
y = (x * sinθ) + (y * cosθ) + t.y

This is, simply put, the value we had before, with the x and y values of t added on.  The matrix therefore rotates an object by *θ*, and then translates the result by *t*.

The matrices used by OpenGL and so on are not, in fact, 2D specific.  Everything is generalised to the 3D case, so we use :

|  cosθ -sinθ   0    t.x  |
|  sinθ  cosθ   0    t.y  |
|   0     0     1     0   |
|   0     0     0     1   |

This is actually a matrix for 3D translations and rotations, with all the z axis stuff left out.

Followers