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 :)

The plan for the game engine

My plan for the engine has always been to release it as open source. With the current release of beta version 3, my plan is becoming a reality. However, the engine is not ready to be released into the wild yet.

I believe half-baked Open Source projects should never be released. In my opinion, an Open Source project should be released when is stable, its basic features work, its documentation is complete and support channels are ready.

My game engine has the essential features to implement a game but still crashes in certain scenarios and lacks 1/3 of the documentation. On top of that, I don't have the time to provide technical support to users and collaborators.

Therefore, I will not release the game engine as an Open Source yet. Instead, I will use the game engine as an educational resource. I plan to teach Game Development in C++ using my game engine.

So, from today to the end of the year I will work on creating game development tutorials for you to learn.

Game Engine Beta v0.0.3

The last time I showed the progress of the engine was back in August where I showcased the first demo of the game engine. Since then I have been working on implementing new features and fixing several issues with the engine. Here is a video showing the progress of the engine:

In this beta version v0.0.3 of the engine, animations and collision detection can work simultaneously. The BHV algorithm was improved helping the engine make better decisions when pairing up 3D models for collision detection. The MVC (Model-View-Controller) flow of information was also improved.

Improvements

The beta version v0.0.3 of the engine can handle animations and collision simultaneously. The game engine can run an animation on a character and at the same time detect a collision. Furthermore, the engine allows a developer to apply action at any keyframe during the animation. For example, the engine allows you to apply an upward force during the second keyframe of an animation. You have direct control over the animation and which action to apply.

In this new version, I improved the flow of information between the Controller and the Model class. In previous versions, I had kept the flow of information in the MVC (Model-View-Controller) simplistic. In this new version, the model receives any actions on buttons and relays the information to the appropriate game character.

This version also improves the BVH algorithm. In the previous version, the BVH paired up incorrect models. This issue led several instances of missed collision detections. In this new version, all models are correctly paired up.

Issues

There is a major issue with the Convex Hull algorithm. For the most part, it works well with simple game characters. However, as soon as you model a character with complex modeling techniques, the algorithm fails. The problem is not a bug in the algorithm, but that it requires clean geometry to compute the hull.

It makes no sense to put a restriction on how to model a character. So, instead, I'm going to develop an external plugin to remove any restrictions. It will allow collision on any 3D character regardless of the modeling techniques used.

Thanks for reading.

How 3D animations work in a game engine? An overview

One of the hardest features to implement in a game engine is the animation of 3D characters. Unlike animation in 2D games, which consists of sprites played sequentially over a period, animation in 3D games consists of an armature influencing the vertices of a 3D model.

3D mesh and a bone armature

To animate a 3D model, the 3D model requires an armature. An armature is a set of 3D bones. Connecting the armature to the 3D model produces a parent to child linkage. In this instance, the armature is the parent, and the 3D model is the child.

Armature linked to the 3D mesh

Bones influence the space coordinates of nearby vertices. For example, rotating the forearm bone, transform the space coordinate of all forearm vertices in the 3D mesh. How much influence a bone has on a vertex is known as a Vertex Weight.

Rotating a bone affects nearby vertices

3D animations are composed of several keyframes. A keyframe stores the rotation and translation of every bone. As keyframes are played, the influence of bones on nearby vertices deforms the 3D model creating the illusion of an animation.

Animation with keyframes

The data stored in keyframes and vertex weights are exported to the game engine using a Digital Asset Exporter (DAE). When a game engine runs an animation, it sends keyframe data to the GPU.

As the GPU receives the keyframe data, the bone's vertex weight and bone's space deforms the 3D model recreating the animation.

Game engine running an animation

However, rendering only the keyframes received by the DAE may produce choppy animations. The game engine smoothes out the animation by interpolating the data in each keyframe. That is, it interpolates the bones' coordinate space between each keyframe.

Thus, even though a game artist may have produced only four keyframes, the game engine creates additional keyframes. So, instead of only sending four keyframes to the GPU, the game engine sends sixteen keyframes.

Hope this helps