jt_vectors

by Jtgibson
A fully-featured object-oriented suite of floating-point vector and coordinate functions to break free of the boundaries of tiles.
ID:77879
 
Keywords: libraries, math

Most BYOND programmers can get along perfectly fine without vectors. If in your game you're content to stay in BYOND's tile grid, and with the standard four- or eight-directional movement, then there is little reason to even know what vectors are, let alone use them. However, once you start moving beyond the standard limits - you might want to be able to fire a weapon at any angle, perform pixel movement in any direction, or detect collisions of an irregularly shaped object - then vectors quickly become useful, and in some cases vital.

This article will give you an overview of what vectors are, describe the mathematics behind them, and show some examples of how you might use them in a BYOND game. I'll be using JTGibson's jt_vectors library for all examples, which is, for the most part, a good general purpose library that covers all standard vector operations along with some extra functions that I won't touch on in this article. Unfortunately the current version (3) contains a few major bugs, and I will point these out as we go along. It's worth noting that once you understand the mathematics of vectors, it's pretty easy to implement your own vector library. For efficiency's sake you might eventually want to create your own optimized set of functions. For now, though, we'll cover the big questions: just what is a vector anyway?

So What is a Vector?

The usual way to understand a vector is that it is quantity that expresses both a magnitude and a direction. For example, if you say a car's speed is 60 mph, then you are just giving the magnitude of how fast the car is moving. However, if you say the car is moving north at 60 mph, then you are giving both a direction and a magnitude, and so you are specifying a vector. For another example, you could say you are 10 miles away from your house, then you've just given a distance. If you say your house is 10 miles away to the west, then that is both a distance (magnitude) and a direction, and thus a vector of the position of your house.

In physics, the difference between a magnitude (technically called a scalar) and a vector is important enough that sometimes they are named differently; so in the first example a scalar speed is called a speed, whereas the vector of speed and direction is called a velocity. In programming, 95% of the time we will be using vectors similar to those in the above two examples above, of velocity and position. These are so-called spatial vectors in that they represent something about a direction in space, and include things such as position, velocity, acceleration, force, and momentum. It's also sometimes useful to use vectors to represent non-spatial things, such as colours, but I will not cover that in this article.

Defining Vectors

So if that's what a vector is, how do we represent them in a computer? Almost always, we'll use a Cartesian coordinate system, such as the familiar representation of pixels on a screen as measured from the bottom-left corner. If we want to indicate the point 100 pixels across, and 50 pixels up, then we measure 100 pixels left-to-right on the x-axis, and 50 pixels bottom-to-top on the y-axis, giving us the vector P:

P = (100,50)

Note the way that the vector P is boldcase, which is the typically the way vectors are shown in text; you might also see then written in non-bold but with a bar underneath or a small left-to-right arrow (⃗) above them. The numbers in brackets separated by a comma, (100,50) are the distances along the x-axis and y-axis in that order, and are technically the x- and y-components of the vector. To store the vector in a program, we store these components, which we would usually refer to as Px and Py. Generally, for a vector A, the components are:

A = (Ax, Ay)

that is, Ax and Ay are the x- and y-components of A, respectively. Let's look at the vector P graphically, in figure 1. We show the vector as an arrow from the origin, and the values of Px (100) and Py (50) can easily be seen as the distances along the x- and y-axes. Note the direction of the arrow; if it was pointing the other way, we would be showing a vector of the exact opposite direction, i.e. (-100,-50).



Figure 1: The vector P has an x-component of 100 and a y-component of 50.

Let's go back to the first example of a car moving north at 60 mph; for positions in the real world, it would be conventional to use the x-axis to refer to the eastwards (west-to-east) direction, and the y-axis for the northwards (south-to-north) direction. To store that velocity in a vector V, we would then have:

V = (0,60)

That is, the x-component of the velocity is 0, indicating it is not moving eastwards or westwards, and the y-component is 60, indicating a northwards speed of 60 mph. Note that the components of V don't mean anything similar to the components of P, since V expresses velocities in mph whereas P indicates the position of pixels on a screen. This brings up the more general point, that vectors don't have any internal representation of what they actually mean, and it's up to the programmer to keep track of what each vector represents. Indeed, it's quite common for a program to use vectors with several different scales and meanings, and to transform between them as needed. Fortunately, the mathematics of vectors makes this quite easy, as I will show later.

For vectors representing a position, an easy to remember convention in DM programming it to make 1 unit of a vector equal to 1 pixel on the map; therefore a vector 32 units long would be the width of a map tile (I will use this scale in the examples I give). However, it would also be perfectly possible to use 1 unit to equal one tile, in which case a pixel would be 0.03125 units (1/32) long, and this would work just as well. Another thing to remember is that if you are using vector to represent a map position, you should know where the origin of the map is; that is, what position the vector (0,0) represents. Usually this would be the bottom-left tile, but not always.

One thing I've not explicitly stated is that so far all of our examples have been in 2D space, so we're representing positions and velocities on flat screens or flat maps of the Earth, with what are technically called 2-vectors. What if you wanted to represent a position in 3D space, such as the position of an aircraft in the sky? Well, you simply add another component to the vector, indicating the z-axis component:

A = (Ax, Ay, Az)

making A a 3-vector.

In BYOND, which lacks the ability to represent 3D graphics efficiently, we'll almost always be using 2D vectors (2-vectors), and the programming examples I will be giving will all be in 2D. However, some vector functions only really make sense in 3D, and the understanding of 3D vectors is a vital part of more advanced graphics platforms such as OpenGL and DirectX. For this reason, I'll be using 3D vectors in some of the mathematical descriptions below. Fortunately you can treat a 3-vector as a 2-vector by simply setting its z-component to zero in most cases.

There's a hidden complication with 3-vectors, regarding the direction of the coordinate axes. It's common to use so-called right-handed coordinates where, to go back to the example of a screen, the x-axis represents left-to-right, the y-axis represents bottom-to-top, and in this case the z-axis points out of the screen, from back to front. However, it's also possible to use left-handed coordinates, in which the z-axis points into the screen, from front to back. Which coordinate system you use doesn't matter, as long as you are consistent. In the examples, I'll be using right-handed coordinates exclusively.

