Duke Nukem 3D Code Review: INTRODUCTION (PART 1 OF 4) >>
Since I left my job at Amazon I have spent a lot of time reading great source code.
the next thing to read was one of the
game of all time :
Duke Nukem 3D and the engine powering it named "Build".
It turned out to be a difficult experience: The engine delivered great value and ranked high in terms of speed, stability and memory consumption but my enthousiasm met a source code controversial in terms of organization, best practices and comments/documentation. This reading session taught me a lot about code legacy and what helps a software live long.
As usual I cleaned up my notes into an article. I hope it will inspire some of us to read more source code and become better engineers.
Part 1: Overview.
Part 2: Engine Internals.
Part 3: Engine legacy.
Part 4: Chocolate Duke Nukem 3D.
I would like to thanks Ken Silverman for proof-reading this article: His patience and diligent replies to my emails were instrumental.
Duke Nukem 3D is not one codebase but two :
- Build engine: Providing rendition, network, filesystem and caching services.
- Game Module: Using Build's services in order to generate a gaming experience.
Why such a division? Because back in 1993, when development started, very few people had the skills and dedication
to produce a good 3D engine. When 3D Realms
decided to write a game that would challenge Doom, they had to find the technology that would power it. That
is where Ken Silverman enters the picture.
According to his well-documented website and interview, Ken Silverman (18 years old at the time) wrote a 3D engine at home and sent a demo for evaluation to 3D Realms. They found his skills promising and worked out a deal:
Silverman would write a new engine for 3D Realms but he would keep the source code. He would only deliver a binary static library (
Engine.OBJ) with an
header file. The 3D Realms team on their side would take care of developing the Game module (
and would also release the final executable
Unfortunately both part of the game were not open sourced simultaneously:
- The Engine module source code was released by Ken Silverman on June 20, 2000 .
- The Game module source code was released by 3D Realms on April 1, 2003.
As a result the full source code was available 7 years after the game was released.
Trivia : The name of the engine "Build" was chosen by Ken Silverman when creating the directory for the new engine: He used a thesaurus to search for a synonyms of "Construction".
Since the original code released rotted a long time ago (It was targeted to Watcom C/C++ compiler and DOS systems) I tried to find
like Chocolate doom: A port that
accurately reproduces the experience of Duke Nukem 3D as it was played in the 90s and would flawlessly compile on modern systems.
It turned out the Duke Nukem open source community is not very active anymore: Most ports have rotted again, some have MacOS 9 PowerPC targets and the only one still maintained (EDuke32) has evolved too far from the original code. I ended up working with xDuke even though it did not compile on Linux or Mac OS X (which ruled out XCode: An outstanding IDE when it comes to reading code and profiling).
xDuke's Visual Studio Solution is fidele to the original workflow. It features two projects: Engine and Game: The "Engine" project compiles to a static library (
Engine.lib) and the "Game" project (featuring the
main method) links against it in order
to generate a
Upon opening VS, the engine source felt unwelcoming with difficult filenames (
Opening those files reveals something
hostile to the eyes and the mind.
An example among many others from
Engine.c (line 693):
if ((globalorientation&0x10) > 0) globalx1 = -globalx1, globaly1 = -globaly1, globalxpanning = -globalxpanning; if ((globalorientation&0x20) > 0) globalx2 = -globalx2, globaly2 = -globaly2, globalypanning = -globalypanning; globalx1 <<= globalxshift; globaly1 <<= globalxshift; globalx2 <<= globalyshift; globaly2 <<= globalyshift; globalxpanning <<= globalxshift; globalypanning <<= globalyshift; globalxpanning += (((long)sec->ceilingxpanning)<<24); globalypanning += (((long)sec->ceilingypanning)<<24); globaly1 = (-globalx1-globaly1)*halfxdimen; globalx2 = (globalx2-globaly2)*halfxdimen;Note : If a file/variable name features a number: it is probably not a good name !
Trivia : The last part of
game.cfeatures a draft of Duke V scenario !
Note : xDuke port uses SDL but the cross-platform API advantage is lost
to WIN32 timers (
QueryPerformanceFrequency). It seems the
SDL Timer used to be too innacurate in order to emulate DOS 120Hz tick rate.
After setting up SDL and DirectX header/lib location the code will build in one click: That is very pleasant. The only last part is to get
DUKE3D.GRP asset file and the game runs....well kinda :/.... SDL seems to have some palette issues with Vista/Windows 7:
Running in Windowed Mode (or better, use Windows 8) seems to fix the issue:
Now the game is running. Within the first seconds Build shines with, in order:
- Sloped floors.
- Realistic environments.
- Free fall.
- Feeling of true 3D.
The last point is probably what struck players the most in 1996.
The level of immersion experienced was unprecedented. Even when
the technology reached its limit because of 2D maps, Todd Replogle and Allen Blum implemented "sector effectors" allowing to teleport the
player and improve the feeling of evolving in a three dimensional world. This feature is used in the legendary "L.A Meltdown" map:
When the player jumps in the ventilation shaft:
A sector effectors triggers and teleports the player at a totally different location on the map just before "landing" :
Trivia : Ever since, 3D engines have tried to improve immersion with better graphics. Things may take a new direction with the release of the Virtual Reality device "The Oculus Rift".
Great games age nicely and Duke Nukem is no exception: Twenty years later the game is still incredibly fun to play. Except now we can start digging in the source!
Engine Library Overview
The engine code is in one file of 8503 lines with 10 master functions (
Engine.c) and two auxiliary files:
cache1.c: Contains the virtual filesystem (sic) and the cache system routines.
a.c: A C reverse-engineered implementation of what used to be highly optimized x86 assembly. It works but is a monstruous pain in the ass to read :( !
Three translation units and few functions makes the high level architecture
hard to comprehend. Unfortunately this is not the only difficulties a reader will face.
As full page is dedicated to the engine: Build Engine Internals.
Game Module Overview
The game module is built completely on top of the Engine module, the way an operating system's system calls are used by a process: Anything the game does is done thought Build (drawing, loading assets, filesystem, caching system, ...). The only exception is the sounds/music system which Game completely owns.
Since I was mostly interested in the engine I did not read it in depth. But it shows more experience and organization: 15 files divide the source into clear modules. It even features a
types.h (precursor of
stdint.h) in order to improve portability.
A few interesting things :
game.cis a beast featuring 11,026 lines of code.
menu.c" features a 3000 lines "switch case".
- Most methods have "void" parameters and return "void". Everything goes via global variables.
- Methods naming does not use camelCase or NAMESPACE prefix.
- Features a neat parser/lexer even though token values are
passed via decimal
values instead of
Overall this part code is easy to read and understand.
Source code legacy
Looking at the innumerable ports that spawned Doom/Quake, I was always puzzled to see so few ports of
Duke Nukem 3D. The same question arose when the engine was ported to OpenGL only when Ken Silverman decided
to do it himself.
Now that I have looked at the code I can risk an explanation in a dedicated page: The legacy of Duke Nukem 3D source code.
Chocolate Duke Nukem 3D
Admiring the engine and loving the game so much, I could not let things this way: I started Chocolate Duke Nukem 3D, a port of the Vanilla source code with two goals in mind:
- Education: Easy to read/understand and very portable.
- Fidelity: The gaming experience should be similar to what ran in 1996 on our 486s.
I hope this inntiative will help the code to find a new legacy. The key modifications are described in Chocolate Duke Nukem 3D page.
None. Go rock climbing: It is awesome !
Add a comment
It's a pitty that they could not just refurbish the graphics, add some new maps and release a new Duke. What they released was a "let's get things done" game and called it "Duke Nukem Forever".
Maybe there will be a "Duke Nukem Community Edition" with all the cool gameplay...
Thanks for your work!
same problem when running Starcraft or Diablo II, the easiest solution is to kill explorer.exe before run the game (use taskmanager or create a batch command :)
May I ask you to write an in depth article on how you actually *read* code? Where do you start, how much notes you make, maybe you document the code you read, and so on. In my experience, reading code is an essential skill for any programmer, but there seem to be absolutely no resources explaining how to do it properly. I've tried reading quake3 code (three times) and tried reading eAthena code (open-source server engine for MMORPG Ragnarok Online) but after couple days I've got lost in detailes and in the end had no clue about how thing works. You are on the other hand extremely skilful at the task and your insights are very valuable for an open community.
I laugh about your note about variables/files with numbers, I totally agree with you. I always remaind my coworkers of that (after some year developing seriously and reading books like Clean Code made ponder the value of good names).
So, what's the next step? do you have any engine you want to review next?
It's a shame that any of the Unreal games doesn't release their source codes.
I can't read the article via Instapaper app, and the page is otherwise unreadable on mobile (and I don't have time to read at my desk)
I've always wondered, what software do you use to make your diagrams?
Excellent post btw, nice deep analysis of the source and render mechanics. I remember looking at ENGINE.C when it was first released and indeed did not feel encouraged to continue investigating :) But I respect that he got a post-DOOM engine working smoothly on such feeble hardware. It took some sacrifices, especially then. Compilers now can turn a ton of types, lambdas and whatnot into a tight loop but back then you really had to write high-level assembly to get stuff fast. Props to Ken and you!
As always a great read!
Once I saw it over at HackerNews while at work, I knew I had to make a short day :-)
One thing: Could you elaborate on why using cross products makes a difference to using a dot product if you have fixed-point/integer math?
Also, two small typos in the related source code snippet:
* If I am not color-blind, the one vector is blue and not green. ;-)
* The return-statement should compare against the 2D zero-vector not a scalar, right?
But why the hell would you use quicktime videos... :D
Chrome give me an alrt that is due to a plugin named : quick time
use html video tag or flash for video other solution are lame !
I wonder what tools you use to make your diagrams.
I appreciate to read your comments and notes on different games, its very nice of you to take the time and read and share it with all of us.
Have a good life
I also enjoyed, very much, your article's page presentation.
Nicely done and pleasant to view.
I had no problem viewing any of the images or QT videos.
Depending on the editor, you have at most 24 lines of 80 columns on a VGA screen. The inside function you mention is 20 lines long - pretty close to that limit. The desire to keep logic sections within the size of the screen is much more important than comments for other people years down the line to enjoy.
Also, regarding globals: While I'm not sure about 486 specifically (I'm too young), a global array of a primitive type (1, 2, or 4 bytes per element) is very fast to access. I believe the address of the element could be calculated as part of the memory fetch instruction.
An array of structs, whether as a global or on the stack, would probably require 2 instructions to calculate the memory address, and a third for the actual fetch.
Aditionally, the size of the stack would have been tightly constrained.
Any plans to mention the active Source Port EDuke32?
OpenGL is very much improved, there is now true Room over Room capabilties and much more.
The team has an very active forum
* Putting as much code into a single file as possible was a good way to help the primitive compilers do some optimisations & inlining
* Arrays of scalars instead of structs are simply much faster to iterate through given limited CPU caches
* The example math method is straightforward bitmask operations on the sign bits
* Ahh, hand-coded assembly. I'll admit it takes the right kind of masochist to read it :)
* Nothing magic about those numbers! Just bitmasks.
* IDEs have no excuse to be slow these days. DJGPP etc handled huge files just fine back then!
I think you mean 120Hz, not 120 ticks per frame (that would be far too much IRQ overhead). But the PIT native frequency was 1193180Hz. You set a divisor value from 0-65535 which determines the frequency of IRQ0. You can't get 120Hz exactly (more like 120.002Hz) so it's unusual to quantize rendering / physics to this as you get graphics "tearing". What did they use this timer for?
Thanks for sharing all this knowledge.
I get C:\Duke3D\ChocolateDuke3D.exe is not a valid Win32 application when tying to start.
When a get a bit more time I will try and get this complied locally, both on Win XP and Linux(Raspberry Pi)
The Videos are in the folder fd.fabiensanglard.net/duke3d/movies/
the 3 *.m4v-files
VLC plays them just fine
Maybe, if you're running out of code bases to review, you should turn to Aleph One. Its kind of "Chocolate Marathon" ( http://en.wikipedia.org/wiki/Marathon_2:_Durandal ).
Its surprising that most of my pet game engines of the past have similar algorithms (in fact, the "current sector" tracking is exactly the same) to Build.
Greetings from Rio ;-)
"The renderer does not rely on recursive function (the way Doom did when walking the BSP). Instead a stack and a loop is used (for sector flooding)" (from your raw notes)
There is no recursion based on machine stack, but rather on software stack. Maybe this is because (if my memory serves me well) Ken prototyped the engine in QuickBASIC and (from my faded memory again) it didn't have recursion until 4.0;
Or perhaps not...maybe was stack size thing from those old dark (and very fun) days?
QuickBasic was a fine "IDE" for some quick hacking. I grew making lousy 3D games in it myself. My biggest inspiration at the time was Ken, but I wasn't aware he used the very same tool I was;
Very interesting review as usual. I already took a look at code some years ago and discover most inner workings but some things remains mysterious, your review cleared them out.
I expected to see an explanation on how mirrors works (why they require an additional empty room with special texture). Still unclear to me.
One interesting trivia : the way updatesector() works caused some well know glitch/cheat during the game, that was used a lot in multiplayer (warp glitch) : if you make player run very fast in a place were sectors are very small (eg : stairs), updatesector get lost and start scanning all sectors. If there is two (or more) overlapping sectors where player is, game sometimes choose the wrong sector (depending their order), and it will teleport player there.
see video : http://www.youtube.com/watch?v=VUOhZIdCSiI
Ken was a true whiz kid - imagine a threesome, hopefully limited to engine concerns, between Carmack, Abrash and Silverman in the 90ies... the arch software rasterizer could have been born ^^
Thanks for your excellent review and bringing the code to life in classic fashion!
I want to play the Atomic Edition but I can't patch to 1.5, please make Chocolate Duke Nukem 3D work for v1.4!
Note that the intro demos work fine.