Algorithms in Game Engine Development

For a game character to experience physics, a game engine needs to compute the equations of motion, collision, contact points, etc. There is a set of basic algorithms that aids a character experience such effects. For example, the Runge-Kutta Method computes the Equations of Motion using numerical integration methods. The Gilbert-Johnson-Keerthi (GJK) algorithm detects collision using the Minkowski Difference. The Sutherland-Hodgman algorithm identifies collision contact points by clipping a polygon.

Numerical Integration Methods

Calculating the equations of motion allows a character to fall as if gravity was acting on the object. The Equations of Motion are Newton's Second Law:

and Rotational Force:

A game engine integrates the Equations of Motion to obtain the velocity and displacement of a character. The engine does this operation in a continuous loop which consists of the following steps:

1. Identify all forces and moments acting on the object.
2. Take the vector sum of all forces and moments.
3. Solve the equation of motion for linear and angular acceleration.
4. Integrate the acceleration with respect to time to find the linear and angular velocity.
5. Integrate the velocity with respect to time to find the linear and angular displacement.

If a character experiences gravitational and torque forces, the continuous loop creates the illusion that an object falls and rotates.

The problem is the Integration of the acceleration and velocity. Computers can only approximate the value of an integral by using Numerical Integration techniques.

There are three numerical integration methods used in game engine development. They are:

• Euler Method
• Verlet Method
• Runge-Kutta Method

The Euler's Method calculates the velocity at a time interval and predicts the next velocity at t+∆t. The method is simple to implement yet it is the least accurate.The illustration below shows the shortcoming of this approach. You can argue that making ∆t smaller, the closer you'll get to the exact solution. However, there is a practical limit as to how small a time step you can take.

The Runge-Kutta Method is a numerical integration technique which provides a better approximation to the equation of motion. Unlike the Euler's Method, which calculates one slope at an interval, the Runge-Kutta calculates four different slopes and uses them as weighted averages.

These slopes are commonly referred as k1, k2, k3 and k4, and an engine needs to compute them at every time step.

The Runga-Kutta uses these slopes as weighted average to better approximate the actual slope, velocity, of the object. The position of the object is then calculated using this new slope.

Collision Detection

Detecting collisions has trade-offs. A simple collision detection system is fast but unprecise. Whereas, a complex collision detection system is precise but very computationally expensive.

During collision detection, an engine bounds a game character with a geometrical volume. This volume is known as a Boundary Volume. And the most common are:

• Sphere
• OBB
• AABB
• Convex Hull

A collision detection system works by detecting if boundary volumes are intersecting. A system that uses Spherical Boundary Volumes are fast but returns many false detections.

Back in the 1980s, I'm sure a detection system using spherical boundary volumes was acceptable, but nowadays, gamers may not be so happy with many false detections.

A more precise detection system uses Convex Hulls as boundary volumes.

The intersection between Convex Hulls is computed using the Gilbert-Johnson-Keerthi (GJK) algorithm. Surprisingly, the mathematics behind this algorithm is quite simple. The algorithm determines if the volumes have intersected if their Minkowski Difference contains the origin point. The image below illustrates two convex hulls intersecting (left). Since the Minkowski Difference (right) includes the origin point, the algorithm reports the intersection.

Even though the mathematics behind the GJK algorithm is simple, it is very computationally expensive.

A collision system circumvents calling the GJK algorithm for every possible collision through a Two-Phase Detection System. These phases are known as Broad-Phase and Narrow Phase detection.

A Broad Phase detection system detects collision using spherical boundary volumes. This phase is fast and reports any possible collision to the Narrow Phase. The Narrow Phase tests the reported collision, but it uses the more expensive and precise GJK algorithm.

To further minimize calls to the GJK algorithm, a game engine parses the space of game characters and creates a tree-like structure known as a Boundary Volume Hierarchy (BVH).

The BVH algorithm parses the position of every object and assigns them to a particular node in the binary tree. The algorithm recursively analyzes each node until each node contains two characters most likely to collide.

Collision Response

A collision detection system reports if a collision has occurred. Unfortunately, it does not report the Contact-Manifold (contact points) of the collision. The contact-manifold are essential to determine the Collision Response (impulse and resulting velocities) of collided characters.

