Rendering 3D games from scratch

At 14, I built a first-person shooter in C++ with OpenGL. You ran around a map full of obstacles while enemies spawned and came for you.

What hooked me wasn't the game. It was that a flat screen could look like a world you walk through, and all it took was some school maths.

So I rebuilt it in the browser, to remember how it all works. No 3D library, every pixel drawn by my own code. This is what it does, in order: drawing the world first, then doing it fast, then the game logic. The game is at the end.

From 3D to the screen

Every object in the game is a set of corners. A pillar is a box with 8 of them. Each corner is three numbers: how far to the side, how far up, and how far ahead.

The screen is flat, so the ahead number has to go somewhere. Picture a sheet of glass one step in front of your eye. Draw a line from your eye to each corner. Where the line goes through the glass is where that corner lands on the screen. Join the 8 points and you've drawn the pillar.

The line hits the glass at the corner's side number divided by its ahead number. Same for up. So a corner twice as far away lands twice as close to the middle. That's why far things look small. It's the line of code that made it click for me:

screenX = x / z;
screenY = y / z;

But that only works if you stand at zero and look straight ahead. In a game you walk around and turn, so every corner goes through two steps first.

First, move. Subtract your position from the corner, so you're at zero. Then turn. If you've turned by an angle θ, every corner swings the other way around you:

x2 = x * cos(θ) - z * sin(θ);
z2 = x * sin(θ) + z * cos(θ);

Walking uses the same sin and cos. Facing θ, one step forward adds sin θ to your side number and cos θ to your ahead number.

Then divide. One more number decides how wide you see: the field of view. The glass is one step ahead, so its half width is tan of half the field of view. Divide by that too and the screen runs from −1 to 1. Last, stretch −1 to 1 across the screen's pixels.

Real engines pack the move, the turn and the field of view into one 4×4 grid of numbers called a matrix. They put the depth into a fourth number, w, and the graphics card does the divide by w for every corner.

There's a catch, and it's one of the first bugs everyone hits. Divide by the straight-line distance to each point, and a flat wall bends like it's seen through a fishbowl. Points off to the side are farther away in a straight line, so they shrink, even though the wall is flat. The right thing to divide by is depth: how far ahead the point is, measured along the way you're looking.

Filling in the shape

Corners only give you an outline. A screen is a grid of pixels, and every one needs a colour.

So every surface is cut into triangles. A pillar is 12 of them. For each triangle, the game works out which pixels sit inside it.

The rule is simple: only the centre of a pixel counts. An edge can cut right through a pixel, but if the centre is on the outside, the pixel stays empty.

To tell which side of an edge a centre is on, you take the edge from corner A to corner B and the centre P, and work out one number:

side = (B.x - A.x) * (P.y - A.y) - (B.y - A.y) * (P.x - A.x);

Positive on one side, negative on the other, zero exactly on the line. Do it for all three edges. Same sign three times means the centre is inside. No angles, no square roots, just multiplying and subtracting.

Those same three numbers also tell you how close the pixel is to each corner. That's how a colour or a depth gets blended smoothly across the triangle, for free.

Every pixel does the same check, and no pixel cares about any other. That turns out to matter a lot later.

The edges are where it gets tricky. Two triangles that share an edge can both decide a pixel on it is theirs, so it gets painted twice, or both decide it isn't, and you get a crack. Graphics cards settle it with a fill rule: a pixel exactly on an edge belongs to only one side. The usual one is the top-left rule. A pixel on an edge goes to the triangle that has that edge on its top or left side.

What's in front

Two triangles can land on the same pixel. Say an enemy is standing in front of a pillar. The enemy should win.

Next to every pixel's colour, the game keeps one more number: how far away that colour came from. A new triangle only paints over a pixel if it's closer than what's already there. This is called a depth buffer.

The depth buffer has a limit people don't expect. It stores depth with a fixed number of steps, and most of those steps are spent close to the camera. Far away, two surfaces that are close together can land on the same step. Which one wins then flips from pixel to pixel, and the surface flickers in stripes. It's called z-fighting.

The fix that works best costs nothing: move the near plane out. That's the closest distance the camera will draw. Most steps go to the space just in front of it, and nobody puts anything 10 cm from their face. At 1 metre instead of 10 cm, the same 16 bits stay sharp ten times further away.

Light

Without light, every face of a shape is the same colour, and a ball looks like a flat disc.

