Introduction

When you study about game programming, there's only one topic you cannot run from: MATHEMATICS.

Math is used to balance characters attributes in game design, when programming game logic and physics, and even when modeling meshes and selecting its colors. A good understanding of mathematics is need in all aspects of life, and game development is no exception to this rule.

In this series, we'll discuss about math and some of it's optimizations needed for performance or only for best practices.

In this first article, we won't discuss about magic math and exoteric optimizations that can only be deducted by Ph.D mathematician. The optimizations presented here are very simple, and can be used in 90% of the cases.

Table of contents

This tutorial is separated in 3 posts:

1. Operations (this page)
2. Algorithm optimization
3. Hardware optimization

Why understand/optimize calculations?

Let's use a well known example: the game loop.

For a game developed in 21st century, every second the game is updated 60 times. For each execution, the (minimum) updates are:

• For each object (a game can have thousands)
  • For each vertex (a character can have thousands)
    • 3 float numbers for position
    • 3 float numbers for rotation
    • 16 floats for each animated bone (a character can have dozens)
• For each particle system
  • For each particle (a system can have thousands)
    • 3 floats for position
    • 4 floats per color

I think you can understand or at least imagine the magnitude of this example. If a developer can optimize, simplify or eliminate some calculations, this can mean a FPS increase, less battery consumption, or even a less expensive hardware needed to play.

The Math Operations

The first step to optimizations is to known and understand each type of operation, as presented below with its operators (the first is faster):

Formulas and equations uses many of this basic operations. Knowing the operations and its relations, we can replace some operations to faster ones.

Multiplication

Let's start with multiplication, which is a very fast operation, but can be optimized in a specific situation, that is when multiplying a number by even numbers (multiples of 2). The operation

143 * 2

can be replaced by

143 << 1

Both operations yield the same result, but the second is faster by a level of magnitude, with a minor limitation.

But wait, why we are shifting the number by 1 instead of 2? It's because the bit shift works in binary, so we shift by the expoent of 2 (2¹ = 2).

In the same way, multiplying by 4 is the same of

143 << 2

because 2² = 4. This will became easier the more we work with bit operations.

Division

Let's move to division. We use division to calculate average, speed, get half of a number, and so on. As the multiplication's inverse operation, it can uses the same bit shift optimization, also only with even numbers. The operation

143 / 2

can be replaced by

143 >> 1

Also both operations yield the same result, but as the division is much slower than multiplication, is improvement is even greater.

But there's another possible optimization that can be used if the divisor is not even. You can multiply the number by the inverse of the second number, as follows:

143 * 0.2

Multiply by 0.2 is the same of divide by 5 (odd number), but the difference in performance is significant. Of course, this optimization makes sense only if this factor is pre-calculated or used as a constant.

Exponentiation

Now things start to get complicated, because this algorithm should consider the expoent value. Internally, exponentiation are implemented using other operations or a combination of loops with multiple multiplications.

But, in most of the cases, we only use exponentiation by square (or 2), so we can simply replace

132²

by

132 x 132

Root Extraction

Root extraction is the operation to calculate a number x in

ⁿ√z = x

... that is the inverse of

xⁿ = z

The most common root extraction is square root, when

²√z = x

In game development, this is most used when calculating distance between two points, using the formula

dist = ²√((x₁ - x₀)² + (y₁ - y₀)² + (z₁ - z₀)²)

As this formula is used a lot, it's implemented in many libraries and engines, like Distance in Unreal Engine 4

...and Vector3.Distance in Unity3D

float dist = Vector3.Distance(other.position, transform.position);

To simply square root calculation, it's currently used math approximations deducted from linear algebra. There's a good video from John Carmack explaining the development needed for Quake III to be became basically playable. The limitation is that this can only be implemented in C/C++:

But for simplification, when can think about the logic flow and check IF we should use an operation with square root. Let's imagine two objects on scene (like enemies), and we need to select which object is closer from the player.

If we only need to know which object is closer, the calculated value is not really important, but the difference between the two distances is. So, we can calculate the distance values without using the square root.

Fortunately, the engine developers already thought about this, and we can use DistanceSquared in Unreal Engine

...but Unity3d don't have such call, so we should use a combination of vector subtraction and the sqrtMagniture from the resulting vector

float dist = (other.position - transform.position).sqrtMagnitude;

There's another simple way to NOT use square root. Let's say we should check if the player is inside an circular area.

The basic way to check this is calculating the distance from the player from the circle's center, then compare if this distance is less or equals the circle's radius (r)

²√((x₁ - x₀)² + (y₁ - y₀)² + (z₁ - z₀)²) <= r
v

Mathematically, we can move the square root to the other side of the inequality becaming an exponentiation, and the comparison yields the same result.

(x₁ - x₀)² + (y₁ - y₀)² + (z₁ - z₀)² <= r²

And, as proposed before, the exponentiation can be replaced by multiplication:

(x₁ - x₀)² + (y₁ - y₀)² + (z₁ - z₀)² <= r * r

The more you use these optimizations, more natural it will be to detect and apply in your code.

Caching

“The fastest code is the code which does not run. The code easiest to maintain is the code that was never written.”

Robert Galanakis

The last optimization proposed is the second fastest one: pre-calculate and cache values.

Every calculation done more than one time with same values is a candidate to be pre-calculated and stored. Obviously, the prefered are the ones from longest equations and slower calculations, like square roots and others.

The scope is also important:

• if a calculation is executed more than once inside a function, store it in a local variable;
• if a calculation is executed more than once (maybe more) inside an object, store it in a instance variable;

A newbie developer could ask:

"why not always use a instance variable or a global variable always?"

The short answer is: the closer the constant is to the code, faster is to be accessed. This point will be clarified when we talk about hardware optimizations.

Conclusion

Some optimizations may look strange or over complicated at first. But the more you use them, the faster you'll recognize the situations and use the optimizations instead of the conventional calculations. You code will be faster or capable to execute more calculations, to enable more objects and your game will be richer in details.

In the next post, we'll talk about algorithms and options to optimize them.

References

• 3D Collision Detection at MDN Web Docs
• Exponentiation
• Why you should avoid square root?
• Fast inverse square root