by Nicholas Carlini 2019-09-13
Why make a Doom clone?
But aside from that fact, I had just made a 3D renderer and wanted to keep working on it more. Also, writing heavily compressed code is something I enjoy doing, (For example, many years ago I created a language and wrote a compiler for a new language designed specifically for use in code golf.)
So that's why an FPS. What about the question “why doom?” The answer here is easier. If you're going to write an FPS, and want to keep it small, doom is about as minimalistic as you can get.
The reason doom is so simple (by today's standards) is clear: doom had to run no hardware five orders of magnitude slower than what we have today. For the same price today, it's entirely possible to build a machine that can do a hundred thousand times the work of the Pentium of 1994. And so, I thought it would be fun to try and re-create something like doom but instead of having performance constraints, have space constraints.
Going from 3D renderer to 3D game engine basically just requires one change: player-controlable camera movement. To do this, I put the player on the inside of a box and worked for a while making movement feel right. Doom has a very distinctive style of movement that I tried to recreate. One feature I added that doom didn't have was I added a small amount of camera roll on every step.
Then I added clipping. There's no reason to create complicated doom-esque mazes if the palyer can walk through walls. Now, the “correct” way to handle clipping is to make the player is a sphere, the walls plans, and then detect sphere-plane intersections. But that would all take a lot of space.
Instead, I extend eight rays out of the current player's position, and detect if any of those rays intersect with a wall. If they do, then I back the player up so that it's at least five units away from the that wall. This has the effect of being a poor-mans sphere collision detection while also coming in at a hundred bytes.
Getting this right was somewhat finicky, especially when intersecting with multiple walls simultaneously. It's still broken in a few situations, so when designing the levels I manually tested for glitches and just designed the levels around the collision detection bugs.
One of the defining characteristics of doom is the levels it puts you through. Each map feels more like a maze, and the player is running around looking for the way out. This was going to be a necessary component to get right.
However, storing the maps naively was going to take far too much space. So, instead of storing maps by saving the position of every wall, maps are represented by a collection of (potentially non-convex) polygons. Each polygon can have a floor height and ceiling height, and when two adjacent polygons share an edge you can pass from one to the other (possibly going up or down accordingly).
Initially I just started creating the maps by hand-coding the polygon locations, but there were two problems with this: first, they were taking a bunch of space, but more importantly, it was taking forever to make them. If I wanted to be able to design enough maps I was going to need to do somthing better.
Figuring it may be possible to resolve both issues simultaneously, I implemented a tiny, tiny turtle programming language to define the locations of the map regions. Initially this language was very turtle-like: the language controled the rotation and position of the turtle, and commands would rotate and move the turtle around the map. It was possible to raise and lower the “pen” in order to change between moving and drawing a polygon.
Unfortunately, this was still difficult to design make maps, as it required programming the turtle in an assembly language designed to be as dense as possible. So instead I scrapped most of the turtle language and made a much simpler language with, initailly, just two opcodes: make-polygon, and backtrack. The make-polygon opcode takes the number of vertices, and then has a sequence of bytes where the high 4 bits gives how far to move along the x axis and the low 4 bits how far to move along the y axis. Backtrack resets the turtle position to where it was N steps ago.
That worked very well, because it let me build a really tiny WYSIWYG interface to help me design maps (shown above) that then compiles these maps to the turtle language, so they can be used in game.
In order to have any objects in the game, I was going to need to represent them somehow. One natural method would be to use the .obj file format. Unfortunately, this is quite large and cumbersome. (This is what I did for my prior 3D remderer to load the mandatory teapot.)
Instead, I decided to write a minimalistic object lathe method: given a 2D path represented as a sequence of points, lathing rotates the points around in a circle to generate a 3D object. This lets you create some very nice objects with only a very small amount of space. For example, the jug pictured above comes in at around twenty bytes of code to represent.
Gun & Enemies
A first person shooter isn't much fun without something to shoot with, or shoot at.
I started with the “shooting with” problem. I wasn't sure if there would be enough space for more than one gun (narrator: there wasn't), and for a game designed around shooting, I figured starting with the chaingun was the natural choice.
The gun model is just a few cylinders made with the object lathe. When walking, the gun swings back and forth (again following the doom style). Shooting has some screenshake, and because there is no ammo, slows down player movement. It's important to give the player a reason to not hold down the trigger the entire game.Hit detection is a simple ray-cast hitscan (using the same code as the collision detection with walls for player movement) followed by creating some explosion particles and a small light flash.
Then I turned to the “shooting at” problem. I initially created a really basic block-model of a person. It's entirely based on cubes which makes it very easy to store: by saving just a single cube model, I can stretch it in arbitrary directions and get an enemy. The basic enemy then consists of eight boxes.
Initially, the death animation was simple and they would just fall over. This didn't look all that bad, but shooting felt weak and boring. So instead, I made a few tweaks so that the enemy would remember each of the constituent cubes that makes it up and then when it gets hit, explode into pieces. This felt much better.
For someone whose degree and career is ostensibly in (with lots of quotes) ““AI””, the enemies here are really rather unintenilgent. Enemies have a position and rotation. They pace back and forth forever, until being woken up, either (a) because the player is within line-of-sight, or (b) because an enemy within line-of-sight is shot.
Once awake, the enemy will move in a straight line directly towards the player. If something gets in the way, the enemy will pick a new random direction and move that way for a few steps, and then return to moving towards the player. Occasionally, the walking enemies will shoot at the player.
Until now everything was very dull being just one texture. I knew there was no way I would fit in any textures---even small ones---so instead I procedurally generated them. I opted to go for just three textures: a tile floor, a brick pattern for walls, and simple Perlin noise for lava and explosions.
The brick generation is somewhat trivial. Draw horizontal lines every N steps, and then vertical lines every N steps offset by N/2 when we're on even numbered rows.
Tile generation is a little bit tricker. First I create a hexagonal dot-matrix. Then, for each pixel in the tile, I draw a line if the distance to the nearest point is equal to double the distance to the second nearest point.
Perlin noise is visually a much nicer type of noise than other noises. It looks more naturally-random than just pure white noise. Perlin noise generation is complicated enough I'll just point to the wikipedia article and say “I do that”. I also add a small amount of perlin noise to the brick pattern to make it less boring.
Having the enemies glide around the map wasn't very visually interesting, so next I added a walking animation. This took surprisingly little space, and was just moving the limbs like pendulums.
Only having one enemy type wasn't going to work, so from here I added a smaller flying enemy. The representation is again very minimalistic: is just two wing-looking trapezoids with a rectangle body. To make it look like it's flying, the wings flap a bit and it flutters up and down.
It seemed like the obvious choice for adding audio was JSFXR. However at this point space was getting tight. After taking a quick look at the code I realized there was a bunch of room for optimizations.
I managed to shorten it by almost a factor of two through a bunch of small tweaks. The biggest saving came from removing the mapping from the array to playable WAV file and replacing it with a WebAudio call which directly takes a float array. Next biggest was a bunch of case statements I replaced with array lookups. That is, I do the multiplexer thing and compute all cases inside of an array, and then just index out the one I want to keep. Slower, but shorter. After replacing the for loops with maps, and writing a clamp helper function, it was short enough to allow writinng a some nice sound effects.
Then I wanted to make the audio system respond to where the player was in the 3d space. I thought this part was going to take a bunch of effort but it turned out that it was quite easy, as there's now a createStereoPanner function which does exactly this for you.
For background music, I transcribed the middle portion of Toccata and Fugue. This just plays on repeat forever.
Thougs on saving space
The main necessary objective to get everything working in 13k is to always be aware of code size. I updated the python script to monitor every time a source file was changed and to re-build the package, and show the number of free bytes remaining on the game itself so it would always be visible and I would ask myself if whatever change I just introduced was worth the complexity.
Constantly showing the current build size required an automated build process. The build script initailly just ran uglifier followed by standard zip to keep track of space. I soon realized that there were some optimizations that I could automate to help compress things more. I wrote a short script to identify all webgl variable names and rewrite the variable names to short one-letter names (since this isn't done by uglify). Then I modified this program to rewrite long WebGL function names like framebufferTexture2D with a short three-character code of e2m (where I take the 8th from last 2nd from last, and and 3rd characters respectively). Near the end of of development I came across advzip which helps more with better comopression