Vectors in jt_vectors

So we now know that we need to store the components of a vector to represent it. When it comes to writing a program, we could of course do this by manually creating a variable for each component of each vector:

    // the vector P
var/Px = 100
var/Py = 50

but by using jt_vectors, we can create a /vector datum that stores the components for us:
    // the vector P
var/vector/P = new(100, 50)

This creates a new vector datum, P, which the x and y components are initialized to 100 and 50, respectively. One thing to note that all vectors in jt_vectors are actually 3-dimensional; but if we create a new vector datum with 2 arguments we have implicitly set the z-component of P to zero. We could do that same thing explicitly:

    // the vector P
var/vector/P = new(100, 50, 0)
to produce exactly the same result. Using 0 as the z-component of a 3-vector effectively turns it into a 2-vector; what we are saying is that all our vectors will lie in the x-y plane at z=0. Note also that if you create a vector datum without specifying any arguments, you create a null vector, with components all equal to zero (0,0,0).

This would be a good time to introduce some ancillary functions of the vector library. You can create a copy of a vector (that is, create a new vector with the same component values) with the Copy() function:

    var/vector/P = new(10,20,30)
var/vector/Q = P.Copy() // components of Q are now (10,20,30)
and you can access each component of a vector by using the ComponentX(), Y and Z functions:
    var/vector/P = new(10,20,30)
// prints 10,20,30
world << "[ P.ComponentX() ],[ P.ComponentY() ],[ P.ComponentZ() ]"

To set the value of each component of a vector individually, use the SetComponentX(value), Y and Z</code functions:

    var/vector/P = new(10,20,30)
P.SetComponentY(50)
// P is now (10,50,30)

You can also adjust components by adding a positive or negative amount using ModComponentX(value), Y and Z:
    var/vector/P = new(10,20,30)
P.ModComponentY(100)
// P is now (10,120,30)

It's also possible to access the x, y, and z components of vector by using the x_comp, y_comp, and z_comp member variables directly. This is bad practice from an object oriented programming point of view, and you should really use the accessor functions given. Direct access might be useful if you need to extend the vector library with new functions or if you have some vital routine that needs to execute as fast as possible, avoiding the overhead of the various function calls.

Vector Mathematics

While the library will handle the mathematics of vectors for you, it's still useful to know how they work yourself. Many vector operations, such as addition and multiplication, are familiar analogues of those used for regular numbers. What might appear to be more esoteric operations, such as dot and cross products, turn out to be very important for calculating things such as intersections and collisions, and I'll be using them extensively in the programming examples.

If all the mathematics in this section seems too too abstruse to you, I'd suggest skipping to the Examples section at the end of the article and downloading and playing with the three demos. They will give you some idea of what vectors can do in a game, and looking through the sources will show you how they are used.

Adding and Subtracting

If you define two vectors, P and Q:

P = (10,-2,0)
Q = (2,4,0)

then you can add the two vectors together to get a third vector, R by simply summing the components of the other two vectors:

R = P + Q
R = (Px + Qx, Py + Qy, Pz + Qz)
R = (10 + 2, -2 + 4, 0 + 0)
R = (12,2,0)


Figure 2: Adding vectors P and Q to get R.