A game engine uses the Sutherland-Hodgman Algorithm to compute the contact manifolds of two colliding characters. The algorithm starts off by identifying a Reference and an Incident polygon.

The segments of the reference polygon serve as Reference Planes for the algorithm.

Once a reference polygon is identified, the algorithm tests each vertex of the incident polygon against each reference plane by using a Clipping rule.

Upon termination, the algorithm generates a new polygon whose vertices are the contact points (Contact Manifold) of two collided polygons.

Visualizing Game Engine Algorithms

Now that you know these game engine algorithms, you may want to know how to implement them. Several books go straight into the implementations of these algorithms without giving you a visual depiction of how they work. I think that if you can see a visual representation of an algorithm, you can implement them easier and faster. Thus, I wrote several posts where I provide a visual explanation for each algorithm. I hope they are helpful:

• Visualizing the Runge-Kutta Method
• Visualizing the GJK Algorithm
• Visualizing the BVH Algorithm
• Visualizing the Sutherland-Hodgman Algorithm

Enjoy.

PS. Sign up to my newsletter and get Game Engine development tips.

Game Engine Second Game Demo

To showcase the changes made in beta version v0.0.3, I decided to make a simple shooting game. Initially, the game was going to be a battle between tanks (see screenshots below). However, as I modeled the 3D game assets, it occurred to me to add an airplane and an anti-aircraft gun.

The final game demo ended up being a battle between the tank, aircraft and the anti-aircraft . Below is a video showcasing the game.

The game demo makes use of the camera rotation. The camera follows the anti-aircraft view direction, thus creating the illusion that the player is controlling the anti-aircraft gun.

The demo also makes use of the collision-detection system and scenegraph. The tank, airplane and anti-aircraft are composed of children game objects. For example, the tank is made of the tank head and the tank base. When a bullet hits the tank, the engine detects the collision. The game disassociates the tank children thus causing the tank head to move up. The same idea is implemented for the airplane.

So what is next?

I found several issues with the engine. The main issue is an occasional crash of the engine during gameplay. It seems to happen in the OpenGL Manager. I will also add several features to the engine such as graphical effects showing an explosion.

Hope to showcase these changes next year :)

Understanding Encapsulation in C++

To understand what encapsulation is, I will start off with a brief explanation of setters/getters and class behavior.

Setters/Getters

C++ is an Object-Oriented Programming (OOP) language. One of the principles of OOP is to encapsulate data members as private members and access them through a public access interface.

Let's take for example the class shown below:

class Person{

private:

    int age; //1. Age is a private data member

public:

    Person();

    ~Person();

    void setAge(int uAge); //2. Sets the value of the age member

    int getAge(); //3. Gets the value of the age member

};

The data member 'age' is a private data member (line 1). The value of this data member is accessed either through the method 'setAge' or 'getAge.' The method 'setAge' sets the value of 'age' (line 2). The method 'getAge' retrieves the value of 'age' (line 3).

In Object-Oriented Programming languages, a method that sets the value of a private data member is known as a 'setter.' In contrast, a method that retrieves the value of a data member is known as a 'getter.' Therefore, the 'setAge' method is referred as a setter. Whereas, the 'getAge' method is referred as a getter.

Class Behavior

In a program, a Class represents a real-world object or entity. A class has data members and methods that account for the behavior of the object.

A class behavior is a common action performed by the object. For example, an artist has a set of common behaviors; before painting a masterpiece, an artist prepares the easel, cleans the brushes and starts painting.

A program can represent an artist behaviors or actions through a Class' method. The snippet below illustrates the behaviors of an artist object in C++. See lines 1, 2 & 3.

class Artist{

private:

public:

    Artist();
    ~Artist();

    void prepareEasel(); //1. Prepares the easel

    void cleanBrushes(); //2. Cleans the brushes

    void paint(); //3. Artist's paint style  
};

Encapsulation

Encapsulation is the act of making data members private and accessing them using a public interface; through setters and getters methods.

Object-Oriented Programming principles suggest always to encapsulate data members. However, data members are not the only entities that should be encapsulated. A Class behavior should also be encapsulated; in particular, behaviors of a class that varies.

