Ken Silverman Interview: Build, Duke Nukem 3D, and the Art of Saving CPU Cycles

Retro Replay: Let’s start with something current rather than immediately dragging you back to DOS. What programming problem, experiment, or project has been occupying your brain lately?

Ken Silverman: I spend most of my time these days doing research, engineering, software, and firmware for Voxel Photonics, a company based in Australia which makes 3D volumetric displays. The job involves both hardware and software design. I also help teach a class at Brown University which involves designing circuit boards.

Retro Replay: Ken’s Labyrinth predates Build, but looking back at its renderer now, can you see specific ideas or mistakes in that game that directly influenced the architecture you chose for Build?

Ken Silverman: Pretty much none of the code from Ken’s Labyrinth ended up in Build. Perhaps the only thing that remains would be some of the silly variable or function names, such as ‘totalclock’. For some of the earliest versions of Build that still ran in 16-bit mode, I copied my wall rendering code from Ken’s Labyrinth. However when I changed everything over to 32 bit mode, even that stuff had to all be rewritten.

Since nobody asked, here are some interesting facts about the internals of Ken’s Labyrinth:

• The texture mapping for walls had special cases for various heights of wall column (although it wasn’t to the extent of Wolfenstein 3D). For example, if the V coordinate quantized to same value to a group of either 3 or 4 pixels, I would jump to the case which handles 3 or 4 pixels in a row. This helped speed up the rendering of taller walls.
• I would skip raycasting a column if the rays on both sides happened to hit the same wall cube. In 320×200 mode, the algorithm would start by ray casting columns 0, 256, and 320, then split in half while necessary.
• I came up with a strange interpolation algorithm for the u-coordinate of masked walls (walls that don’t always face you, such as doors). If you look at them edge-on in the original game, you will see them warp in strange ways that you don’t see on normal walls. Note that this was before I knew the proper math. Even stranger – I can’t seem to find the QuickBasic test program that I might have used to prototype the algorithm.
• Back then, I didn’t bother to keep C-equivalent code for blocks of assembly code. So, if the assembly code was faster (or even the same speed), I would simply delete the C code. Obviously, that’s a bad habit if you ever wish to port something in the future.

Retro Replay: Is there a particular piece of Ken’s Labyrinth code that makes you look back and think, “I was definitely going to have to invent a better way of doing this”?

Ken Silverman: See my earlier answer about the rendering code in Ken’s Labyrinth.

Retro Replay: Once Build started being used by commercial teams, several developers could effectively be working from different snapshots of your engine at once. Before Git, GitHub and modern distributed version control, how did you actually keep all of that straight?

Ken Silverman: I didn’t worry about different versions. The teams were expected to update to the latest version on every update. Sometimes new features caused incompatibilities, and that could cause headaches. I would always include instructions in the BUILD.TXT (or BUILD2.TXT) files on what to do to convert to the new code, but it didn’t always go smoothly.

Retro Replay: Did you use formal source-control software during the core Build years, or was version management closer to dated directories, ZIP files, backups and very careful human memory?

Ken Silverman: I did things the hard way – still do. For bigger changes, When doing small optimizing, I liked to copy my directory to a RAM drive. If what I did crashed, I didn’t want to keep the changes anyway. For bigger changes, I would usually ZIP up the source code to a temporary directory on my HD. I didn’t trust floppies very much, but back then there was no other choice when traveling. There may have been cases where I lost a few hours of work, but I don’t remember ever losing anything big.

Retro Replay: When you changed an engine function that Duke Nukem 3D, Blood, Shadow Warrior or another project depended upon, how did you prevent one team from unknowingly building against an obsolete version?

Ken Silverman: I didn’t have to. The compiler would have complained about such stupidity. Everyone knew that when updating to my latest version, they had to read my associated TXT file entry. There were a few times when I broke things without realizing it, but it usually didn’t take long to find the problem.

Retro Replay: How did you decide which parts of Build deserved a stable interface for game developers and which routines should remain undocumented because you wanted the freedom to completely rewrite them?

Ken Silverman: Basically everything started out as hidden and internal – until someone absolutely needed it. I was very protective of my source code at the time. The less I reveal, the simpler it would appear to an outside developer. Of course, they all wanted more control over time.

