MMO Architecture: Creating a ghosting system

In this post I will talk about a common part of an MMO's internal architecture, often referred to as ghosting. Ghosting is how the server tells the client about the world loading around the player as that player moves through the world. Because MMOs are often open-world games you cannot simply have the player load up all of the objects in the entire zone they're in, the game just couldn't run like that on a single player's computer. On top of that the server would have to constantly update every player about every thing happening within a zone, which would create bandwidth issues for both clients and server.

I'll discuss a few different, but similar, ways that ghosting can be achieved (I'm sure there are other ways as well). First of all, the server will only need to send down information of objects in the world that are not environmental, for example there is no need to send information to a client about a tree they're in range of, because that tree is likely static and can never change. The client will know about that tree based on assets/files on their own computer. The server will have an easy way to know which objects have information that can change (like their position, or stats, or state, etc...), so the main work the server will need to do is determine which of these networked objects are close enough to the player to tell the client about.

Method #1: Ghosting objects within a proximity around the player
With most physics engine the most efficient way to ghost objects within a proximity of the player is to give the player an axis-aligned bounding box (AABB). Axis-aligned shapes will have smaller broadphase sizes, which will result in them being checked against less objects for collision. Attach an AABB to a player on the server, and whichever networked objects collide with this box are entered into a list to send updates to the player about. Whenever the object un-collides with the bounding box then the server can tell the client to unload that object. Generally this bounding box is large enough the player doesn't see all of the objects loading and unloading right around them.

Method #2: Ghosting objects that have players in their proximity
This method is similar to the last method in that we're ghosting objects to clients based on proximity to those objects, the difference here is that rather than attaching an AABB to the player, you instead put AABBs on the networked objects instead. This method has its pros and cons. On the plus side this allows designers and engineers to tweak the distances that an object with ghost down to the player, on a per object basis. This means that if an object is deemed to be a higher priority than other objects then designers can increase the distance as which they'll ghost to players. The down side to this method is that it will use more memory and hit performance a bit more on the server, this is because you have potentially many more AABBs in the world checking for collisions.

Method #3:  Distance checking
This method is similar to method #1 in that it is proximity-based. This method entails mathematically brute force checking the player's position against the position of ghosted objects nearby. To realistically use this in a large-world MMO you would need some kind of spatial partitioning in your world so you knew which sub-set of objects were close enough to the player to do distance checking again, otherwise you'd likely be doing hundreds of distances checks per frame per player, possibly many more. If you already have spatial partitioning in your world you may not even need this method, which leads me to Method #4.

Method #4: Spatial partitioning
If your MMO's world is using a decent spatial partitioning algorithm to sort the scene then the server may already know which networked objects are close enough to the player, and could send those objects down. This method is the least expensive in terms of how expensive the ghosting is, however the spatial partitioning itself has a decent expense to it most of the time, so if ghosting was your only reason for using spatial partitioning on the server, then you're probably just as well off using Method #1 so long as you have a decent physics engine (as most physics engines have their own spatial partitioning anyway).

The above methods will allow you gather the objects that a client will care about. From here it's fairly simple, when the objects first enter range of the player (or the player first enters the object's range), you send the player an initial packet with the full current info about the object, and any changes that need to be networked while that object is in range will also go the player. This allows the player to get the full info as objects enter range so that they can see that object in the same state that the server does, and then it should receive any changes from the server object while it's in range as well. Combining all of this gives you a basic but fairly complete ghosting system for an MMO.

Havok: Setting mesh color in the Visual Debugger, Part 2

In part 1 of this series I showed you how to colorize your physics meshes in the Havok Visual Debugger (HVD). However as you may have noticed, this only works for colorizing meshes that are already loaded in the HVD, so if you connect the HVD to the game after those colors have been set you will not see that information. Here's a simple way to get around that problem.

You program is likely directly using an hkVisualDebugger, what you will need to do is derived a new class from hkVisualDebugger. The hkVisualDebugger class has an m_clients variable, but it's access is protected, and there is no accessor to its information in hkVisualDebugger so unless you have the actual source code for Havok, you're going to need to derive your own class from hkVisualDebugger so you can create an accessor to the data that you need.

Create a new header file in your project, name it 'PhysicsVisualDebugger' or whatever class name you would like to use. The code below is the entire class, no .cpp file is needed.

#pragma once

#ifndef __PhysicsVisualDebugger_h_
#define __PhysicsVisualDebugger_h_

#include <common\visualize\hkvisualdebugger.h>

class PhysicsVisualDebugger : public hkVisualDebugger
{
public:
    PhysicsVisualDebugger(const hkArray<hkProcessContext*>,
                          const class hkVtableClassRegistry* classReg = HK_NULL)
         : hkVisualDebugger(contexts, classReg)
    {}

    virtual ~PhysicsVisualDebugger() {};

    unsigned int GetNumClients() const { return m_clients.getSize(); }
};

#endif //__PhysicsVisualDebugger_h_

Make sure any place you were using an 'hkVisualDebugger' that you're not using your new class you've just made.

The goal we're aiming for is to know when somebody connects the HVD to your program. The GetNumClients() above will return to you the number of current clients connected, if you call it at the appropriate time you can compare it to check if that number has just increased.

In my example below, 'm_pDebugger' is a pointer to a 'PhysicsVisualDebugger'. Put this code wherever you're currently stepping the HVD.

unsigned int numConnections = m_pDebugger->GetNumClients();

// Update the debuggers (which also checks for new clients)
m_pDebugger->step(m_fStepLength);

// If there are now more connections than before the update
if ( m_pDebugger->GetNumClients() > numConnections )
{
    // This is where you will want to go through all physics
    // objects and have to re-send their color info to the
    // debugger.
    UpdateDebuggerInfoForAllEntities();
}