Let's analyze the Artist class shown above. The class contains these actions:

• Prepares Easel
• Cleans Brushes
• Paints

Of these behaviors, painting differs among painters. For example, an artist's could paint in a modern, impressionist or abstract style. The other two actions do not change among painters. Every artist prepares an easel and cleans a brush the same way.

Therefore, we should encapsulate the 'paint' behavior since it varies from object to object.

In C++, abstract classes are used to encapsulate behaviors. The snippet below shows an abstract class, 'PaintStyle,' that encapsulates the 'paint' behavior (see line 1).

class PaintStyle{

public:

    virtual void paint()=0;  //1. Paint virtual method

    virtual ~PaintStyle(){}; //2. Virtual destructor
};

To make use of the abstract class, you need to create a subclass. The snippet below shows a subclass of 'PaintStyle.' Notice that its 'paint' behavior prints "I paint in a modern style" (line 4).

class ModernPaintStyle:public PaintStyle{

private:

public:

    ModernPaintStyle(); //1. Constructor

    ~ModernPaintStyle(); //2. Destructor

    void paint(); //3. Paint method

};

ModernPaintStyle::ModernPaintStyle(){}

ModernPaintStyle::~ModernPaintStyle(){}

void ModernPaintStyle::paint(){

    std::cout<<"I paint in a modern style"<<std::endl; //4. Prints "I paint in modern style"

}

Let's create a second subclass of 'PaintStyle.' But this time set the behavior to print "I paint in an impressionist style" (line 4).

class ImpressionistPaintStyle:public PaintStyle{

private:

public:

    ImpressionistPaintStyle(); //1. Constructor

    ~ImpressionistPaintStyle(); //2. Destructor

    void paint(); //3. Paint method

};

ImpressionistPaintStyle::ImpressionistPaintStyle(){}

ImpressionistPaintStyle::~ImpressionistPaintStyle(){}

void ImpressionistPaintStyle::paint(){

    std::cout<<"I paint in an Impressionist style"<<std::endl; //4. Prints "I paint in an Impressionist style"

}

Let's go back to the Artist class and apply the changes shown below.

The snippet shows a pointer member of type 'PaintStyle' (line 1). Line 4 illustrates the addition of the method 'setPaintStyle.' This method along with the modification of the 'paint' method (line 5) injects polymorphism into the class. That is, the Artist class can change behaviors during runtime (See lines 6 &7).

class Artist{

private:

    PaintStyle *artistStyle; //1. Pointer member to 'PaintStyle'

public:

    Artist();
    ~Artist();

    void prepareEasel(); //2. Prepares the easel

    void cleanBrushes(); //3. Cleans the brushes

    void setPaintStyle(PaintStyle *uStyle); //4. Sets the paint style

    void paint(); //5. Artist's paint style

};

Artist::Artist(){}

Artist::~Artist(){}

void Artist::setPaintStyle(PaintStyle *uStyle){

    artistStyle=uStyle; //6. Sets the style of the painter
}

void Artist::paint(){

    artistStyle->paint(); //7. Calls the paint method of the subclass

}

Polymorphism permits the artist class to paint in a modern style. The next minute it can behave like an artist that paints in an impressionist style.

The snippet below showcase these properties.

int main(){

    Artist *picasso=new Artist(); //1. Create an instance of an artist

    PaintStyle *modernStyle=new ModernPaintStyle(); //2. Create an instance of a modern painter style

    PaintStyle *impressionistStyle=new ImpressionistPaintStyle(); //3. Create an instance of an impressionist painter style

    picasso->setPaintStyle(modernStyle); //4. sets the painter style to a modern style

    picasso->paint(); //5. Calls paint method. It prints "I paint in a modern style"

    picasso->setPaintStyle(impressionistStyle); //6. Change the painter style to an impressionist style

    picasso->paint(); //7. Calls the paint method. It prints "I paint in an impressionist style"

    return 0;

}

Line 1 creates an instance of an artist object. Lines 2 & 3 creates instances of different paint styles. The painter style is set in line 4, and when the method 'paint' is executed, it prints "I paint in a modern style" (line 5).