Retro Replay: When somebody on one of the game teams reported a bug, what was your preferred method for figuring out whether the culprit was Build, the game code, a map, or somebody doing something with the engine you never expected?

Ken Silverman: I was often working remotely with the teams – by phone and modem. If something couldn’t be tracked down immediately, I would ask them to send me their files so I could try to reproduce it myself. With that, I could usually find the problem pretty quickly. The game teams didn’t have my engine source, so for that reason it was usually my responsibility to figure such things out.

Retro Replay: Did Ken-Build effectively become a laboratory where you could reproduce strange problems discovered by the Duke, Blood or Shadow Warrior teams before touching the engine itself?

Ken Silverman: While I could use Ken-Build to reproduce bugs, I used it more as a test bench to show off my latest effects, such as doors, subways, or bouncing platforms. It was my hope that every game would adopt these things in their code. I didn’t work too much with other people’s code, unless they needed help with debugging something.

Retro Replay: Were there categories of bugs that commercial developers found precisely because they abused Build in ways you never would have thought to test yourself?

Ken Silverman: Sure. A good example of this is a map designer creating a really big room that would cause a divide overflow. Divide overflows were quite common when using scaled integers, especially when doing a 64 by 32 bit divide, as the denominator not only had to not be 0, but also not less than 1/2^32 of the numerator. Sometimes, I would fix these things by shifting up or down a few bits. Sometimes, my only choice was to add a comparison to bypass the bad case. I hated doing that, as it slowed things down.

Retro Replay: Build’s map format evolved through multiple versions before settling on the familiar version 7 format. What kind of engine change was serious enough to justify changing the map format itself?

Ken Silverman: I’ll answer that with a list:
V1->V2: sprite struct:: add status lists, allowing quickly traversing active versus dormant sprites.
V2->V3: sector/wall structs: better texture control; sprite struct: add extra.
V3->V4: sector/wall structs: even better texture control; sprite struct: add momentum.
V4->V5: add: palette, visibility, tags, more flags.
V5->V6: add: palette, clipdist, remove unneeded things.
V6->V7: align all structures to 32-bit.

Retro Replay: When creating a Build map, how much responsibility falls on the editor to prevent mathematically nasty geometry versus the renderer simply having to survive whatever insanity a level designer creates?

Ken Silverman: The main rule for sectors to render properly is: the polygon must not have any intersecting lines. They can touch but not cross. I made sure the touching cases worked because I wanted to support things like sliding doors without it getting too complex.

Retro Replay: Did you ever intentionally construct completely ridiculous maps just to attack your own rendering algorithms and see where they broke?

Ken Silverman: I would obviously test things – it was easy enough to do in the Build Editor. I think the most obvious example would be overlapped sectors. I have an OVERLAP.MAP dated May 14 1994, so I clearly tried it pretty early on. I had to make a few small modifications to the engine to support it better, such as searching neighboring sectors first when you had moving sprites.

Retro Replay: Duke Nukem 3D became famous for environments that appeared much more interactive and flexible than most shooters of the period. Were there moments where the Duke team asked Build to do something and your first reaction was basically, “You want it to do WHAT?”

Ken Silverman: I had no shortage of requests from all teams. Like every project I’ve ever worked on, some things are practical, and some are not. You just have to ignore and skip what can’t be done in a timely manner.

While they took some ideas from Ken-Build, Todd and Allen were able to figure out a lot on their own. Their system of putting extra sprites in a sector was quite novel and powerful at the time. I believe they were the first team to do that. Note how I never did this in Ken-Build.

Retro Replay: Of all the tricks that shipped in Duke Nukem 3D, is there one that players tend to assume was simple but was actually particularly ugly or clever under the hood?

Ken Silverman: Sure. The network code was a mess. Using a synchronous protocol was a clever way to minimize bandwidth. The problem was the changes mostly had to made in game code, so I had to coach each team on how to convert their existing single player code (where you can be sloppy with physics) to a multiplayer design. Mainly, the physics code had to be rewritten to run at the same speed on all machines, and execute every call in the same order. Random seeds had to be initialized the same, and separated between physics and render code, as we still wanted rendering to occur at the highest frame rate possible. Any physics code that didn’t follow these rules would cause the game to go out of sync – and these things were often very hard to find, other than to study the code line by line.

