The mathematics / algorithms of game development

Why game development?

Game development is one of the central, if not the most central, pipeline for people to get into programming. I still remember being $12$ years old and the intrigue I felt when my father tried to teach me basic Java so that I could make mods in Minecraft, just for me to give it up almost immediately after writing my first Hello World. Several years later I spent IT classes writing games in Javascript thinking I wanted to get into game development. While I do not aspire to that anymore, game development is still very exciting, and the techniques behind it even more so.

When I was getting into it I was watching tons of YouTube videos behind it and gradually became more interested in the process than the result. For maximal indoctrination I highly, highly, highly recommend the Sebastian Lague $\rightarrow$ Freya Holmér $\rightarrow$ 3Blue1Brown pipeline!

How to render a cube

The first demo is deliberately small: a cube rendered on the CPU.

This is not how one would normally draw a cube in a serious game engine. If the goal were merely to display a cube, I would use WebGL or Three.js and let the GPU do its job. Here the goal is different. I want the steps to be visible.

A cube begins as eight points in its own local coordinate system:

The renderer rotates those points, moves them in front of a camera, projects them onto the screen, and then draws the resulting faces and edges.

That tiny pipeline already contains the main idea of 3D graphics:

To rotate the cube, we apply rotations to its vertices. For example, rotation around the $y$-axis is given by

Now, the matrix-multiplication is perhaps not that useful for our intuition. In reality, the matrix above just represents the aggregation of multiple transformations which when completed look like a rotation around the $y$-axis, the matrix is simply a more compact way of describing this series of transformations.

Thus we get our first glimpse at the machinery behind most of 3D-graphis: linear algebra. That’s right, the math which plagues many stem-majors’ undergraduate education informs the techniques used to draw graphics in video games for our enjoyment.

In a full graphics pipeline, the same idea is organized into several coordinate systems:

First describe the object in its own coordinates. Then place it in the world. Then describe where it is relative to the camera. Then decide what the camera can see. Finally, turn the visible geometry into pixels.

Perspective projection

With the above steps, we get the orthographic view which you can check out in the demo. As you may see, the image is lacking in depth, so that is our next step.

A point in space has coordinates

but the screen only has two dimensions. Perspective projection turns that point into something like

The rough idea is

The larger the depth $z$ is, the smaller the projected coordinates become. This is why distant objects appear smaller.

Orthographic projection removes this division by depth. Parallel lines stay parallel, and distant objects do not shrink. That is useful for technical views, strategy games, editors, and diagrams, but it does not mimic ordinary visual perspective.

Why triangles appear everywhere

The cube has square faces, but the demo can show each square split into two triangles. Real-time graphics is largely built around triangle meshes.

Triangles are convenient because three points always determine a flat surface. A complicated model can therefore be approximated by many small triangles. A cube is only

but the same idea scales to characters, terrain, buildings, and almost everything else you see in a 3D game.

A real renderer would clip those triangles against the camera frustum, rasterize them into fragments, shade them, depth-test them, and finally write pixels to the screen. This demo is not so sofisticated as it simply sorts the cube faces by depth and draws them back-to-front using Canvas 2D. That is called the painter’s algorithm. It works fine here, just know that it is not robust enough for arbitrary 3D scenes.

Why this is a CPU renderer

This is a tiny CPU renderer because the point is to expose the machinery.

Three.js would be better engineering if all we wanted was a nice cube. But for a demo, hiding the matrix math inside a library would defeat the purpose. This little renderer has no z-buffer, no clipping, no lighting model, no texture mapping, and no perspective-correct interpolation. It only has the skeleton:

Hopefully this is sufficiently elcudating such that some readers will look deeper into the even more fascinating techniques used to make even more interesting things appear on the screen!

I highly recommend checking out Acerola for anyone interested in 3D graphics more broadly!

Further rabbit holes

This demo connects to one of my earliest graphics rabbit holes. My first real foray into rendering from scratch was following Software Rendering from Scratch.

Some other resources I like for this topic:

• Coding Adventure: Software Rasterizer - Sebastian Lague
• Linear transformations and matrices — 3Blue1Brown
• Code-It-Yourself! 3D Graphics Engine Part #1 — Triangles & Projection
• LearnOpenGL: Coordinate Systems
• The Math behind (most) 3D games - Perspective Projection - Brendan Galea

Notes for myself on things to add

• Collision detection (uses more lin. alg., convexity, sep. axis thm) with demo where you can:
  • take two rectangles/polygons,
  • drag around,
  • show projection intervals on axes,
  • resolve collision.
• Pathfinding (uses graphs, shortest paths [has NP-complete variants!], datastructures like priority queues) with pathfinding demo where you can use:
  • BFS,
  • Dijkstras,
  • Greedy,
  • $A^*$.
• Procedural noise (uses interpolation, gradients, smooth random, frequencies and octaves) with demo where you can:
  • slide frequency, amplitude, octaves, persistence,
  • output 2D terrain heightmap or scrolling landscape or something.
• Wave function collapse (inspired by quantum mechanics, buty is really a CSP) with demo where you can:
  • tile a grid,
  • watch as each cell fill with many possible tiles such that,
  • selection propogates constraints to neighbors.
• Marching squares/cubes (uses scalar fields, level sets, interpolation) with demo where you can:
  • threshold on a 2D scalar field so that
  • grid cells show cases and a contour line appears. Marching squares is cool because it was created for medical imaging, but is now known as a central technique in gamedev.
• Boids (more lin. alg., local rules, is a dynamical systems and gives emergent behavior from simple rules) with demo where you can:
  • choose which rules for the boids to follow to see how they give the desired behavior.
• Cellular automata with demo where you can:
  • choose between e.g. conway and other known simple automatas,
  • or even a noita style cellular physics simulation.