Game Programming: Time Slicing

Source files and future updates are available on Patreon.
You can follow me on Twitter.

This post is part of my Game Programming Series.

Prerequisite

Introduction

In the previous tutorial, I used exposure avoidance as an example to demonstrate how to optimize computation with delayed result gathering. The basic idea is: kick jobs to run on worker threads and gather the results later. This prevents the main thread from being stalled.

If the game can afford one-frame latency, then we can kick the job in one frame and gather the results in the next frame. If the game cannot afford such latency, it’s still worth trying kicking the job early and gather the results later in the same frame.

What if the job takes too long to fit in a single frame? Or what if the job is just taking longer than we’d like? Then we can split the work across multiple frames. This is the core idea of time slicing, another optimization technique I picked up at work and one of my longtime favorites.

If you think about it, time slicing is everywhere. Texture streaming, seamless loading, etc., work that happens “in the background” without tanking a game’s frame rate. Can’t do it all in one frame? Then do it across multiple! It’s a simple but very effective idea.

Continue reading
Posted in Uncategorized | Leave a comment

Game Programming: Delayed Result Gathering

Source files and future updates are available on Patreon.
You can follow me on Twitter.

This post is part of my Game Programming Series.

本文之中文翻譯在此

Introduction

Back at DigiPen (my college where I learned gamedev), whenever people from the games industry came over on a company day to share their industry experience, one question always came up during Q&A: please tell us one thing you wish you had known at school (it can be anything: technical skills, social skills, production skills, etc.). I often wondered what I would tell the students if I had been at the podium. For a very long time, I had no answers in mind. But now, if I were to present on a company day, I would probably have an answer specifically for CS students. I wish I had known two particular optimization techniques when I was working on my game projects back at school: delayed result gathering and time slicing.

These are the first two techniques I learned since I joined Naughty Dog. And I have found them the most useful throughout my career. I have used them in numerous in-game systems up to this day. They are simple general solutions that can be applied almost everywhere and are usually very effective.

In this tutorial, I will talk about the first of the two: delayed result gathering. I will cover time slicing in the next tutorial.

The Example: Exposure Map & Exposure Avoidance

First, I’ll introduce the example that serves as the testbed for the two optimization techniques. It will be modified throughout these two tutorials to demonstrate how to apply the optimization techniques to an existing system.

The example is exposure map & exposure avoidance. We have a grid that represents whether each cell is exposed to a “sentinel,” and we have a character that tries to move to and hide in a nearby cell that is not exposed. As the sentinel moves around, the character runs away once their current cell becomes exposed. Meet shy ball.

Continue reading
Posted in Uncategorized | 2 Comments

Game Math: Dot Product, Rulers, And Bouncing Balls

Source files and future updates are available on Patreon.
You can follow me on Twitter.

This post is part of my Game Math Series.

本文之中文翻譯在此

Prerequisites

Overview

The dot product is a simple yet extremely useful mathematical tool. It encodes the relationship between two vectors’ magnitudes and directions into a single value. It is useful for computing projection, reflection, lighting, and so much more.

In this tutorial, you’ll learn:

  • The geometric meaning of the dot product.
  • How to project one vector onto another.
  • How to measure an object’s dimension along an arbitrary ruler axis.
  • How to reflect a vector relative to a plane.
  • How to bounce a ball off a slope.
Continue reading
Posted in Gamedev, Math, Uncategorized | 2 Comments

Game Math: Inverse Trigonometric Functions, Slope Angles, And Facing Objects

Source files and future updates are available on Patreon.
You can follow me on Twitter.

This post is part of my Game Math Series.

本文之中文翻譯在此

Prerequisites

Overview

At this point, we have learned about the three basic trigonometric functions: sine, cosine, and tangent. Now, we are going to take a look at their inverse functions, as well as how they can be utilized in games.

In this tutorial, you’ll learn:

  • The inverse functions of the three basic trigonometric functions.
  • How to compute the angle of a slope given a desired slope value.
  • The domains and ranges of inverse trigonometric functions.
  • The special convenience inverse trigonometric function atan2.
  • How to make an object face towards the mouse cursor.