With physics code running at a different frame rate from rendering, there was a need for interpolation. So I had to tell everyone how to do that.

Later on, I came up with a way of doing client-side prediction. This term wasn’t known at the time. Once again, this affected all the physics and network code. Of course every team had to have it, and so I found myself coaching them again. All these things would have been a lot cleaner if I had known what I was doing from the start.

When implementing slopes, I was worried about how to do shading without significantly affecting frame rate. I eventually thought of using a lookup table based on the y-coordinate.

There was some complicated things in the Build Editor, such as the code for handling the space bar when drawing sectors. Also, joining sectors was quite complicated. The map designers quickly learned to make backups before attempting such sorcery in the Build Editor.

Retro Replay: You mentioned that Build had client-side prediction and that Duke Nukem 3D actually shipped before Quake. How did your prediction system work, and how much difference did it make to the experience of playing Duke over a modem or higher-latency connection?

Ken Silverman: The client side prediction made a big difference, especially when playing over a modem connection. The prediction code I came up with back then was quite messy though. I had to coach every game developer on how to make a 2nd copy of their player structure, often using the prefix “fake” in front of everything. When a difference in game structure was detected, I had to have it copy structure from the tic of when it was the same, and re-generate all the physics since that point.

Prediction basically made the game feel like a single player game. The only time it got weird is when the other player was interacting with you, in which case you’d see funny stuff like lag and warping, or as I used to call it – rubber banding. I had the Build games predict as much as possible – including both player orientation and position – even elevators. I believe Quake only predicted the player’s orientation, which was certainly a much simpler hack.

Retro Replay: Blood, Shadow Warrior, Duke Nukem 3D and other Build games all feel noticeably different despite sharing the same underlying technology. From the engine programmer’s perspective, which game surprised you most with what its developers managed to wring out of Build?

Ken Silverman: I think of it like this: Duke was first. Putting it out early was a big reason why their game was so successful. That’s not to say that the game wasn’t great as well. Blood and Shadow Warrior had another year to add things. For me, what stands out is the voxel sprites and room-over-room effects. The later games also had a more colorful palette.

Retro Replay: Was there ever a Build game where you saw an effect or level and initially had to stop and figure out how they had accomplished it with your own engine?

Ken Silverman: I suppose I got that reaction from Allen Blum’s early water code, which is present in Lameduke. Sadly, it had to be removed due to conflicts with newer video modes.

Retro Replay: Build could move sectors and geometry at runtime without relying on the sort of precompiled BSP structure associated with some competing engines. What rules did moving geometry have to obey so that the renderer didn’t lose its mind?

Ken Silverman: Haha, it’s ok. You can say ‘Doom’. See my earlier answer about the rules for sector geometry.

Retro Replay: Without a conventional Z-buffer, Build still had to correctly combine solid walls, masked walls, sprites, translucent surfaces, floors and ceilings. Which ordering situation caused you the most headaches?

Ken Silverman: If it was just masked walls, everything would have been sorted perfectly because they are just the walls (which are sorted perfectly by my algorithm) rendered in reverse. When you mix in all the other stuff, there is obviously no perfect way to sort things without having to split polygons – which is something I never got around to doing in Build due to its complexity. To improve the sorting of floor sprites, I made a hack to at least get them sorting correctly vertically if their x-y centers were all the same. This helped to eliminate a few glitches, such as boxes that were made out of sprites.

Retro Replay: Build’s world-coordinate system looks straightforward from the outside. Was the numerical scale deliberately calculated around integer precision and maximum map size, or did it evolve experimentally until you found the sweet spot?

Ken Silverman: Build uses purely integer math – except for 1 silly hack I did with texture-mapped slopes. So when picking a scale, I had to think carefully about getting enough precision without causing overflow problems. This choice would have occurred when I was writing the 1993 grid-based engine. When porting to 32-bit Watcom C, it appears I upgraded the coordinate sizes to 32-bit, but never bothered to add any precision. I suppose that would have required a lot of hacks to the existing code. I must not have thought it was worth the effort. However, I did notably give the Z axis 4 extra bits of precision. This was a bit of an annoyance for any physics functions that used vector math.

Curiously, I don’t remember anyone ever requesting more precision. The circular walls, which is where X-Y precision would have been noticed most easily, seemed to look good enough.