Notice we query the number of connections before stepping the debugger, store that number, and then after stepping the debugger we query for number of connections again. If the number of clients has increased, then you should find a way of having all of your objects resend their color information to the HVD. In my case whenever I add an object to the Havok world, I keep track of its pointer in a list so I can call a function on everything in that list at any time to have them refresh their information for the HVD.

Using Vector Mathematic, Finding closest point on a line

In this post we will be looking at determining the closest point on a line from another point. This technique by itself isn't worth much, but it's required as part of other techniques, such as an intersection test between a line and a sphere, which I may post about later.

Describing how this works using only words is going to be tough. Lets start with a picture to help:

Of the points in this picture, only point B lies along the line segment. Technically you could say that the closest point on the segment to point A is P1, and to C is P2, but in most cases where you want the closest point on a line segment you want to exclude points that aren't going to lie in that segment, so we will exclude them for our purposes.

First we need to get some information setup that we'll be able to test with.

1. We need a vector from P1 to P2, which is achieved by doing P2 - P1.
   Line difference vector is (5 - 0, 0 - 0, 0 - 0) = (5, 0, 0)
2. We need the squared length of the vector we just got in step 1.
   I'm not even doing the math for this part, only one component is non-zero, which is the 5, so the   length in this case is 5, leaving squared length at 25.
3. We need a vector from P1 to our test point (point B), which is B - P1.
   Point difference from P1 is (3 - 0, 0 - 0, -2 - 0) = (3, 0, -2)

Now we do the dot product between our line difference vector and our line to point vector
line diff ( dot ) line to point = ( 3*5 + 0*0 + -2*0 ) = 15

Notice that unlike previous posts, we don't unitize our difference vectors before doing a dot product. In this case we take that dot product and now divide it by the squared length.

Percentage from start to end point = 15 / 25 = 0.6 (0.6 is the same as saying 60%)

Note: We didn't test points A or C because we could see from the picture they weren't on the line segment, but normally you won't be able to just pick which point you want to test, you test every point, and if your value above (which for point B is 0.4) is less than 0.0 or greater than 1.0, then you know it's outside of the line segment.

Now, the closest point is calculated as such:
P1 + ( U * ( P2 - P1 ) )

Which for our example becomes this:
(0, 0, 0) + ( 0.6 * ( 0, 0, 5 ) ), which simplifies to ( 3, 0, 0 )

Here's the code for this:

Vector3 GetClosestPointOnLineSegment(const Vector3& LinePointStart, const Vector3& LinePointEnd,
                                     const Vector3& testPoint)
{
    const Vector3 LineDiffVect = LinePointEnd - LinePointStart;
    const float lineSegSqrLength = LineDiffVect.LengthSqr();

    const Vector3 LineToPointVect = testPoint - LinePointStart;
    const float dotProduct = LineDiffVect.dot(LineToPointVect);

    const float percAlongLine = dotProduct / lineSegSqrLength;

    if (  percAlongLine  < 0.0f ||  percAlongLine  > 1.0f )
    {
        // Point isn't within the line segment
        return Vector3::ZERO;
    }

    return ( LinePointStart + ( percAlongLine * ( LinePointEnd - LinePointStart ));
}

Using Vector Mathematics (and a bit of trig), Point against cone intersection test

In this post we're going to see how to check if a point lines within a 3D cone. To be clear, it's not exactly a cone, it's like a cone that goes on forever, or if we give a max distance it's like a cone with a round bottom instead of flat.

You might wonder what this kind of intersection test is good for; It's mostly used for things like checking if a point is within an object's field-of-view.

So for checking if a point is within an object's field of view, we need 4 parameters.
We need the position of the object, the direction it is facing, the position of the point we're checking, and the field of view of the object.

We'll pick some convenient values to make things easier to understand.
Object position = (0, 0, 0)
Object facing direction (0, 0, 1)
Point position = (0.5, 0, 1.5)
Field of view = π/3 radians (60 degrees)

We need to get the direction from the object to the point:
Difference vector = (0.5 - 0, 0 - 0, 1.5 - 0) = (0.5, 0, 1.5)

Now that we have the difference, we need to unitize it to get a direction.
length = √( 0.5² + 0² + 1.5² ) = √( 0.25 + 0 + 2.25 ) = √2.5 = 1.5811388
inverse length = 1 / 1.5811388 = 0.63245554
direction = (0.5 * 0.63245554, 0 * 0.63245554, 1.5 * 0.63245554) = (0.31622777, 0, 0.94868331)

Now that we have the direction from the object to the point we get the dot product between that vector and the object's facing direction.

Facing direction (dot) direction to point = (0 * 0.31622777 + 0 * 0 + 1 * 0.9486331) = 0.9486331

Now we need to calculate the cosine of half of the player's field of view. We use half because we want the angle from the center of the cone of FOV, just like dot product is the angle from the center.

half of FOV = π/6
cosine(π/6) = 0.866025

And finally, what determines if the point is in the object's FOV is if the dot product (0.9486331) is greater than or equal to the cosine of half of the FOV (0.866025). In this case it is greater than or equal to the cosine of the FOV, so that point is in the object's FOV.

And here's the function for doing this type of calculation:

bool IsPointWithinCone(const Vector3& coneTipPosition,
                       const Vector3& coneCenterLine,
                       const Vector3& point,
                       const float FOVRadians)
{
    Vector3 differenceVector = point - coneTipPosition;
    differentVector.Unitize();

    return ( coneCenterLine.Dot(differenceVector) >=
             cos( FOVRadians ) );
}

The above function assumes a cone the continues on forever. If the we assume that our object cannot see for an infinite distance then we can add a distance check.

bool IsPointWithinFiniteCone(const Vector3& coneTipPosition,
                             const Vector3& coneCenterLine,
                             const Vector3& point,
                             const float FOVRadians,
                             const float maxDistance)
{
    Vector3 differenceVector = point - coneTipPosition;

    // Notice that Unitize() is returning a float. The
    // original one we wrote didn't return a float, we'll
    // cover this change in an upcoming blog post
    float length = differentVector.Unitize();

    if ( length > maxDistance )
    {
        return false;
    }

    return ( coneCenterLine.Dot(differenceVector) >=
             cos( FOVRadians );
}

In our original example at the top of the post our point was 1.58 units away, so if we used a finite distance check like the function just above and passed a max distance of 1.5 in, the object would be considered outside of the view.

Using Vector Mathematics, Complete Vector3 Class

After a large series of vector mathematics blog posts, here is a full Vector3 class that I wrote, it's fairly efficient and should be enough to suit your needs if you would like to use it. There are other 3rd-party math libraries out there if you'd like to browse your options.

Header file: Vector3.h

#pragma once // Most compilers are compatible, remove if yours isn't
#ifndef VECTOR_3
#define VECTOR_3

#include <math.h>
#include <ostream>

class Vector3
{
public:
Vector3(void);
explicit Vector3(const float x, const float y, const float z);

// Copy constructor
Vector3(const Vector3& rhs);

~Vector3(void);

bool operator==(const Vector3& rhs) const { return ( (x == rhs.x) 
                                                  && (y == rhs.y)
                                                  && (z == rhs.z));}
bool operator!=(const Vector3& rhs) const { return ( (x != rhs.x)
                                                  || (y != rhs.y)
                                                  || (z != rhs.z));}
Vector3 operator+(const Vector3& rhs) const;
void operator+=(const Vector3& rhs);
Vector3 operator-(const Vector3& rhs) const;
Vector3 operator-(void) const;
void operator-=(const Vector3& rhs);
void operator*=(const int scalar);
void operator*=(const float scalar);

// Non-member operators get a friend declaration
friend Vector3 operator*(const Vector3& vector, const int scalar);
friend Vector3 operator*(const Vector3& vector, float scalar);
friend Vector3 operator*(const int scalar, const Vector3& vector);
friend Vector3 operator*(const float scalar, const Vector3& vector);
friend std::ostream& operator<<(std::ostream& ofs,const Vector3& rhs);

inline void Flip(void) { x = -x; y = -y; z = -z; }

inline float Dot(const Vector3& rhs) const { return (x * rhs.x
                                                   + y * rhs.y
                                                   + z * rhs.z); }

Vector3 Cross(const Vector3& rhs) const;

float Length(void) const { return sqrtf( LengthSqr() ); }

inline float LengthSqr(void) const { return (x * x + y * y + z * z); }

float Unitize(void);

void Reflect( const Vector3& rhs );

static Vector3 Reflect( const Vector3& first, const Vector3& second );
static Vector3 GetLongest(const Vector3& first, const Vector3& second);

static const Vector3 Left;
static const Vector3 Right;
static const Vector3 Up;
static const Vector3 Down;
static const Vector3 Forward;
static const Vector3 Backward;

static const Vector3 UnitX;
static const Vector3 UnitY;
static const Vector3 UnitZ;

static const Vector3 Zero;


float x;
float y;
float z;
};

#endif //VECTOR_3

Implementation File, Vector3.cpp:

#include "Vector3.h"

#include <sstream>

const Vector3 Vector3::Right(1.f, 0.f, 0.f);
const Vector3 Vector3::Up(0.f, 1.f, 0.f);
const Vector3 Vector3::Forward(0.f, 0.f, 1.f);
const Vector3 Vector3::Left(-1.f, 0.f, 0.f);
const Vector3 Vector3::Down(0.f, -1.f, 0.f);
const Vector3 Vector3::Backward(0.f, 0.f, -1.f);

const Vector3 Vector3::UnitX(1.f, 0.f, 0.f);
const Vector3 Vector3::UnitY(0.f, 1.f, 0.f);
const Vector3 Vector3::UnitZ(0.f, 0.f, 1.f);
const Vector3 Vector3::Zero(0.0f, 0.0f, 0.0f);

Vector3::Vector3(void) : x(0.0f), y(0.0f), z(0.0f)
{
}

Vector3::Vector3(const float x, const float y, const float z)
{
    this->x = x;
    this->y = y;
    this->z = z;
}

// Copy constructor
Vector3::Vector3(const Vector3& rhs)
{
    x = rhs.x;
    y = rhs.y;
    z = rhs.z;
}

Vector3::~Vector3(void)
{
}
Vector3 Vector3::operator+(const Vector3& rhs) const
{
    Vector3 newVector;
    newVector.x = x + rhs.x;
    newVector.y = y + rhs.y;
    newVector.z = z + rhs.z;
    return newVector;
}

void Vector3::operator+=(const Vector3& rhs)
{
    x += rhs.x;
    y += rhs.y;
    z += rhs.z;
}

Vector3  Vector3::operator-(const Vector3& rhs) const
{
    Vector3  newVector;
    newVector.x = x - rhs.x;
    newVector.y = y - rhs.y;
    newVector.z = z - rhs.z;
    return newVector;
}

Vector3 Vector3::operator-(void) const
{
    Vector3  newVector(-x, -y, -z);
    return newVector;
}

void Vector3::operator-=(const Vector3& rhs)
{
    x -= rhs.x;
    y -= rhs.y;
    z -= rhs.z;
}

void Vector3::operator*=(const int scalar)
{
    x *= scalar;
    y *= scalar;
    z *= scalar;
}

void Vector3::operator*=(const float scalar)
{
    x *= scalar;
    y *= scalar;
    z *= scalar;
}

Vector3 operator*(const Vector3& vector, const int scalar)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const Vector3& vector, const float scalar)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const int scalar, const Vector3& vector)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}