Continue reading
Posted in Gamedev, Math, Unity | 1 Comment

Game Math: Trigonometry Basics – Tangent, Triangles, And Cannonballs

Source files and future updates are available on Patreon.
You can follow me on Twitter.

This post is part of my Game Math Series.

本文之中文翻譯在此

Prerequisite

Overview

In the previous tutorial, we have learned about two basic trigonometric functions: sine & cosine. This time, we are going to look at another basic trigonometric function: tangent. Together, these three functions form the basis of trigonometry, and they can be used to solve all sorts of geometric problems that arise in game development.

In this tutorial, you’ll learn:

  • A geometric interpretation of another basic trigonometric function: tangent.
  • The relationships among sine, cosine, and tangent.
  • How to use tangent to create smooth intro and outro motion.
  • How to relate angles and sides of right triangles using trigonometric functions.
  • How to simulate a cannonball, given an initial speed and an elevation angle.
  • How to draw predicted trajectories even before firing the cannonball.
  • How to place cannonball targets, given a horizontal distance and an elevation angle.
Continue reading
Posted in C#, Gamedev, Math, Programming, Unity | Leave a comment

Game Math: Trigonometry Basics – Sine & Cosine

Source files and future updates are available on Patreon.
You can follow me on Twitter.

This post is part of my Game Math Series.

本文之中文翻譯在此

Overview

Trigonometry is a very essential building block to a huge portion of game math. That’s why I’ve chosen this topic for the first tutorial of my new Gamedev Tutorials series. Having a solid understanding of basic of trigonometry can go a long way for game development. It is used extensively in game problem solving.

In this tutorial you’ll learn:

  • A geometric interpretation of two basic trigonometric functions: sine & cosine.
  • The comparison of two different angle units: degrees & radians.
  • Some basic properties of sine & cosine.
  • How to move and arrange things in a circular fashion:
  • How to move things in a spiral fashion:
  • How to create simple harmonic motion:
  • How to create damped spring motion:
  • How to create pendulum motion:
  • How to generate hovering motion:
Continue reading
Posted in Gamedev, Math, Programming | Tagged , , , , , | 9 Comments

Readable & Debuggable Multi-Condition Game Code

This post is part of my Game Programming Series.

Over time, I have adopted several coding patterns for writing readable and debuggable multi-condition game code, which I systematically follow.

By multi-condition code, I’m talking about code where certain final logic is executed, after multiple condition tests have successfully passed; also, if a test fails, further tests will be skipped for efficiency, effectively achieving short-circuit evaluation.

NOTE: I only mean to use this post to share some coding patterns I find useful, and I do NOT intend to suggest nor claim that they are “the only correct ways” to write code. Also, please note that it’s not all black and white. I don’t advocate unconditionally adhering to these patterns; I sometimes mix them with opposite patterns if it makes more sense and makes code more readable.

Shortcuts:
Early Outs
Debuggable Conditions
Debug Draw Locality
Forcing All Debug Draws

Continue reading

Posted in Gamedev, Programming | 7 Comments

Game Math: Deriving the Slerp Formula

This post is part of my Game Math Series.

It occurred to me that the entire time I’ve been working with quaternions, I have never read or learned about the derivation of the formula for slerp, spherical linear interpolation. I just learned the final formula and have been using it.

Upon a preliminary search I couldn’t seem to immediately find a straightforward derivation, either (at least not one that fits in the context of game development). So I thought it might be a fun exercise to derive it myself.

As it turns out, it is indeed fun and could probably serve as an interesting trigonometry & vector quiz question!

A quick recap: slerp is an operation that interpolates between two vectors along the shortest arc (in any dimension higher than 1D). It takes as input the two vectors to interpolate between plus an interpolation parameter:

    \[ Slerp(\overrightarrow{a}, \overrightarrow{b}, t) = \frac{sin((1-t)\Omega)}{sin\Omega} \overrightarrow{a} + \frac{sin(t\Omega)}{sin\Omega} \overrightarrow{b},  \]

where \Omega is the angle between the two vectors:

    \[ \Omega = \frac{cos^{-1}(\overrightarrow{a} \cdot \overrightarrow{b})}{||\overrightarrow{a}|| \, ||\overrightarrow{b}||} \]