Because of polymorphism and encapsulation, the behavior of the class can change with a simple method call as shown in line 6. When the 'paint' method is called again, it prints "I paint in an impressionist style" (line 7).

Polymorphism and encapsulation give flexibility and modularity to an application. And it enables a program to be extended and modified with few changes. For example, years from now, a new paint style can be added without ever touching the Artist class.

Hope this helps.

Understanding Polymorphism in C++

Polymorphism gives flexibility to a program. To understand how polymorphism provides flexibility to your program, let's start off with a brief introduction to Abstract Classes.

An abstract class is a class that acts as a legal contract. The legal contract states that if you are a subclass of an abstract class, you must implement every method of the abstract class.

An abstract class has the following properties:

1. It does not have a constructor method.
2. Its destructor must be declared as a virtual method.
3. Since it does not have a constructor, you can't create instances of an abstract class.
4. Methods in an abstract class must contain the keyword 'virtual' in their declaration
5. Methods in a virtual class are always set to '0.'

The snippet below declares an abstract class called "Dog."

class Dog{

private:

public:

    virtual void run()=0; //1. Virtual Run method

    virtual ~Dog(){}; //2. Virtual destructor

};

Line 1 declares the virtual 'run' method. Line 2 declares the class virtual destructor. Notice that these methods are declared within the public interface. A different name for an abstract class is an Interface.

Since an instance of an abstract class is not possible, an abstract class requires subclasses to be useful. As stated earlier, the subclass must implement every method of the abstract class.

The snippet below declares the subclass 'Beagle.' The implementation of the 'run' method is shown in line 5.

class Beagle:public Dog{

private:

public:
    Beagle(); //1. Constructor

    ~Beagle(); //2. Destructor

    void run(); //3. Implement the run method

};

Beagle::Beagle(){}

Beagle::~Beagle(){}

void Beagle::run(){

    std::cout<<"I run like a beagle"<<std::endl; //5. Print "I run like a beagle"

}

In practice, you would create an instance of the 'Beagle' subclass as shown in the snippet below:

int main(){

    Beagle *myBeagle=new Beagle(); //1. Creating an instance of the subclass

    return 0;
}

However, you shouldn't create the instance as shown above. Instead, you should create the instance as shown below:

int main(){

    Dog *myBeagle=new Beagle(); //1. Code to the interface, not the implementation

    return 0;
}

Notice that myBeagle points to the abstract class type. It does not point to the subclass type. This approach is known as "Code to the interface, not to the implementation" and is one of the 7 Principles of Object-Oriented Programming. In the statement above, "Interface" refers to an Abstract Class. "Implementation" refers to a Subclass.

"Code to the interface, not to the implementation" injects polymorphism into your project, thus making it flexible.

To see polymorphism in action, let's create a subclass call 'Pitbull' as shown below:

class Pitbull:public Dog{

private:

public:
    Pitbull(); //1. Constructor

    ~Pitbull(); //2. Destructor

    void run(); //3. Implement the run method

};

Pitbull::Pitbull(){}

Pitbull::~Pitbull(){}

void Pitbull::run(){

    std::cout<<"I run like a pitbull"<<std::endl; //5. Print "I run like a pitbull"

}

As required, the subclass implemented the 'run' method (line 5).

Let's create a function called 'youRunLike' as shown below. Notice the argument of the function is of type 'Dog,' the abstract class.

void getRunSpeed(Dog *uDog); //1. Function declaration

void getRunSpeed(Dog *uDog){ //2. Function definition

    uDog->run(); //3. Call the run method

}

Notice the call to the 'run' method of the 'Dog' class (line 3). This is a bit weird. The abstract class never implemented this method, only its subclasses have. How does it know which subclass to call?

Polymorphism allows the function to use the same argument for either subclass type, 'Beagle' or 'Pitbull' and it will direct the call to the correct 'run' method. You do not need to create different functions with different argument types.

For example, in the snippet below, lines 1 & 2 creates the instances of the subclasses using the "Code to the interface, not to the implementation" approach. Lines 3 & 4 calls the function 'youRunLike.'