Vector3 operator*(const float scalar, const Vector3& vector)
{
    return Vector3(vector.x * scalar, vector.y * scalar, vector.z * scalar);
}
std::ostream& operator<< (std::ostream& os, const Vector3& vector)
{
    std::stringstream stream;
    stream << "X: " << vector.x << ", Y: " << vector.y << ", Z: " << vector.z; 
    os.write(const_cast<char*>(stream.str().c_str()),
             static_cast<std::streamsize>(stream.str().size() *
             sizeof(char)) );
    return os;
}

Vector3 Vector3::Cross(const Vector3& rhs) const
{
    return Vector3( (y * rhs.z) - (z * rhs.y), 
                    (z * rhs.x) - (x * rhs.z),
                    (x * rhs.y) - (y * rhs.x) );
}

float Vector3::Unitize(void)
{
    const float length = Length();
    const float inverseLength = 1.0f / length;
    x *= inverseLength;
    y *= inverseLength;
    z *= inverseLength;
    return length;
}

void Vector3::Reflect( const Vector3& normal )
{
    const float dotProductTimesTwo = Dot(normal) * 2.0f; 
    x -= dotProductTimesTwo * normal.x;
    y -= dotProductTimesTwo * normal.y;
    z -= dotProductTimesTwo * normal.z;
}

Vector3 Vector3::Reflect(const Vector3& vector, const Vector3& normal)
{
    Vector3  newVector;
    const float dotProductTimesTwo = vector.Dot(normal) * 2.0f;
    newVector.x = vector.x - (dotProductTimesTwo * normal.x);
    newVector.y = vector.y - (dotProductTimesTwo * normal.y);
    newVector.z = vector.z - (dotProductTimesTwo * normal.z);
    return newVector;
}

Vector3 Vector3::GetLongest(const Vector3& first, const Vector3& second)
{
    if ( first.LengthSqr() > second.LengthSqr() )
        return first;

    return second;
}

Using Vector Mathematics, Cross Products

Cross products are the most complicated use of vectors we've covered so far. One thing you'll need to know is if your game engine's coordinate system is left-handed or right-handed. If you're unfamiliar with coordinate system handedness, you might read over this article on Wikipedia.

The cross product method is very handy for finding the vector that is perpendicular/orthogonal to two other vectors. Any two non-parallel vectors will form a plane, and the line perpendicular to that plane that passes through the two vectors will always exist, that line can be found with a cross product. You might be asking how this is useful in 3D games? It's often used for finding an object's forward, up, or right vector. An object's forward vector is the vector that goes from the position of the object outward through the front of the object, an up vector is a vector that goes from the position of the object upward out of the top of the object, and the right vector goes from the position of the object out the right side of the object. Any vectors parallel to those vectors qualify as well. A picture might help clarify (or it might confuse you more):

Don't worry, this stuff confused me when I first started as well, a large part of being comfortable doing vector mathematics in games is just being able to picture multiple points and vectors in 3D, so you can picture exactly what it is you're trying to get. If you still want some info on Cross Product after this blog post, this video on YouTube might clarify.

Anyway, let's move on to explaining the math behind a cross product. Here's the exact formula:

If A and B are vectors, and x, y, z, denote the parameter within the vector

A (cross) B = ( Ay*Bz - Az*By, Az*Bx - Ax*Bz, Ax*By - Ay*Bx )

Don't feel bad if you don't memorize this, I haven't got it memorized either.

So let's take some vectors we know to be orthogonal, and see if the cross product gets us the same result:

Vector A = (1, 0, 0)

Vector B = (0, 1, 0)

Vector C = (0, 0, 1)

A (cross) B, should result in C given the three vectors we defined just above.

A (cross) B = ( 0*0 - 0*1, 0*0 - 1*0, 1*1 - 0*0 ) = (0, 0, 1)

As you can see A (cross) B, does indeed give us Vector C as we had defined it above.

