Jump to content

  • Log In with Google      Sign In   
  • Create Account

Splinter of Chaos' Blog



Make a mathematical vector class already!

Posted by , 22 August 2011 - - - - - - · 904 views

I can't count the number of times i've gone on to a forum and seen code like this: (Using a modified example from gafferongames.com)


posX = posX + velX * dt;
posY = posY + velY * dt;

velX = velX + (forceX/mass) * dt;
velY = velY + (forceY/mass) * dt;
I'm going to use this space to explain why such code is bad, especially in more complicated examples, and how simple it is to make it better. First, i think it would be clearest if i simply showed how this looks if posX and posY are represented by a vector, pos, and do they same for vel and force.

pos = pos + vel * dt;
vel = vel + (force/mass) * dt;
Obviously, this is simpler, cleaner, and more readable.


Why this code is bad.



You have to write twice as many lines of code than necessary, for 2D, and three times for 3D. Even using vectors, a complex physics equation, for example, might take 5 lines, which means 15 lines using 3D math without vectors. You have to make redundantly names variables (posX, posY; redundancy highlighted). It's harder for people to read your code, and for you to maintain it since the lines have to do the exact same thing.


Vectors basically take multidimensional equations and lets you evaluate them on one dimension.


What is a vector?


A vector is simply a piece of data representing both a direction and magnitude (or length). The most obvious way to represent that is through a polar vector. While out of the scope of this log, a polar vector is one around a pole, simple enough, with a distance from the center and an angle from an arbitrary axis.

A vector used more often in games is simply represented by an (using a 2D example) x and y like so: <x,y>. We can find the magnitude with sqrt( x*x + y*y ) (Pythagorean Theorem) and the direction from the x-axis by using atan2( y, x ). Even though it contains neither a magnitude or direction, directly, we can derive those values from x and y and thus they make a vector.

For an example of a vector: say you had a screen object at (1,1). That's the position vector, s, <1,1>. If next from you want it to move one unit left, that means its velocity vector, v, is <1,0>, 1 for one unit left and 0 for no movement in the y direction. s + v = the position next frame. s + v = <1,1> + <1,0> = <1+1,1+0> = <2,1>. If a = <x,y> and b = <q,w>, a + b = <x+q,y+w>,


Vectors are incredibly easy to write! (Without a lot of knowledge about math.)


The simplest vector implementation, in c++, is this:


struct Vector {
    float x, y;
};
With this, posX and posY become pos, but would not make the above example any prettier. What it does do is simplifies writing a class. One with a position and velocity should have two members (pos, vel), not four (posX, posY, velX, velY). To really see any gains, we need to start adding functions that do common calculations on vectors. For example, adding to vectors:
Vector add( Vector a, Vector b ) {
    return { a.x + b.x, a.y + b.y };
}

// ...

Vector velDt = { vel.x * dt, vel.y * dt };
pos = add( pos, velDt );
Although the intent of this code is not quite as clear as a simple "pos = pos + vel*dt", it still looks better than seeing two lines of "x = x + velX*dt". Many languages do not allow what's called operator overloading, but c++ does and we can simplify the code further by adding two functions:

Vector operator + ( Vector a, Vector b ) {
    return { a.x + b.x, a.y + b.y };
}

Vector operator * ( Vector a, float b ) {
    return { a.x * b, a.y * b };
}

// ...

pos = pos + vel * dt;


Useful Functions




Aside the already mentioned ones, you should be equipped with at least a dot and cross product, a function to find a vector's length. When you begin to look up vector equations, these functions will come up a lot. To learn their meanings and uses is outside the scope of this, but: A dot product is the sum of two vectors with their like components multiplied and returns a scaler (non-vector) value: <a,b> * <x,y> = a*x + b*y. A cross product is used to find a vector tangent to both a and b.

//Using a 3D Vector class:
int operator * ( Vector a, Vector b )
{
    return a.x*b.x + a.y*b.y + a.z*b.z;
}

// Crosses only make sense with 3D vectors.
Vector cross( Vector a, Vector b )
{
    Vector c;
    c.x = a.y*b.z - a.z*b.y;
    c.y = a.z*b.x - a.x*b.z;
    c.z = a.x*b.y - a.y*b.x;
    return c;
}

// The square of a vector, v*v, is the dot product of itself.
Vector square( Vector v )
{
    return v * v;
}

// This can also be named "length" or "size".
Vector magnitude( Vector v )
{
    // Pythorous' theorem states the answer is sqrt( v.x*v.x + v.y*v.y + v.z*v.z ).
    // Notice that v*v = v.x*v.x + v.y*v.y ... so the above is equal to sqrt( v*v ).
    return std::sqrt( v*v );
}
<br class="Apple-interchange-newline">// Another name for sqrt(v*v). Often written ||v||.
// Note that |-5| = sqrt((-5)*(-5)) = sqrt(25) = 5.
Vector abs( Vector v )
{
    return magnitude( v );
}


Going Further