Retro Replay: How much performance did Build gain from lookup tables for things like reciprocals, trigonometry, shading and other expensive operations? Was there one table that bought you an almost ridiculous amount of speed?

Ken Silverman: For most things on a 486/Pentium, lookup tables were so mandatory that I wouldn’t have even though about prototyping a floating point version to compare it to. It is more interesting to talk about a boost from converting C to assembly language.

Retro Replay: The palette and shade-table system helped give games like Duke Nukem 3D and Blood much of their visual character. From your perspective, was that primarily an artistic system or an extremely convenient computational shortcut that artists then turned into something expressive?

Ken Silverman: In 1993, I was not a fan of using palette lookup tables because they would significantly affect the speed of all my texture mapping loops. Originally, I did shading like in Ken’s Labyrinth. For each hue, I reserved 2 palette indices on the dark side, so that 1 or 2 could be subtracted from the palette index to darken it. This worked well for darkening the North&South side of wall cubes in Ken’s Labyrinth. This is a very limiting and wasteful system, however. The artist could not use the lower 2 indices of any hue, because there’s no fast way to do saturation.

It would be cool to see how much faster a 486 could render without palette lookups. One way to avoid the lookup penalty would be to use a texture cache – so you might have several copies of each texture in memory, pre-rendered on the fly to different shades. It would have worked well, as long as no surface had a sharp transition from bright to dark, which I imagine was often in some areas.

Retro Replay: Today a programmer can profile almost anything instantly. On a 486, how did you actually prove that a particular function was the bottleneck before spending hours rewriting it in assembly?

Ken Silverman: In the early versions of Build, I used hand coded function-based profiling. I picked a few functions that I thought were slow, such as the texture-mapping loops. To get stable readings, I would run the game for a while at the starting position, making sure not to move, and then upon quit it would display a bunch of numbers in text mode.

Later on, I figured out how to get more accurate timings with the internal 1.193MHz timer. This way, you could get accurate readings without having to sit there for a while.

Retro Replay: When Pentium processors appeared, did you actively rearrange assembly instructions around the dual pipelines, or was chasing that level of CPU-specific optimization more trouble than it was worth?

Ken Silverman: Of course. I was very interested in optimizing for the Pentium. I don’t understand why everyone isn’t obsessed with assembly language. 😉

Retro Replay: Were there cases where an optimization that screamed on a 486 actually performed worse on a Pentium, forcing you to choose which generation of machine to favor?

Ken Silverman: Usually everything that ran faster on a 486 would also benefit a Pentium. There were a few exceptions. One instruction that caught me by surprise was ‘shld’. When I got my first Pentium, I quickly found a replacement using ‘rol’ instead.

I saw this problem a lot more when comparing Pentium to Pentium Pro/II. The Pentium II suffered partial register stalls (reading a full register after writing a part, such as: mov ah, 17 followed by: mov edx, eax).

When optimizing the slope code, I had run out of registers. To avoid doing a read-modify-write sequence, I found that using an FPU register to remember a value was faster – at least on the 486 DX2/66 I was using at the time. I believe it gave a tiny speedup, like 1fps when staring at a full screen slope. Unfortunately, this wrecked performance on a 486SX, which doesn’t have an FPU. I regret making this decision.

Retro Replay: Is there a Build optimization you were extremely proud of in 1995 that would actually be a terrible idea on a modern CPU because caches, branch prediction and out-of-order execution have changed everything?

Ken Silverman: When I look at modern CPUs, I am more interested in looking at what SIMD instructions they support, and the number of cores. Multi-threading helps to eliminate branching penalties, but memory contention is still a big problem. Lookup tables are terrible when compared to SIMD instructions, where it is better to approximate things with math.

Build could be rewritten to be much faster on a modern CPU. Simply converting things to floating point would have made the code a lot simpler, but not necessarily faster. Most of the speed improvement would come from multi-threading, which would require all texture mapping (including walls) to be done in horizontal strips to take full advantage. SIMD could be used to do a divide per pixel, although it might still be faster to use integer affine interpolation every 8 pixels. Of course, it’s a bit silly to write a polygon engine on the CPU, when everyone has a fully capable GPU.