And to give a real world scenario I often run into in actual game development. If we take an NPC that is always upright (by upright I mean that it's not laying on its side or something), if we want to get its right or left vectors, we just need the forward vector, and since its always upright we already have the up vector. Based on having the forward and up vector, forward (cross) up will give you the right vector.

Here's a guide of what vectors crossed (in a left-handed coordinate system) will give you:

Forward (cross) up --> Right

Up (cross) Forward --> Left

Forward (cross) right --> Down

Right (cross) Forward --> Up

Up (cross) right --> Backward

Right (cross) up --> Forward

If you read that first link I gave to Wikipedia about coordinate handedness, you'll find you can use your pointer finger, thumb, and middle finger to represent the three axes to determine the cross product order and what it will give you. 

I'll try and explain. Hold out your left hand in closed fist and give a thumbs up, now point your pointer finger straight ahead of you now point your middle finger out perpendicular to your thumb and pointer finger. In this position you can think of the cross product as:

Pointer (cross) Thumb --> Middle

Using this you can use whatever vectors you have to figure out which order to use the cross product. For example let's say you want an UP vector. Hold out your hand like I explained earlier, but turn your arm or wrist so that your middle finger is pointed upward now, and you will now see that your pointer finger is pointing Forward, and your thumb is pointed Left. Therefore: Forward (cross) Left --> Up, and you can always reverse the order to get Down, so Left (cross) Forward --> Down.

Hope this all makes sense. And here's the function for a cross product:

Vector3 Vector3::Cross(const Vector3& rhs) const
{
    return ( (y * rhs.z) - (z * rhs.y),
             (z * rhs.x) - (x * rhs.z),
             (x * rhs.y) - (y * rhs.x) );
}

Using Vector Mathematics, finding a signed angle between two vectors

In the last blog post we talked about finding the angle between two vectors, but sometimes you will find it necessary to know which side of a vector another vector is. This is especially useful for A.I. steering, having an enemy know that it needs to turn 50 degrees isn't useful unless you also can tell it which way to turn.

Here's a handy little function you can use to get the angle between vectors in a signed format (+/-). You'll pass in your source vector (which is generally the way something is facing), the destination vector (the way something is wanting to turn to), and an angle that is 90 degrees to the right of the destination angle (we'll call it 'DestsRight'). To get an angle 90 degrees to the right of the destination angle you may need to use a Cross Product, which we'll be going over in the this blog post.

float GetSignedAngleBetweenVectors( const Vector3& Source, 
                                    const Vector3& Dest,
                                    const Vector3& DestsRight ) 
{    // We make sure all of our vectors are unit length
    Vector3 SourceCopy = Source;
    SourceCopy.Unitize();
    Vector3 DestCopy = Dest;
    DestCopy.Unitize();
    Vector3 DestsRightCopy = DestsRight;
    DestsRightCopy.Unitize();
    
    float forwardDot = Vector3.Dot( SourceCopy, DestCopy );
    float rightDot = Vector3.Dot( SourceCopy, DestsRightCopy );

    // Make sure we stay in range no matter what, so Acos
    // doesn't fail later
    if ( forwardDot < -1.0f )
    { 
        forwardDot = -1.0f;
    }
    else if ( forwardDot > 1.0f )
    {
        forwardDot = 1.0f;
    }

    float angleBetween = acos( forwardDot ); 

    if ( rightDot < 0.0f )
    {        
        angleBetween *= - 1.0f;
    }        

    return angleBetween;
}

If we were to use this above function with these vectors:

The dot between S and D would be greater than 0, dot between S and R would be less than 0, so the final result angle would be negative, so we would know if D is the way we're facing we'd need to turn left to get to S.

The dot between S and D would be greater than 0, dot between S and R would be greater than 0, so the final result angle would be positive, so we would know if D is the way we're facing we'd need to turn right to get to S.

I'm too lazy right now to do a math proof of the above function, so you'll just need to trust me that it works (I've used something like this in production code).

Using Vector Mathematics, finding angle between two vectors

In the last blog post we learned about Dot Products, and how it could be used to find relative differences between two vectors, but now we will learn how to find the exact angle between those two vectors.

For this example we will use two very simple vectors. To get the angle between two vectors you will need to unitize your vectors or make sure they're already unit-length, for simplicity I will just use two unit-length vectors to start with in this example:

Vector a = (1, 0, 0)
Vector b = (0, 0, 1)

You'll notice the above vectors are both along an axis, which means they're perfectly perpendicular, which also means we know already that they're 90 degrees apart ( π/2 radians apart ), but we'll use that knowledge as proof that what I'm about to show you does in fact work. Also, for future reference, please note that any vectors that are perpendicular to each other are also known as orthogonal, this term is often used when referring to vectors, so it's important to know.

Ok, so first we'll get the dot product of the vectors, which should end up being 0 since the vectors are orthogonal.

a (dot) b = (1*0 + 0*0 + 0*1) = 0

And now to get the angle between the vectors, we will use the trigonometric function for arc-cosine, called acos(). Please note that acos() requires a value between -1 and 1, anything outside of that range will cause acos() to return a non-number return value, which you don't want. It's safest to range check what you're about to pass it just in case.

acos(0) = π/2 radians, which is 90 degrees.

If you have two vectors that are parallel, you'll always get a dot product of ±1, and acos(-1) or acos(1) is always 0 radians/degrees as you would expect. But lets test it with a dot product just for fun:

Vector c = (1, 0, 0)
Vector d = (1, 0, 0)

c (dot) d = (1*1 + 0*0 + 0*0) = 1
acos(1) = 0 radians/degrees

Vector e = (-1, 0, 0)

c (dot) e = (1*-1 + 0*0 + 0*0) = -1
acos(-1) = 0 radians/degrees

And.....now some code:

inline float FindAngleBetweenVectors( const Vector3& first,
                                      const Vector3& second )
{
    // You might leave these Unitize calls out if you know
    // you're always passing in Unitized vectors. However
    // I recommend having two versions of this function,
    // one that takes unit vectors, and one that will unitize
    // them for you.
    // Copies are required because we're passing in 'first'
    // and 'second' by const reference, which allows the
    // user to pass in vectors and not worry about them
    // unintentionally getting unitized.
    Vector3 firstCopy = first;
    firstCopy.Unitize();

    Vector3 secondCopy = second;
    secondCopy.Unitize();

    const float dotProduct = firstCopy.Dot(secondCopy);

    // A range check here is a good idea for safe code, I'll
    // leave it out for this sample though.

    return acos(dotProduct);
}

Using Vector Mathematics, Dot Products

Dot product is one of the properties of vectors that you can get when multiplying them. The dot product has many useful properties with vectors, in fact, the Dot Product and Cross Product are probably some of the most important properties of vectors in 3D math used in video games. The Dot Product is most often used to tell us information about the angle between two vectors, this can be used, for example, to tell if a point is in front of a player, or behind them.

To get a dot product, you multiply each component of two vectors, and then add each component together, like such:

Vector a = (3, -5, 7)
Vector b = (5, -2, -9)

a (dot) b = ((3 * 5) + (-5 * -2) + (7 * -9)) = 15 + 10 - 63 = -38

While the above method is using the dot product, most often you'll find you need the dot product of two unit-length vectors, which will always yield a result between -1 and +1, and as we'll discuss later on, that is extremely useful. So, we will unitize the two vectors from our above example, which will basically give us two direction vectors.

Length of a = √(3*3 + -5*-5 + 7*7) = √(9 + 25 + 49) = √83 = 9.110433
Inverse length of a = 1 / 9.110433  = 0.1097642
Unitized vector a = (3 * 0.1097642, -5 * 0.1097642, 7 * 0.1097642) = (0.3292926, -0.548821, 0.7683494)

Length of b = √(5*5 + -2*-2 + -9*-9) = √(25 + 4 + 81) = √110 = 10.488088
Inverse length of b = 1 / 10.488088 = 0.0953463
Unitized vector b = (5*0.0953463, -2*0.0953463, -9*0.0953463) = (0.4767315, -0.1906926, -0.8581167)

Alright, now that we have unit vectors let's try the dot product again:
a (dot) b = (0.3292926 * 0.4767315) + (-0.548821 * -0.1906926) + (0.7683494 * -0.8581167)
              = 0.1569842 + 0.1046561 + -0.65933345
              = -0.39769315, or let's just round it to -0.4

So, what does -0.4 really mean to you in this case? Well here's the cool part. With a dot product, if we treat the two vectors as directions, then a value less than 0 means that vector 'b' is behind vector 'a'. A value greater and 0 means it would be in front, and a value of 0 means it's directly to the left or right of 'a'.

So in this particular example, if we think of 'a' as the direction an object is facing, and think of vector 'b' as a point in space than that means that the point 'b' is behind the object. This is extremely useful for things like artificial intelligence, if an enemy knows the player is behind them, then it can be told to start turning around to face the player, or if the enemy knew the player was in front of them then they might know they are able to attack the player. Knowing where one object is in relation to another, especially based on that object's rotation, is essential for all kinds of things that require steering, not just A.I. So if you plan on making a 3D game, then the Dot Product is your friend. Learn it, live it, love it.


Here's a rough sketch of what this looks like, in this example I've done a top-down perspective, so I left the Y component out of the sketch, but based on the Y-components if this were in-game the enemy would be slightly higher than the player. Anyway, in the picture the arrow is the direction the player is facing, the line perpendicular to the arrow would be the left and right of the player, and as you can see the position of the enemy (which is 5, -9) is behind the player (and a bit to the right as well).

And finally, here's the code for our above example:

The Dot function would be a member of a Vector class most likely:

inline float Vector3::Dot( const Vector3& rhs ) const
{
    return (x * rhs.x
          + y * rhs.y
          + z * rhs.z);
}

And now to put our new Dot function to use:

Vector3 first = Vector3(3, -5, 7);
Vector3 second = Vector3(5, -2, -9);

first.Unitize();
second.Unitize();

float dotProduct = first.Dot(second);

// dotProduct is approx. -0.4

Using Vector Mathematics, utilizing squared lengths

As we've learned in the Optimizing Methods blog post, the most expensive part about doing distance checks is the square-root calculation. There are some cases where we need to do things like compare distances, but we can forego the square-root calculation.

If we want to compare two vectors to see which is longer we can do that without a square-root calculation. We don't need to know the exact length of each vector, we just need to know which is longer, so if we just skip the square-root calculation during the Length() function, when instead end up getting a squared length, which is all we want in this case.

Here's a static/helper method:

float GetSquaredLength( const Vector3& inVect )
{
    return ( inVect.x * inVect.x
           + inVect.y * inVect.y
           + inVect.z * inVect.z );
}

Here's the method you might find in a Vector class:

inline float Vector3::SquaredLength() const
{
    return ( x*x + y*y + z*z );
}

So if we put this two the test, with two vectors, (2, 2, 2) and (2, 2, 3).

The squared length of (2, 2, 2) is ( 2² + 2² + 2² ), or 12.

The squared length of (2, 2, 3) is ( 2² + 2² + 3² ), or 17.

Based on the calculations we know that (2, 2, 2) is the shorter of the two vectors, which may have been obvious, but now we've seen the proof. The actual length of these vectors isn't needed to know which is shorter, but just for some more proof, to find the actual lengths now is very easy because we already have the squared length, so we can now just do the square-root calculation:

The length of (2, 2, 2) is √12, or 3.4641.
The length of (2, 2, 3) is √17, or 4.1231.

In the Optimizing Methods blog post I mentioned that sometimes is isn't the method itself that needs to be optimized, but rather that sometimes you can avoid needing the expensive methods together. Using squared lengths for distance comparisons is just one example of this.

Here's a helper function for returning the longest of two vectors:

Vector3 Vector3::GetLongest(const Vector3& first,
                            const Vector3& second) const
{
    if ( first.SquaredLength() > second.SquaredLength() )
        return first;

    return second;
}

Using Vector Mathematics, finding direction from one point to another

Finding the direction from one point to another is fairly easy, in order to do this you'll need to understand how to unitize vectors and how to do vector subtraction, please make sure you've read up about unitizing vectors from this blog post, and read up about vector subtraction from this blog post.

If you understand unitizing vectors and vector subtraction, then this will be incredibly simple.

Let's imagine our player is standing at position (10, 4, 7), and an enemy is standing at position (5, 9, -9), and we want to find the direction from the player to the enemy. To do this we first subtract the player's position from the enemy's position, and this gives us the vector from the player to the enemy.

(5 - 10, 9 - 4, -9 - 7) = (-5, 5, -16).

Now we simply unitize this vector and we have our direction.
Get the length of the vector √(-5 * -5 + 5 * 5 + -16 * -16) = √(25 + 25 + 256) = √306 = 17.4928556
Now using the inverse of length we can get unitize the vector:

Inverse length = 1 / 17.4928556, or 0.05711619.

Multiple inverse length by each element of our vector:
( -5 * 0.05711619, 5 * 0.05711619, -16 * 0.05711619 ) = ( -0.28583097, 0.28583097, 0.91385904 )


The code for this is very simple, we'll use the Unitize() method from our previous blog post, which is this:

inline void Vector3::Unitize()
{
    const float inverseLength = 1.0f / GetLength(); 
    x *= inverseLength;
    y *= inverseLength;
    z *= inverseLength;
}

Here's our simple function from getting the direction from the first point to the second:

Vector3 GetDirectionFromFirstToSecond( const Vector3& first,
                                       const Vector3& second )
{
    const Vector3 differenceVector = second - first;
    differenceVector.Unitize();
    return differenceVector;
}

Here's what the original sample vectors about would look like in code:

Vector3 playerPos = (10, 4, 7);
Vector3 enemyPos = (5, 9, -9);

Vector3 dirPlayerToEnemy = GetDirectionFromFirstToSecond( 
                                       playerPos, enemyPos );

// dirPlayerToEnemy is ( -0.28583097, 0.28583097, 0.91385904 )

Havok: Connecting your in-game camera to the Havok Visual Debugger

In projects using Havok, one thing that I've found invaluable is having the Havok Visual Debugger (HVD) visually match what you see in the game. Luckily, Havok provides a way for you to pass your camera's information to the HVD.

To send a camera's information to the HVD, you'll need the following:

• The position of the camera
• The forward/facing direction
• The up vector/axis
• The near and far plane distances
• The camera's FOV (field of view), in degrees (NOT radians)
• The name of the camera that you want to be seen and shown in the HVD.

Once you have all that information, you simply make the call to Havok's macro. I recommend creating an update function that you can call each frame when the camera updates, or when the renderer finally grabs the camera's information.

void UpdateVisualDebugger()
{
    Vector3 destination = m_position + m_forwardDir;

    HK_UPDATE_CAMERA( m_position, destination, m_upDir, m_nearPlaneDist, 
                      m_farPlaneDist, m_FOV, m_Name.c_str() );
}

Havok doesn't deal with STL types like strings, so you'll need to use .c_str() to send it the char pointer instead.

When you first connect the debugger to the game you will notice it isn't connected to the camera (this can be made to happen automatically, I may go over that in a future post). To connect to the camera, go to View->User Cameras->WhateverCameraNameYouChose.

If you're not properly or currently sending any camera information to Havok you may not see the 'User Cameras' option at all. Use a breakpoint to make sure you're hitting the macro during program execution.

If all worked well you should see your HVD window match your game's window. Please note that you can resize your HVD window and game window seperately, if you chose different aspect ratios for each window you will not get a perfect visual match between them, so try and keep them similar.

You'll also notice at the bottom of the HVD the name of the camera you're attached to. In my example above I've named my camera "Main Camera".

You may find that you're changing or creating cameras during the course of a game's execution, unfortunately Havok does not support automatically changing to new or different user cameras in the debugger when you change camera's from within game. I have put a support ticket in with them to consider including this in a future version. In the mean-time if you want this functionality you will need to have a user camera name that represents whatever camera happens to be active at the time. I recommend sending the active camera each frame under a generic name like "Active Camera" or "Main Camera", as well as the active camera by its unique name like "Character Camera". This will allow the developer to choose to always see the active camera from within Havok, or choose a unique camera and not have it switch automatically.

Havok: Setting mesh color in the Visual Debugger, Part 1

Anyone developing a game using Havok no doubt knows about the Havok visual debugger (which I'll refer to as the HVD), however if you're using the free SDK there is little provided information on how to send data to the visual debugger. Having worked with the full Havok source on a previous project I can provide what I hope to be some valuable insight on how to better utilize the HVD, which should help you debug your game easier.

Setting colors is the HVD is actually really simple, Havok provides a macro that does the work for you, you only have to pass a byte-packed unsigned 32-bit integer representing the color you want, and the pointer to the hkpCollidable. The format of your integer is 1 byte per channel, first byte is the alpha-channel, then red, blue, and green.

Here's a simple function that does the dirty work for you:

// Needed for calling color change macro
#include <common\visualize\hkdebugdisplay.h>

// You'll of course need any other headers for any other physics stuff 
// you're doing in your file

void SetColorForPhysicsDebugger( unsigned int Red, unsigned int Green,
                                 unsigned int Blue, unsigned int Alpha, 
                                 const hkpCollidable* pCollidable )
{
    // Havok takes an unsigned int (32-bit), allowing 8-bits for 
    // each channel (alpha, red, green, and blue, in that
    // order).

    // Because we only need 8-bits from each of the 32-bit ints 
    // passed into this function, we'll mask the first 24-bits.
    Red &= 0x000000FF;
    Green &= 0x000000FF;
    Blue &= 0x000000FF;
    Alpha &= 0x000000FF;

    // Now we pack the four channels into a single int
    const uint32_t color = (Alpha << 24) | (Red << 16) | (Green << 8) | Blue;

    // We use the macro provided by Havok
    HK_SET_OBJECT_COLOR( reinterpret_cast<hkulong>( pCollidable ), color );
}

In the image below you can see this in action. I have a running sample in which rigid bodies are red and opaque by default, whereas phantoms/triggers are blue and translucent.

Using colors for different categories of objects in your game can be extremely powerful. On one project I was on I created an entire custom interface and tool around filtering physics to show developers only what they were looking for, for example NPCs could collide with certain triggers that human players could not, so there was a filter for looking at the physics world from an NPCs point of view, while in the filter you could only see physics that the NPC could collide with.

This is part 1 of 2 of this series, part 2 shows you how to know when somebody connects to the HVD, because you'll need to resend all color information anytime someone connects.

Using Vector Mathematics, finding distance between points

Finding the distance between points is fairly simple, especially if you're familiar with the Pythagorean Theorem. The Pythagorean Theorem is the formula for finding the length of the hypotenuse of a triangle, which is essentially from finding the distance between two points in 2D space.

Pythagorean Theorem in its simplest form:
a² + b² = c²

If you've taken geometry then you likely know about a 3-4-5 triangle. Which is a commonly known fact that a right triangle can legally have sides with lengths of 3, 4, and 5. Using the Pythagorean Theorem we can prove this:
3² + 4² = 5², or 9 + 16 = 25, and √25 = 5.

So how is this related to finding the distance between two vectors? Let's think of the formula in a different way:
x² + y² = length², so with a 2D vector of (3, 4), that vector will have squared length of 25. Finding the length of the vector (3, 4) is the same as distance between (0, 0) and (3, 4), so you now essentially know how to find the distance between two points. If one of points is not (0, 0) you just use vector subtraction to get the difference between the two vectors, and get the length of that. For example, if we have two points, (1, 4) and (3, 5), the difference between them is ( 3-1, 5-4 ), which comes to (2, 1), and the length of (2, 1) is √(2² + 1²) or √5.


As you can see, finding the length of a 2D vector is essentially using the Pythagorean Theorem. A 3D version of this is just as you might imagine:
x² + y² + z² = length², which simplifies to √(x² + y² + z²)


So here's the function to get the length of a vector:

float GetLength( const Vector3& inVect )
{
    return sqrtf( inVect.x * inVect.x
                + inVect.y * inVect.y
                + inVect.z * inVect.z );
}

And you'll most likely want this function as part of the Vector class itself, here's a version for that:

inline float Vector3::Length() const
{
    return sqrtf( x*x + y*y + z*z );
}

And a nice helper function for finding the distance between two points, using the GetLength() function we already made above:

inline float DistanceBetweenTwoPoints( const Vector3& first, 
                                       const  Vector3& second )
{
    const  Vector3 differenceVector = second - first;
    return GetLength(differenceVector);
}

Using Vector Mathematics, Vector addition and subtraction

3D Math in games is largely based on Vector Mathematics. If you're unfamiliar with this term, please read up on 'Vectors' before continuing.

If you're programming in C++, do not confuse vectors used for 3D math with the vector container used in the standard template library (STL).

In this post we'll talk about 3D vectors, 2D vector math is pretty much identical, just lacking calculations done in one of the dimensions. If you understand 3D vectors then you'll have no trouble understanding 2D vectors.

Vectors are defined by three components: x, y, and z. These components usually define either a position, direction, or velocity along the x, y, and z axes.



Vector Addition and Subtraction
Adding and subtracting vectors is just simple arithmetic, you add or subtract each component of the two vectors.

For example, addition:
(0, 0, 0) + (3, 5, 7) = (3, 5, 7)

Code:

Vector3 first = Vector3(0, 0, 0);
Vector3 second = Vector3(3, 5, 7);

Vector3 result = Vector3(first.x + second.x,
                         first.y + second.y,
                         first.z + second.z);

// result.x is 3, result.y is 5, result.z is 7 

If you're using a pre-defined vector class, it will probably have an addition and subtraction operator. Here's what vector addition will generally look like:

Vector3 result = first + second;

subtraction:
(0, 0, 0) - (3, 5, 7) = (-3, -5, -7)

Code:

Vector3 first = Vector3(0, 0, 0);
Vector3 second = Vector3(3, 5, 7);

Vector3 result = Vector3(first.x - second.x,
                         first.y - second.y,
                         first.z - second.z);

// result.x is -3, result.y is -5, result.z is -7

Common uses of vector addition and subtraction

• Applying force to an object.

If you wanted to apply gravity to an object, for example, you would add gravity to an object's velocity each frame. You would want to take the elapsed frame's time into account as well.

void ProcessGravity( float elapsedTime )
{
    Vector3 myVelocity = (5, 0, 5);
    Vector3 gravity = (0, -9.8f, 0);

    gravity *= elapsedTime;

    myVelocity = myVelocity + gravity;
}

In the above method I've defined the variables for velocity and gravity, but generally this method would be part of the object, so velocity would be a member variable. Also, gravity would usually be passed into the method, not defined within it. Finally, the vector class will likely have a += operator. So the function would be look closer to this:

void MyClass::ApplyGravity( const Vector3& gravity, float elapsedTime )
{
    m_Velocity += (gravity * elapsedTime);
}

You may notice that gravity is being multiplied by a float. That operation is generally an overloaded operator that works like such:

gravity.x *= elapsedTime;
gravity.y *= elapsedTime;
gravity.z *= elapsedTime;

Optimizing methods, Unitizing vectors

Speeding up small but often used functions can have a big result if they're something you're doing many times each frame.

In this post we'll look at a very commonly used technique in 3D game programming, unitizing/normalizing of a 3D vector. Unitizing vectors is needed for all kinds of things like finding distances, angles between directions (dot product), A.I., rendering techniques, finding cross products.

void Vector3::Unitize()
{
    x /= GetLength();
    y /= GetLength();
    z /= GetLength();
}

The above version of Unitize() is easy readable, but about as far from optimized as you can get. The compiler may optimize this a bit for you, but lets do as much as we can ourselves to see what could be faster.

1.) We're calling GetLength()three times, we should call it once and use that result instead. Length is somewhat expensive because it requires using a square root calculation.

2.) Rather than dividing each component by 'length', we could multiply each component by 1.0f / length. Multiplications are almost always faster than division.

3.) Rather than multiplying each component by 1.0f / length we could store 1.0f / length in a variable and use that in place to save 2 extra division calculations.

4.) Declare our function inline, which helps the chances that the compiler will choose to inline the method in the final machine code, which saves a function call. Standard function calls have a small expense to them.

Let's see what we have ended up with:

inline void Vector3::Unitize()
{
    const float inverseLength = 1.0f / GetLength(); 
    x *= inverseLength;
    y *= inverseLength;
    z *= inverseLength;
}

Please note, premature optimization can be wasteful, I prefer to wait until my program is having performance issues, and then I profile to find out what is slow and then target that. Even if a profiler told you that your normalization function was taking up a lot of your program's time, you might find that the compiler has already optimized it to the level we see above. You might be better off finding ways to not call certain functions as often as you are, for example, to help improve performance, rather than optimize the functions themselves. Also, anytime you try and optimize something that is already working you have a chance of causing new bugs, or possibly making performance worse rather than better. But, knowledge is power, if you know an efficient way of doing something, and you know it works, then you might as well do it that way the first time.