A vector class can be built to hold ints or floats, but sometimes one is more convenient than another for different situations. That means either you can write a vector for each type or make it templated. You might want a 2D vector for a 2D game, or a 3D vector for a 3D game. Again, you can make a different class for both, but doing that and one for int and float means four classes! Of course, for most situations, you only need a 3D class and just set z to zero if you're making a 2D game, but what if you wanted to make a 4D vector, the fourth dimension perhaps being time?

So, if you really need a robust vector class it needs to be templated by size, and type is convenient.

template< int Size, typedef T >
struct Vector
{
    // Provide typedefs to be able to reference the types this class uses, externally.
    typedef T value_type;

    // Do the same for the size.
    // static_size is barrowed from std::array.
    enum { static_size = Size }

    // Since the number of dimensions are variable, we must hold an array instead of individual members.
    value_type dims[ static_size ];

    // Overload [] so that dims can be accessed more conveniently.

    T&   	operator [] ( int i )   	{ return *(data + i); } 
    const T& operator [] ( int i ) const { return *(data + i); } 
};
Now, defining the operators on this class can be a little difficult. At times, i've written the operators as normal, templated, free function, but depending on the calling code, thanks to standard C++ function lookup rules, you'll get a weird error. Take this example, using the above class.

template< class T, int X >
Vector<T,X> operator * ( Vector<T,X> v, T a )
{
    Vector<T,X> vec = v;
    
    for( int i=0; i < X; i++ )
        vec[i] *= a;
}

int main()
{
    Vector<int,2> v; v[0] = 1; v[1] = 1;
    Vector<int,2> x = v * 5.4;
}
The error received on g++, version 4.2, is "error: no match for ‘operator*’ in ‘v * 5.4000...0625e+0’". It doesn't know to convert 5.4 to an int to match the function signature. When a conversion is required, neither the left nor right operator takes precedence. We can see that the float should be converted to a float, but the compiler doesn't know it shouldn't convert the vector to a Vector<double,2>!

We could rewrite it to let the second argument be a different type, but we don't want that. In the + operation, a conversion has to take place whether vec[i] needs conversion to a float, then to be converted back to an int for storage, or a has to convert to an int. It just makes sense that the conversion should happen when the function calls.

I wish i could give a link that explains this problem better, or that explains why the solution i'm about to give works, but i don't. What needs to happen is the operator needs to be defined outside the class, but as a friend of it, defined inline. Again, this has to do with lookup rules.

The class must be defined like this:

template< class T, int X >
struct Vector
{
    T data[X];

    T* begin() { return data;   }
    T* end()   { return data+X; }

    T&    operator [] ( int i )      { return *(data + i); }
    const T& operator [] ( int i ) const { return *(data + i); }

    template< class T, int X >
    friend Vector<T,X> operator * ( Vector<T,X> v, T a )
    {   	
        Vector<T,X> vec = v;
 
        for( int i=0; i < X; i++ )
            vec[i] *= a;    
    }   	

    // More operators...
};

This is how i wrote my own class for my game. The code can be found at https://github.com/splinterofchaos/Orthello/blob/master/Vector.h


Chaos Attractors, current progress.

Posted by , 11 February 2011 - - - - - - · 376 views

Chaos Attractors is nearly finished, now, or at least it seems. I figure i could work on it my entire life and i might not consider it done. It's been seven months already.

Chaos Attractors is a simple game; it's my first game. You play a circle in the middle of the screen, moving around with the arrow keys or WASD. Enemies spawn at ever-increasing intervals and are pulled in by your gravitational force. When they collide with you, you die, if they hit each other, they die. More recently, i added "chaos mode". Here, everything, not just the player, has a gravitational pull.

This is not exactly the first of its kind. Not even by me! I made it first using DigiPen's Project Fun during a two week workshop. DigiPen owns that version, so i then took a C++ class at a community college and made the game again. Then my hard drive crashed and i lost that version too. Finally, i played this and knew that my game was better, so i remade it a third time and that's my current project.

A few people have commented they made a similar game. I know the core mechanic is not unique, though i wish it was. What i believe is unique is my design of the enemies. I have blue orbitals which accelerates towards its target based on some constant over the distance to the player. Stoppers are the next enemy; they're like orbitals, but larger, slower, and when they're hit, they stop. If hit again, it'll start moving again. The only way to kill a stopper is if the player runs into it while it's stopped. Then are the twisters. They are the only enemy to use the actual gravitational equation: some constant over the distance squared. I called them twisters because they're drawn as an oval that rotates based on its trajectory's curvature (k from calculus).

The rest of the enemies are only available in chaos mode, where everything attracts everything else. The first is negative. I called it that because it has a negative mass, causing other enemies to be repelled, while it is attracted towards them. I debate calling it hunter because as its victim is pushed away, it pursues. Finally, you have the greedy. Actually, that's a terrible name, but i can't think of a better one. It is only attracted to the player, despite being in chaos mode. This adds some occasionally interesting dynamics.

I guess that's all i have to say about it right now.

The source code repository.


The latest release as of this post.





August 2016 »

S M T W T F S
 123456
78910111213
14151617181920
212223 24 252627
28293031   


PARTNERS