What is the physical significance of the value of R? Figure 2 shows the result of adding the two vectors graphically. If we place the start of vector Q on the end of vector P, we can see that the sum R points from the start of P to the end of Q. (It's also useful to note that doing vice versa - placing P at the end of Q - produces the same result, so vector addition is commutative i.e. P + Q = Q + P in just the same way that addition of normal numbers is commutative).

Although adding vectors seems a trivial exercise, it's actually quite a useful property. Let's imagine P represents the position on the screen from the origin to the centre of some object - say the player. Now make Q the vector from the centre of the object to some important feature of the player object - say the player's gun. Now we can find the location of the gun on the screen simply by adding P and Q.

Subtracting vectors is very similar, except that the components are subtracted rather than added:

R = P - Q
R = (Px - Qx, Py - Qy, Pz - Qz)
R = (10 - 2, -2 - 4, 0 - 0)
R = (8,-6,0)

Note that as you might expect, subtracting vectors is not commutative e.g. P - QQ - P.


Figure 3: Subtracting vector Q from P to get R.

Looking at things graphically, as in figure 3, shows that subtracting is the same as adding except that the vector Q is traced the opposite direction, from end to start. Subtracting vectors is particularly useful for finding relative positions and changing vector origins. If P and Q represent coordinates of measured from the same origin, then P-Q is a vector from the tip of Q to the tip of P. This aspect of vectors is used many times in the examples, where it's often useful to find the relative position vector between two objects.

Subtracting Q from P is entirely equivalent of adding to P the inverse of vector Q:

P - Q = P + (-Q)

The inverse (also called the reverse or flip) of a vector is just the same vector with the components negated:

R = -Q
R = (-Qx, -Qy, -Qz)
R = (-2,-4,0)

The functions for adding, subtracting, and inverting vectors in the library are mostly simple to use:

    var/vector/P = new(10,-2,0)
var/vector/Q = new(2,4,0)

var/vector/R = P.AddVector(Q)
// vector R now is P+Q = (12,2,0)

R = Q.SubtractVector(P)
// vector R is now P-Q = (8,-6,0)

R = Q.Reverse()
// vector R is now -Q = (-2,-4,0)

However, note the current version of jt_vectors (version 3) has a bug: the subtraction operation works the opposite way around than stated in the documentation, so that P.SubtractVector(Q) produces Q-P rather than P-Q as you might expect. To fix this temporarily, I would suggest writing a fixed version until the library is corrected:

vector/proc/SubVector(vector/alt)
return src.AddVector( alt.Reverse() )
or of course you could edit the SubractVector() function in the library to correct this problem. I'll be using SubVector() for the remainder of this article and for the examples.

Note that all three functions, in common with most in jt_vectors, return the result as a new vector. Calling P.AddVector(Q) makes no direct changes to either P or Q; if you want to add another vector to P "in place" you must use P = P.AddVector(Q).

Length and Scale

As stated previously, vectors have both a magnitude and a direction. To obtain that magnitude back from a vector, we need to find its length (also known as the norm of the vector. This is calculated from the Pythagorean length of the components, and is written as the vector surrounded by vertical bar symbols (|) :

|A| = √(Ax² + Ay² + Az²)

that is, the length of a vector is the square root of the sum of the squares of its components. For example:

A = (3,4,0)
|A| = √(3² + 4² + 0²) = √(9 + 16) = √25 = 5

This is achieved in the library by using the Magnitude() function:

    var/vector/A = new(3,4,0)
var/lengthA = A.Magnitude()
// lengthA is now 5

Note that the length of a vector can be zero (for the null vector (0,0,0) ) but it can't be negative; a negative vector would have the same positive length but point in the other direction. Thus |A| = |-A| for all vectors.

You can change the length of a vector by rescaling, or scalar multiplication, which multiplies all the components by the same scalar value:

sA = (s·Ax, s·Ay, s·Az)

For example, to halve the length of a vector:

A = (10, 5, 0)
0.5A = (0.5·10, 0.5· 5, 0.5·0) = (5, 2.5, 0)

The library uses the function Scale(value) for this purpose:

    var/vector/A = new(10,5,0)
var/vector/B = A.Scale(0.5) // B is now (5,2.5,0)

As long as the scale factor is positive, the factor scales the length of the vector by the same amount:

s|A| = |sA|

If the scale factor is negative, the vector ends up pointing in the opposite direction. Scaling by -1 is equivalent to flipping the vector. Dividing a vector by a scalar is equivalent to multiplication by the reciprocal of the scalar (1/s):

A / s = (1/s)A

A special case occurs when you scale a vector by the reciprocal of its length, a process called normalization:

A = (3,4,0)
|A| = 5
s = 1 / |A| = 1/5
sA = A / |A| = (3,4,0)/5 = (0.6, 0.8, 0)
|sA| = 1

The resulting scaled vector is in the same direction as the original vector, but always has length 1 (unless the vector was the null vector, in which case the value 1/|A| can't be determined). The resulting normalized vector, called a unit vector, indicates the direction of the original vector but without its magnitude.

Normalized vectors are very useful as we shall see later, so they have their own notation indicated by placing a caret or hat (^) character over the vector, but due to the limits of common fonts I will show it with the hat character afterwards (A^). The unit vector of A, for example, is pronounced A-hat:

A^ = A / |A|

To normalize a vector using jt_vectors the UnitVector() function is used:

    var/vector/A = new(3,4,0)
var/vector/Ahat = A.UnitVector()
world << "[Ahat.Magnitude()]" // prints 1

Note that the internals of the library will catch an attempt to normalize the null vector, and instead return a unit vector in the y-direction (0,1,0). This may or may not be what you want, so this is something to be wary of when normalizing.

If you scale a unit vector, then (since a unit vector is length 1), the resulting vector has the same length as the scale factor. That is:

|sA^| = s

is true for all unit vectors A^.

Dot Product

We've seen that we can multiply a vector by a scalar value, but does it make sense to try to multiply two vectors together? There's no direct equivalent, but there are operation that are slightly similar to multiplication. In fact, you can do it in two different ways, called the dot product and the cross product. We'll start with the dot product, which is much the simplest.

If you have two vectors A and B, their dot product is given by the sum of the products of each of their components:

A·B = Ax·Bx + Ay·By + Az·Bz

For example:

A = (10,5,0)
B = (2,4,0)
A·B = 10·2 + 5·4 + 0·h0 = 40

Note that the result of the dot product is a scalar number, not a vector, which is why it's sometimes called the scalar product. As for vector addition, the dot product is commutative (A·B = B·A).

In the library, the dot product is obtained by:

    var/vector/A = new(10,5,0)
var/vector/B = new(2,4,0)
var/dp = A.DotProduct(B)

The significance of the dot product is shown by its alternative definition:

A·B = |A||B|cos θ

That is, the value of the dot product of two vectors is the product of the magnitude of the vectors with the cosine of the angle between them. Due to the nature of the cosine function, this means that if A and B are aligned (pointing in the same direction), the value of their dot product is just |A||B|. If they are pointing exactly in opposite directions, then the cos term is -1 and the dot product is -|A||B|. If the two vectors are orthogonal (at right angles to each other), then the cos term is zero and the dot product is zero.

Also consider what happens if both A and B are normalized. Their dot product is then:

A^·B^ = |A^||B^|cos θ = cos θ

since the length of any normalized vector is 1. This gives us a way to measure the angle between any two vectors: if we normalize them, then taking the inverse cosine (arccos) of their dot product gives the angle between them:

θ = arccos(A^·B^)

We could also do the normalization as part of the process:

θ = arccos(A·B / |A||B|)

This will give us an angle from 0 to 180 degrees. For example:

A = (10,0,0)
|A| = 10
B = (4,4,0)
|B| = √32 = 4√2
A·B = 10·4 + 0·4 + 0·0 = 40
A·B / |A||B| = 40 / (4√2 · 10) = 1/√2
θ = arccos(A·B / |A||B|) = arccos(1/√2) = 45°


Figure 4: Finding the closest point of approach to point A along vector B using the dot product.

As well as angles, you can also find distances using the dot product. Consider a situation like that in figure 4. You have a player at point O, and target at point A, giving a vector A joining O to A. The player fired a weapon from O towards point B, along the vector B, at an angle θ to A. Can we find point C, the point of closest approach of vector B to point A? We can use the dot product of A with B^:

A·B^ = |A||B^|cos θ = |A|cos θ

Some simple trigonometry shows that |A|cos θ is the length of the side of the triangle from O to point C. To find the position of C, we scale the normalized vector B^ by this length:

C = (A·B^) B^

And so we can find the closest point along the line OB to the point A with just a few vector operations. In terms of library calls, this procedure looks like this:

    var/vector/A = new (10,3,0)       // the target vector
var/vector/B = new (50,0,0) // the shot vector

var/vector/Bhat = B.UnitVector() // normalized direction of the shot

var/vector/C
// the closest point that the shot approaches the target
C = Bhat.Scale( A.DotProduct(Bhat) )

Cross Product

The second way that vectors can be combined in a multiplication-like way is called the cross product. The cross product between two vectors is written as:

C = AxB

Note that, unlike the dot product, the result of the cross product is another vector (which is why it is sometimes called the vector product). Calculation of the cross product is rather more complex, and in fact it's easiest to show it in terms of the components of the resultant vector C:

Cx = Ay·Bz - Az·By
Cy = Az·Bx - Ax·Bz
Cz = Ax·By - Ay·Bx

or all at once:

AxB = (Ay·Bz - Az·By, Az·Bx - Ax·Bz, Ax·By - Ay·Bx)

The significance of the cross product is slightly harder to explain. The magnitude of the resulting vector is related to the sine of the angle betwen the two vectors, in a manner similar to the dot product:

|AxB| = |A||B|sin θ

Understanding the direction of the cross product vector requires thinking in 3D. Recall that at the beginning of this article I said we would be using a right-handed coordinate system. Hold your right hand out in front of you, pointing forwards with your index finger (forefinger). Now point your middle finger to the left, and stick out your thumb. If your index finger represents the direction of vector A, and your middle finger the direction of vector B, then your thumb represents the direction of their cross product, AxB (see figure 5). (If we were using a left-handed coordinate system, you would use your left hand and the direction of AxB would be exactly opposite).


Figure 5: The cross product of A (inward) and B (leftward) is directed vertically upwards.

Note that the AxB vector will be at right angles (perpendicular) to both A and B, and this is a very useful property in some 3D problems. The only time this fails is if the two vector point in the same or exactly opposite directions: in that case, due to the sine term the magnitude of the cross product is zero. Unlike the dot product, the cross product is anti-commutative (i.e. AxB = -BxA).

It's an important point that the cross product is only properly defined for 3D vectors. For a 2D vector, the cross product would point either out of or into x-y plane (i.e. along the positive of negative z-axis), which of course is not possible in 2D. However, that doesn't mean that the cross product is useless in 2D. Recall that we're representing 2D vectors by treating them as 3D vectors in which the z-component is always 0. From the definition above of C=AxB, you can see that since both Az and Bz are zero, the Cx and Cy terms must also be zero. Only the Cz term of the cross product does not vanish:

Cz = Ax·By - Ay·Bx

This is in fact quite a useful number, as we can see if we compute it for two example vectors:

A = (0,10,0)
B = (-5,5,0)

C = AxB
C = (0, 0, 0·5 - 10·-5) = (0,0,50)

The value of Cz is positive, and it is so because, looking down on the x-y plane, the direction of vector A is clockwise of vector B. If we change B to (5,5,0), then Cz = -50, and since it is negative you now know that A is anti-clockwise (counter-clockwise) of B. This property of the cross product is very useful when it comes to detecting whether a point in space is inside or outside a convex shape defined by a number of vectors tracing its outline, as we shall see when we come to the example of hit detection.

To perform the cross product in the library, we use:

    var/vector/A = new(0,10,0)
var/vector/B = new(-5,5,0)
var/vector/C = A.CrossProduct(B)
world << C.ComponentZ() // should print 50
B = new(5,5,0)
C = A.CrossProduct(B)
world << C.ComponentZ() // should print -50

Unfortunately, if you try compiling this example you will quickly find that in the current version of jt_vectors, the cross product routine is bugged. I would suggest either editing the library to fix the problem or using a replacement routine:

 vector/proc/FixedCrossProduct(vector/alt)
return new /vector(
src.y_comp*alt.z_comp - src.z_comp*alt.y_comp,
src.z_comp*alt.x_comp - src.x_comp*alt.z_comp,
src.x_comp*alt.y_comp - src.y_comp*alt.x_comp )

Note also that the routine calculates the full 3D cross product even in if we are using 2D vectors, which of course means that it must calculate the x- and y-components even if they are always zero. This is somewhat inefficient, and you are working exclusively with 2D vectors you might want to extend the library to add a routine that calculates and returns only the Z-component of a cross product.

Other Functions

There are a number of other functions provided by jt_vectors which may prove to be useful.

When working with 2D vectors (that is, vectors in the x-y plane), it is sometimes useful to calculate the angle of the vector in the plane. The library provides two functions for this, Angle() and Bearing(). The first returns the angle measured in the standard mathematical sense, anti-clockwise from the x-axis. The second returns the angle from the the north direction (y-axis), measuring clockwise. Both return angles in degrees in the range 0-360°.

The library has RotateX(angle), RotateY(angle), and RotateZ(angle) functions which rotate a vector around the given axis by a specified angle. For 2D vectors, rotation around the z-axis indicates a rotation in the x-y plane. Note that in this case a positive rotation angle indicates an anti-clockwise rotation.

The jt_vectors library contains a number of other functions I do not cover, including a whole /coordinate datum which is designed to represent location coordinates (however, everything that /coordinate can do can also be done with /vector, so it is essentially redundant). For further information, consult the library documentation.

Examples

So you've made it through the mathematics of vectors, and are perhaps starting to wonder if knowing this stuff will prove actually useful for programming a game. I'll present three demos showing various aspects of how vectors can be used. While I won't describe every aspect of each demo (nor do I promise that they are brilliantly programmed), I will cover the way vectors are used and how they interact with the normal aspects of DM programming.

Demo 1 - Vectors and Movement

The first demo is a simple example of using vectors for placement and movement of mobs and objs. It's an (incomplete) version of Asteroids - you have ship, which you can rotate and thrust, and fire a projectile from. Asteroids glide around the screen, and if shot, the larger ones break into smaller pieces. Everything takes place on a single screen (no map scrolling) and object moving off the edge wrap to the opposite edge. In this demo, asteroid-asteroid and asteroid-ship collisions are not implemented (and so there is no way to die).

The ship, the projectiles, and the asteroids each contain two vector variables: a position (pos) and a velocity (vel). Scaling of the position vector is such that 1 unit equals 1 pixel on the map, with the origin of the map being such that an object at (0,0) has its icon centred on the southwest corner of the southwest-most turf on the map. This is done by the set_location() proc defined under atom/movable:

    proc/set_location(vector/L)
var/vx = L.x_comp
var/vy = L.y_comp
var/tx = round(vx / 32)+1
var/ty = round(vy / 32)+1
loc = locate(tx,ty,1)
pixel_x = vx - 32*tx +16
pixel_y = vy - 32*ty +16

This takes a vector location and sets the movable's map turf location and pixel offset, and this is designed so that pixel offsets never range beyond +/-16. The proc is called whenever the object's position vector is updated. Another proc, wrap_location(), ensures that an object moving off of one edge of the screen is wrapped to the opposite edge automatically.

The movement of the objects occurs in the update() proc of /mob/ship (for the player's ship) and of /obj/mover (which encompasses both the asteroids and the projectiles). The main game loop in world.New() calls the update proc of the ship and all moving objects at every iteration of the loop. For /obj/mover objects, it looks like this:

    proc/update()
pos = pos.AddVector(vel)
wrap_location(pos)
set_location(pos)
return
which simply adds the velocity vector to the current position vector, then wraps the position vector to the map, and finally updates the object's map position and pixel offset. The effect is that objects will drift with a constant speed and direction across the map, unless their velocity is changed.

The ship, /mob/ship, contains some additional logic. The heading variable is the ship's current heading (measured in degrees as a bearing clockwise from north), and the update_icon() proc converts this into one of 32 icon_states which contain the rotated images of the ship. (With 32 frames for 360°, there is an angle of 11.25° (=360/32) between each frame.) The update_heading() proc changes the heading depending on the operation of the left and right cursor keys, and ensures that is wrapped into the range 0-360° correctly.

Pressing the down cursor key calls the ship's thrust() proc, the relevant portion of which is:

    var/vector/thrustdir = new(sin(heading), cos(heading))
vel = vel.AddVector( thrustdir.Scale(thrust_accel) )
Here the current heading of the ship is turned into a unit vector (T^) in the direction of the heading, through simple trigonometry:

T^ = (sin θ, cos θ)

where θ is the heading angle (measured clockwise from north). This is necessarily a unit vector due to the properties of the unit circle (sin² θ + cos² θ ≡ 1). The thrust direction is therefore in the same direction that the ship is facing, so it will accelerate forwards. This thrust vector is then scaled by thrust_accel (a), a constant set for the ship, and added to the ship's velocity vector:

V = V + aT^

The net effect is to accelerate the ship in the direction it is facing. Note that this doesn't mean the ship will go in that direction - if the ship already has a substantial velocity in one direction, then thrust in the opposite direction will only slow it down at first.

On pressing the up cursor key, the ship's shoot() proc is called. The important part of this routine is:

    var/vector/shipdir = new(sin(heading), cos(heading))
var/obj/mover/shot/S = new()
S.owner = src
S.pos = pos.AddVector( shipdir.Scale(GUN_OFFSET) )
S.vel = vel.AddVector( shipdir.Scale(S.speed) )
S.set_location(pos)

Once again a normalized vector (shipdir) in the direction of the ship's heading is created. A new /obj/mover/shot obj is created and placed a distance GUN_OFFSET forward from the centre of the ship (this is a constant equal to 12 pixels in this case). The shot's velocity vector is also initialized, giving it a velocity pointing towards the ship's heading, but also adding to it the velocity of the ship itself. This produces a shot that retains the momentum of the ship that fired it.

Another aspect of the shot object is that, as it moves, it checks for collision with the asteroids. This is performed in the check_collision() proc called from the shot's update() proc after the usual movement update has taken place. The collision checking is straightforward:

    for(var/obj/mover/asteroid/B in range(1, src))
var/vector/L = src.pos.SubVector(B.pos)
if(L.Magnitude() <= B.radius)
// collision occurred

The routine looks for any asteroid object within a range of 1 from the shot's current turf location (this is necessary since objects may be overlaying an adjacent turf due to pixel offsets). If one is found, a vector is created pointing from the asteroid's position to the shot's position. Comparing the magnitude of this vector with the asteroid's radius shows whether the shot is inside or outside the asteroid. Since the asteroids are approximately circular, this simple range checking is all that is needed for accurate collision detection.

Note the way that BYOND's standard tile grid is used to find close asteroids before performing the more accurate collision detection. Since vector calculations can be relatively "expensive" to do, it would be inefficient to check the range from each shot to every asteroid on them map. By using BYOND's built in grid to find approximate locations, we can quickly cull any asteroids out of possible collision range, leaving us with relatively few collision calculations. This technique (technically a "uniform grid subdivision" approach) becomes important as more complex collision routines are required, as we will see in the examples below.

To complete the game, we would need to add asteroid-ship collisions. Unfortunately, in this case a range check will not work since the ship is not a simple circular object. For pixel-precise collision detection we would need to use the techniques described in the next two examples below.

Demo 2 - Vectors and Hit Detection

The second demo is rather different from the first. We have a player mob that moves conventionally on the grid, using the cursor keys. Clicking the map fires a beam from the player towards the click point. Collision of the beam is tested against the walls of the area (which fill a whole turf) and various blocker objects (which are are circular but of varying radii). The demo uses the same coordinate scale for vector positioning as used in the first demo, with 1 unit = 1 pixel and the origin being the southwest corner of the southwest-most map turf.

The major vector operations of this demo are contained in the /mob/player's shoot() proc, which is supplied the vector shot as an argument (containing a vector from the player's position to the point clicked). The routine traces the length of the beam and attempts to find the blocking object and intersection point which is closest to the start of the beam. The proc is quite complex and I will describe it in stages.

    var/vector/self = src.get_vector(16,16)
var/vector/dirn = shot.UnitVector()
var/vector/delta = dirn.Scale(16)
var/vector/start = self.AddVector(delta)
var/vector/beam = dirn.Scale(shot_range)
var/list/colliders = get_colliders(start,beam)

First, the routine defines a number of vectors: self, the position of the (centre of) the player's mob; dirn, which is a unit vector normalized from the shot vector; and delta, which is the direction vector scaled by 16 units. The vector start is the location that the beam will start from, and beam is the maximum extent of the beam constructed by scaling dirn by the constant shot_range.

Also defined is a list of objects which could collide with the beam, which is obtained from the global get_colliders() proc. In this demo, get_colliders() simply returns all collidable objects in world, but a more efficient versions could be written (see later).

The next section of the routine prepares various variables used in the tracing of the beam.

    var/beam_dist = shot_range
var/vector/collider = new()
var/vector/origin = new()
var/vector/hitpoint = new()
var/vector/result = new()
var/atom/hit

The value beam_dist contains the current maximum travel distance of the beam; this will be shot_range at the start but is reduced as the beam intersects blocking objects. During the beam tracing, the vector collider is the position of the candidate colliding object, origin is the start of the beam (relative to the colliding object), hitpoint is the intersection point of the beam, and result is the final beam intersection position. The variable hit contains the atom that collided with the beam, or null if none did.

The actual beam tracing takes place in the next section of code:

    for(var/atom/A in colliders)
collider = A.get_vector(16,16)
origin = start.SubVector(collider)

if(origin.Magnitude() > (beam_dist + 23))
continue

hitpoint = A.approx_collide(origin, dirn, beam_dist)

if(hitpoint)
var/dist = hitpoint.Magnitude()
if(beam_dist > dist)
beam_dist = dist
hit = A
if(hit)
collider = hit.get_vector(16,16)
origin = start.SubVector(collider)
hitpoint = hit.exact_collide(origin, dirn, shot_range)
beam_dist = hitpoint.Magnitude()
result = origin.AddVector(hitpoint.AddVector( collider ) )

The trace loops through all atoms in the colliders list, and calculates each one's position vector (collider). Subtracting this from the beam start position gives a relative vector of the collider from the beam start (origin). Finding the magnitude of this allows any candidate collider object which is further away from the current maximum beam length (beam_dist) to be discarded immediately. A slop of 23 pixels is allowed in this calculation to account for the maximum possible distance from the centre of an atom to its corners (≈16√2).

If the collider atom is within range of the beam, then the atom's approx_collide() proc is called, returning an intersection point in hitpoint (or null if the beam did not hit). The approx_collide() proc is designed to be authoritative (that is, it is always correct about whether the beam intersected the atom), but only needs to return an approximate hitpoint. This is an efficiency issue - by using an approximate hitpoint calculation, the trace loop can quickly find which atom intersects the beam closest to the start, then once that is known do the more computationally expensive accurate intersection point calculation just once per beam. This is done by the exact_collide() proc for the colliding atom. The final intersection location is stored in the vector result.

With the hit location now known (or alternately no collision found), the beam is now drawn:

    var/vector/position = start.Copy()
var/dist = 0
while(dist <= beam_dist)
new/obj/beam(position, dirn)
position = position.AddVector(delta)
dist += 16

This is done by placing a trail of /obj/beam objs along the length of the beam, in steps of 16 units. The object is position by its New() proc, which also sets the correct icon_state for the beam's angle depending on its heading, in exactly the same way as the ship in the first demo.

As described above, each collidable atom defines two procs, approx_collide() and exact_collide(). The former proc for the round /obj/blocker objects is as follows:

 approx_collide(vector/origin, vector/beamdir, beamlength)
var/near_dist = -(origin.DotProduct(beamdir))
if(near_dist < 0 || near_dist > beamlength)
return null
var/vector/nearpoint = origin.AddVector(beamdir.Scale(near_dist))
var/dist = nearpoint.Magnitude()
if(dist > radius)
return null
return nearpoint.SubVector(origin)

The situation is similar to the earlier discussion of the point of closest approach, and is illustrated in figure 6. The collider, at point A is circular with a radius r (radius). The beam starts at point O in direction B^ (beamdir) and is length b (beamlength). Vector O (origin) joins the collider's centre to the start of the beam. We wish initially to find point C, the point of nearest approach to the collider. We obtain this by calculating -O·B^ (near_dist) which is the distance from O to C in the B^ direction. The routine checks to see if this value is less than 0 or greater than b, which would indicate that point C is outside the length of the beam.


Figure 6: Finding the intersection point of vector B with a circle centred on point A.

The routine can now calculate the vector C (nearpoint) joining A to C, and by comparing its magnitude (dist) to the radius of the collider determine whether point C is inside the collider or not. The routine finally returns (C-O), giving the position of point C relative to point O.

The exact_collide() proc of /obj/blocker is very similar, following the same logic to calculate vector C (nearpoint) and its magnitude (dist). Following this, it calculates an exact intersection point of the collider circle and the beam:

    var/back_dist = sqrt(radius*radius - dist*dist)
var/vector/hitpoint = nearpoint.SubVector( beamdir.Scale(back_dist) )
return hitpoint.SubVector(origin)
Here back_dist is the distance CD (d) on the right-angled triangle ACD, calculated from Pythagoras. With this known, the vector joining A to D (hitpoint) is easily calculated from (C - dB^) and again returned relative to the beam origin.

The /turf/wall atom also defines approx_collide() and exact_collide() procs. Relative to the centre of the atom, the wall's collidable shape is a square from (-16,16) to (16,16). The approx_collide() routine first calculates the bounding box of the the beam - that is, the coordinates of the box that has the beam stretching across the diagonal - and does a simple coordinate comparison with the bounding square of the wall. If this test fails, there can be no possible intersection between the beam and wall and the routine returns.

Vector Intersection


Figure 7: Finding the intersection point of vectors A and B.

The second part of the test is a vector intersection test. This is a relatively complex bit of mathematics, but is extremely useful for collision detection, so I will go through how it works. Looking at figure 7, we have two vectors in space A and B, with a vector C giving the displacement from the start of A to the start of B. Graphically, it's easy to see that the two vectors intersect at a point E. Consider another vector D, locating a point D from the start of A:

D = C + sB

where s is some (unknown) scalar multiplier. For all values of s, point D will always lie on the same line as the vector B, and for some particular s will be at the same position as the intersection point E. To find this value, we need to find s when D is parallel to A. Mathematically, the simplest way to find this condition is by creating A', which is the vector A rotated by 90° in the plane of the diagram. If we take the dot product of D with A', it will be zero when the two vectors are perpendicular (due to the cos term in the dot product). Thus:

D·A' = (C + sB)·A' = 0

By components, this is:

(Cx + s Bx)Ax' + (Cy + s By)Ay' = 0

Now A' = (Ax',Ay') is perpendicular to A, and in 2D can be constructed from A by swapping its components and negating one of them:

Ax' = -Ay
Ay' = Ax

A' = (-Ay,Ax)

Substituting these components and solving for s gets us:

s = (Ay·Cx - Ax·Cy) / (Ax·By - Ay·Bx)

This is the scalar we need to scale B so it will reach point E on the diagram. Note that if it is out of the range 0<=s<=1, then the intersection point is outside the length of the vector. If the denominator (Ax·By - Ay·Bx) is zero, then A and B are parallel and cannot meet. A similar analysis can be performed to find the scalar for A. Putting them together, we get the intersection routine:

 vector/proc/intersect(vector/v, vector/sv)

var/d = (src.x_comp * v.y_comp - src.y_comp * v.x_comp)
if(abs(d) <= 1e-36)
return null

var/r1 = (sv.x_comp * v.y_comp - sv.y_comp * v.x_comp)/d
var/r2 = (sv.x_comp * src.y_comp - sv.y_comp * src.x_comp)/d

if(r1 < 0 || r1 > 1 || r2 < 0 || r2 > 1)
return null
return src.Scale(r1)

Here src is vector A, v is B, and sv is C. The proc returns the intersection point (relative to the start of A).

Now we can find the intersection point, we can test the beam against the extents of the turf to find if it hits it. The turf has four sides, but for the quick test in approx_collide() we can just test the intersection with the diagonals of the square:

    var/vector/side = new(32,32)
var/vector/vert = new(-16,-16)

var/vector/C = side.intersect(beam, origin.SubVector(vert))

if(C)
return C.AddVector(vert.SubVector(origin))

side = new(32,-32)
vert = new(-16,16)

C = side.intersect(beam, origin.SubVector(vert))

if(C)
return C.AddVector(vert.SubVector(origin))
return null

The diagonals are the vector (32,32) from the southwest point (-16,-16) and vector (32,-32) from the northwest point (-16,16). For the full intersection case in exact_collide(), the beam is tested against the four sides of the square instead. The intersection that results in the shortest beam (i.e. hits the edge closest to the start of the beam) is returned as the collision point.

Demo 3 - Spacewar!

The third demo is the only one that could be considered a full game - it's a version of Spacewar!, one of the first computer games ever written. Two spaceships (red and blue) duel while in orbit of a central sun. They attempt to shoot each other with projectiles (which also orbit), while avoiding crashing into the sun or each other. The game is for two players using the same keyboard - the red player uses the WASD keys, the blue player the cursor keys.

Much of the movement, thrust, and firing code is similar to the asteroids game of first demo, with one major change being that the origin of the position vectors and our coordinate system is now the sun at the centre of the screen. The sun continuously applies gravity to every moving object, so that update() procs that handles object movement include the line:

       vel = vel.AddVector(gravity(pos))
adding an acceleration given by the gravity() proc:
proc/gravity(var/vector/pos)
return pos.Scale( GRAV / pos.Magnitude2()**1.5)

The acceleration acts towards the central sun (this is the reason for making all position vector relative to the sun), and is scaled so that the force is inversely proportional to the square of the distance from the sun, which means we are simulating a real Newtonian gravity. The Magnitude2() is a custom vector function that returns the magnitude squared of a vector (to avoid an unnecessary square-root operation) and GRAV is a negative constant that scales the amount of gravitational attraction (in physics terms, the product of the universal gravitational constant G and the mass of the sun). The exponentiation to the power of 1.5 seems odd, but examining the whole equation we have (where A is the acceleration, and P is the position vector):

A = P ( g / (|P|²)^(1.5) )

Simplifying this gives:

A = gP^ / |P

which is an acceleration in the direction of the sun, inversely proportional to the square of the distance from the sun, as we require.

In the game, all the moving objects are attracted by gravity and all do some collision checks. All objects, including the particles (used for the thrust and explosion effects) are checked with a simple radius comparison to the sun. Shots are additionally checked against collisions with ships, and ships against collision with other ships. For the shot-to-ship and ship-to-ship collisions we use pixel-precise checking, and for that we need to have a way to describe the shapes of the ships. This is simple conceptually but the implementation is fairly complex to keep it efficient.


Figure 8: Defining the postition vectors (green) and outline vectors (red) of the shape of the ship.

Examine figure 8, which is the red ship when facing north. It's roughly a trapezium in shape, and from the centre of the ship (O) we define vectors (green) to each corner (A,B,C,D). We also define outline vectors (blue) between each outer point in a clockwise direction: A to B, B to C, C to D, and D to A. These two sets of vectors are stored as two lists, hull and hullvecs, in a special shape datum for each ship type.

We could rotate these vectors to match the current heading of the ship as needed, but that takes time and is inefficient. Instead, we pre-rotate the ships to the angle of each heading state (1-32) and store the rotated vectors in a list of shape datums, one for each heading state. The caching of this data is done by the global make_caches() proc.


Figure 9: Determining whether point P is inside the shape ABCD by taking cross products.

For detecting shot-to-ship collision, we have a situation similar to that in figure 9. The ship is at some rotation angle and is described by the four points ABCD and the vectors between them. The shot is at point P and we wish to find if P lies within ABCD (which indicates a collision). To do so, we construct vectors from each ship point to P, then find the cross product of the outline vector with the vector to P.

For instance, at point A we take the cross product of the vector AB with vector AP. If AP is clockwise of AB, then the value of the cross product will be negative. As long as the shape is convex, and the outline vectors are defined clockwise around the perimeter of the ship, then this must be true at all points ABCD if P is inside the shape. For figure 9, this is true at points A,B and D, but if you look at point C you can see that the vector CP is anti-clockwise of CD. The cross product is thus positive, and we have determined that point P is outside of the shape.

The code for this is straightforward:

shape/proc/pointInShape(var/vector/p)
var/vector/q
var/vector/r

for(var/i = 1 to hull.len)
q = hull[i]
r = hullvecs[i]
var/xpz = r.CrossProductZ( p.SubVector(q) )

if(xpz>0)
return FALSE
return TRUE

Note the use of the CrossProductZ() proc, which as described in the section on the cross product computes just the Z-component of the cross product, which is all that is needed in the case of 2D vectors in the x-y plane.

Ship-to-ship collision is handled using a similar method: We find the position of each of the hull points (at the ships current position and heading) and test to see if that point is within the perimeter of the other ship. Although this is alone is not a sufficient condition for collision, both ships check each other (blue ship checks for its points inside red ship, and vice versa), which will detect all collisions except pathological cases where the ships are overlaying one another with no points inside each other. This however should be a fairly rare occurrence.

Conclusion

I hope this article has been some use to you; even if your eyes glazed over at the mathematical parts, you can take a look at the demo source code and see how vectors are used. I'd suggest attempting to extend some of the demos as a first step - perhaps you could add asteroid-to-ship collision checking into the first demo, and make it closer to a finished game. You could do a simple distance comparison, or if you're feeling adventurous, try to integrate the shape system of the third demo to handle more precise collision checking.

Needs some tl;dr :P

Now I know why it took so long, I'm going to start reading it now. I'll be lucky if I'm done by tomorrow.
Whats tl;dr mean?
Yash 69 wrote:
Whats tl;dr mean?

too long; didn't read
Very good article and a good intro to vectors. I wouldn't worry about it being too long - it's more valuable if it hasn't been dumbed-down.
ok.
one thousand percent awesome
This is the mathematical parts that I lack in my projects.
It's too bad I'm too lazy right now to actually learn about this stuff.
My collision detection is the simple distance or box collision :\.
Just wait until he gets into dot product and cross product.
Awesome Awesome! I hope to actually come back and read the whole thing at some point. Now I can go day dream in vectors instead of just squares.

Hrmmm... my bathroom floor won't be so useful anymore...

ts
I hope no one expects to make multiplayer games out of this. I mean, not spacewar single-computer ones, at least. Sure it sounds and looks cool and inspirational for daring developers, but you won't get past a single computer unless you run the game with tick_lag at least greater than 1.
Until BYOND could get faster, which probably will never happen :(
Kaiochao wrote:
I hope no one expects to make multiplayer games out of this. I mean, not spacewar single-computer ones, at least. Sure it sounds and looks cool and inspirational for daring developers, but you won't get past a single computer unless you run the game with tick_lag at least greater than 1.
Until BYOND could get faster, which probably will never happen :(

The demo's perform great on my machine. I'm wildly impressed and excited.
Tsfreaks wrote:
The demo's perform great on my machine. I'm wildly impressed and excited.

What I meant was, you can't host it and expect players to have it as smooth as you do.
The demo3 (classic space war game) is really amazing (for Byond).

ts
Kaiochao wrote:
Tsfreaks wrote:
The demo's perform great on my machine. I'm wildly impressed and excited.

What I meant was, you can't host it and expect players to have it as smooth as you do.

Yeah, your right. However, single player "flash" like games are that much more feasible though right? Creative multi-player client/server games are also a possibility as well. They always have been but "libraries" like this one will help catapult efforts in that direction.

ts
Thumbs up!
Contrary to what Kaiochao is suggesting about vectors being somehow unsuitable for BYOND, vectors are all about how you use them. In the case of a game like Space Station 13, vectors are key in generating a smarter and far more efficient air system to the current tile-based one, while still keeping all of the player features. They are a mechanism, a data structure, they are no more inherently slow than any other structure in terms of design. It's all about use, an inefficient tree structure or complex list in BYOND is inefficient because of how suited it is to your task and where you used it, not any inherent speed issue.
Nice article, wish I was a better programmer so I could use it though. (I'm new)
Stephen001 wrote:
Contrary to what Kaiochao is suggesting about vectors being somehow unsuitable for BYOND, ...

I meant having a smooth pixel-movement system. It isn't a problem with the calculations, but just how quickly the screen must be updated for it to look smooth. BYOND just lags too much for the average host to have anything smooth, I suppose. Normal BYOND games use the built-in movement system where icons move from tile to tile smoothly because of pixel_step_size.

Vectors and coordinates are just numbers. I never said they were unsuitable.
Speaking of coordinates, I wonder why Hobnob uses a /vector for containing the location of a ship, instead of a /coordinate. I guess it's because they both have Add/SubtractVector and contain numbers able to be projected onto the pixel offsets.
I really don't see much point in the library's /coordinate datum - apart from a few minor functions, everything the library lets you do with /coordinate can also be done with /vector. I don't see a good reason to create an artificial distinction between a vector representing a position and a vector representing something else (e.g. velocity or acceleration), and so I decided to ignore /coordinate when writing the article.
Page: 1 2