A surface facing the sun head on is brightest. As it turns away it gets darker, and past 90 degrees it gets no light at all. The brightness is the cosine of the angle between where the surface faces and where the sun is.

Lighting each face once makes a ball look like a disco ball. The trick is to give every corner the direction of the real, round ball, then blend between corners for every pixel. The faces vanish, but look at the edge: it's still made of straight lines. The shine is one more number: how straight the sun bounces off the surface into your eye.

Effects without melting your PC

When you kill an enemy, it bursts into shards. Each shard is a tiny object with a position, a speed and a timer. Every frame, gravity pulls it down, it moves a little, and its timer ticks. When the timer runs out, it's gone.

A few hundred of these are nothing. Tens of thousands every frame will drop your frame rate. Games keep effects cheap with a few simple rules:

• A hard limit. My game never keeps more than 512 shards. A burst that would go over just makes fewer.
• Short lives. A second and a half at most.
• Cheap shapes. A shard is one triangle, not a 3D model.
• Reused memory. A dead shard gets recycled instead of a new one being made.

The naive way makes a new object for every spark and draws each one on its own. At 100,000 sparks that drops to a few frames a second. Games make one big array once and reuse it forever. Then they hand the whole thing to the GPU in a single draw call, and it stays smooth.

How engines skip work

A real game level has millions of triangles, and you only ever see a small slice of it. The fastest triangle is the one you never draw.

So engines skip:

• Everything behind you or outside your view.
• The back sides of shapes, which their fronts always hide.
• Whole rooms behind walls.
• Detail on things far away. A distant enemy covers a few pixels, so a much simpler shape looks the same.

Working out what's hidden behind walls is expensive to do every frame. Quake did it ahead of time. Before the game ran, it split the level into rooms and worked out which rooms could possibly see which, by trying sight lines through every doorway. While you played, it just looked up the list for the room you were standing in.

Being joined by doors isn't enough. Rooms linked by a chain of doorways often can't see each other at all, because the doors don't line up.

CPU vs GPU

A 1080p screen has about 2 million pixels. At 60 frames a second, that's 120 million pixels to colour every second.

A CPU has a handful of very fast workers, and they colour pixels one after another. A GPU has thousands of slower, simpler workers, each colouring its own pixel, all at the same time. Since every pixel can be worked out without the others, the GPU wins by a mile.

Below, the same shape is drawn both ways and timed live on your machine. At a small size, both keep up. Make it bigger and the CPU blows past the 60 fps line, because it lights every pixel one after another. The GPU barely notices.

My game draws on the CPU on purpose, at a tiny 320 by 180, so every step stays in code I wrote.

This is also why graphics cards ended up running AI. Training a neural network is the same kind of work: billions of small multiply-and-add sums that don't depend on each other.

Distance and collisions

Now the game itself. Almost every rule in it comes down to one number: how far apart two things are.

The game knows where you are and where an enemy is. The gap to the side and the gap ahead make a right triangle, and the real distance is its long side. Pythagoras gives it: √(side² + ahead²).

That one number runs the game. If the distance is less than your size plus an enemy's, it has reached you and you lose a hit.

The obvious way for an enemy to chase you is to walk straight at you. It works until there's a pillar in the way, and then it walks into the pillar forever.

So enemies search for a path. The map becomes a grid of cells, and the search spreads out from the enemy one cell at a time until it reaches you. A plain search spreads in every direction. A* is smarter: it always tries the cell that looks closest to you first, using the same Pythagoras distance as a guess. It reaches you after exploring less than a third of the cells.

The guess isn't perfect. A wall that cups toward the enemy fools it for a moment, and it has to back out and go round. It still finds the shortest path.

That's still one search per enemy, every time you move. With hundreds of enemies it adds up. Strategy games flip it around: one search, spreading out from you, writes an arrow into every cell pointing the quickest way to you. Every enemy just follows the arrow under its feet. When you move, that's one more search, not one per enemy.

The game

Here it is: the shooter, rebuilt on everything above. No 3D library. Every pixel is worked out by my own code on the CPU, the way games did before graphics cards. The graphics card only puts the finished picture on screen.

Click to start. W A S D to move, Shift to run, Space to jump, mouse to aim, click to shoot, Esc to pause. You can jump over the low blocks, or stand on one: the fast yellow ones can't reach you up there. You have 5 hits. Red ones die in one shot, blue ones take three, and the yellow ones are fast. The longer you last, the more of them come.