If the interpolation parameter t changes at a constant rate, the angular velocity of the slerp result is also constant. If t is set to 0.25, it means the slerp result is “the 25% waypoint on the arc from \overrightarrow{a} to \overrightarrow{b}: the angle between \overrightarrow{a} and the slerp result is 0.25\Omega, and the angle between \overrightarrow{b} and the slerp result is 0.75\Omega.

In the context of game development, slerp is typically used to interpolate between orientations represented by quaternions, which can be expressed as 4D vectors. In this case the shortest arc slerp interpolates across lies on a 4D hypersphere.

As mentioned before, this formula can be used on any vectors in any dimension higher than 1D. So it can also be used to interpolate between two 3D vectors along a sphere, or between two 2D vectors along a circle.

In the context of game development, we almost exclusively work with unit quaternions. So in my derivation, I make the assumption that the vectors we are working with are all unit vectors. The flow of the derivation should be pretty much the same even if the vectors are not unit vectors.

Without further ado, here’s the derivation.

The Derivation

Let \overrightarrow{c} be the results of slerp:

    \[ \overrightarrow{c} = Slerp(\overrightarrow{a}, \overrightarrow{b}, t) \]

And let \Omega be the angle between \overrightarrow{a} and \overrightarrow{b}.

Knowing that the angle between \overrightarrow{a} and \overrightarrow{c} is t\Omega, and the angle between \overrightarrow{b} and \overrightarrow{c} is (1-t)\Omega, we can come up with this figure:

Continue reading

Posted in Gamedev, Math | Leave a comment

Game Math: Swing-Twist Interpolation (…Sterp?)

This post is part of my Game Math Series.

Source files are on GitHub.
Shortcut to sterp implementation.
Shortcut to code used to generate animations in this post.

An Alternative to Slerp

Slerp, spherical linear interpolation, is an operation that interpolates from one orientation to another, using a rotational axis paired with the smallest angle possible.

Quick note: Jonathan Blow explains here how you should avoid using slerp, if normalized quaternion linear interpolation (nlerp) suffices. Long store short, nlerp is faster but does not maintain constant angular velocity, while slerp is slower but maintains constant angular velocity; use nlerp if you’re interpolating across small angles or you don’t care about constant angular velocity; use slerp if you’re interpolating across large angles and you care about constant angular velocity. But for the sake of using a more commonly known and used building block, the remaining post will only mention slerp. Replacing all following occurrences of slerp with nlerp would not change the validity of this post.

In general, slerp is considered superior over interpolating individual components of Euler angles, as the latter method usually yields orientational sways.

But, sometimes slerp might not be ideal. Look at the image below showing two different orientations of a rod. On the left is one orientation, and on the right is the resulting orientation of rotating around the axis shown as a cyan arrow, where the pivot is at one end of the rod.

If we slerp between the two orientations, this is what we get:

Mathematically, slerp takes the “shortest rotational path”. The quaternion representing the rod’s orientation travels along the shortest arc on a 4D hypersphere. But, given the rod’s elongated appearance, the rod’s moving end seems to be deviating from the shortest arc on a 3D sphere.

My intended effect here is for the rod’s moving end to travel along the shortest arc in 3D, like this:

The difference is more obvious if we compare them side-by-side:

This is where swing-twist decomposition comes in.

Continue reading

Posted in Gamedev, Math, Programming, Unity | 2 Comments

Unity Debug Draw Utility – Now with Shaded Styles

View post on imgur.com

This post is part of my Game Programming Series.

Complete source code for the debug draw utility and Unity scene for generating the demo animation above can be found on GitHub. Here is a shortcut to the debug draw utility class. And here is a shortcut to the shaders.

Debug Draw Upgraded

A couple weeks ago, I documented how I implemented a wireframe Unity debug draw utility using cached mesh pools and vertex shaders.

Recently, I have upgraded the utility to now support various shaded styles, including solid color, flat-shaded, and smooth-shaded. This post is a documentation of my development process and how I solved some of the challenges on the way.

Continue reading

Posted in C#, Gamedev, Programming, Shader, Unity | Leave a comment