int main(){

    Dog *myBeagle=new Beagle(); //1. Instance of Beagle

    Dog *myPitbull=new Pitbull; //2. Instance of Pitbull

    getRunSpeed(myBeagle); //3. Call the function-It prints "I run like a beagle"

    getRunSpeed(myPitbull); //4. Call the function- It prints "I run like a pitbull"

    return 0;
}

When you execute the snippet above, line 3 will print 'I run like a beagle.' Whereas, line 4 will print 'I run like a Pitbull.' As expected, the correct 'run' method for each subclass was evoked.

Polymorphism gives flexibility and modularity to an application. If 100 years from now, a new subclass is defined, it will be able to use the same 'youRunLike' function without any modifications.

Hope this helps

Understanding Inheritance in C++

Inheritance is when one class inherits the behaviors of a parent class. That is, a class can inherit the data members and methods of a parent class.

For example, the snippet below shows a class of type Dog with two methods: bark and run.

class Dog{

private:

public:
    Dog();    //1. Constructor
    ~Dog();  //2. Desctuctor

    void bark(); //3. Bark method
    void run(); //4. Run method

};

Dog::Dog(){

    std::cout<<"Dog creat"<<std::endl;
}

Dog::~Dog(){}

void Dog::bark(){

    std::cout<<"I bark"<<std::endl; //5. Print "I bark"
}

void Dog::run(){

    std::cout<<"I run"<<std::endl; //6. Print "I run"

}

These methods have a particular behavior. The bark method prints "I bark" (line 5). The run method prints "I run" (line 6).

Just like a child inherits the traits of his father, a child class can inherit the traits of a parent class. In C++, a subclass refers to a child class. A super class refers to a parent class.

Inheritance in C++ requires the following syntax:

class subclass_type::public superclass_type{};

For instance, the snippet below declares the Beagle class a subclass of the Dog class:

class Beagle:public Dog{

private:

public:
    Beagle(); //1. Constructor
    ~Beagle(); //2. Destructor

};

Beagle::Beagle(){}

Beagle::~Beagle(){}

Notice a crucial point. The Beagle class does not need to declare nor define the bark and run methods. However, it can use them.

For example, the snippet below creates an instance of a Beagle class and access the bark and run methods. See lines 2 & 3.

int main(){

    Beagle beagle; //1. Create an instance of the class

    beagle.bark(); //2. Access the bark method
    beagle.run(); //3. Access the run method

    return 0;
}

When you execute the snippet above, the program will print "I bark" and "I run."

Overwriting a Method

Not every dog barks nor runs the same. These behaviors among dogs are different. This fact implies that we need to modify the behaviors of the Beagle class. C++ allows a subclass to change its behaviors by overwriting a method.

To overwrite a method, you need to declare and define the method you want to modify. In the example below, the bark and run methods have been modified to print: "I bark like a Beagle" and "I run like a Beagle." See lines 5 and 6.

class Beagle:public Dog{

private:

public:
    Beagle(); //1. Constructor
    ~Beagle(); //2. Destructor

    void bark(); //3. Overwrite the bark method

    void run(); //4. Overwrite the run method

};

Beagle::Beagle(){

    std::cout<<"Beagle creat"<<std::endl;

}

Beagle::~Beagle(){}

void Beagle::bark(){

    std::cout<<"I bark like a beagle"<<std::endl; //5. Print "I bark like a beagle"

}

void Beagle::run(){

    std::cout<<"I run like a beagle"<<std::endl; //6. Print "I run like a beagle"

}

When you execute the snippet below, the bark and run methods will print: "I bark like a beagle" and "I run like a beagle."

int main(){

    Beagle beagle; //1. Create an instance of the class

    beagle.bark(); //2. Access the bark method- It prints "I bark like a beagle"
    beagle.run(); //3. Access the run method- It print "I run like a beagle"

    return 0;
}

Before I conclude this lesson, I want to state a crucial point of inheritance in C++. When you create an instance of a class, C++ calls the class constructor. However, when you create an instance of a subclass, C++ calls the superclass constructor and the subclass constructor. C++ calls the superclass constructor before calling the subclass constructor.

Hope this helps