Retro Replay: Flip that around: is there any hand-written routine from old Build that you suspect a modern optimizing compiler still wouldn’t recreate quite as elegantly without being given some serious hints?

Ken Silverman: Of course. Back then, you could get a huge boost by using self-modifying code. It is interesting to note that self-modifying code can still help on a modern CPU, but the point of tradeoff is a lot higher. One extreme example would be an in-memory compiler, such as EVALDRAW.

Some of the benefits of self-modifying code are:
1. To save registers by storing values as immediate constants. 32-bit mode only had 8 registers, one of which was (mostly) off limits – ESP.
2. To avoid shifting or rotating by a variable (CL). In many CPUs, a shift by immediate value is faster than a variable one.

Another one of my favorite hacks is to use stack pointer (ESP) as a small counter. No compiler writer would ever think of doing this.

Retro Replay: Did you ever experiment with really dangerous tricks like self-modifying code or generating specialized rendering loops at runtime, or was even 1990s Ken Silverman willing to draw a line somewhere?

Ken Silverman: See my earlier explanation of self-modifying code. And no, it’s not dangerous at all. It seemed to work on all CPUs. You just need to know what you’re doing. (BTW, Doom used self-modifying code, but I didn’t know that until the code was released years later.)

Retro Replay: The .ART and .GRP formats are refreshingly uncomplicated compared with modern game-asset pipelines. Was simplicity itself an optimization because it made both the engine and your homemade tools easier to understand and debug?

Ken Silverman: Yes. I made it simple because I liked it that way. If I had designed it today, it would have been nice to store a date & time with each file. That way, when looking at the file 30 years later, I would have more time stamps to narrow down clues to my history.

Retro Replay: Build source ports now have to reproduce behavior from code written three decades ago. Are there any bugs, quirks or technically “wrong” behaviors that became features simply because released games and maps came to depend on them?

Ken Silverman: These quirks were an issue if you wanted your port to be network compatible (i.e. stay in sync) with the original game. Any difference in physics code would have caused a loss of sync. Luckily, we avoided things like the Pentium FDIV bug, as there was no floating point code used in the physics part of the engine.

I remember the guys doing the Mac port mentioning they had to figure out my reciprocal function – which was written only in assembly language of course. This was used in some of my physics functions.

Retro Replay: If you had to build an automated torture-test suite for Build today, what obscure behavior would you absolutely include because you know it can expose weaknesses that ordinary maps won’t?

Ken Silverman: There are plenty of bugs in the latest Build. There’s all kinds of problems with collision detection – being squished or warping to weird places. The network code was judged not by if a game went out of sync, but by how often it did. Sprite sorting could never be perfect. The Build Editor could crash in many ways. Try crossing a few wall lines and then joining or copying sectors.

Retro Replay: Here’s one for people who actually want to learn from your code: if somebody wanted to understand Ken Silverman’s programming style rather than simply understand how Build works, what function or small portion of the source would you tell them to study?

Ken Silverman: I don’t see much benefit to studying a coding style. I do what makes sense to me and I don’t care what other people think. My style has evolved over the years as I find reasons to organize code better. My naming convention is slightly improved. I use fewer globals and more structures. I like to align similar lines of code to help spot typos.

Retro Replay: And now the question your email practically begged me to ask: what is the single assembly optimization from your career that still occupies permanent space in your brain? Give us the gloriously nerdy explanation if you want; I’m genuinely curious.

Ken Silverman: I’ve written a lot of assembly code since Build, but if I had to point out something from Build, it would be ‘vlineasm4’, which could texture-map 4 vertical lines of a wall simultaneously. Having 4 consecutive 8-bit values allowed 32-bit writes to the video card, which was nice boost on a 486 with 32-bit VLB card. The challenge was figuring out how to fit all 4 texel coordinates in registers.

Retro Replay: For a slightly more fun hypothetical: imagine somebody hands 1995 Ken Silverman a modern PC but tells him he still has to make Duke Nukem 3D using the basic Build philosophy. What is the first engine feature you would go completely overboard implementing simply because the old hardware no longer gets to tell you “no”?

Ken Silverman: I would not waste my time on a computer system that nobody else has.

In 1996, I was approached by 2 different companies – ATI and 3DFX – about porting Build to their very early GPUs. I looked at the ATI first. I discovered it to be a decelerator. That kind of turned me off to GPUs. I did look at the 3DFX briefly. It seemed to run fast enough, but I still wasn’t convinced. The thing is: any serious gamer would have had a Pentium at that time, in which case Build already ran pretty fast in the 640×480 ‘hi-res’ mode. The only new feature would have been the blurry textures from bilinear filtering. I didn’t think it was worth the effort for that.

In 2003, I wrote POLYMOST, which was essentially what they would have wanted. It took many months to get it working glitch-free, so I believe I made the right decision at the time.

In 2006, I started BUILD2, which had some of the features I could have only dreamed of in 1995, such as: native room-over-room, full 6dof, real-time shadows, and 6dof voxel sprites.

Retro Replay: You called the early ATI hardware you tested a “decelerator.” What specifically made it slower than software Build? Was it driver overhead, texture uploads, fill rate, latency, or simply that the hardware was not yet capable of beating a well-optimized Pentium renderer?

Ken Silverman: I could not tell you why it was slower. It was a black box to me and I only spent a couple days with it. If I had to guess, it was probably fill rate. The card just sucked. I’m pretty sure it was an original ATI 3D Rage.

Retro Replay: You mentioned BUILD2 having native room-over-room, full 6DOF, real-time shadows, and 6DOF voxel sprites. Of all the things you finally got to implement there that 1995 hardware would not realistically allow, which one produced the most interesting technical problem?

Ken Silverman: These are all interesting and complex problems. That’s why I listed them. What many people don’t know about BUILD2 is that it takes POLYMOST to the next level, so you can look straight up and down. This could in theory be used in the Build ports to OpenGL.

Retro Replay: Of all the Build-engine games, including Duke Nukem 3D, Blood, Shadow Warrior and the less obvious titles, is there one you would point a technically curious player toward and say, “Play this and pay attention to what they managed to make my engine do”?

Ken Silverman: It sounds like you are leading me to point to Ion Fury, which your question was cleverly written to not specifically exclude.

Retro Replay: Bonus oddball question: did you ever spend an objectively ridiculous amount of time saving an objectively tiny number of CPU cycles simply because figuring out how to save them became more entertaining than whatever you were supposed to be doing?

Ken Silverman: Yes. I would say this is an accurate description of the majority of my time. Optimizing assembly language is a very relaxing pastime. Everyone should try it.

Retro Replay: Build helped power some of the defining PC action games of the 1990s, but you’ve spent decades programming things far removed from Duke Nukem. Is there something you’ve created since then that you personally find more technically interesting than Build, even though almost nobody interviewing you asks about it?

Ken Silverman: Sure. You’ll find plenty of stuff on my website. If you like 3D engines, there’s Voxlap, Build2, and PND3D. You’ll also find a lot of cool stuff on my Projects page, including EVALDRAW. In many ways, that’s my largest software project to date.

I’ve worked on a lot of hardware projects as well. I don’t post much about them on my website, because it’s not something you can download and try for yourself. I suppose I could post pictures and videos of them. At Brown, I’ve worked on several 6dof input devices – one using inductive coils, another using an optical/IMU hybrid. Then there’s all of the work I’ve done with Voxel Photonics. I am responsible for a lot of what goes on inside. You can go to their website to see pictures and videos about that.

Retro Replay: Is there a technical misconception about Build that you still see repeated online and immediately think, “No, that is not how it works”?

Ken Silverman: The one that stands out most is: Build is not a raycaster. I like to refer people to Fabien Sanglard’s site, which has an accurate description of the inner workings of Build:
https://fabiensanglard.net/duke3d/index.php

Retro Replay: After reading all those old interviews, I noticed that people naturally focus on the famous features… sectors, slopes, voxels, the editor, portals. What part of Build do people almost never ask you about that you think contains a genuinely interesting algorithm or design decision?

Ken Silverman: Hmm..

• The ability to edit in full screen 3D mode. Build may have been the first.
• Client-side prediction – nobody had done this before in a 3D game. (Duke 3D beat Quake by a month ;-P)

Retro Replay: Finally, when I publish this, are there any current projects, source repositories, technical pages, programs, experiments, or other places you would specifically like me to direct readers toward?

Ken Silverman: I suppose this would be a good place to plug my company, Voxel Photonics:
https://voxel3d.co/